Thursday, June 24, 2010

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.

0 Comments:

Post a Comment

<< Home

Site Meter