# Proving $(\forall a\in\mathbb{Z^+})(m\in\mathbb{Z^+}\to a^m\equiv a^{m-\phi(m)}\pmod{m})$

Problem: $(\forall a\in\mathbb{Z^+})(m\in\mathbb{Z^+}\to a^m\equiv a^{m-\phi(m)}\pmod{m})$

My work: Start by letting $m=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}$. If $(a,p_i)=1$ for some integer $i$, then we have that $$a^{\phi(p_i^{a_i})}\equiv 1\pmod{p_i^{a_i}}$$ by Euler's theorem. Since $\phi(p_i^{a_i}) \mid \phi(m)$, we have that $p_i^{a_i}\mid (a^{\phi(m)}-1)$ if $(a,p_i)=1$.

Beyond this, I am stuck at the moment.

• This is a time test for 8:23 – Daniel W. Farlow Mar 14 '15 at 0:23

## 1 Answer

Pretty sure I've got it now, but more efficient/alternative solutions would be appreciated.

Proof. Start by letting $m=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}$. If $(a,p_i)=1$ for some integer $i$; then, we have that $$a^{\phi(p_i^{a_i})}\equiv 1\pmod{p_i^{a_i}}$$ by Euler's theorem. Since $\phi(p_i^{a_i}) \mid \phi(m)$, we have that $p_i^{a_i}\mid (a^{\phi(m)}-1)$ if $(a,p_i)=1$. Since we know that $p_i^{a_i-1}\mid \phi(m)$ for $i=1,2,\ldots,m$, it follows that $p_i^{a_i-1}\mid (m-\phi(m))$. Also, since $m-\phi(m)\geq 1$, it follows that $m-\phi(m)\geq p_i^{a_i-1}\geq a_i$ (because $q^{a-1}\geq a$ when $q,a\in\mathbb{Z^+}$ and $q\geq 2$). Thus, if $(a,p_i)>1$, so that $p_i\mid a$, we have $p_i^{a_i}\mid p_i^{m-\phi(m)}$, which implies that $p_i^{a_i}\mid a^{m-\phi(m)}$. Consequently, we conclude that for every integer $a$ we have $$p_i^{a_i}\mid a^{m-\phi(m)}(a^{\phi(m)}-1)=a^m-a^{m-\phi(m)}$$ for $i=1,2,\ldots,r$. It follows that $m\mid (a^m-a^{m-\phi(m)})$, which implies that $$a^m\equiv a^{m-\phi(m)}\pmod{m},$$ thus concluding the proof.