Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
1  
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
show 2 more comments

1 Answer 1

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|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
show 5 more comments

Your Answer

 
discard

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