Generalisation of Euler's Theorem

Question

I have no idea how to start thinking about this. Any hints are welcome:

Prove that

$a^{m} \equiv a^{m-\phi{(m)}} (mod\ m)$ for any integer m

I only know how to do it for $\gcd(a,m)=1$.

Answer 1

First method : elementary number theory.

By the factorization theorem let $m=p^kq^l$ and $a$ an integer not divided by $p^k q^l$ ($p,q$ two distinct prime numbers and $k,l$ integers $\ge 1$). We can also generalize to $m=p_1^{b_1}...p_n^{b_n}$ but it will be the same method but longer.

The first thing is to prove that $\gcd(p,q)=1 \Rightarrow \gcd(p^k,q^l)=1$ ? All the powers of $p$ and $q$ are divided respectively by $p$ and $q$ which are difference, is that enough ? Probably (here). But here's a more formal proof with a weaker hypothesis ($p,q$ not necessarily prime numbers). Supposing $\gcd(p,q)=1$, so there exists $u,v\in \mathbb{Z}$ such that $up+vq=1$. Multiplying by itself it gives : $1=u^2p^2+2uvpq+v^2q^2=(u^2p+2uvq)p+v^2q^2=1\Rightarrow \gcd(p,q^2)=1$. Again, traducing the new hypothesis by Bachet-Bézout theorem and by multiplying by $(up+vq=1)$ it gives that $\gcd(p,q^3)=1$. We repeat this $l-2$ times and it gives $\gcd(p,q^l)=1$.

It implies that there exists $u,v\in\mathbb{Z}$ such that $up+vq^l=1$. Multiplying by itself it gives $\gcd(p^2,q^l)=1$. This time we repeat the operation $k-1$ times and it gives $\gcd(p^k,q^l)=1$.

We can start the second step :

First thing is to prove with an induction on $k\ge 1$ that $a^{p^{k-1}(p-1)}\equiv 1 \pmod {p^k} $.

Initialisation : for $k=1$ we found Fermat little theorem so it's true.

Heredity : for $k=k+1$ we want to prove that : $a^{p^{k}(p-1)}\equiv 1 \pmod {p^{k+1}} $.

$a^{p^{k}(p-1)}= a^{p^{k-1}p(p-1)}=(a^{p^{k-1}(p-1)})^p=(up^{k}+1)^p=\sum \limits_{l=0}^{p}\binom{p}{l}(up^k)^l=1+up^{k+1}+"..."$, where $"..."$ is divided by $p^{k+1}$. So $a^{p^{k}(p-1)}\equiv 1 \pmod {p^{k+1}} $.

We deduce the same thing for all $l\ge 1$.

Then we have : $K=a^{p^{k-1}(p-1)q^{l-1}(q-1)}= (a^{p^{k-1}(p-1)})^{q^{l-1}(q-1)}\equiv 1 \pmod{p^k}$ and also $K=a^{q^{l-1}(q-1)p^{k-1}(p-1)}=(a^{q^{l-1}(q-1)})^{p^{k-1}(p-1)}\equiv 1 \pmod{q^l}$

So now, we can say that there exists $\nu$ and $\mu$ $\in \mathbb{Z}$ such that : $K=\nu p^k +1=\mu q^l +1$

Then $\nu p^k=\mu q^l$. With the fact that $\gcd(p^k,q^l)=1$ we have by Gauss lemma $p^l$ which divides $\mu$. So there exists $\epsilon \in \mathbb{Z}$ such that $\mu=\epsilon p^k$ and finally $K=\epsilon p^kq^l+1$. Then $a^{p^{k-1}(p-1)q^{l-1}(q-1)}\equiv 1\ \pmod{p^kq^l=m}$.

The last step consists in proving that $\phi(m)=\phi(p^kq^l)=p^{k-1}(p-1)q^{l-1}(q-1)$. To do this you consider for instance the group of units of $(\mathbb{Z}/p^k\mathbb{Z})^{\times}$ i.e the number of inverse elements in this groups (i.e the set of $x$ such that $\gcd(x,p^k)=1$). We list the elements of the group $(\mathbb{Z}/p^k\mathbb{Z})=\{0,1,...,p,...,2p,...,pp=p^2,...,p^{k}-1\}$. Now, between $0$ and $p$ we have $(p-1)$ coprime numbers with $p$ and we deduce that for each list of length $p$ we have $(p-1)$ coprime numbers with $p$ and we have $p^{k-1}$ lists. So the formula is right. It is the same for $q^l$.

Finally $a^{\phi(m)}\equiv 1 \pmod{m}$.

Second method : group theory.

We still consider $m=p^kq^l$ (by factorization theorem). Then by the form of the CRT with the ring isomorphism we have an isomorphism between $(\mathbb{Z}/m\mathbb{Z})$ and $(\mathbb{Z}/p^k\mathbb{Z})\times(\mathbb{Z}/q^l\mathbb{Z})$. Which means that for the group of units : $\vert(\mathbb{Z}/p^k\mathbb{Z})^{\times}\vert\times\vert(\mathbb{Z}/q^l\mathbb{Z})^{\times}\vert =\vert (\mathbb{Z}/m\mathbb{Z})^{\times}\vert=\phi(m)=p^{k-1}(p-1)q^{l-1}(q-1)$ (as previously).

Let $a\in (\mathbb{Z}/m\mathbb{Z})^{\times}$ a generator (the group is cyclic in our case), the order of $a$ divides $\phi(m)$. Let $y$ the order of $a$ so there exists $z\in \mathbb{Z}$ such that $yz=\phi(m)$. We have $a^y\equiv 1 \pmod m\Rightarrow (a^y)^z=a^{\phi(m)}\equiv 1 \pmod m$. It works because $\gcd(p^k,q^l)=1$ !