Prime Numbers Wiki Presentation Cryptography Problem A list of primes ithprime(3); IiIm isprime(6); SSZmYWxzZUclKnByb3RlY3RlZEc= Does the polynomial n^2+n+41 attains always prime values for n = 1,2,...? for n from 1 to 100 do if not isprime(n^2+n+41) then print(n, n^2+n+41);fi; end do; NiQiI1MiJSJvIg== NiQiI1QiJWo8 NiQiI1ciJUA/ NiQiI1wiJSJcIw== NiQiI2MiJUxL NiQiI2wiJUpW NiQiI3ciJSQqZQ== NiQiIyIpIiUkbyc= NiQiIyMpIiVabw== NiQiIyUpIiUiPSg= NiQiIygpIiUocCg= NiQiIyopIiVeISk= NiQiIyIqIiU4JSk= NiQiIycqIiVgJCo= Sieve of Erathostenes How does Maple determine primality? showstat(isprime); isprime := proc(n) local btor, nr, p, r; 1 if not type(n,'integer') then 2 if type(n,('complex')('numeric')) then 3 error "argument must be an integer" else 4 return 'isprime(n)' end if end if; 5 if n < 2 then 6 return false elif member(n,isprime:-special_primes) then 7 return true elif igcd(2305567963945518424753102147331756070,n) <> 1 then 8 return false elif n < 10201 then 9 return true elif igcd(8496969489233418110532339909187349965926062586648932736611545426342203893270769390909069477309509137509786917118668028861499333825097682386722983737962963066757674131126736578936440788157186969893730633113066478620448624949257324022627395437363639038752608166758661255956834630697220447512298848222228550062683786342519960225996301315945644470064720696621750477244528915927867113,n) <> 1 then 10 return false elif n < 1018081 then 11 return true else 12 r := gmp_isprime(n); 13 if not r or n <= 5000000000 then 14 return r end if; 15 nr := igcd(408410100000,n-1); 16 nr := igcd(nr^5,n-1); 17 r := iquo(n-1,nr); 18 btor := modp(('power')(2,r),n); 19 if cyclotest(n,btor,2,r) = false or irem(nr,3) = 0 and cyclotest(n,btor,3,r) = false or irem(nr,5) = 0 and cyclotest(n,btor,5,r) = false or irem(nr,7) = 0 and cyclotest(n,btor,7,r) = false then 20 return false end if; 21 if isqrt(n)^2 = n then 22 return false end if; 23 for p from 3 while numtheory:-jacobi(p^2-4,n) <> -1 do 24 NULL end do; 25 return evalb(TraceModQF(p,n+1,n) = [2, p]) end if end proc Top ten largest primes Mersenne primes Exercise: Find all the primes of the form 2^i-1, where i =2,3,....20. State a conjecture of the form "If 2^i-1 is prime then i...." Can you prove this conjecture? (Extra credit homework) for n from 1 to 100 do print(n, isprime(2^n-1),2^n-1); end do; NiUiIiJJJmZhbHNlRyUqcHJvdGVjdGVkR0Yj NiUiIiNJJXRydWVHJSpwcm90ZWN0ZWRHIiIk NiUiIiRJJXRydWVHJSpwcm90ZWN0ZWRHIiIo NiUiIiVJJmZhbHNlRyUqcHJvdGVjdGVkRyIjOg== NiUiIiZJJXRydWVHJSpwcm90ZWN0ZWRHIiNK NiUiIidJJmZhbHNlRyUqcHJvdGVjdGVkRyIjag== NiUiIihJJXRydWVHJSpwcm90ZWN0ZWRHIiRGIg== NiUiIilJJmZhbHNlRyUqcHJvdGVjdGVkRyIkYiM= NiUiIipJJmZhbHNlRyUqcHJvdGVjdGVkRyIkNiY= NiUiIzVJJmZhbHNlRyUqcHJvdGVjdGVkRyIlQjU= NiUiIzZJJmZhbHNlRyUqcHJvdGVjdGVkRyIlWj8= NiUiIzdJJmZhbHNlRyUqcHJvdGVjdGVkRyIlJjQl NiUiIzhJJXRydWVHJSpwcm90ZWN0ZWRHIiUiPik= NiUiIzlJJmZhbHNlRyUqcHJvdGVjdGVkRyImJFE7 NiUiIzpJJmZhbHNlRyUqcHJvdGVjdGVkRyImbkYk NiUiIztJJmZhbHNlRyUqcHJvdGVjdGVkRyImTmIn NiUiIzxJJXRydWVHJSpwcm90ZWN0ZWRHIidyNTg= NiUiIz1JJmZhbHNlRyUqcHJvdGVjdGVkRyInVkBF NiUiIz5JJXRydWVHJSpwcm90ZWN0ZWRHIicoR0Mm NiUiIz9JJmZhbHNlRyUqcHJvdGVjdGVkRyIodiZbNQ== NiUiI0BJJmZhbHNlRyUqcHJvdGVjdGVkRyIoXnI0Iw== NiUiI0FJJmZhbHNlRyUqcHJvdGVjdGVkRyIoLlY+JQ== NiUiI0JJJmZhbHNlRyUqcHJvdGVjdGVkRyIoMicpUSk= NiUiI0NJJmZhbHNlRyUqcHJvdGVjdGVkRyIpOnN4Ow== NiUiI0RJJmZhbHNlRyUqcHJvdGVjdGVkRyIpSldiTA== NiUiI0VJJmZhbHNlRyUqcHJvdGVjdGVkRyIpaikzcic= NiUiI0ZJJmZhbHNlRyUqcHJvdGVjdGVkRyIqRnhATSI= NiUiI0dJJmZhbHNlRyUqcHJvdGVjdGVkRyIqYmFWbyM= NiUiI0hJJmZhbHNlRyUqcHJvdGVjdGVkRyIqNjQob2A= NiUiI0lJJmZhbHNlRyUqcHJvdGVjdGVkRyIrQj11dDU= NiUiI0pJJXRydWVHJSpwcm90ZWN0ZWRHIitaT1taQA== NiUiI0tJJmZhbHNlRyUqcHJvdGVjdGVkRyIrJkhuXEgl NiUiI0xJJmZhbHNlRyUqcHJvdGVjdGVkRyIrImZNKiplKQ== NiUiI01JJmZhbHNlRyUqcHJvdGVjdGVkRyIsJD1wKXpyIg== NiUiI05JJmZhbHNlRyUqcHJvdGVjdGVkRyIsbiRRKGZWJA== NiUiI09JJmZhbHNlRyUqcHJvdGVjdGVkRyIsTm5aPihv NiUiI1BJJmZhbHNlRyUqcHJvdGVjdGVkRyItck0mKlF1OA== NiUiI1FJJmZhbHNlRyUqcHJvdGVjdGVkRyItVnAheihbRg== NiUiI1JJJmZhbHNlRyUqcHJvdGVjdGVkRyItKClRImV2XCY= NiUiI1NJJmZhbHNlRyUqcHJvdGVjdGVkRyIudnhpNiYqNCI= NiUiI1RJJmZhbHNlRyUqcHJvdGVjdGVkRyIuXmJEQiEqPiM= NiUiI1VJJmZhbHNlRyUqcHJvdGVjdGVkRyIuLjZeWSEpUiU= NiUiI1ZJJmZhbHNlRyUqcHJvdGVjdGVkRyIuMkEtJDQneik= NiUiI1dJJmZhbHNlRyUqcHJvdGVjdGVkRyIvOlcvJz0jZjw= NiUiI1hJJmZhbHNlRyUqcHJvdGVjdGVkRyIvSikpM3NWPU4= NiUiI1lJJmZhbHNlRyUqcHJvdGVjdGVkRyIvanc8VyhvLig= NiUiI1pJJmZhbHNlRyUqcHJvdGVjdGVkRyIwRmBOKVtQMjk= NiUiI1tJJmZhbHNlRyUqcHJvdGVjdGVkRyIwYjFyd1xaIkc= NiUiI1xJJmZhbHNlRyUqcHJvdGVjdGVkRyIwNjhVYCpcSGM= NiUiI11JJmZhbHNlRyUqcHJvdGVjdGVkRyIxQkUlbyEqKiplNyI= NiUiI15JJmZhbHNlRyUqcHJvdGVjdGVkRyIxWl9vOCkqel5B NiUiI19JJmZhbHNlRyUqcHJvdGVjdGVkRyIxJlxxdGkqZi5Y NiUiI2BJJmZhbHNlRyUqcHJvdGVjdGVkRyIxIio0dWEjKj4yISo= NiUiI2FJJmZhbHNlRyUqcHJvdGVjdGVkRyIyJCk+WzQmKVI5IT0= NiUiI2JJJmZhbHNlRyUqcHJvdGVjdGVkRyIyblInKj1xekdnJA== NiUiI2NJJmZhbHNlRyUqcHJvdGVjdGVkRyIyTnojei4lZmQ/KA== NiUiI2RJJmZhbHNlRyUqcHJvdGVjdGVkRyIzcmUmZTIpPTpUOQ== NiUiI2VJJmZhbHNlRyUqcHJvdGVjdGVkRyIzVjxyXmhQSSMpRw== NiUiI2ZJJmZhbHNlRyUqcHJvdGVjdGVkRyIzKFtCTUlfMll3Jg== NiUiI2dJJmZhbHNlRyUqcHJvdGVjdGVkRyI0dnAlb2cvOiNIOiI= NiUiI2hJJXRydWVHJSpwcm90ZWN0ZWRHIjReUnA4IzRJJWVJIw== NiUiI2lJJmZhbHNlRyUqcHJvdGVjdGVkRyI0LnpRRiU9Z282WQ== NiUiI2pJJmZhbHNlRyUqcHJvdGVjdGVkRyI0MmV4YW8uc0xBKg== NiUiI2tJJmZhbHNlRyUqcHJvdGVjdGVkRyI1OjtiNFAyV25XPQ== NiUiI2xJJmZhbHNlRyUqcHJvdGVjdGVkRyI1Sks1PnU5KVskKm8k NiUiI21JJmZhbHNlRyUqcHJvdGVjdGVkRyI1ams/UVtId3B5dA== NiUiI25JJmZhbHNlRyUqcHJvdGVjdGVkRyI2RkhUdycqZV9SZFoi NiUiI29JJmZhbHNlRyUqcHJvdGVjdGVkRyI2YmUjR056XiF6OSZI NiUiI3BJJmZhbHNlRyUqcHJvdGVjdGVkRyI2NjxsMChlLiJlSCFm NiUiI3FJJmZhbHNlRyUqcHJvdGVjdGVkRyI3Qk1JNnVyPztmIT0i NiUiI3JJJmZhbHNlRyUqcHJvdGVjdGVkRyI3Wm9nQVtWVEs9aEI= NiUiI3NJJmZhbHNlRyUqcHJvdGVjdGVkRyI3JnA4X2twR1ttQnMl NiUiI3RJJmZhbHNlRyUqcHJvdGVjdGVkRyI3IlJGL0hSZCdIdFclKg== NiUiI3VJJmZhbHNlRyUqcHJvdGVjdGVkRyI4JHlhM2V5OSRmWSopKT0= NiUiI3ZJJmZhbHNlRyUqcHJvdGVjdGVkRyI4biY0PDtkSCc9JCp5eCQ= NiUiI3dJJmZhbHNlRyUqcHJvdGVjdGVkRyI4TiI+TUs5ZnNqeWJ2 NiUiI3hJJmZhbHNlRyUqcHJvdGVjdGVkRyI5ciNRb2tHPVhGZDZeIg== NiUiI3lJJmZhbHNlRyUqcHJvdGVjdGVkRyI5VmxuJEhkTyFcWEpBSQ== NiUiI3pJJmZhbHNlRyUqcHJvdGVjdGVkRyI5KDNgdGU5dCEpNEhZLyc= NiUiIyEpSSZmYWxzZUclKnByb3RlY3RlZEciOnZocXUiSFloPmUjKjM3 NiUiIyIpSSZmYWxzZUclKnByb3RlY3RlZEciOl5CVFwkZSNII1I7JnlUIw== NiUiIyMpSSZmYWxzZUclKnByb3RlY3RlZEciOi5aIykpcDsmZSV5S3FOWw== NiUiIyQpSSZmYWxzZUclKnByb3RlY3RlZEciOjIlXHdSTHEicGIxOW4q NiUiIyUpSSZmYWxzZUclKnByb3RlY3RlZEciOzopKUgmem1TJFE2OEdNPg== NiUiIyYpSSZmYWxzZUclKnByb3RlY3RlZEciO0p3ZiFmTCJvd0FFY29R NiUiIycpSSZmYWxzZUclKnByb3RlY3RlZEciO2pfPiI9bmlMYkNEcnQo NiUiIygpSSZmYWxzZUclKnByb3RlY3RlZEciPEYwUmlWYHMxIlxdVVo6 NiUiIykpSSZmYWxzZUclKnByb3RlY3RlZEciPGI1eUMob11NQCk0XVs0JA== NiUiIyopSSV0cnVlRyUqcHJvdGVjdGVkRyI8NkBjXHU4IXBVJz4rKCo9Jw== NiUiIyEqSSZmYWxzZUclKnByb3RlY3RlZEciPUJVNyoqW0YhUSZHUislekIi NiUiIyIqSSZmYWxzZUclKnByb3RlY3RlZEciPVolWyMpelwwd3EmeSspZVoj NiUiIyMqSSZmYWxzZUclKnByb3RlY3RlZEciPSYqb1wnZio0QDo5ZCx3Xlw= NiUiIyQqSSZmYWxzZUclKnByb3RlY3RlZEciPSJ6JCpIPio+VUlHOS5fLioq NiUiIyUqSSZmYWxzZUclKnByb3RlY3RlZEciPiRlKClmUSlSJTNtJkcxLzIpPg== NiUiIyYqSSZmYWxzZUclKnByb3RlY3RlZEciPm5eKD54J3pvQDhkNzM5J1I= NiUiIycqSSZmYWxzZUclKnByb3RlY3RlZEciPk4uJlJhJGZQVkU5RDtHI3o= NiUiIygqSSZmYWxzZUclKnByb3RlY3RlZEciP3IxIXozKD12J0cmR11LYyVlIg== NiUiIykqSSZmYWxzZUclKnByb3RlY3RlZEciP1Y4IWU8dS5OZHEwXUUicEo= NiUiIyoqSSZmYWxzZUclKnByb3RlY3RlZEciPyhvLTtOWzJxOVQ2K2AjUWo= NiUiJCsiSSZmYWxzZUclKnByb3RlY3RlZEciQHZgPy5uXCwlSCNHLWddd0Ui for n from 1 to 100 do if isprime(n) then print(n, isprime(2^n-1),2^n-1); fi; end do; NiUiIiNJJXRydWVHJSpwcm90ZWN0ZWRHIiIk NiUiIiRJJXRydWVHJSpwcm90ZWN0ZWRHIiIo NiUiIiZJJXRydWVHJSpwcm90ZWN0ZWRHIiNK NiUiIihJJXRydWVHJSpwcm90ZWN0ZWRHIiRGIg== NiUiIzZJJmZhbHNlRyUqcHJvdGVjdGVkRyIlWj8= NiUiIzhJJXRydWVHJSpwcm90ZWN0ZWRHIiUiPik= NiUiIzxJJXRydWVHJSpwcm90ZWN0ZWRHIidyNTg= NiUiIz5JJXRydWVHJSpwcm90ZWN0ZWRHIicoR0Mm NiUiI0JJJmZhbHNlRyUqcHJvdGVjdGVkRyIoMicpUSk= NiUiI0hJJmZhbHNlRyUqcHJvdGVjdGVkRyIqNjQob2A= NiUiI0pJJXRydWVHJSpwcm90ZWN0ZWRHIitaT1taQA== NiUiI1BJJmZhbHNlRyUqcHJvdGVjdGVkRyItck0mKlF1OA== NiUiI1RJJmZhbHNlRyUqcHJvdGVjdGVkRyIuXmJEQiEqPiM= NiUiI1ZJJmZhbHNlRyUqcHJvdGVjdGVkRyIuMkEtJDQneik= NiUiI1pJJmZhbHNlRyUqcHJvdGVjdGVkRyIwRmBOKVtQMjk= NiUiI2BJJmZhbHNlRyUqcHJvdGVjdGVkRyIxIio0dWEjKj4yISo= NiUiI2ZJJmZhbHNlRyUqcHJvdGVjdGVkRyIzKFtCTUlfMll3Jg== NiUiI2hJJXRydWVHJSpwcm90ZWN0ZWRHIjReUnA4IzRJJWVJIw== NiUiI25JJmZhbHNlRyUqcHJvdGVjdGVkRyI2RkhUdycqZV9SZFoi NiUiI3JJJmZhbHNlRyUqcHJvdGVjdGVkRyI3Wm9nQVtWVEs9aEI= NiUiI3RJJmZhbHNlRyUqcHJvdGVjdGVkRyI3IlJGL0hSZCdIdFclKg== NiUiI3pJJmZhbHNlRyUqcHJvdGVjdGVkRyI5KDNgdGU5dCEpNEhZLyc= NiUiIyQpSSZmYWxzZUclKnByb3RlY3RlZEciOjIlXHdSTHEicGIxOW4q NiUiIyopSSV0cnVlRyUqcHJvdGVjdGVkRyI8NkBjXHU4IXBVJz4rKCo9Jw== NiUiIygqSSZmYWxzZUclKnByb3RlY3RlZEciP3IxIXozKD12J0cmR11LYyVlIg== The largest Mersenne primes How many Mersenne primes..? A number is perfect if it is equal to the sum of its divisors other than itself. For example, 6 is perfect. 1. Make a procedure to find some perfect numbers. 2. Prove that an even number is perfect if and only if n=2^(q-1)(2^q-1), where 2^q-1 is prime. 3. Are there any odd perfect numbers smaller than 1000? with(numtheory); N1NJJkdJZ2NkRzYiSSliaWdvbWVnYUdGJEkmY2ZyYWNHRiRJKWNmcmFjcG9sR0YkSStjeWNsb3RvbWljR0YkSSlkaXZpc29yc0dGJEkpZmFjdG9yRVFHRiRJKmZhY3RvcnNldEdGJEknZmVybWF0R0YkSSlpbWFndW5pdEdGJEkmaW5kZXhHRiRJL2ludGVncmFsX2Jhc2lzR0YkSSlpbnZjZnJhY0dGJEknaW52cGhpR0YkSS1pc2N5Y2xvdG9taWNHRiRJKmlzc3FyZnJlZUdGJEksaXRocmF0aW9uYWxHRiRJJ2phY29iaUdGJEkqa3JvbmVja2VyR0YkSSdsYW1iZGFHRiRJKWxlZ2VuZHJlR0YkSSltY29tYmluZUdGJEkpbWVyc2VubmVHRiRJKG1pZ2NkZXhHRiRJKm1pbmtvd3NraUdGJEkobWlwb2x5c0dGJEklbWxvZ0dGJEknbW9iaXVzR0YkSSZtcm9vdEdGJEkmbXNxcnRHRiRJKW5lYXJlc3RwR0YkSSpudGhjb252ZXJHRiRJKW50aGRlbm9tR0YkSSludGhudW1lckdGJEknbnRocG93R0YkSSZvcmRlckclKnByb3RlY3RlZEdJKXBkZXhwYW5kR0YkSSRwaGlHRiRJI3BpR0YkSSpwcHJpbXJvb3RHRiRJKXByaW1yb290R0YkSShxdWFkcmVzR0YkSStyb290c3VuaXR5R0YkSSpzYWZlcHJpbWVHRiRJJnNpZ21hR0YkSSpzcTJmYWN0b3JHRiRJKHN1bTJzcXJHRiRJJHRhdUdGJEkldGh1ZUdGJA== divisors(24); PCoiIiIiIiMiIiQiIiUiIiciIikiIzciI0M= ifactor(24); KiYpLUkhRzYiNiMiIiMiIiQiIiItRiU2I0YpRio= perfect:=proc(n) local div,sumDivisors: div:=divisors(n); sumDivisors:=sum(div[j],j=1..nops(div)-1); evalb(sumDivisors=n); end proc: perfect(25); SSZmYWxzZUclKnByb3RlY3RlZEc= for n from 2 to 10000 do if perfect(n) then print(n); fi; od; IiIn IiNH IiQnXA== IiVHIik= How many primes...? Gauss: pi(n) ~ n / (1/2+1/3+.... +1/n) Prime Number Theorem (de la Vallee Poussin , Haddamard ): pi(n) ~ x/ln(nz) (Perhaps conjectured by Gauss when he was 14!) An even better approximation is x/(ln(n)-1) gauss:=n-> n/sum(1/j,j=2..n); Zio2I0kibkc2IkYlNiRJKW9wZXJhdG9yR0YlSSZhcnJvd0dGJUYlKiZGJCIiIi1JJHN1bUc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkdGJTYkKiRJImpHRiUhIiIvRjI7IiIjRiRGM0YlRiVGJQ== for i from 2 to 10 do print(i,evalf(gauss(i))); od; NiQiIiMkIiIlIiIh NiQiIiQkIisrKysrTyEiKg== NiQiIiUkIisjcDJCcCQhIio= NiQiIiYkIisnKlE1JypRISIq NiQiIickIitNNSR6OCUhIio= NiQiIigkIitNKT1ZUiUhIio= NiQiIikkIitkWSdwbCUhIio= NiQiIiokIis8ciEzI1whIio= NiQiIzUkIislXD1UPSYhIio= Exercise: Write a procedure to "check" the results about the number of primes above. (First write a program that counts the number of primes smaller than n)./ PI:=proc(n) local counter,i; counter:=0; for i from 2 to n do if isprime(i) then counter:=counter+1; fi; od; counter; end: PI(3); IiIj PI(10); IiIl Consequences of the Prime Number Theorem 1. Number of primes 2. The n-th prime 3. The chance of a random integer being a prime. Density Theorem (Euler) The sum of the reciprocal value of prime numbers is infinite Exercise Chebyshev said it we say it again there is always a prime between N and 2N. (Poem from Prime Numbers, a computational perspective, by Crandal and Pomerance) Exercise: Find examples of the previous theorem. Exercise: For each integer N=2,3,4,5... does there always exist a prime between N^2 and (N+1)^2? Check this statement for N=2, 3, 4....100. Twin primes Exercise: Find all twin primes smaller than 1000. The largest twin primes. The Goldbach conjecture For each even number n betweeen 1000 and 1100 find a pair of primes p and q such that n=p+q. HOw many pairs you can find for each number? Fermat numbers with(numtheory);