Struggling with the proof of Fermat's little theorem

I am working through Dirichlet's proof of Fermat's little theorem.

I am at the stage where I am trying to prove that: $(a, 2a, 3a, ..., (p-1)a) \mod p$ is a rearrangement of $1,2,3..., p-1$.

In the proof it is written that this can be shown by considering $ra$ and $sa$ and showing that $ra$ and $sa$ must be distinct: $ra \not\equiv sa \mod p$ where r and s are arbitrary coefficients of $a$.

However I do not understand why this is valid. I it would have to be proven that: $ra \ne sa$ rather than $ra \not\equiv sa\mod p$

• $\Bbb Z_p$ is a field, so $U(p) = \Bbb Z_p \setminus 0$ is a multiplicative group, and we have $aG=G$ for $a \in G$. I'm just kidding. – Kenny Lau Aug 30 '17 at 3:20
• What are "ra" and "sa"? – Omnomnomnom Aug 30 '17 at 3:25
• arbitrary coefficients of a – Nav Hari Aug 30 '17 at 3:28
• arbitrary multiples of $a$. – Eric Towers Aug 30 '17 at 3:30

3 Answers

The claim is that the list of residues $$1 \cdot a , 2 \cdot a , \dots, (p-1) \cdot a \pmod{p}$$ is a permutation of the list of residues $$1 , 2 , \dots, (p-1) \pmod{p} \text{.}$$

At this point in the proof, we must know that $p \not \mid a$, since otherwise, the first list is a list of $p-1$ copies of $0 \pmod{p}$ which quite evidently is not a permutation of the second list.

If the "multiply by $a$" map is a permutation, then since the domain and range of the map have the same finite cardinality, the map is injective. By contraposition, if the map is not injective, it is not a permutation.

For purposes of contradiction, suppose the "multiply by $a$" map is not injective. Then there must be two distinct multiples of $a$ in the first list that are equal, call them $ra$ and $sa$, where $r \neq s$. We find $$r a \equiv s a \pmod{p} \text{.}$$ (If you know the integers modulo $p$ are a field, then cancel $a$ from both sides, see $r \equiv s$, observe both of these are in $[1,p-1]$, an interval containing at most one representative from each equivalence class modulo $p$, so they are equal. Otherwise, ...) This says $(r-s)a = ra - sa = k p$ for some $k \in \mathbb{Z}$. Since $p$ is prime, either $p \mid (r-s)$ or $p \mid a$. We have previously observed $p \not \mid a$. Since $r-s \in [1 - (p-1), (p-1)-1] = [2-p, p-2]$, we must have $|r-s| < p$, so if $p \mid (r-s)$, $r-s = 0$, a contradiction. Therefore, the "multiply by $a$" map is injective and the first list of residues above is a permutation of the second list.

If we had $ra\ne sa$, that would still leave the possibility that $ra-sa$ is a multiple of $p$, since $ra$ and $sa$ can have a difference greater than $p-1$. If that were true, then we would have $ra\equiv sa\pmod{p}$, which would mean the multiples of $a$ would not form a complete residue system. Do you see how that's a problem?

The confusion here seems to be over notation. When we write:

$$a\equiv b\pmod{p},$$

we are not saying that $a$ is what you get when you reduce $b$ modulo $p$. We're saying that, modulo $p$, the numbers $a$ and $b$ are the same. For example:

$$12\equiv 27\pmod 5$$

is a true statement. The $\pmod5$ at the end doesn't apply to the $27$; it applies to the $\equiv$ sign. What that statement really means is that $12-27$ is a multiple of $5$.

Thus, what you are meaning when you say "$ra\pmod{p}\ne sa\pmod{p}$" (which is not a generally accepted notation), is precisely what we mean when we write $ra\not\equiv sa\pmod{p}$.

• How come it is not: ra (modp) ≠ sa (modp), which would mean the residues are never the same? Surely that is what needs proving? – Nav Hari Aug 30 '17 at 13:27
• Numbers can be unequal and have the same residue. For example, $2\cdot 5 \ne 3\cdot 5$, but they have the same residue modulo $5$. – G Tony Jacobs Aug 30 '17 at 13:29
• Oh wait, I see what you're asking. The notation $ra \pmod{p}$ isn't really used in this context. We use $\pmod{p}$ to describe an equivalence, not a number. – G Tony Jacobs Aug 30 '17 at 13:32
• What does that mean? – Nav Hari Aug 30 '17 at 13:33
• The notation $a\equiv b\pmod{p}$ means that $a$ and $b$ are in the same residue class, because $p$ divides $a-b$. The notation $a\pmod{p}$ simply isn't used in number theory. – G Tony Jacobs Aug 30 '17 at 13:36

If $ra \not\equiv sa \pmod{p}$ then $ra \ne sa$. But incongruence mod $p$ is the key property because that's what equality means in $\mathbf{Z}_p$. If we take two elements $[x], [y] \in \mathbf{Z}_p$ then $[x] = [y]$ if and only if $x \equiv y \pmod{p}$. Here $[x]$ denotes the equivalence class of $x \bmod{p}$.

Maybe it will help to see an example. Take $p = 5$ and $a = [2]$. Then

$$\Big([1][2], [2][2], [3][2], [4][2] \Big) = \Big([2], [4], [1], [3] \Big).$$

So multiplication by $[2]$ corresponds to the permutation

$$\begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \end{pmatrix}.$$