{VERSION 5 0 "IBM INTEL NT" "5.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "" -1 256 "" 0 1 0 128 0 1 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 257 "" 0 1 0 128 0 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 261 "" 0 1 128 128 128 1 0 0 0 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 1" -1 3 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 4 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 2" -1 4 1 {CSTYLE "" -1 -1 "Ti mes" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 2 1 0 1 0 2 2 0 1 }} {SECT 0 {PARA 0 "" 0 "" {TEXT 257 50 "High School Modules > Algebra by Gregory A. Moore " }}{PARA 3 "" 0 "" {TEXT -1 4 " " }{TEXT 256 9 " GCD & LCM" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 37 "An examination of the concept of the " }{TEXT 259 3 "gcd" }{TEXT -1 5 " and " }{TEXT 260 3 "lcm" }{TEXT -1 164 ". We explore the concep t, 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 ." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 258 153 "[D irections : Execute the Code Resource section first. Although there wi ll be no output immediately, these definitions are used later in this \+ worksheet.]" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{SECT 0 {PARA 4 "" 0 " " {TEXT -1 7 "0. Code" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "rest art; " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 978 "FactorTable := \+ proc( n, m )\n local N, M, P, i,j,k, A, p ;\n print( n = ifac tor(n) );\n print( m = ifactor(m) );\n N := numtheory[factor set](n);\n M := numtheory[factorset](m);\n P := N union M; p := nops(P);\n #for k from 1 to nops(M) do print( M[k]); od;\n \+ A := array( [seq( [ \n seq( ` `, j = 1..p+2 ) \n \+ ], i = 1..2+2 ) \n ]);\n for j from 1 to p do A[1,j+2] := P[j]; od;\n for j from 1 to p do A[2 ,j+2] := `__`; od;\n A[3,1] := n; A[4,1] := m;\n A[3,2] := `|`; A[4,2] := `|`; A[1,1] := `primes =`;\n\n for k from 1 to p do\n for i from 0 by 1 \n while (irem(n,P[k]^ i)=0) do end do; \n A[3, k + 2] := ifactor(P[k]^(i-1)); \n od;\n\n for k from 1 to p do\n for i from 0 by \+ 1 \n while (irem(m,P[k]^i)=0) do end do; \n \+ A[4, k + 2] := ifactor(P[k]^(i-1));\n od;\n print(A);\n \n end proc:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1531 "GCDTable \+ := proc( n, m )\n local N, M, P, i,j,k, A, p ;\n N := numthe ory[factorset](n);\n M := numtheory[factorset](m);\n P := N un ion M; p := nops(P);\n #for k from 1 to nops(M) do print( M[k]); od;\n A := array( [seq( [ \n seq( ` `, j = 1..p+ 3 ) \n ], i = 1..2+4 ) \n ]); \n for j from 1 to p do A[1,j+2] := P[j]; od;\n for j from 1 t o p do A[2,j+2] := `__`; od;\n for j from 1 to p do A[5,j+2] := `_ _`; od;\n A[3,1] := n; A[4,1] := m;\n A[3,2] := `|`; A[4 ,2] := `|`;\n A[1,1] := `primes =`;\n\n #______Row with 1st fac torization_________\n for k from 1 to p do\n for i from 0 \+ by 1 \n while (irem(n,P[k]^i)=0) do end do; \n \+ A[3, k + 2] := ifactor(P[k]^(i-1));\n od;\n\n #______ Row with 2nd factorization_________\n for k from 1 to p do\n \+ for i from 0 by 1 \n while (irem(m,P[k]^i)=0) do end d o; \n A[4, k + 2] := ifactor(P[k]^(i-1));\n od; \n #______Last row with GCD factorization_________\n for k from \+ 1 to p do\n for i from 0 by 1 \n while (irem(m,P [k]^i)=0) do end do; \n A[6, k + 2] := ifactor(\n \+ min( expand(A[3,k+2]),expand(A[4,k+2]))); \n \+ od;\n\n A[6,1] := `GCD =`; \n A[6, p + 3] := 1;\n \+ for k from 1 to p do\n A[6, p + 3] := expand(A[6, p+3]* A[6 ,k+2]); \n od;\n\n A[6, p + 3] := cat(`= `, A[6, p + 3]);\n print(A);\n\n end proc:\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1389 "LCMTable := proc( n, m )\n local N, M, P, i,j,k, A, p \+ ;\n N := numtheory[factorset](n);\n M := numtheory[factorset]( m);\n P := N union M; p := nops(P);\n #for k from 1 to nops( M) do print( M[k]); od;\n A := array( [seq( [ \n \+ seq( ` `, j = 1..p+3 ) \n ], i = 1..2+4 ) \n \+ ]);\n for j from 1 to p do A[1,j+2] := P[j]; od;\n for j from 1 to p do A[2,j+2] := `__`; od;\n for j from 1 to \+ p do A[5,j+2] := `__`; od;\n A[3,1] := n; A[4,1] := m;\n A [3,2] := `|`; A[4,2] := `|`;\n A[1,1] := `primes =`;\n\n for k from 1 to p do\n for i from 0 by 1 \n while ( irem(n,P[k]^i)=0) do end do; \n A[3, k + 2] := ifactor(P [k]^(i-1));\n od;\n\n for k from 1 to p do\n for i from 0 by 1 \n while (irem(m,P[k]^i)=0) do end do; \n \+ A[4, k + 2] := ifactor(P[k]^(i-1));\n od;\n\n \+ for k from 1 to p do\n for i from 0 by 1 \n whi le (irem(m,P[k]^i)=0) do end do; \n A[6, k + 2] := ifact or(\n max( expand(A[3,k+2]), expand(A[4 , k+2]))); \n od;\n\n A[6,1] := `LCM =`; \n A[6, p + 3] := 1;\n for k from 1 to p do\n A[6, p + 3] := expand (A[6, p+3]* A[6,k+2]); \n od;\n\n A[6, p + 3] := cat(`= `, \+ A[6, p + 3]);\n print(A);\n\n end proc:\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 174 "min_element := proc( S)\n local n, i, min;\n \+ n := nops(S);\n min := S[1];\n for i from 1 to n do \n i f( min > S[i] ) then min := S[i]; fi; od; \n min;\nend proc:\n\n" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 172 "max_element := proc( S)\n \+ local n, i, max;\n n := nops(S);\n max := S[1];\n for i from 1 \+ to n do \n if( max < S[i] ) then max := S[i]; fi; od; \n ma x;\nend proc:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 382 "gcd_conce pt := proc(n, m)\n local N, M, Common;\n N := numtheory[divisors](n );\n print(cat(`\\ndivisors of `,n, ` = `,convert(N , string)));\n \+ M := numtheory[divisors](m);\n print(cat(`\\ndivisors of `,m, ` = ` ,convert(M , string))); \n Common := % intersect %%:\n print( `\\n Common divisors` = Common); \n print( `\\nGCD = maximum divisor ` = max_element( Common ));\nend proc:\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 420 "lcm_concept := proc(n, m)\n local N, M, Common;\n \+ N := \{seq( n*k, k = 1..m)\};\n print(cat(`\\nmultiples of `,n, ` = `)); print(cat(` `, convert(N , string)) );\n M := \{seq( m*k, k = \+ 1..n)\};\n print(cat(`\\nmultiples of `,m, ` = `)); print(cat(` `, c onvert(M , string)) );\n Common := % intersect %%:\n print(`\\nCom mon multiples` = Common);\n print(`\\nLCM = minimum multiple ` = min _element( Common ));\nend proc:\n\n " }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 39 "1. Creating a Prime Factorization Table" }}{PARA 0 "" 0 " " {TEXT -1 84 "\nEvery positive integer (greater than one) can be fact ored into a product of primes." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "24: % = ifactor(%);\n90: % = ifactor(%);" }}}{PARA 0 "" 0 "" {TEXT -1 279 "\nGiven two numbers, we can create a table, by organizin g this information. We write the original numbers along the left side, and list ALL of the primes available in either of the two numbers alo ng the top. Then we fill in what power of the given prime is present i n each number." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "FactorTabl e( 24, 90);" }}}{PARA 0 "" 0 "" {TEXT -1 30 "\nLets try some other exa mples." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "FactorTable( 20, 1 5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "FactorTable( 42,36); " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "FactorTable( 144, 196); " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "FactorTable( 15801075, \+ 149232375);" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 25 "2. The Concept of the GCD" }}{PARA 0 "" 0 "" {TEXT -1 430 "\n Each integer has a certain number of divisors - numbers which \+ divide into the number evenly. If we make a list of the divisors of ea ch number, then take the intersection of those two sets, we have a lis t of common factors. These common divisors are the only numbers which \+ divide both of the two original numbers.\n\nNow we if simply take the \+ greatest of these common divisors, we have the gcd - the \"greatest co mmon divisor.\"\n " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "gcd _concept( 18, 24);\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "gcd _concept( 25, 35);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "gcd_c oncept( 144, 192);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "gcd_c oncept( 45, 210);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "gcd_co ncept( 120, 180);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "gcd_co ncept( 17810275, 5686625);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "gcd_concept( 300766484081591, 477666356354107);" }}}{PARA 0 "" 0 " " {TEXT -1 77 "\n\nNotice that if there are no common prime factors, t hen the gcd is always 1." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 " gcd_concept( 8, 9 );" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "gcd _concept( 25,36);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "gcd_co ncept( 144, 149);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "gcd_co ncept( 96, 95);" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 0 {PARA 4 " " 0 "" {TEXT -1 25 "3. The Concept of the LCM" }}{PARA 0 "" 0 "" {TEXT -1 358 "\nWe can take multiples of any number. For example, the \+ multiples of 6 are 6, 12, 18, 24, 36, 42, 48, 54, 60, 66, ....\nThere \+ are an infinite number of multiples. \n\nIf we have two numbers, each \+ has its own list of multiples. If we take the intersection of those tw o sets, we get the common multiples. The least of these is the LCM, or \"least common multiple.\"\n" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "lcm_concept( 4, 6);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "lcm_concept( 8, 10);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "lcm_concept( 18, 24);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "l cm_concept( 48, 72);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "lcm _concept( 105, 189);" }}}{PARA 0 "" 0 "" {TEXT -1 99 "\n\nNote - that \+ if there are no common prime factors, then the LCM is the product of t he two numbers." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "lcm_conce pt( 5, 7);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "lcm_concept( \+ 24, 25); 25*24;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "lcm_ concept( 32, 30); 32*24;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "lcm_concept( 125, 126); 125*126;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "lcm_concept( 345, 198); 345 * 198;" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 47 "4. Finding \+ the GCD from the Factorization Table" }}{PARA 0 "" 0 "" {TEXT -1 120 " \n To find the the GCD of two numbers - the greatest common divisor - \+ create a prime factorization table ... and ...\n " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "FactorTable( 24, 28);\n" }}}{PARA 0 "" 0 "" {TEXT -1 94 "\n... then take the MINIMUM of each column of primes. \+ The product of these minimums is the GCD." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "GCDTable( 24, 28);" }}}{PARA 0 "" 0 "" {TEXT -1 33 " \n Lets find the GCD of 15 and 20." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "GCDTable( 15, 20);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "GCDTable( 80, 200);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "GCDTable( 48, 72);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "GCDTable( 105, 140);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "GCDTable( 144, 192);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "GCDTable( 2239245, 2626275);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "GCDTable( 10983487, 11348973);" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 47 "5. Finding th e LCM from the Factorization Table" }}{PARA 0 "" 0 "" {TEXT -1 116 "\n To find the the LCM of two numbers - the greatest common multiple - cr eate a prime factorization table ... and ...\n" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "FactorTable( 24, 28);" }}}{PARA 0 "" 0 "" {TEXT -1 73 "\n...this time...take the MAXIMUM of each column rather than th e minimum.\n" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "LCMTable( 18 , 24);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "LCMTable( 16, 24) ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "LCMTable( 25, 35);" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "LCMTable( 28, 49);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "LCMTable( 108, 81);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "LCMTable( 96, 72);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "LCMTable( 80, 45);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "LCMTable( 1734, 1581);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 36 "6. Finding the GCD & L CM Using Maple" }}{PARA 0 "" 0 "" {TEXT -1 52 "\nMaple can compute the se very quickly and directly :" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "gcd( 18, 24);\nlcm( 18, 24);" }}}{PARA 0 "" 0 "" {TEXT -1 16 "\n Here is another" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "gcd( 100, 120);\nlcm( 100, 120);" }}}{PARA 0 "" 0 "" {TEXT -1 93 "\nHere is som ething interesting. This also works for algebraic expressions as well \+ as numbers." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "gcd( 4*x^2, 6 *x);\nlcm( 4*x^2, 6*x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 84 " A := 24*(x^5)*(y^2);\nB := 36*(x^4)*(y^3);\n`gcd ` = gcd( A, B);\n`lcm ` = lcm( A, B);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 78 "A := ( x-3)*(x+8);\nB := (x+5)*(x+8);\n`gcd ` = gcd( A, B);\n`lcm ` = lcm( A , B);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 106 "A := x^3+11*x^2+1 9*x+9;\nB := x^3+9*x^2-x-9;\n`gcd ` = factor( gcd( A, B ));\n`lcm ` \+ = factor( lcm( A, B));" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 23 "7. Product Relationship" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 76 "Lets compare the produc t of two numbers to the product of their gcd and lcm." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 125 "A := 24; B := 36;\n`gcd = ` = gcd(A, B) ; `lcm = ` =lcm(A, B); print(` `);\n`A*B = ` =A*B; \n`gcd * lcm ` =gc d(A, B)*lcm(A, B);" }}}{PARA 0 "" 0 "" {TEXT -1 105 "\nIsn't that amaz ing? The two products are the same! Lets try some other examples to se e if they work too." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 126 " A : = 64; B := 72;\n`gcd = ` = gcd(A, B); `lcm = ` =lcm(A, B); print(` `) ;\n`A*B = ` =A*B; \n`gcd * lcm ` =gcd(A, B)*lcm(A, B);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 127 " A := 105; B := 75;\n`gcd = ` = g cd(A, B); `lcm = ` =lcm(A, B); print(` `);\n`A*B = ` =A*B; \n`gcd * l cm ` =gcd(A, B)*lcm(A, B);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 129 " A := 2100; B := 750;\n`gcd = ` = gcd(A, B); `lcm = ` =lcm(A, B) ; print(` `);\n`A*B = ` =A*B; \n`gcd * lcm ` =gcd(A, B)*lcm(A, B);" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 128 " A := 488; B := 160;\n`g cd = ` = gcd(A, B); `lcm = ` =lcm(A, B); print(` `);\n`A*B = ` =A*B; \+ \n`gcd * lcm ` =gcd(A, B)*lcm(A, B);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 77 "\nIt appears there i s a formula : A*B = gcd(A,B) * lcm(A*B). Can you prove it?" }}}{PARA 0 "" 0 "" {TEXT 261 36 "\n \251 2002 Waterloo Maple Inc " }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}}{MARK "0 0" 30 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }