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.

  • $\begingroup$ 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." $\endgroup$ – André Nicolas Mar 21 '14 at 19:41
  • $\begingroup$ 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. $\endgroup$ – Lars M Mar 21 '14 at 20:40
  • $\begingroup$ @AndréNicolas I think I fixed my question and made it more clear. $\endgroup$ – 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.

  • $\begingroup$ Is the proof that there is a good number $g$ such that $gb$ is good for any bad number $b$? $\endgroup$ – Lars M Mar 23 '14 at 22:15
  • $\begingroup$ 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$. $\endgroup$ – André Nicolas Mar 23 '14 at 22:27
  • $\begingroup$ How does this show that there is are at most half bad numbers? $\endgroup$ – Lars M Mar 24 '14 at 15:04
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Mar 24 '14 at 15:11
  • $\begingroup$ 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$. $\endgroup$ – Lars M Mar 24 '14 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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