{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 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 257 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 1 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 0 128 0 1 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 262 "" 0 1 0 128 0 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 263 "" 0 1 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 264 "" 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 "Times" 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 262 50 "High School Modules > Algebra by Gregory A. Moore " }}{PARA 3 "" 0 "" {TEXT -1 4 " " }{TEXT 261 22 "Primes & Factorization" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 139 "The concepts of prime and composite numbers , how t o find them, prime factorization, the infinitude of the primes, and sq uare-free numbers." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 263 153 "[Directions : Execute the Code Resource section first. \+ Although there will be no output immediately, these definitions are us ed 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 22 "restart; with(plots): " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 252 "Primes := proc( N )\n local n, m, M;\n n := \+ min(14, floor( sqrt(N)*1.5 ));\n m := ceil( N/n);\n print(cat(`T he first `, n*m, ` primes : `)); print(` `);\n array( [seq( [ seq( ithprime( (j-1)*n+i), j = 1..n ) ], i = 1..m) ]);\n end proc:\n\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1028 "Sieve := proc( N )\n \+ local n, m, A,M, p,i,j,k, K;\n n := min(20, floor( sqrt(N)*1.5 ) );\n m := ceil( N/n); M := n*m;\n A:= array( [seq( [ seq( (i-1 )*n+j+1, j = 1..n ) ], i = 1..m) ]):\n print(cat(`Here are the in tegers from 2 to `, M+1)); print(` `);\n print(A); print(` `);print (` `);print(` `);\n\n K := 0; \n for K while ( ithprime(K+1) < e valf(sqrt(M))) do end do; \n \n for k from 1 to K do\n p := ithprime(k);\n for i from 1 to m do\n for j from 1 to n do\n if(A[i,j]<>p)\n then if( irem(A[i,j],p )=0) then A[i,j]:=` ` fi; fi; \n od;od;\n\n print(cat(`Here \+ are the integers from 2 to `, M+1,\n ` after removing m ultiples of `,p,` (except `,p,` itself)`)); \+ print(` `);\n print(A);print(` `);print(` `);\n od;\n pri nt(` `);\n print(`This is the Sieve of Erasathones. EVERY number le ft in this sieve is a prime number`);\n print(`because we have remo ved all of the composite numbers!!`);\n end proc:\n\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 714 "LargestPrime := proc(p)\nlocal n,k , P, N,NS,product;\nn := 0;\nfor n while ( ithprime(n) < p) do end do; P:= ithprime(n);\nprint(cat(`If `, P, ` (the `,n,`th prime) is the la rgest prime, then \"all known\" primes would be :`));\nproduct := 1;\n for k from 1 to n do\n product := product* ithprime(k); print(ithpr ime(k)); \nod;\nprint(` `); print(cat(`The product of all these \"know n\" primes is `, product));\nN := product +1 ;\nprint(cat(`If we add o ne to this product, we get the number `, N));\nNS := numtheory[factor set](N);\nif ( nops(NS) = 1) \n then print(cat(N,` is a \"new\" prim e number itself!`));\n else print(cat(N,` is not prime, but it conta ins \"new\" primes.`)); \n print(N = ifactor(N)); \nfi;\n\nend \+ proc:\n\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 406 "FindSquare := proc(N)\n local n,k,FS, square;\n if( numtheory[issqrfree](N) )\n \+ then print(cat(N,` is squarefree!`));\n else\n FS := numthe ory[factorset](N);\n square := 1; n:= nops(FS);\n for k \+ from 1 to n do \n if( irem(N, FS[k]^2) = 0) then square := square*FS[k]^2; fi;\n od;\n print(cat(square, ` is the gr eatest square that divides `,N));\n fi;\n \n\nend proc:" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 19 "1. What is a Prime?" }}{PARA 0 "" 0 "" {TEXT -1 100 "\nIn considering the natural numbers other than one, the re are two types of numbers :\n - " }{TEXT 256 13 "prime n umbers" }{TEXT -1 90 " - those numbers which can only be divided by 1 \+ and the number itself, and\n - " }{TEXT 257 18 "compositie numbers" }{TEXT -1 61 " - those numbers which can also be factored by other numbers\n" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 86 "`These a re prime numbers : `; \n7: %=ifactor(%); 31: %=ifactor(%); 173: %=if actor(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 92 "`These are com posite numbers : `;\n 6: %=ifactor(%); 35: %=ifactor(%); 221: %=ifa ctor(%); " }}}{PARA 0 "" 0 "" {TEXT -1 137 "\nAll natural numbers grea ter than one must be either prime or composite. Lets look at a larger \+ set of integers - the numbers from 2 to 40" }}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 35 "Integers := \{ seq(k, k = 2..40) \} ;" }}}{PARA 0 " " 0 "" {TEXT -1 75 "\nHere are the prime numbers \262 40. Notice that \+ NONE of them can be factored." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 106 "Primes := select( isprime, Integers );\nfor k from 1 to nops(Pr imes) do Primes[k] = ifactor(Primes[k]); od;" }}}{PARA 0 "" 0 "" {TEXT -1 81 "\nHere are the composite numbers \262 40. Note that each \+ one of them can be factored." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "Composites := remove( isprime, Integers);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 79 "for k from 1 to nops(Composites) do Composites[k ] = ifactor(Composites[k]); od;" }}}{PARA 0 "" 0 "" {TEXT -1 299 "\n\n There is an ancient method of finding primes. You start with a table o f natural numbers, then cast out multiples of primes. You leave the pr ime itself but remove all other multiples of that prime. You need only use primes less than or equal to the square root of the largest numbe r in your table. " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "Sieve( \+ 100);" }}}{PARA 0 "" 0 "" {TEXT -1 1 "\n" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 27 "2. The Sieve of Erasathon es" }}{PARA 0 "" 0 "" {TEXT -1 478 "\nThere is an ancient method of fi nding a whole bunch of primes at once. You start with a table of natur al numbers, then cast out multiples of primes. You leave the prime its elf but remove all other multiples of that prime. You need only use pr imes less than or equal to the square root of the largest number in yo ur table. \n\nLets look for all the primes up to about 40 .....\n(Note : After you execute this next line, you'll need to manually scroll ba ck up to look at each step)." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "Sieve(40);" }}}{PARA 0 "" 0 "" {TEXT -1 269 "You can see the distr ibution of primes from this diagram also. Notice the twin primes\" : ( 3,5), (5,7),(11,13), (17,19), (29,31),(41,43).\n\nHow many primes are \+ there less than 46? Look at the diagram and count how many numbers you see. You can also execute the next line." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "numtheory[pi](46);" }}}{PARA 0 "" 0 "" {TEXT -1 101 " \n\n\n\n\n\nIf you're ready for a little more excitement, hit the next command ... and hold on to your hat!" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "Sieve(199);" }}}{PARA 0 "" 0 "" {TEXT -1 321 "\n\nYou can also see the distribution of primes less than 200 here! Notice th at they seem to get more sparse as the numbers go up - in general. How ever, there are still \"twin primes\" such as 191 and 193 or 197 and 1 99 even close to the end!\n\nCan you count how many primes are in this chart? You should counted this number :" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "numtheory[pi](200);" }}}{PARA 0 "" 0 "" {TEXT -1 200 "\n\n\nWe can look at the distribution of primes another way too. If w e count how many primes are less than or equal to a given number, then make a graph of that count we get this very interesting graph :" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "plot( numtheory[pi](floor(x) ), x = 2..120);" }}}{PARA 0 "" 0 "" {TEXT -1 60 "\nThere seems to be a pattern...which was Gauss's conjecture." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "plot( \{numtheory[pi](floor(x)), x/ln(x)\}, x = 2..12 0);" }}}{PARA 0 "" 0 "" {TEXT -1 1 "\n" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 22 "3. Prime Factorization" }}{PARA 0 "" 0 "" {TEXT -1 39 "\n In this sense, composite numbers are " }{TEXT 258 8 "composed" } {TEXT -1 67 " of smaller numbers, while primes are composed only of th emselves. " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "2100 = `(30)(7 0)`; " }}}{PARA 0 "" 0 "" {TEXT -1 77 "\nHowever, each of the factors \+ is composite, since they can be factored also. " }}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 31 "30 = `(6)(5)`; 70 = `(7)(10)`;" }}}{PARA 0 " " 0 "" {TEXT -1 75 "\nAnd even some of these factors are composite and can be factored further. " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "6 = `(3)(2)`; 10 = `(5)(2)`;" }}}{PARA 0 "" 0 "" {TEXT -1 243 "\n Since each composite number can be factored, and possibly those factor s factored further, eventually this process must end . If a factor is \+ not prime, it can be factored further. The process ends when all of th e factors of a number are prime." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "2100 = `(30)(70) = (6)(5)(7)(10) = (3)(2)(5)(7)(5)(2)`;" }}} {PARA 0 "" 0 "" {TEXT -1 136 "\n\nIf we collect all the like primes to gether, and sort them in ascending order, we get a unique prime factor izaton for every composite :" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "ifactor(2100);" }}}{PARA 0 "" 0 "" {TEXT -1 108 "\n\nWe can easily get the prime factorizations for any composite using maple's integer \+ factorization command, " }{TEXT 259 7 "ifactor" }{TEXT -1 1 "." }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 63 "32: % = ifactor(%); \n105: % = ifactor(%);\n192: % = ifactor(%);\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "432: % = ifactor(%); \n4332: % = ifactor(%);\n4320: % = ifactor(%);" }}}{PARA 0 "" 0 "" {TEXT -1 178 "\n\n\nIn practice, yo u can make a factor tree to complete factor a number. Then collect all of the 'leaves' of the tree which are the same prime number, to expre ss in exponent form." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 67 "4. How many primes are there? and What is the Larges t Prime Number?" }}{PARA 0 "" 0 "" {TEXT -1 92 "\nThere appear to be n o shortage of prime numbers :\n\nHere are the first 20 prime numbers . ..." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "Primes(20);" }}} {PARA 0 "" 0 "" {TEXT -1 39 "\nand, here are the first 200 primes ... " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "Primes(100);" }}}{PARA 0 "" 0 "" {TEXT -1 42 "\nHere are the first 250 prime numbers ...." }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "Primes(250);" }}}{PARA 0 "" 0 "" {TEXT -1 30 "\nWe can find the 100th prime :" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "ithprime(100);" }}}{PARA 0 "" 0 "" {TEXT -1 49 "\nor the 200th, 300th, 400th ..., 2000th prime...." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 78 "for k from 1 to 20 do print( cat(10 0*k, `th prime is `, ithprime(100*k))); od;" }}}{PARA 0 "" 0 "" {TEXT -1 482 "\nIs there a largest prime number? Suppose there was. Let say \+ that p is the largest prime number. Then if we multiply all of the pri me numbers together, and add one :\n N = 1 + p1*p2*p3*.....*pn\n \nThis new number is not divisible any prime number - which makes a co ntradiction. So there must be more primes than this supposedly \"large st prime.\" This means there are actually an infinite number of primes . \n\nLets try this out on some prime. Suppose that 7 were the largest prime. " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "LargestPrime(7); \n" }}}{PARA 0 "" 0 "" {TEXT -1 70 "\nWhat if we thought that 17 might be the largest prime? or 37, or 53? " }{TEXT 260 140 "(Warning : the \+ bigger the number, the longer it will take. If it takes too long, hit \+ the red stop-sign button on the Maple tool bar at top.)" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "LargestPrime(17);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "LargestPrime(37);" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 17 "LargestPrime(53);" }}}{PARA 0 "" 0 "" {TEXT -1 486 "\nThus there are an infinite number of prime numbers, because \+ no matter how large of a prime number we find, there is always a large r one! Mathematicians have found prime numbers with hundreds of thousa nds of digits. How many pages would it take to display a 300,000 digit number?\n\nLets do an experiment. Using my computer (a Powerbook with 1024x768 monitor), I find that this number is the largest power of te n I can display on my screen on a single line. Lets assume 52 lines pe r page." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "1*10^105;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 82 "`number of digits` = 300000; \n`number of lines` = %/105;\n`number of pages` = %/50;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "evalf((300000)/(105*52));" }}} {PARA 0 "" 0 "" {TEXT -1 205 "\nIt would take most of 55 pages just to display one of these large prime numbers. Why don't we not try to fin d it and display, but go away with the comforting feeling that we now \+ know such numbers exist..\n" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 32 "5. Squarefree Numbers [optional]" }} {PARA 0 "" 0 "" {TEXT -1 226 " \nLater when we want to simplify square roots, we will want to leave only square-free numbers inside the radi cal.\n\nA square-free number is a number which contains no perfect squ ares. Look at the following numbers for a minute." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "42 : % = ifactor(%);\n330 : % = ifactor(%);\n 2431 : % = ifactor(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 50 "F indSquare(42);\nFindSquare(330);\nFindSquare(2431);" }}}{PARA 0 "" 0 " " {TEXT -1 127 "\nEach of these composite numbers is factorable - but \+ each factor has an exponent of 1. \n\nObviously all primes are square \+ free. " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 62 "17 : % = ifactor(% );\n41 : % = ifactor(%);\n97 : % = ifactor(%);" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 47 "FindSquare(17);\nFindSquare(41);\nFindSquare(9 7);" }}}{PARA 0 "" 0 "" {TEXT -1 118 "\nNow lets look at these numbers , which are NOT square free. Can you identify a perfect square \"hidin g\" in each number?" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 87 "12 : \+ % = ifactor(%);\n375 : % = ifactor(%);\n72 : % = ifactor(%);\n686 : % \+ = ifactor(%);\n\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "FindSq uare(12);\nFindSquare(375);\nFindSquare(72);\nFindSquare(686);" }}} {PARA 0 "" 0 "" {TEXT -1 218 "\n\nNotice that squarefree numbers are a lways products of distint primes - each with an exponent of 1! If a pr ime has a square, cube, 4th power, ...etc... then it contains at least a perfect square of that prime squared." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "6 : % = ifactor(%); FindSquare(%%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "12 : % = ifactor(%); FindSquare( %%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "24 : % = ifactor(%) ; FindSquare(%%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "48 \+ : % = ifactor(%); FindSquare(%%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "96: % = ifactor(%); FindSquare(%%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "192 : % = ifactor(%); FindSquare (%%);" }}}{PARA 0 "" 0 "" {TEXT -1 1 "\n" }}}{PARA 0 "" 0 "" {TEXT 264 37 "\n \251 2002 Waterloo Maple Inc " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{MARK "0 0" 24 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 } {PAGENUMBERS 0 1 2 33 1 1 }