Exercise 2.3.44* (Generalization of Euler's theorem: $a^m \equiv a^{m-\phi(m)} \pmod m$ for all $a$)

Proof. If $m=1$, any integer is congruent to any other modulo $m$, so there is noting to prove. We suppose now that $m>1$.

Let $m=p_1^{a_1}\cdots p_k^{a_k}$ be the decomposition of $m$ in prime factors, where $a_i>0$. We will prove $a^m\equiv a^{m-\varphi (m)}(\mathit{mod}{p}_i^{a_i})$ for all $i$.

• Suppose first that $p_i\mid a$. Then

  $$\begin{array}{llll}\hfill m-\varphi (m)& =p_1^{a_1}\cdots p_k^{a_k}-p_1^{a_1-1}\cdots p_k^{a_k-1}(p_1-1)(p_k-1),& \hfill & \end{array}$$

  that is

  $$\begin{array}{lll}\hfill m-\varphi (m)& =p_1^{a_1-1}\cdots p_k^{a_k-1}\left[p_1\cdots p_k-(p_1-1)\cdots (p_k-1)\right].& \hfill \text{(1)}\end{array}$$

  We know that $n<2^n$ for all $n\ge 0$ (by induction, or using $n=|A|<|𝒫(A)|=2^n$).

  Therefore, using (1), $0\le a_i-1<2^{a_i-1}\le p_1^{a_i-1}\le m-\varphi (m)$. This shows that, for all index $i$,

  $$a_i\le m-\varphi (m).$$

  Therefore

  $$p_i^{a_i}\mid p_i^{m-\varphi (m)}\mid a^{m-\varphi (m)}.$$

  A fortiori $p_i^{a_i}\mid a^m$, so

  $$0\equiv a^m\equiv a^{m-\varphi (m)}(\mathit{mod}{p}_i^{a_i}).$$

• Suppose now that $p_i\nmid a$. Then $a\wedge p_i^{a_i}=1$.

  By Euler’s theorem,

  $$a^{\varphi (p_i^{a_i})}\equiv 1(\mathit{mod}{p}_i^{a_i}).$$

  Since $\varphi (p_i^{a_i})\mid \varphi (m)={\prod <!--\; FUNCTION\; APPLICATION\; -->}_{j=1}^k\varphi (p_j^{a_j})$, a fortiori

  $$a^{\varphi (m)}\equiv 1(\mathit{mod}{p}_i^{a_i}).$$

  Therefore, using $\varphi (m)\le m$,

  $$a^m=a^{m-\varphi (m)}{a}^{\varphi (m)}\equiv a^{m-\varphi (m)}(\mathit{mod}{p}_i^{a_i}).$$

In both cases

Since the integers $p_1^{a_1},\dots ,p_k^{a_k}$ are relatively prime by pairs, where $m=p_1^{a_1}\cdots p_k^{a_k}$,

for any integer $a$. □