1
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.