# Fermat's Theorem Proof

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.

• Not respectively, but in some order. – lhf Jun 21 '18 at 18:01
• There are p-1 distinct equivalence classes represented by $1,... p-1$.. If $m_i$ are pairwise not congruent, then the each belong to a distinct class and each class is represented by one of them. So each $m_i \equiv n_i\mod p$ where $n_i$ are distinct member of $\{1,2,3...., p-1\}$. You added the word "respectively" (implying $n_i = i$). I strongly doubt that that was actually in the text, as it is not true. – fleablood Jun 21 '18 at 18:12
• I removed the theorem-provers tag, which is for automatic proof checkers. Please make use of the tag summaries when choosing tags. – joriki Aug 9 '18 at 6:03

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

• As I understand it doesn't mean that, for example $m_1 \equiv 1 \pmod{p}$ and $m_2 \equiv 2 \pmod{p}$, does it? It can have another order, for example $m_1 \equiv 2 \pmod{p}$. Is it correct or not? – E. Shcherbo Jun 21 '18 at 18:03
• @E.Shcherbo Yes, you are right. Check the example I mentioned in the answer. – Math Lover Jun 21 '18 at 18:04
• I got you. Thank you very much for your help :-) – E. Shcherbo Jun 21 '18 at 18:06

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

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

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.