Struggling with the proof of Fermat's little theorem

Question

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$

Answer 1

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}$.

Answer 2

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}. $$

Answer 3

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.