# Failing Fermat Primality Test

Consider the following algorithm:

Suppose $n\geq 2$, and let FermatTest be an algorithm such that if $a^{n-1}\not\equiv 1\mod n$ then return composite. If FermatTest yields $a^{n-1}\equiv 1 \mod n$, then it returns possibly prime.

Let $n\geq 2$ be a composite integer that is not a Carmichael number. Let $a \in \{1,2,\cdots n-1\}$. Why is it that if I randomly select $a$, there is a 1/2 chance that the test will say that it is composite. I understand the group theoretic reason, but I was hoping for a number theoretic argument.

This question is inspired by this one here.

• I am a bit puzzled about the statement of the problem. There are $n$ such that $\frac{\varphi(n)}{n}$ is quite small. The test returns composite for any $a$ not relatively prime to $n$, which can be much more than "at most $1/2$ of the time." Anyway, I do not think you intend "at most." – André Nicolas Mar 21 '14 at 19:41
• I guess I'm wondering why the Fermat test will say that this is possibly prime 1/2 of the time whenever $n$ is a composite, non Carmichael number. – Lars M Mar 21 '14 at 20:40
• @AndréNicolas I think I fixed my question and made it more clear. – Lars M Mar 21 '14 at 20:53

Let $n$ be composite. Consider the $\varphi(n)$ numbers in the interval $1\le a\le n-1$ such that $a$ is relatively prime to $n$.

Call such a number good if $a^{n-1}\not\equiv 1\pmod{n}$. So $a$ is good if using $a$ in the Fermat test we find that $n$ cannot be prime. Let the set of good numbers be $G$.

Call $a$ bad if it is not good, meaning that if we apply the Fermat primality test, we get the answer "possibly prime." Let the set of bad numbers be $B$.

We want to show that if $n$ is not a Carmichael number, then at least half of the $\varphi(n)$ numbers $a$ in our interval are good.

Since $n$ is not a Carmichael number, there is a good number $g$. Note that $gb$ is good for any bad number $b$. For $$(gb)^{n-1}=g^{n-1}b^{n-1}\equiv g^{n-1}\not\equiv 1\pmod{n}.$$ The values of $gb$ as $b$ ranges over $B$ are distinct modulo $n$. Thus there are at least as many good numbers as there are bad. This completes the argument.

Remark: Let $n$ be composite but not Carmichael. The above result shows that even if $n$ is very large, repeated use of the Fermat Primality Test, with randomly chosen $a$, will, with probability close to $1$, quickly detect the compositeness.

• Is the proof that there is a good number $g$ such that $gb$ is good for any bad number $b$? – Lars M Mar 23 '14 at 22:15
• Not "there is a good number such that" although that happens to follow. It is "if $g$ is any good number, then $gb$ is good for all bad $b$. – André Nicolas Mar 23 '14 at 22:27
• How does this show that there is are at most half bad numbers? – Lars M Mar 24 '14 at 15:04
• The total number of numbers is $n$. Suppose that there are more than $n/2$ in $B$, and that there is at least one good $g$ ("not Carmichael"). We have shown that all the $gb$ are good, and they are distinct, so we have $\gt n/2$ good. Add. Altogether, the sum of the number of bad and the number of good would be greater than $n/2+n/2$, which is impossible, since there are only $n$ numbers altogether. – André Nicolas Mar 24 '14 at 15:11
• Let me make sure I understand. First we fix a composite non-Charmichael $n$. Then we consider the set $\phi(n)$. Out of all these relatively prime integers to $n$ we partition them into the Good and Bad set. To show are at most half bad numbers we fix a $g$ where $g$ is a good number and consider $(bg)^{n-1}\not\equiv 1 \mod n$. My last issue is why are they distinct as you range over $b$. – Lars M Mar 24 '14 at 15:33