$n$-ary Congruence Product Rule (in proof of Euler's totient theorem)

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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