# Proving the Fermat's theorem

Fermat's theorem: if a is not divisible by p, then $a^{p-1} \equiv 1 \pmod p$

Since $\varphi(p)=p-1$, this is a special case of Euler's theorem. If $(a,m)=1$, then $a^{\varphi(m)}\equiv 1 \pmod m$.

Proof: Let $c_1,.....,c_{\varphi(m)}$ be a reduced residue system $(mod\text{ } m)$ and let a be prime to m. Then $ac_1,.....,ac_{\varphi(m)}$ is also a reduced residue system $(mod\text{ } m)$, and therefore

$$\prod_{i=1}^{\varphi(m)}ac_i \equiv \prod_{i=1}^{\varphi(m)}c_i \pmod m$$

Why is the latter true?

$\varphi(p)$ counts the number of elements ina reduced residue system mod p

• m is a prime number – TheMathNoob Jul 10 '16 at 4:26
• There is only one reduce residue system mod $m$. We have $\{c_1,\ldots,c_{\varphi(m)}\}=\{ac_1,\ldots,ac_{\phi(m)}\}$, i.e. $c_1,\ldots,c_{\varphi(m)}$ is a permutation of $ac_1,\ldots,ac_{\phi(m)}$. Therefore, we have $c_1\cdots c_{\varphi(m)}\equiv ac_1\cdots ac_{\phi(m)}\pmod{m}$. By the way, e.g. we also have $c_1+\cdots+c_{\varphi(m)}\equiv ac_1+\cdots+ac_{\varphi(m)}\pmod{m}$, which is irrelevant here. – user236182 Jul 10 '16 at 4:27
• Sorry, but your Question was unclear. Apparently you are asking why a proof of Euler's theorem works? – hardmath Jul 10 '16 at 4:27
• Or maybe you're asking why $ac_1,\ldots,ac_{\phi(m)}$ is also a reduced residue system mod $m$? – user236182 Jul 10 '16 at 4:28
• I am just typing what the book says, but my question is why the latter works. Why can you say such statement? – TheMathNoob Jul 10 '16 at 4:29

The sets $$\{c_1,c_2,\ldots,c_{\varphi(m)}\},\qquad \{ac_1,ac_2,\ldots,ac_{\varphi(m)}\}$$ are the same set $\!\!\pmod{m}$, hence the product of the elements has to be the same: $$a^{\varphi(m)}\prod_{k=1}^{\varphi(m)}c_k \equiv \prod_{k=1}^{\varphi(m)}c_k\pmod{m}$$ leads to $a^{\varphi(m)}\equiv 1\pmod{m}$ as wanted.

• Explain the downvote. – Jack D'Aurizio Sep 25 '16 at 21:32

An important part here is that for $(a,m)=1$ you have $$ab\equiv ac \pmod m \Rightarrow b\equiv c \pmod m.$$ This implies that $\{ac_1,\dots,ac_{\varphi(m)}\}$ belong to $\varphi(m)$ different residue classes.

Moreover, if $(a,m)=1$ and $(c,m)=1$, then also $(ac,m)=1$. (See here, here or here.) So all of them are reduced residue classes.

Therefore $\{ac_1,\dots,ac_{\varphi(m)}\}$ is a reduced residue system. (It has $\varphi(m)$ elements, each number is in a different residue class, each number is coprime to $m$.)

Recall the Congruence Product Rule  [below all congruences are  mod $\,m$]

$$\begin{eqnarray} &&\quad b_1\!\!&\equiv&\, c_1\\ &&\quad b_2\!\!&\equiv&\, c_2\\ \Rightarrow\ &&b_1 b_2\!\! &\equiv&\, c_1 c_2 \end{eqnarray}$$

By induction the rule extends to $\ b_i\equiv c_i\,\Rightarrow\, \prod b_i \equiv \prod c_i$

In other words, if two equal length lists $\,B,C\,$ of integers are element-wise congruent $\,b_i \equiv c_i\,$ then their products are also congruent. Yours is the special case where $\, B = \{b_i\},\ C = \{c_i\}\,$ are reduced residue systems.

Alternatively it is a special case of the multivariate extension of the Congruence Polynomial Rule, for the $\,k$-ary product polynomial $\,P(x_1,x_2,\ldots, x_k) = x_1 x_2\cdots x_k,\$ i.e.

$$b_i\equiv c_i\,\Rightarrow\, P(b_1,b_2,\ldots, b_k) \equiv P(c_1, c_2,\ldots, c_k)$$