Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
