0
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Not respectively, but in some order. $\endgroup$ – lhf Jun 21 '18 at 18:01
  • $\begingroup$ 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. $\endgroup$ – fleablood Jun 21 '18 at 18:12
  • 2
    $\begingroup$ I removed the theorem-provers tag, which is for automatic proof checkers. Please make use of the tag summaries when choosing tags. $\endgroup$ – joriki Aug 9 '18 at 6:03
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – E. Shcherbo Jun 21 '18 at 18:03
  • 1
    $\begingroup$ @E.Shcherbo Yes, you are right. Check the example I mentioned in the answer. $\endgroup$ – Math Lover Jun 21 '18 at 18:04
  • $\begingroup$ I got you. Thank you very much for your help :-) $\endgroup$ – E. Shcherbo Jun 21 '18 at 18:06
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

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