# 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 '14 at 15:13
$91$ is the only two-digit number that I consistently mistake for a prime. – Ryan Aug 10 '14 at 17:15