Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?
share|improve this question
1  
Have a look at en.wikipedia.org/wiki/Fermat_pseudoprime –  mfl Aug 10 at 15:13
2  
$91$ is the only two-digit number that I consistently mistake for a prime. –  Ryan Aug 10 at 17:15

1 Answer 1

up vote 7 down vote accepted

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

share|improve this answer
    
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.