{VERSION 3 0 "IBM INTEL NT" "3.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 0 12 0 0 128 1 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "# F_n.ms\n" }{TEXT -1 723 "## Is 2^p-1 prime for infinitely many p? ##\n# Is 2^(2 ^n)+1 prime for some n > 4? #\n# \+ #\n# John B. Cosgrave, #\n# \+ Department of Mathematics, #\n# St. Patrick's Co llege, #\n# Drumcondra, # \n# Dublin 9, #\n# IRELAND. #\n# \+ #\n# Home e-mail: johnbcos@iol.ie #\n# College e -mail: John.Cosgrave@spd.ie #\n# \+ #\n# 2^sqrt(2) is transcendental. Pi(x)~x/ln(x). # \n## \+ .12345678910111213 ... is normal. Is Pi? ##\n\n" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 104 "This worksheet is about applying the Lucas-(Krait chik)-Lehmer-Selfridge theorem to the 'Fermat numbers'." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 161 "It's actually only \+ the Lehmer part that we use here, since here the numbers 'N' that are \+ being tested are such that 'N-1' has ONLY ONE prime factor, namely '2' . " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 141 "Th e (famous) 'Fermat numbers' - F[n]- are the numbers of the form (2^m + 1), where 'm' is itself a power of 2 (m = 2^n, n = 0, 1, 2, 3, ... ) " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 180 "Ferm at believed that ALL these numbers were prime. They ARE prime for n = \+ 0,1,2,3 and 4, BUT no value of 'n' greater than 4 has been found for w hich F(n) ( = 2^(2^n) + 1) is prime." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "F := n -> 2^(2^n) + 1;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 43 "The numbers F(n) grow in size very rapidly:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "F(0);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "F(1);" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 5 "F(2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "F(3);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "F(6);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "F(7);" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 5 "F(8);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "F(9);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "isprime(F(4)) ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "isprime(F(5));" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 217 "Let's use Fermat tests to base 2 (3, ... ) to see what h appens ... . If an F(n) fails the Fermat test we know it is composite, but if an F(n) passes the Fermat test we will use Lehmer to see if we can prove primality." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 20 "We start with F(4): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "2&^(F(4) - 1) mod F(4); # F(4) passes Fermat's test to base '2' :" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "2&^((F(4) - 1)/2) mod \+ F(4); # then Lehmer is no use:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "3&^(F(4) - 1) mo d F(4); # F(5) passes Fermat's test to base '3':" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 62 "3&^((F(4) - 1)/2) mod F(4); # here Lehmer pr oves F(4) is prime" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 20 "Let's see its value:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "F(4);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 9 "Now F(5):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "2&^(F(5) - 1) mod F(5); # F(5) passes Fermat's test to base '2':" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "2&^((F(5) - 1)/2) mod F(5); # then Lehmer is no use:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 62 "3&^(F(5) - 1) mod F(5); # F (5) fails Fermat test to base '3':" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 47 "And so F(5) is composite. Let's see its value:" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 5 "F(5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 9 "Now F(6):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 62 "2&^(F(6) - 1) mod F(6); # F(6) passes Fermat test to base '2':" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "2&^((F(6) - 1)/2) mod F(6); # then Lehme r is no use:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 62 "3&^(F(6) - 1) mod F(6); # F(6) fai ls Fermat test to base '3':" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 47 "An d so F(6) is composite. Let's see its value:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "F(6);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" } }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 9 "N ow F(7):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 62 "2&^(F(7) - 1) mod F(7); # F(6) passes Fermat test to base '2':" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "2&^((F(7) - 1)/2) mod F(7); # then Lehmer is no use: " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 62 "3&^(F(7) - 1) mod F(7); # F(7) fails Fermat t est to base '3':" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 47 "And so F(7) i s composite. Let's see its value:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "F(7);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 9 "Now F(8): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 63 "2&^(F(8) - 1) mod F(8); # F(8) passes Fermat test to base '2':" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "2&^((F(8) - 1)/2) mod F(8); # then Lehmer is no use: " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 62 "3&^(F(8) - 1) mod F(8); # F(8) fails Fermat t est to base '3':" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 47 "And so F(8) i s composite. Let's see its value:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "F(8);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 9 "Now F(9): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 63 "2&^(F(9) - 1) mod F(9); # F(9) passes Fermat test to base '2':" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "2&^((F(9) - 1)/2) mod F(9); # then Lehmer is no use: " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 62 "3&^(F(9) - 1) mod F(9); # F(9) fails Fermat t est to base '3':" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 47 "And so F(9) i s composite. Let's see its value:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "F(9);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 10 "Now F(10) :" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 66 "2&^(F(10) - 1) mod F(10); # F (10) passes Fermat test to base '2':" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "2&^((F(10) - 1)/2) mod F(10); # then Lehmer is no us e:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "3&^(F(10) - 1) mod F(10); # F(10) fails Ferm at test to base '3':" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 48 "And so F( 10) is composite. Let's see its value:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "F(10);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 147 "F(n) is KNOWN to be composite for n = 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, [UNKNOWN for 22], 23 , 24, ... and for many other greater values." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 38 "F(n) has been COMPLETELY factor ed for:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 21 " n = 5 (Euler, 1732)" }}{PARA 0 "" 0 "" {TEXT -1 22 " n = 6 (Lan dry, 1880)" }}{PARA 0 "" 0 "" {TEXT -1 38 " n = 7 (Morrison and Brill hart, 1975)" }}{PARA 0 "" 0 "" {TEXT -1 45 " n = 8 (Brent and Pollard - using Pollard's " }}{PARA 0 "" 0 "" {TEXT -1 29 " 'rho' me thod, 1981)" }}{PARA 0 "" 0 "" {TEXT -1 52 " n = 9 (Lenstra (Arjen), \+ Lenstra (Hendrik), Manasse" }}{PARA 0 "" 0 "" {TEXT -1 51 " a nd Pollard - using the NFS method, 1993)" }}{PARA 0 "" 0 "" {TEXT -1 24 " n = 10 (Brent, 1995?)," }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 52 "and some factors are known for larger values of 'n'." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 69 " The factorization of F(n) represents a HUGE challenge to mathematics. " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "58 15 0" 44 } {VIEWOPTS 1 1 0 1 1 1803 }