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.

$a^{p-1} \equiv 1 \pmod p$

Why do Carmichael numbers prevent Fermat's Little Theorem from being a guaranteed test of primality? Fermat' Little theorem works for any $a$ such that $1≤a\lt p$, where $p$ is a prime number. Carmichael numbers only work for $a$'s coprime to $N$ (where $N$ is the modulus). Doesn't this mean that for some non-coprime $a$ the Carmichael number will fail the test? Therefore if every $a$ is tested, a Carmichael number wouldn't pass.

share|improve this question
1  
Google (weak) probable prime and pseudoprime and then let us know if you stll have a question. –  Bill Dubuque Apr 20 '12 at 23:15
1  
@Farhad Yusufali: Perfectly correct. But if we view the matter probabilistically, it may be that numbers between $1$ and $m-1$ that are not relatively prime to $m$ are rare, so a test that relied on bumping into such a number would be impractical. –  André Nicolas Apr 20 '12 at 23:20
    
If $a$ is composite and not Carmichael then the proportion of $a \bmod m$ such that $a^{m-1} \not\equiv 1 \bmod m$ is at least $50\%$, which is substantial. But if $a$ is composite and Carmichael then the proportion of $a \bmod m$ such that $a^{m-1} \not\equiv 1 \bmod m$ can be very small; in fact the only such $a$ are precisely those sharing a common factor greater than 1 with $m$, so finding them randomly amounts to finding a factor of $m$ randomly. For instance, if $m = 294409$ then the proportion of $a \bmod m$ such that $a^{m-1} \not\equiv 1 \bmod m$ is $4.9\%$. –  KCd Apr 21 '12 at 1:59
1  
If you think testing every $a$ is a good idea, then you can ignore all nonobvious math and just do trial division. –  KCd Apr 21 '12 at 2:00
    
@KCd - I am obviously not going to test every $a$ - that would be trivial. I was just curious why the test would fail IF you tested every $a$ –  user26649 Apr 21 '12 at 16:26
add comment

2 Answers

up vote 1 down vote accepted

If the goal of the Fermat Primality test is to guarantee that a number is prime, then testing against all possible $a$ is no better than simply trying to divide our number by all primes.

In particular, if it were easy to find a number that is not coprime to $n$, then it's easy to factor $n$ and so we wouldn't need to use any sort of Fermat primality.

But you are correct. Notably, if $p | n$, then doing the test$\mod p$ would yield $0$.

share|improve this answer
add comment

In case you looked at the Wikipedia article on Carmichael numbers, your question may have resulted from the sentence "Since Carmichael numbers exist, [the Fermat] primality test cannot be relied upon to prove the primality of a number". This is a bad formulation, since the Fermat primality test isn't meant to be used as proof of the primality of a number, but as a probabilistic test that is very likely to prove the compositeness of any composite number. It's that latter use that Carmichael numbers interfere with. As the article on the Fermat primality test shows, for numbers $n$ other than primes and Carmichael numbers, at least half of all numbers coprime to $n$ are Fermat witnesses, i.e. let the test prove compositeness. Thus the Fermat primality test serves its function well for non-Carmichael numbers, whereas for Carmichael numbers with relatively high prime factors, such as $8911=7\cdot19\cdot67$, the probability of proving compositeness with a randomly chosen number $\lt n$ is significantly reduced (roughly from $1$ in $2$ to in this case $1$ in $7$ per test).

share|improve this answer
add comment

Your Answer

 
discard

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