A03-LCDGCD.html

High School Modules > Algebra by Gregory A. Moore

GCD & LCM

An examination of the concept of the gcd and lcm . We explore the concept, examine a method to compute these values, use a quick Maple way of computing them, and examine an interesting property of gcd's and lcm's.

[Directions : Execute the Code Resource section first. Although there will be no output immediately, these definitions are used later in this worksheet.]

0. Code

> restart;

>    FactorTable := proc( n, m )
     local N, M, P, i,j,k, A, p ;
     print( n = ifactor(n) );
     print( m = ifactor(m) );
     N := numtheory[factorset](n);
     M := numtheory[factorset](m);
     P := N union M;   p := nops(P);
     #for k from 1 to nops(M) do print( M[k]); od;
     A := array( [seq( [
                  seq( ` `, j = 1..p+2 )
                       ],   i = 1..2+2 )
                  ]);
     for j from 1 to p do A[1,j+2] := P[j]; od;
     for j from 1 to p do A[2,j+2] := `__`; od;
     A[3,1] := n;     A[4,1] := m;
     A[3,2] := `|`;   A[4,2] := `|`;   A[1,1] := `primes =`;

     for k from 1 to p do
         for i from 0 by 1
               while (irem(n,P[k]^i)=0) do end do;
               A[3, k + 2] := ifactor(P[k]^(i-1));
          od;

    for k from 1 to p do
         for i from 0 by 1
               while (irem(m,P[k]^i)=0) do end do;
               A[4, k + 2] := ifactor(P[k]^(i-1));
          od;
     print(A);

end proc:

>    GCDTable := proc( n, m )
     local N, M, P, i,j,k, A, p ;
     N := numtheory[factorset](n);
     M := numtheory[factorset](m);
     P := N union M;   p := nops(P);
     #for k from 1 to nops(M) do print( M[k]); od;
     A := array( [seq( [
                  seq( ` `, j = 1..p+3 )
                       ],   i = 1..2+4 )
                  ]);
     for j from 1 to p do A[1,j+2] := P[j]; od;
     for j from 1 to p do A[2,j+2] := `__`; od;
     for j from 1 to p do A[5,j+2] := `__`; od;
     A[3,1] := n;     A[4,1] := m;
     A[3,2] := `|`;   A[4,2] := `|`;
     A[1,1] := `primes =`;

    #______Row with 1st factorization_________
     for k from 1 to p do
         for i from 0 by 1
               while (irem(n,P[k]^i)=0) do end do;
               A[3, k + 2] := ifactor(P[k]^(i-1));
          od;

    #______Row with 2nd factorization_________
    for k from 1 to p do
         for i from 0 by 1
               while (irem(m,P[k]^i)=0) do end do;
               A[4, k + 2] := ifactor(P[k]^(i-1));
          od;
    #______Last row with GCD factorization_________
    for k from 1 to p do
         for i from 0 by 1
               while (irem(m,P[k]^i)=0) do end do;
               A[6, k + 2] := ifactor(
                               min( expand(A[3,k+2]),expand(A[4,k+2])));
          od;

     A[6,1] := `GCD =`;
     A[6, p + 3] := 1;
     for k from 1 to p do
         A[6, p + 3] := expand(A[6, p+3]* A[6,k+2]);
         od;

    A[6, p + 3] := cat(`= `, A[6, p + 3]);
     print(A);

end proc:

>    LCMTable := proc( n, m )
     local N, M, P, i,j,k, A, p ;
     N := numtheory[factorset](n);
     M := numtheory[factorset](m);
     P := N union M;   p := nops(P);
     #for k from 1 to nops(M) do print( M[k]); od;
     A := array( [seq( [
                  seq( ` `, j = 1..p+3 )
                       ],   i = 1..2+4 )
                  ]);
     for j from 1 to p do A[1,j+2] := P[j]; od;
     for j from 1 to p do A[2,j+2] := `__`; od;
     for j from 1 to p do A[5,j+2] := `__`; od;
     A[3,1] := n;     A[4,1] := m;
     A[3,2] := `|`;   A[4,2] := `|`;
     A[1,1] := `primes =`;

     for k from 1 to p do
         for i from 0 by 1
               while (irem(n,P[k]^i)=0) do end do;
               A[3, k + 2] := ifactor(P[k]^(i-1));
          od;

    for k from 1 to p do
         for i from 0 by 1
               while (irem(m,P[k]^i)=0) do end do;
               A[4, k + 2] := ifactor(P[k]^(i-1));
          od;

    for k from 1 to p do
         for i from 0 by 1
               while (irem(m,P[k]^i)=0) do end do;
               A[6, k + 2] := ifactor(
                                max( expand(A[3,k+2]), expand(A[4, k+2])));
          od;

     A[6,1] := `LCM =`;
     A[6, p + 3] := 1;
     for k from 1 to p do
         A[6, p + 3] := expand(A[6, p+3]* A[6,k+2]);
         od;

    A[6, p + 3] := cat(`= `, A[6, p + 3]);
     print(A);

