0
$\begingroup$

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

Could someone provide proof for this statement?

  • 0
    @Joriki: Ah yes, you're right.2012-04-23

1 Answers 1

4

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.

  • 0
    Thank You! That made$a$lot more sense!2012-04-23