# Can Fermat's little theorem be used to list primes?

I was reading about Fermat's little Theorem, which states that if p is prime, then for any integer a, $a^p-a$ would be a multiple of p. So, I started wondeing if this could be used to determine whether a number p was prime. In other words, I wanted to check whether the above statement only holds iff p is prime. I'm a programmer, not a mathematician, so I wrote a little program in Python.

for i in xrange(1, 101):
if ((3**i) - 3) % i == 0:
print i

This program iterates over all numbers from 1 to 100 inclusive, and plugs them into Fermat's theorem as p. For a, I chose 3. It printed the following (with multiple numbers put on the same line for brevity):

1 2 3 5 6 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 66 67 71 73 79 83 89 91 97

So, the output contains some come composite numbers, but these always seem to be multiples of 3. So I changed my program to exclude multiples of 3:

And it looks like that works, it only prints primes. I've tried this with a couple of values of a now, and I'm getting the same results for all of them.

So this leads me to two related questions:

• Can you test whether a number p is prime by checking whether $a^p - a$ is divisible by p, for a given a such that a and p are relatively prime? Are there other constraints on a?
• Will the above program ever print a composite number, when iterating over all natural numbers?
-
Have a look at en.wikipedia.org/wiki/Fermat_pseudoprime –  mfl Aug 10 at 15:13
$91$ is the only two-digit number that I consistently mistake for a prime. –  Ryan Aug 10 at 17:15

## 1 Answer

It does not hold , you can check out "carmichael numbers" you already have a counterexample in your list: 91 is not a prime, 91=13*7

for fast checking if a number is prime, use the rabin-miller-test. it works fine for very very large numbers. The Rabin-Miller-Test is an algorithm, that uses the fermat test in a way, but does a little more

-
since you seem to use python, i could give you my rabin-miller-test source code if you want –  supinf Aug 10 at 15:16
That'd be nice. –  bigblind Aug 10 at 16:22
pastebin.com/TPRM0a9d here you go. if you want to understand the algorithm, check en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test –  supinf Aug 10 at 17:12
Consider looking at primo's mymath.py: codepad.org/KtXsydxK which does the (non-strong) BPSW test -- no false positives below 2^64 with only the cost of ~3 M-R tests, and no known counterexamples of any size. Add more M-R tests with random bases if desired. –  DanaJ Aug 11 at 6:58