Fermat's Little Theorem and Prime Numbers

Date: 09/28/98 at 13:41:06
From: Dan Levitt
Subject: Fermat's Little Theorem

Dear Dr. Math,

Greetings from NYC. I hope you can help me.

Please explain how to use Fermat's Little Theorem to test whether a 
number is prime.

Thank you,
Dan

Date: 09/28/98 at 17:02:31
From: Doctor Rob
Subject: Re: Fermat's Little Theorem

You can't, but you can test to see if a number is composite! If you 
think that this is paradoxical, read on.

Fermat's Little Theorem says that if n is a prime number, and 
(a,n) = 1, then a^(n-1) = 1 (mod n).

Take the number n that you wish to test. Pick any a you like with 
1 < a < n, and compute d = (a,n). If d > 1, n is composite (you have 
just found a factor, namely d). If d = 1, continue by computing 
r = a^(n-1) (mod n), with 0 <= r < n. If n is prime, then by Fermat's 
Little Theorem, r = 1. Thus if r > 1, n cannot be prime, and must 
be composite.

Unfortunately, there are composite numbers n and bases a for which 
d = 1 and r = 1, such as n = 2047 = 23*89 and a = 2. This means that 
when r = 1, we cannot say whether or not n is prime, but when r > 1, 
n is definitely composite.

Of course we can repeat this test with different a's. If all of the 
a's we try give r = 1, we may feel that our inability to prove n 
composite gives some weight to the allegation that n is prime, but we 
still do not have a proof. In fact, there are numbers called 
Carmichael numbers, the smallest of which is n = 561 = 3*11*17, such 
that whenever d = 1, you will have r = 1, too. There are infinitely 
many of these, although they are not common, so unless you try all a's 
up to n^(1/3), you will not be sure by using this kind of test that 
your n is not a Carmichael number instead of a prime.

That is why you cannot use Fermat's Little Theorem to prove a number 
prime, but you may be able to use it to prove a number composite.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/   

Date: 09/28/98 at 19:21:57
From: Levitt, Dan U
Subject: Re: Fermat's Little Theorem

Thank you for responding so quickly. If I take:

   a = 2
   n = 7

What is d?

   2^6 = 64 

After this point I am stuck. How do I proceed further?

Please help. Thank You.
Dan 

Date: 09/29/98 at 09:08:33
From: Doctor Rob
Subject: Re: Fermat's Little Theorem

d is the GCD (Greatest Common Divisor) of 2 and 7, which is 1. You can
compute it by using the Euclidean Algorithm: divide the larger number 
by the smaller, with remainder. If the remainder is zero, stop. If 
not, replace the larger number by the remainder, and repeat. The last 
nonzero remainder is the GCD:

   7 = 3*2 + 1
   2 = 2*1 + 0

The last nonzero remainder is d = 1, the GCD of 64 and 9. Then
2^6 = 64 = 1 (mod 7), so r = 1. Thus you have failed to prove 7 
composite. Good thing, since 7 is prime!

The notation (a,n) = d means that the GCD of a and n is d. That's a
notation used in number theory (and probably nowhere else) which can 
be confusing. r is the remainder when you divide a^(n-1) by n.

Another example: n = 299, a = 3. d = (200,3) = 1, so we compute
r = 3^298 (mod 299):

   3^8 = (3^4)^2 = 81^2 = 6561 = 282 (mod 299)
   3^9 = 3*3^8 = 3*282 = 846 = 248 (mod 299)
   3^18 = (3^9)^2 = 248^2 = 209 (mod 299)
   3^36 = (3^18)^2 = 209^2 = 27 (mod 299)
   3^37 = 3*3^36 = 3*27 = 81 (mod 299)
   3^74 = (3^37)^2 = 81^2 = 282 (mod 299)
   3^148 = (3^74)^2 = 282^2 = 289 (mod 299)
   3^149 = 3*3^148 = 3*289 = 269 (mod 299)
   3^298 = (3^148)^2 = 269^2 = 3 (mod 299)

Thus r = 3 > 1, so 299 is composite. Notice that this says nothing 
about what the factors are. You can, however, notice that 3^33 = 1 
(mod 299) (because 3^36 = 27 = 3^3 (mod 299)) so that the order of 3 
(mod 299) is 33, so the order of 3 (mod p) divides 33 for every prime 
divisor p of 299. This can be used to reduce the search to a short 
one, and the factors turn out to be 13 and 23.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/