Primality Testing

Today I was teaching my 6th graders about prime numbers and why they are so important. I already gave my 5th graders an assignment on finding primes using Eratosthenese Sieve method. They are now comfortable about trivial divisibility tests like division by 2,3,4,6,8,9 and 11. Anyway I should mention the divisibility test of 11. All one has to do is take alternate digits of a number and add them and then see if the difference is divisible by 11. The other important test is Fermat's little theorem which is a corollary of Euler Fermat's theorem. In a nutshell it says that if gcd(a,b) =1 then a^phi(b) = 1 mod b and also b^phi(a) = 1 mod a. When b or a is prime then phi(b) = b-1 and the formula become a^(b-1) = 1 mod(b) which is Fermat's little theorem.

If one stares at the initial condition gcd(a,b) =1, its easy to see that gcd(2,oddnumber) = 1. Can we conclude 2^(oddnumber-1) = 1 mod (oddnumber) means that our oddnumber is a prime. If one checks this for first few hundred numbers one is tempted to conclude that. However it is not the case. The first anomaly one encounters is at number 341. I wrote a small Maple code to find out for first 20,000 number and here is the code with output

for i from 2 to 20000 do if isprime(i) = false then if mod(2^(i-1), i) = 1 then print(i, isprime(i)) end if end if end do;

341, false

561, false

645, false

1105, false

1387, false

1729, false

1905, false

2047, false

2465, false

2701, false

2821, false

3277, false

4033, false

4369, false

4371, false

4681, false

5461, false

6601, false

7957, false

8321, false

8481, false

8911, false

10261, false

10585, false

11305, false

12801, false

13741, false

13747, false

13981, false

14491, false

15709, false

15841, false

16705, false

18705, false

18721, false

19951, false

Its insightful to see that there are only 36 such numbers less than 20,000 and there is no number in 9,000 and 17,000. Now this was with respect to 2 and since all these numbers are composites but behave like primes (recall fermat's little theorem) these are called pseudoprimes. Also out of 2262 primes less than 20,000 there are only 36 composite which pass these test. Thus the probability that a number passing this probability test is a primes is 2262/(2262+36) =.984334. Which is very high and thus primes coming out of this test are called as industrial grade primes. Now as we did this for number 2 we could have equally chosen number 3, 5, 7 and so on. Again these give a different set of composite numbers. Here is Maple program and output for number 3

for i from 2 to 20000 do if isprime(i) = false then if mod(3^(i-1), i) = 1 then print(i, isprime(i)) end if end if end do;

91, false

121, false

286, false

671, false

703, false

949, false

1105, false

1541, false

1729, false

1891, false

2465, false

2665, false

2701, false

2821, false

3281, false

3367, false

3751, false

4961, false

5551, false

6601, false

7381, false

8401, false

8911, false

10585, false

11011, false

12403, false

14383, false

15203, false

15457, false

15841, false

16471, false

16531, false

18721, false

19345, false

What one notices is that there are again a different set of numbers and we now have 34 different numbers. One can do this for many more. Then there is this question. Are there numbers which are relative primes to more number and the answer is yes. These are called Carmichael number. Except for their prime factors these numbers are these are relative prime to all other numbers. 561, 1105 and 1729 are the first 3 Carmichael numbers. 561 = 3*11*17. Thus other than these three number it is relative prime to all other numbers.