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

  • $\begingroup$ m is a prime number $\endgroup$ – TheMathNoob Jul 10 '16 at 4:26
  • 1
    $\begingroup$ 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. $\endgroup$ – user236182 Jul 10 '16 at 4:27
  • $\begingroup$ Sorry, but your Question was unclear. Apparently you are asking why a proof of Euler's theorem works? $\endgroup$ – hardmath Jul 10 '16 at 4:27
  • $\begingroup$ Or maybe you're asking why $ac_1,\ldots,ac_{\phi(m)}$ is also a reduced residue system mod $m$? $\endgroup$ – user236182 Jul 10 '16 at 4:28
  • $\begingroup$ I am just typing what the book says, but my question is why the latter works. Why can you say such statement? $\endgroup$ – 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.

  • $\begingroup$ Explain the downvote. $\endgroup$ – 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)$$


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.