Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If $a^{N-1} \neq 1\pmod{N}$ for some $a$ relatively prime to $N$, then must the equality fail for at least half the choices of $a<N$

Could someone provide proof for this statement?

share|cite|improve this question
Do you mean $\neq$ instead of $=/=$? Then you should use \neq. And you can write $s \mod 3$ instead of $s$ $mod$ $3$ using \mod. – Beni Bogosel Apr 23 '12 at 15:14
Try to show that the a's that do it form a subgroup of the group of coprime residue classes mod N. – franz lemmermeyer Apr 23 '12 at 15:18
@Bogosel: Better to use \bmod for $s\bmod 3$ (note the difference in spacing); or \pmod for $s\pmod{3}$. – Arturo Magidin Apr 23 '12 at 15:31
No, it sometimes need not happen for any a relatively prime to $N$, with $N$ not a prime. That's the problem of Carmichael numbers. – KCd Apr 23 '12 at 15:32
Corrected the statement – user26649 Apr 23 '12 at 15:35
up vote 4 down vote accepted

The proof is in the Wikipedia article on the Fermat primality test.

[Edit in response to the comment:]

The proof in more detail: If $N$ is composite, a number $a$ is called a Fermat witness for $N$ if $a^{N-1} \not\equiv1\pmod N$, and a Fermat liar if $a^{N-1}\equiv1\pmod N$. Given $N$, let $a$ be a Fermat witness coprime to $N$, and $b$ a Fermat liar (and thus also coprime to $N$). Then

$$(ab)^{N-1}\equiv a^{N-1}b^{N-1}\equiv a^{N-1}\cdot1\equiv a^{N-1}\not\equiv1\;,$$

so $ab$ is a Fermat witness. Since the residue classes $\bmod N$ coprime to $N$ form a multiplicative group (denoted by $(\mathbb Z/N\mathbb Z)^*$ in the Wikipedia article), this Fermat witness $ab$ is also coprime to $N$ and is different for every Fermat liar $b$. Thus, a single Fermat witness $a$ coprime to $N$ suffices to establish that for every Fermat liar there must be at least one Fermat witness coprime to $N$, and hence at least half of all residues $\bmod N$ coprime to $N$ (and thus also half of all residues $\bmod N$) must be Fermat witnesses.

share|cite|improve this answer
I didn't understand the proof. Could you please expand on it? – user26649 Apr 23 '12 at 15:28
@Farhad: OK, I spelled it out a bit. – joriki Apr 23 '12 at 16:08
Let $X:= \{ x | x^{N-1} \equiv 1 \mod N \}$ and $Y:= \{ y | y^{N-1} \not\equiv 1 \mod N \}$. Fix some $a \in Y \neq \emptyset$. Then $f: X \rightarrow Y$, $f(x)=ax$ is one to one. Thus, $Y$ has more elements than $X$, and thus more than half of the elements.... – N. S. Apr 23 '12 at 16:24
@N.S.: No, $f$ is only one-to-one if $a$ is coprime to $N$; otherwise this proof would work for Carmichael numbers. – joriki Apr 23 '12 at 16:27
good point, missed that. Anyhow that is part of the assumption :) – N. S. Apr 23 '12 at 16:32

Your Answer


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