Fermat's Theorem Proof

Question

I'm reading Fermat's Theorem (that $a^{p-1} \equiv 1 \pmod{p}$) proof (What is mathematics book) and they consider the multiples of a $m_1 = a, m_2 = 2a, m_3 = 3a, ..., m_{p-1} = (p-1)a$. They explain why no two of these numbers can be congruent modulo p. Also, I understand why these numbers aren't congruent to $0$ modulo p. Then they say that the numbers $m_1, m_2, ..., m_{p-1}$ must be respectively congruent to the numbers 1, 2, 3, ..., p-1.

I can't understand how they came to the last conclusion which is in bold. I will be grateful for any help you can provide.

Answer 1

Note that two numbers are not congruent to each other modulo $p$, and none of them is congruent to $0$. Furthermore, the remainders of $m_1, m_2, \cdots , m_{p-1}$ belong to the set $\{1,2,\cdots, p-1\}$. Since they are not equal to each other, it must be true that $$m_1 \times m_2 \times \cdots \times m_{p-1} \equiv 1\times 2 \times \cdots \times (p-1) \pmod{p}.$$

As an example, consider $p=5$ and $a=2$. Consequently, $$m_1 \equiv 2, m_2\equiv 4, m_3 \equiv 1, m_4\equiv3 \pmod{5},$$ and $$m_1 \times m_2 \times m_3 \times m_{4} \equiv 1\times 2 \times 3 \times 4 \pmod{5}.$$

Answer 2

$m_i$ is conguent modulo $p$ to a unique number $j_i\in\{0,1,2,\ldots,p-1\}$, and $$ i\ne i'\quad\Longrightarrow\quad j_i\ne j_{i'} $$ Thus, by virtue of the Pigeonhole Principle $$ \{j_1,\ldots,j_{p-1}\}=\{1,\ldots,p-1\}. $$ Note also that $$ m\equiv j \mod p\qquad \text{and}\qquad m'\equiv j' \mod p\quad\Longrightarrow\quad mm'\equiv jj' \mod p $$ Hence $$ m_1\cdots m_{p-1}\equiv j_1\cdots j_{p-1}\equiv (p-1)!\mod p $$

Answer 3

Note that:

$$\prod_{i=1}^{p-1}m_i = a^{p-1}\prod_{i=1}^{p-1}i$$ $$a^{p-1}\prod_{i=1}^{p-1}i \equiv 1\cdot \prod_{i=1}^{p-1}i \pmod p$$

Answer 4

You know there are p-1 numbers m. Either they are all different, or some of them are the same. If they are all different, then p-1 different numbers m can only be the numbers 1,2,...p-1. Ask yourself if they can be the same: let m(i) be congruent to m(j), for example. Then m(i) - m(j) would be congruent to 0. Since the two numbers are multiples of a, that would further mean that two multipliers of a (i.e. two of the set 1,2,3....p-1) are congruent. But that is not true, so we know that no two numbers m can be the same. Hence, since there are p-1 of them, they must be congruent to the numbers 1,2,...p-1 although not in the same order.