Associated Topics || Dr. Math Home || Search Dr. Math

### 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

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

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?

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/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search