Let $a,m\in\mathbb{N^*}$, with $m>1$, such that $(a,m)=1$. Show that, if $n_1\equiv n_2\pmod{\phi(m)}$, then $a^{n_1}\equiv a^{n_2}\pmod m$.

I thought about some things, but nothing conclusive, I thought of using the Euler's theorem, or check $m\mid \phi(m)$ in the case, but nothing helped me, could save me?


WLOG let's $n_1 \ge n_2$

From the condition we have: $n_1 = \phi(m)\cdot k + n_2$, where $k \in N$

Then we have: $a^{n_1} = a^{\phi(m)\cdot k + n_2} = a^{\phi(m)\cdot k} \cdot a^{n_2} \equiv a^{n_2} \pmod m$

All you need is to know Euler's Theorem.


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.