end proc:

>    min_element := proc( S)
  local n, i, min;
   n := nops(S);
   min := S[1];
   for i from 1 to n do
          if( min > S[i] ) then min := S[i]; fi; od;
   min;
end proc:

>    max_element := proc( S)
  local n, i, max;
   n := nops(S);
   max := S[1];
   for i from 1 to n do
          if( max < S[i] ) then max := S[i]; fi; od;
   max;
end proc:

>    gcd_concept := proc(n, m)
  local N, M, Common;
   N := numtheory[divisors](n);
   print(cat(`\ndivisors of `,n, ` = `,convert(N , string)));
   M := numtheory[divisors](m);
   print(cat(`\ndivisors of `,m, ` = `,convert(M , string)));
   Common := % intersect %%:
   print( `\nCommon divisors` = Common);
   print( `\nGCD = maximum divisor ` = max_element( Common ));
end proc:

>    lcm_concept := proc(n, m)
  local N, M, Common;
   N := {seq( n*k, k = 1..m)};
   print(cat(`\nmultiples of `,n, ` = `)); print(cat(` `, convert(N , string)) );
   M := {seq( m*k, k = 1..n)};
   print(cat(`\nmultiples of `,m, ` = `)); print(cat(` `, convert(M , string)) );
   Common := % intersect %%:
   print(`\nCommon multiples` = Common);
   print(`\nLCM = minimum multiple ` = min_element( Common ));
end proc:

1. Creating a Prime Factorization Table

Every positive integer (greater than one) can be factored into a product of primes.

> 24: % = ifactor(%);
90: % = ifactor(%);

Given two numbers, we can create a table, by organizing this information. We write the original numbers along the left side, and list ALL of the primes available in either of the two numbers along the top. Then we fill in what power of the given prime is present in each number.

> FactorTable( 24, 90);

Lets try some other examples.

> FactorTable( 20, 15);

> FactorTable( 42,36);

> FactorTable( 144, 196);

> FactorTable( 15801075, 149232375);

2. The Concept of the GCD

Each integer has a certain number of divisors - numbers which divide into the number evenly. If we make a list of the divisors of each number, then take the intersection of those two sets, we have a list of common factors. These common divisors are the only numbers which divide both of the two original numbers.

Now we if simply take the greatest of these common divisors, we have the gcd - the "greatest common divisor."

> gcd_concept( 18, 24);

$`\ndivisors of 18 = {1, 2, 3, 6, 9, 18}`$
$`\ndivisors of 18 = {1, 2, 3, 6, 9, 18}`$

$`\ndivisors of 24 = {1, 2, 3, 4, 6, 8, 12, 24}`$
$`\ndivisors of 24 = {1, 2, 3, 4, 6, 8, 12, 24}`$

$`\nCommon divisors` = {1, 2, 3, 6}$
$`\nCommon divisors` = {1, 2, 3, 6}$

$`\nGCD = maximum divisor ` = 6$
$`\nGCD = maximum divisor ` = 6$

> gcd_concept( 25, 35);

$`\ndivisors of 25 = {1, 5, 25}`$
$`\ndivisors of 25 = {1, 5, 25}`$

$`\ndivisors of 35 = {1, 5, 7, 35}`$
$`\ndivisors of 35 = {1, 5, 7, 35}`$

$`\nCommon divisors` = {1, 5}$
$`\nCommon divisors` = {1, 5}$

$`\nGCD = maximum divisor ` = 5$
$`\nGCD = maximum divisor ` = 5$

> gcd_concept( 144, 192);

$`\ndivisors of 144 = {1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72, 144}`$
$`\ndivisors of 144 = {1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72, 144}`$

$`\ndivisors of 192 = {1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 192}`$
$`\ndivisors of 192 = {1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 192}`$

$`\nCommon divisors` = {1, 2, 3, 4, 6, 8, 12, 16, 24, 48}$
$`\nCommon divisors` = {1, 2, 3, 4, 6, 8, 12, 16, 24, 48}$

$`\nGCD = maximum divisor ` = 48$
$`\nGCD = maximum divisor ` = 48$

> gcd_concept( 45, 210);

$`\ndivisors of 45 = {1, 3, 5, 9, 15, 45}`$
$`\ndivisors of 45 = {1, 3, 5, 9, 15, 45}`$

$`\ndivisors of 210 = {1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210}`$
$`\ndivisors of 210 = {1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210}`$

$`\nCommon divisors` = {1, 3, 5, 15}$
$`\nCommon divisors` = {1, 3, 5, 15}$

$`\nGCD = maximum divisor ` = 15$
$`\nGCD = maximum divisor ` = 15$

> gcd_concept( 120, 180);

$`\ndivisors of 120 = {1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120}`$
$`\ndivisors of 120 = {1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120}`$

$`\ndivisors of 180 = {1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180}`$
$`\ndivisors of 180 = {1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180}`$

$`\nCommon divisors` = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}$
$`\nCommon divisors` = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}$

