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<N$

Could someone provide proof for this statement?

  • 0
    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`.2012-04-23
  • 1
    Try to show that the a's that do it form a subgroup of the group of coprime residue classes mod N.2012-04-23
  • 0
    @Bogosel: Better to use `\bmod` for $s\bmod 3$ (note the difference in spacing); or `\pmod` for $s\pmod{3}$.2012-04-23
  • 0
    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.2012-04-23
  • 0
    Corrected the statement2012-04-23
  • 0
    @KCd: The statement was correct as originally stated; I rolled back the edit. A Carmichael number is a composite number $N$ for which there is no $a$ relatively prime to $N$ such that $a^{N-1}\not\equiv1\pmod N$, so the first part of the statement says precisely that $N$ is neither a prime nor a Carmichael number.2012-04-23
  • 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
    I didn't understand the proof. Could you please expand on it?2012-04-23
  • 0
    @Farhad: OK, I spelled it out a bit.2012-04-23
  • 0
    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....2012-04-23
  • 0
    @N.S.: No, $f$ is only one-to-one if $a$ is coprime to $N$; otherwise this proof would work for Carmichael numbers.2012-04-23
  • 0
    good point, missed that. Anyhow that is part of the assumption :)2012-04-23
  • 0
    Why does $ab$ being coprime to $N$ prove there has to be a Fermat Liar for every Fermat Witness?2012-04-23
  • 0
    @Farhad: There was a lot more to the argument than just $ab$ being coprime to $N$. Could you formulate your question more closely with respect to my answer, pointing out which part of the argument you don't understand? I find it hard to answer without knowing what part of my argument you're referring to.2012-04-23
  • 0
    I was lost at multiplicative group - I have absolutely no knowledge in group theory. From what I understood your flow of logic was: 1)$ab$ is a Fermat Witness 2)Mod $N$ integers coprime to $N$ form a multiplicative group (do not understand what a multiplicative group is due to lack of knowledge in group theory) 3)Therefore equal number of Fermat Witnesses and Liars (I am lost to how you came to this conclusion)2012-04-23
  • 0
    @Farhad: I see -- thanks for the detailed explanation. The relevant fact from group theory is that for a given $a$ you get different residues $ab$ if you multiply different residues $b$ by $a$. That's only true if $a$ is coprime to $N$. You can also show it without group theory: If two different residues $b_1$ and $b_2$ yield the same products, $ab_1\equiv ab_2\pmod N$, then $a(b_2-b_1)\equiv0\pmod N$, which is impossible if $a$ is coprime to $N$. If different $b$ lead to different $ab$ and for every liar $b$ this $ab$ is a witness, then there must be at least as many witnesses as liars.2012-04-23
  • 0
    Thank You! That made a lot more sense!2012-04-23