1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ $\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. $\endgroup$ – Kenny Lau Aug 30 '17 at 3:20
  • $\begingroup$ What are "ra" and "sa"? $\endgroup$ – Omnomnomnom Aug 30 '17 at 3:25
  • $\begingroup$ arbitrary coefficients of a $\endgroup$ – Nav Hari Aug 30 '17 at 3:28
  • 1
    $\begingroup$ arbitrary multiples of $a$. $\endgroup$ – Eric Towers Aug 30 '17 at 3:30
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How come it is not: ra (modp) ≠ sa (modp), which would mean the residues are never the same? Surely that is what needs proving? $\endgroup$ – Nav Hari Aug 30 '17 at 13:27
  • $\begingroup$ 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$. $\endgroup$ – G Tony Jacobs Aug 30 '17 at 13:29
  • $\begingroup$ 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. $\endgroup$ – G Tony Jacobs Aug 30 '17 at 13:32
  • $\begingroup$ What does that mean? $\endgroup$ – Nav Hari Aug 30 '17 at 13:33
  • $\begingroup$ 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. $\endgroup$ – G Tony Jacobs Aug 30 '17 at 13:36
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.