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