3
$\begingroup$

$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.

  • 0
    @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$2012-04-21

2 Answers 2

2

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$.

5

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).