$`\nGCD = maximum divisor ` = 60$
$`\nGCD = maximum divisor ` = 60$

> gcd_concept( 17810275, 5686625);

$`\ndivisors of 17810275 = {1, 5, 7, 25, 31, 35, 49, 67, 155, 175, 217, 245, 335, 343, 469, 775, 1085, 1225, 1519, 1675, 1715, 2077, 2345, 3283, 5425, 7595, 8575, 10385, 10633, 11725, 14539, 16415, 2298...$
$`\ndivisors of 17810275 = {1, 5, 7, 25, 31, 35, 49, 67, 155, 175, 217, 245, 335, 343, 469, 775, 1085, 1225, 1519, 1675, 1715, 2077, 2345, 3283, 5425, 7595, 8575, 10385, 10633, 11725, 14539, 16415, 2298...$
$`\ndivisors of 17810275 = {1, 5, 7, 25, 31, 35, 49, 67, 155, 175, 217, 245, 335, 343, 469, 775, 1085, 1225, 1519, 1675, 1715, 2077, 2345, 3283, 5425, 7595, 8575, 10385, 10633, 11725, 14539, 16415, 2298...$
$`\ndivisors of 17810275 = {1, 5, 7, 25, 31, 35, 49, 67, 155, 175, 217, 245, 335, 343, 469, 775, 1085, 1225, 1519, 1675, 1715, 2077, 2345, 3283, 5425, 7595, 8575, 10385, 10633, 11725, 14539, 16415, 2298...$

$`\ndivisors of 5686625 = {1, 5, 7, 25, 35, 67, 97, 125, 175, 335, 469, 485, 679, 875, 1675, 2345, 2425, 3395, 6499, 8375, 11725, 12125, 16975, 32495, 45493, 58625, 84875, 162475, 227465, 812375, 113732...$
$`\ndivisors of 5686625 = {1, 5, 7, 25, 35, 67, 97, 125, 175, 335, 469, 485, 679, 875, 1675, 2345, 2425, 3395, 6499, 8375, 11725, 12125, 16975, 32495, 45493, 58625, 84875, 162475, 227465, 812375, 113732...$
$`\ndivisors of 5686625 = {1, 5, 7, 25, 35, 67, 97, 125, 175, 335, 469, 485, 679, 875, 1675, 2345, 2425, 3395, 6499, 8375, 11725, 12125, 16975, 32495, 45493, 58625, 84875, 162475, 227465, 812375, 113732...$

$`\nCommon divisors` = {1, 5, 7, 25, 35, 67, 175, 335, 469, 1675, 2345, 11725}$
$`\nCommon divisors` = {1, 5, 7, 25, 35, 67, 175, 335, 469, 1675, 2345, 11725}$

$`\nGCD = maximum divisor ` = 11725$
$`\nGCD = maximum divisor ` = 11725$

> gcd_concept( 300766484081591, 477666356354107);

$`\ndivisors of 300766484081591 = {1, 11, 29, 47, 71, 97, 113, 149, 173, 319, 517, 781, 1067, 1243, 1363, 1639, 1903, 2059, 2813, 3277, 3337, 4321, 4559, 5017, 5311, 6887, 7003, 8023, 8131, 10579, 10961...$
$`\ndivisors of 300766484081591 = {1, 11, 29, 47, 71, 97, 113, 149, 173, 319, 517, 781, 1067, 1243, 1363, 1639, 1903, 2059, 2813, 3277, 3337, 4321, 4559, 5017, 5311, 6887, 7003, 8023, 8131, 10579, 10961...$
$`\ndivisors of 300766484081591 = {1, 11, 29, 47, 71, 97, 113, 149, 173, 319, 517, 781, 1067, 1243, 1363, 1639, 1903, 2059, 2813, 3277, 3337, 4321, 4559, 5017, 5311, 6887, 7003, 8023, 8131, 10579, 10961...$
$`\ndivisors of 300766484081591 = {1, 11, 29, 47, 71, 97, 113, 149, 173, 319, 517, 781, 1067, 1243, 1363, 1639, 1903, 2059, 2813, 3277, 3337, 4321, 4559, 5017, 5311, 6887, 7003, 8023, 8131, 10579, 10961...$
$`\ndivisors of 300766484081591 = {1, 11, 29, 47, 71, 97, 113, 149, 173, 319, 517, 781, 1067, 1243, 1363, 1639, 1903, 2059, 2813, 3277, 3337, 4321, 4559, 5017, 5311, 6887, 7003, 8023, 8131, 10579, 10961...$
$`\ndivisors of 300766484081591 = {1, 11, 29, 47, 71, 97, 113, 149, 173, 319, 517, 781, 1067, 1243, 1363, 1639, 1903, 2059, 2813, 3277, 3337, 4321, 4559, 5017, 5311, 6887, 7003, 8023, 8131, 10579, 10961...$
$`\ndivisors of 300766484081591 = {1, 11, 29, 47, 71, 97, 113, 149, 173, 319, 517, 781, 1067, 1243, 1363, 1639, 1903, 2059, 2813, 3277, 3337, 4321, 4559, 5017, 5311, 6887, 7003, 8023, 8131, 10579, 10961...$
$`\ndivisors of 300766484081591 = {1, 11, 29, 47, 71, 97, 113, 149, 173, 319, 517, 781, 1067, 1243, 1363, 1639, 1903, 2059, 2813, 3277, 3337, 4321, 4559, 5017, 5311, 6887, 7003, 8023, 8131, 10579, 10961...$
$`\ndivisors of 300766484081591 = {1, 11, 29, 47, 71, 97, 113, 149, 173, 319, 517, 781, 1067, 1243, 1363, 1639, 1903, 2059, 2813, 3277, 3337, 4321, 4559, 5017, 5311, 6887, 7003, 8023, 8131, 10579, 10961...$
$`\ndivisors of 300766484081591 = {1, 11, 29, 47, 71, 97, 113, 149, 173, 319, 517, 781, 1067, 1243, 1363, 1639, 1903, 2059, 2813, 3277, 3337, 4321, 4559, 5017, 5311, 6887, 7003, 8023, 8131, 10579, 10961...$
$`\ndivisors of 300766484081591 = {1, 11, 29, 47, 71, 97, 113, 149, 173, 319, 517, 781, 1067, 1243, 1363, 1639, 1903, 2059, 2813, 3277, 3337, 4321, 4559, 5017, 5311, 6887, 7003, 8023, 8131, 10579, 10961...$
$`\ndivisors of 300766484081591 = {1, 11, 29, 47, 71, 97, 113, 149, 173, 319, 517, 781, 1067, 1243, 1363, 1639, 1903, 2059, 2813, 3277, 3337, 4321, 4559, 5017, 5311, 6887, 7003, 8023, 8131, 10579, 10961...$
$`\ndivisors of 300766484081591 = {1, 11, 29, 47, 71, 97, 113, 149, 173, 319, 517, 781, 1067, 1243, 1363, 1639, 1903, 2059, 2813, 3277, 3337, 4321, 4559, 5017, 5311, 6887, 7003, 8023, 8131, 10579, 10961...$
$`\ndivisors of 300766484081591 = {1, 11, 29, 47, 71, 97, 113, 149, 173, 319, 517, 781, 1067, 1243, 1363, 1639, 1903, 2059, 2813, 3277, 3337, 4321, 4559, 5017, 5311, 6887, 7003, 8023, 8131, 10579, 10961...$
$`\ndivisors of 300766484081591 = {1, 11, 29, 47, 71, 97, 113, 149, 173, 319, 517, 781, 1067, 1243, 1363, 1639, 1903, 2059, 2813, 3277, 3337, 4321, 4559, 5017, 5311, 6887, 7003, 8023, 8131, 10579, 10961...$
$`\ndivisors of 300766484081591 = {1, 11, 29, 47, 71, 97, 113, 149, 173, 319, 517, 781, 1067, 1243, 1363, 1639, 1903, 2059, 2813, 3277, 3337, 4321, 4559, 5017, 5311, 6887, 7003, 8023, 8131, 10579, 10961...$
$`\ndivisors of 300766484081591 = {1, 11, 29, 47, 71, 97, 113, 149, 173, 319, 517, 781, 1067, 1243, 1363, 1639, 1903, 2059, 2813, 3277, 3337, 4321, 4559, 5017, 5311, 6887, 7003, 8023, 8131, 10579, 10961...$
$`\ndivisors of 300766484081591 = {1, 11, 29, 47, 71, 97, 113, 149, 173, 319, 517, 781, 1067, 1243, 1363, 1639, 1903, 2059, 2813, 3277, 3337, 4321, 4559, 5017, 5311, 6887, 7003, 8023, 8131, 10579, 10961...$
$`\ndivisors of 300766484081591 = {1, 11, 29, 47, 71, 97, 113, 149, 173, 319, 517, 781, 1067, 1243, 1363, 1639, 1903, 2059, 2813, 3277, 3337, 4321, 4559, 5017, 5311, 6887, 7003, 8023, 8131, 10579, 10961...$
$`\ndivisors of 300766484081591 = {1, 11, 29, 47, 71, 97, 113, 149, 173, 319, 517, 781, 1067, 1243, 1363, 1639, 1903, 2059, 2813, 3277, 3337, 4321, 4559, 5017, 5311, 6887, 7003, 8023, 8131, 10579, 10961...$
$`\ndivisors of 300766484081591 = {1, 11, 29, 47, 71, 97, 113, 149, 173, 319, 517, 781, 1067, 1243, 1363, 1639, 1903, 2059, 2813, 3277, 3337, 4321, 4559, 5017, 5311, 6887, 7003, 8023, 8131, 10579, 10961...$

$`\ndivisors of 477666356354107 = {1, 19, 29, 47, 71, 97, 113, 137, 173, 551, 893, 1349, 1363, 1843, 2059, 2147, 2603, 2813, 3277, 3287, 3337, 3973, 4559, 5017, 5311, 6439, 6887, 8023, 8131, 9727, 10961...$
$`\ndivisors of 477666356354107 = {1, 19, 29, 47, 71, 97, 113, 137, 173, 551, 893, 1349, 1363, 1843, 2059, 2147, 2603, 2813, 3277, 3287, 3337, 3973, 4559, 5017, 5311, 6439, 6887, 8023, 8131, 9727, 10961...$
$`\ndivisors of 477666356354107 = {1, 19, 29, 47, 71, 97, 113, 137, 173, 551, 893, 1349, 1363, 1843, 2059, 2147, 2603, 2813, 3277, 3287, 3337, 3973, 4559, 5017, 5311, 6439, 6887, 8023, 8131, 9727, 10961...$
$`\ndivisors of 477666356354107 = {1, 19, 29, 47, 71, 97, 113, 137, 173, 551, 893, 1349, 1363, 1843, 2059, 2147, 2603, 2813, 3277, 3287, 3337, 3973, 4559, 5017, 5311, 6439, 6887, 8023, 8131, 9727, 10961...$
$`\ndivisors of 477666356354107 = {1, 19, 29, 47, 71, 97, 113, 137, 173, 551, 893, 1349, 1363, 1843, 2059, 2147, 2603, 2813, 3277, 3287, 3337, 3973, 4559, 5017, 5311, 6439, 6887, 8023, 8131, 9727, 10961...$
$`\ndivisors of 477666356354107 = {1, 19, 29, 47, 71, 97, 113, 137, 173, 551, 893, 1349, 1363, 1843, 2059, 2147, 2603, 2813, 3277, 3287, 3337, 3973, 4559, 5017, 5311, 6439, 6887, 8023, 8131, 9727, 10961...$
$`\ndivisors of 477666356354107 = {1, 19, 29, 47, 71, 97, 113, 137, 173, 551, 893, 1349, 1363, 1843, 2059, 2147, 2603, 2813, 3277, 3287, 3337, 3973, 4559, 5017, 5311, 6439, 6887, 8023, 8131, 9727, 10961...$
$`\ndivisors of 477666356354107 = {1, 19, 29, 47, 71, 97, 113, 137, 173, 551, 893, 1349, 1363, 1843, 2059, 2147, 2603, 2813, 3277, 3287, 3337, 3973, 4559, 5017, 5311, 6439, 6887, 8023, 8131, 9727, 10961...$
$`\ndivisors of 477666356354107 = {1, 19, 29, 47, 71, 97, 113, 137, 173, 551, 893, 1349, 1363, 1843, 2059, 2147, 2603, 2813, 3277, 3287, 3337, 3973, 4559, 5017, 5311, 6439, 6887, 8023, 8131, 9727, 10961...$
$`\ndivisors of 477666356354107 = {1, 19, 29, 47, 71, 97, 113, 137, 173, 551, 893, 1349, 1363, 1843, 2059, 2147, 2603, 2813, 3277, 3287, 3337, 3973, 4559, 5017, 5311, 6439, 6887, 8023, 8131, 9727, 10961...$
$`\ndivisors of 477666356354107 = {1, 19, 29, 47, 71, 97, 113, 137, 173, 551, 893, 1349, 1363, 1843, 2059, 2147, 2603, 2813, 3277, 3287, 3337, 3973, 4559, 5017, 5311, 6439, 6887, 8023, 8131, 9727, 10961...$
$`\ndivisors of 477666356354107 = {1, 19, 29, 47, 71, 97, 113, 137, 173, 551, 893, 1349, 1363, 1843, 2059, 2147, 2603, 2813, 3277, 3287, 3337, 3973, 4559, 5017, 5311, 6439, 6887, 8023, 8131, 9727, 10961...$
$`\ndivisors of 477666356354107 = {1, 19, 29, 47, 71, 97, 113, 137, 173, 551, 893, 1349, 1363, 1843, 2059, 2147, 2603, 2813, 3277, 3287, 3337, 3973, 4559, 5017, 5311, 6439, 6887, 8023, 8131, 9727, 10961...$
$`\ndivisors of 477666356354107 = {1, 19, 29, 47, 71, 97, 113, 137, 173, 551, 893, 1349, 1363, 1843, 2059, 2147, 2603, 2813, 3277, 3287, 3337, 3973, 4559, 5017, 5311, 6439, 6887, 8023, 8131, 9727, 10961...$
$`\ndivisors of 477666356354107 = {1, 19, 29, 47, 71, 97, 113, 137, 173, 551, 893, 1349, 1363, 1843, 2059, 2147, 2603, 2813, 3277, 3287, 3337, 3973, 4559, 5017, 5311, 6439, 6887, 8023, 8131, 9727, 10961...$
$`\ndivisors of 477666356354107 = {1, 19, 29, 47, 71, 97, 113, 137, 173, 551, 893, 1349, 1363, 1843, 2059, 2147, 2603, 2813, 3277, 3287, 3337, 3973, 4559, 5017, 5311, 6439, 6887, 8023, 8131, 9727, 10961...$
$`\ndivisors of 477666356354107 = {1, 19, 29, 47, 71, 97, 113, 137, 173, 551, 893, 1349, 1363, 1843, 2059, 2147, 2603, 2813, 3277, 3287, 3337, 3973, 4559, 5017, 5311, 6439, 6887, 8023, 8131, 9727, 10961...$
$`\ndivisors of 477666356354107 = {1, 19, 29, 47, 71, 97, 113, 137, 173, 551, 893, 1349, 1363, 1843, 2059, 2147, 2603, 2813, 3277, 3287, 3337, 3973, 4559, 5017, 5311, 6439, 6887, 8023, 8131, 9727, 10961...$
$`\ndivisors of 477666356354107 = {1, 19, 29, 47, 71, 97, 113, 137, 173, 551, 893, 1349, 1363, 1843, 2059, 2147, 2603, 2813, 3277, 3287, 3337, 3973, 4559, 5017, 5311, 6439, 6887, 8023, 8131, 9727, 10961...$
$`\ndivisors of 477666356354107 = {1, 19, 29, 47, 71, 97, 113, 137, 173, 551, 893, 1349, 1363, 1843, 2059, 2147, 2603, 2813, 3277, 3287, 3337, 3973, 4559, 5017, 5311, 6439, 6887, 8023, 8131, 9727, 10961...$
$`\ndivisors of 477666356354107 = {1, 19, 29, 47, 71, 97, 113, 137, 173, 551, 893, 1349, 1363, 1843, 2059, 2147, 2603, 2813, 3277, 3287, 3337, 3973, 4559, 5017, 5311, 6439, 6887, 8023, 8131, 9727, 10961...$

$`\nCommon divisors` = {1, 29, 47, 71, 97, 113, 173, 1363, 2059, 2813, 3277, 3337, 4559, 5017, 5311, 6887, 8023, 8131, 10961, 12283, 16781, 19549, 96773, 132211, 154019, 199723, 232667, 235799, 317869, ...$
$`\nCommon divisors` = {1, 29, 47, 71, 97, 113, 173, 1363, 2059, 2813, 3277, 3337, 4559, 5017, 5311, 6887, 8023, 8131, 10961, 12283, 16781, 19549, 96773, 132211, 154019, 199723, 232667, 235799, 317869, ...$
$`\nCommon divisors` = {1, 29, 47, 71, 97, 113, 173, 1363, 2059, 2813, 3277, 3337, 4559, 5017, 5311, 6887, 8023, 8131, 10961, 12283, 16781, 19549, 96773, 132211, 154019, 199723, 232667, 235799, 317869, ...$
$`\nCommon divisors` = {1, 29, 47, 71, 97, 113, 173, 1363, 2059, 2813, 3277, 3337, 4559, 5017, 5311, 6887, 8023, 8131, 10961, 12283, 16781, 19549, 96773, 132211, 154019, 199723, 232667, 235799, 317869, ...$
$`\nCommon divisors` = {1, 29, 47, 71, 97, 113, 173, 1363, 2059, 2813, 3277, 3337, 4559, 5017, 5311, 6887, 8023, 8131, 10961, 12283, 16781, 19549, 96773, 132211, 154019, 199723, 232667, 235799, 317869, ...$
$`\nCommon divisors` = {1, 29, 47, 71, 97, 113, 173, 1363, 2059, 2813, 3277, 3337, 4559, 5017, 5311, 6887, 8023, 8131, 10961, 12283, 16781, 19549, 96773, 132211, 154019, 199723, 232667, 235799, 317869, ...$

$`\nGCD = maximum divisor ` = 183506091569$
$`\nGCD = maximum divisor ` = 183506091569$

Notice that if there are no common prime factors, then the gcd is always 1.

> gcd_concept( 8, 9 );

$`\ndivisors of 8 = {1, 2, 4, 8}`$
$`\ndivisors of 8 = {1, 2, 4, 8}`$

$`\ndivisors of 9 = {1, 3, 9}`$
$`\ndivisors of 9 = {1, 3, 9}`$

$`\nCommon divisors` = {1}$
$`\nCommon divisors` = {1}$

$`\nGCD = maximum divisor ` = 1$
$`\nGCD = maximum divisor ` = 1$

> gcd_concept( 25,36);

$`\ndivisors of 25 = {1, 5, 25}`$
$`\ndivisors of 25 = {1, 5, 25}`$

$`\ndivisors of 36 = {1, 2, 3, 4, 6, 9, 12, 18, 36}`$
$`\ndivisors of 36 = {1, 2, 3, 4, 6, 9, 12, 18, 36}`$

$`\nCommon divisors` = {1}$
$`\nCommon divisors` = {1}$

$`\nGCD = maximum divisor ` = 1$
$`\nGCD = maximum divisor ` = 1$

> gcd_concept( 144, 149);

$`\ndivisors of 144 = {1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72, 144}`$
$`\ndivisors of 144 = {1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72, 144}`$

$`\ndivisors of 149 = {1, 149}`$
$`\ndivisors of 149 = {1, 149}`$

$`\nCommon divisors` = {1}$
$`\nCommon divisors` = {1}$

$`\nGCD = maximum divisor ` = 1$
$`\nGCD = maximum divisor ` = 1$

> gcd_concept( 96, 95);

$`\ndivisors of 96 = {1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 96}`$
$`\ndivisors of 96 = {1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 96}`$

$`\ndivisors of 95 = {1, 5, 19, 95}`$
$`\ndivisors of 95 = {1, 5, 19, 95}`$

$`\nCommon divisors` = {1}$
$`\nCommon divisors` = {1}$

$`\nGCD = maximum divisor ` = 1$
$`\nGCD = maximum divisor ` = 1$

3. The Concept of the LCM

We can take multiples of any number. For example, the multiples of 6 are 6, 12, 18, 24, 36, 42, 48, 54, 60, 66, ....
There are an infinite number of multiples.

If we have two numbers, each has its own list of multiples. If we take the intersection of those two sets, we get the common multiples. The least of these is the LCM, or "least common multiple."

> lcm_concept( 4, 6);

$`\nmultiples of 4 = `$
$`\nmultiples of 4 = `$

$`\nmultiples of 6 = `$
$`\nmultiples of 6 = `$

$`\nCommon multiples` = {12, 24}$
$`\nCommon multiples` = {12, 24}$

$`\nLCM = minimum multiple ` = 12$
$`\nLCM = minimum multiple ` = 12$

> lcm_concept( 8, 10);

$`\nmultiples of 8 = `$
$`\nmultiples of 8 = `$

$`\nmultiples of 10 = `$
$`\nmultiples of 10 = `$

$`\nCommon multiples` = {40, 80}$
$`\nCommon multiples` = {40, 80}$

$`\nLCM = minimum multiple ` = 40$
$`\nLCM = minimum multiple ` = 40$

> lcm_concept( 18, 24);

$`\nmultiples of 18 = `$
$`\nmultiples of 18 = `$

$`\nmultiples of 24 = `$
$`\nmultiples of 24 = `$

$`\nCommon multiples` = {72, 144, 216, 288, 360, 432}$
$`\nCommon multiples` = {72, 144, 216, 288, 360, 432}$

$`\nLCM = minimum multiple ` = 72$
$`\nLCM = minimum multiple ` = 72$

> lcm_concept( 48, 72);

$`\nmultiples of 48 = `$
$`\nmultiples of 48 = `$

$`\nmultiples of 72 = `$
$`\nmultiples of 72 = `$

$`\nCommon multiples` = {144, 288, 432, 576, 720, 864, 1008, 1152, 1296, 1440, 1584, 1728, 1872, 2016, 2160, 2304, 2448, 2592, 2736, 2880, 3024, 3168, 3312, 3456}$
$`\nCommon multiples` = {144, 288, 432, 576, 720, 864, 1008, 1152, 1296, 1440, 1584, 1728, 1872, 2016, 2160, 2304, 2448, 2592, 2736, 2880, 3024, 3168, 3312, 3456}$
$`\nCommon multiples` = {144, 288, 432, 576, 720, 864, 1008, 1152, 1296, 1440, 1584, 1728, 1872, 2016, 2160, 2304, 2448, 2592, 2736, 2880, 3024, 3168, 3312, 3456}$

$`\nLCM = minimum multiple ` = 144$
$`\nLCM = minimum multiple ` = 144$

> lcm_concept( 105, 189);

$`\nmultiples of 105 = `$
$`\nmultiples of 105 = `$

$`\nmultiples of 189 = `$
$`\nmultiples of 189 = `$

$`\nCommon multiples` = {945, 1890, 2835, 3780, 4725, 5670, 6615, 7560, 8505, 9450, 10395, 11340, 12285, 13230, 14175, 15120, 16065, 17010, 17955, 18900, 19845}$
$`\nCommon multiples` = {945, 1890, 2835, 3780, 4725, 5670, 6615, 7560, 8505, 9450, 10395, 11340, 12285, 13230, 14175, 15120, 16065, 17010, 17955, 18900, 19845}$
$`\nCommon multiples` = {945, 1890, 2835, 3780, 4725, 5670, 6615, 7560, 8505, 9450, 10395, 11340, 12285, 13230, 14175, 15120, 16065, 17010, 17955, 18900, 19845}$

$`\nLCM = minimum multiple ` = 945$
$`\nLCM = minimum multiple ` = 945$

Note - that if there are no common prime factors, then the LCM is the product of the two numbers.

> lcm_concept( 5, 7);

$`\nmultiples of 5 = `$
$`\nmultiples of 5 = `$

$`\nmultiples of 7 = `$
$`\nmultiples of 7 = `$

$`\nCommon multiples` = {35}$
$`\nCommon multiples` = {35}$

$`\nLCM = minimum multiple ` = 35$
$`\nLCM = minimum multiple ` = 35$

> lcm_concept( 24, 25); 25*24;

$`\nmultiples of 24 = `$
$`\nmultiples of 24 = `$

$`\nmultiples of 25 = `$
$`\nmultiples of 25 = `$

$`\nCommon multiples` = {600}$
$`\nCommon multiples` = {600}$

$`\nLCM = minimum multiple ` = 600$
$`\nLCM = minimum multiple ` = 600$

> lcm_concept( 32, 30); 32*24;

$`\nmultiples of 32 = `$
$`\nmultiples of 32 = `$

$`\nmultiples of 30 = `$
$`\nmultiples of 30 = `$

$`\nCommon multiples` = {480, 960}$
$`\nCommon multiples` = {480, 960}$

$`\nLCM = minimum multiple ` = 480$
$`\nLCM = minimum multiple ` = 480$

> lcm_concept( 125, 126); 125*126;

$`\nmultiples of 125 = `$
$`\nmultiples of 125 = `$

$`\nmultiples of 126 = `$
$`\nmultiples of 126 = `$

$`\nCommon multiples` = {15750}$
$`\nCommon multiples` = {15750}$

$`\nLCM = minimum multiple ` = 15750$
$`\nLCM = minimum multiple ` = 15750$

> lcm_concept( 345, 198); 345 * 198;

$`\nmultiples of 345 = `$
$`\nmultiples of 345 = `$

$`\nmultiples of 198 = `$
$`\nmultiples of 198 = `$

$`\nCommon multiples` = {22770, 45540, 68310}$
$`\nCommon multiples` = {22770, 45540, 68310}$

$`\nLCM = minimum multiple ` = 22770$
$`\nLCM = minimum multiple ` = 22770$

4. Finding the GCD from the Factorization Table

To find the the GCD of two numbers - the greatest common divisor - create a prime factorization table ... and ...

> FactorTable( 24, 28);

... then take the MINIMUM of each column of primes. The product of these minimums is the GCD.

> GCDTable( 24, 28);

Lets find the GCD of 15 and 20.

> GCDTable( 15, 20);

> GCDTable( 80, 200);

> GCDTable( 48, 72);

> GCDTable( 105, 140);

> GCDTable( 144, 192);

> GCDTable( 2239245, 2626275);

> GCDTable( 10983487, 11348973);

5. Finding the LCM from the Factorization Table

To find the the LCM of two numbers - the greatest common multiple - create a prime factorization table ... and ...

> FactorTable( 24, 28);

...this time...take the MAXIMUM of each column rather than the minimum.

> LCMTable( 18, 24);

> LCMTable( 16, 24);

> LCMTable( 25, 35);

> LCMTable( 28, 49);

> LCMTable( 108, 81);

> LCMTable( 96, 72);

> LCMTable( 80, 45);

> LCMTable( 1734, 1581);

>

6. Finding the GCD & LCM Using Maple

Maple can compute these very quickly and directly :

> gcd( 18, 24);
lcm( 18, 24);

Here is another

> gcd( 100, 120);
lcm( 100, 120);

Here is something interesting. This also works for algebraic expressions as well as numbers.

> gcd( 4*x^2, 6*x);
lcm( 4*x^2, 6*x);

> A := 24*(x^5)*(y^2);
B := 36*(x^4)*(y^3);
`gcd ` = gcd( A, B);
`lcm ` = lcm( A, B);

> A := (x-3)*(x+8);
B := (x+5)*(x+8);
`gcd ` = gcd( A, B);
`lcm ` = lcm( A, B);

> A := x^3+11*x^2+19*x+9;
B := x^3+9*x^2-x-9;
`gcd ` = factor( gcd( A, B ));
`lcm ` = factor( lcm( A, B));

7. Product Relationship

Lets compare the product of two numbers to the product of their gcd and lcm.

> A := 24; B := 36;
`gcd = ` = gcd(A, B); `lcm = ` =lcm(A, B); print(` `);
`A*B = ` =A*B;
`gcd * lcm ` =gcd(A, B)*lcm(A, B);

Isn't that amazing? The two products are the same! Lets try some other examples to see if they work too.

> A := 64; B := 72;
`gcd = ` = gcd(A, B); `lcm = ` =lcm(A, B); print(` `);
`A*B = ` =A*B;
`gcd * lcm ` =gcd(A, B)*lcm(A, B);

> A := 105; B := 75;
`gcd = ` = gcd(A, B); `lcm = ` =lcm(A, B); print(` `);
`A*B = ` =A*B;
`gcd * lcm ` =gcd(A, B)*lcm(A, B);

> A := 2100; B := 750;
`gcd = ` = gcd(A, B); `lcm = ` =lcm(A, B); print(` `);
`A*B = ` =A*B;
`gcd * lcm ` =gcd(A, B)*lcm(A, B);

> A := 488; B := 160;
`gcd = ` = gcd(A, B); `lcm = ` =lcm(A, B); print(` `);
`A*B = ` =A*B;
`gcd * lcm ` =gcd(A, B)*lcm(A, B);

>

It appears there is a formula : A*B = gcd(A,B) * lcm(A*B). Can you prove it?