# Why is $R_m(a^x)=R_m(a^{R_{\phi(m)}(x)})$?

Why does the following identity hold $$R_m(a^x)=R_m(a^{R_{\phi(m)}(x)})$$ where $R_m(a)$ is the remainder of $a$ divided by $m$, also denoted $a \mod m$, and $\phi(m)$ is Euler's totient function.

It is useful for calculating remainders of large numbers very quickly by hand, e.g. $R_{990}(5^{722})$.

-

It only holds if $a$ is relatively prime to $m$, i.e. if $\gcd(a,m)=1$.

To see a counterexample when this is not the case note that, if we choose $a=2$, $m=16$, and $x=9$, we have $R_m(a^x)=R_{16}(2^9)=0$, but $\phi(m)=\phi(16)=8$, so that $$R_m(a^{R_{\phi(m)}(x)})=R_{16}(2^{R_{8}(9)})=R_{16}(2^1)=2.$$ However, when $a$ is relatively prime to $m$, then Euler's theorem states that $a^{\phi(m)}\equiv 1\bmod m$, and therefore $a^{k\phi(m)}\equiv 1^k\equiv 1\bmod m$ for any $k\geq 0$. By the division algorithm, for any integer $x$ there is a $k$ such that $$x=k\phi(m)+R_{\phi(m)}(x),$$ and therefore $$a^x=a^{k\phi(m)+R_{\phi(m)}(x)}=a^{k\phi(m)}\cdot a^{R_{\phi(m)}(x)}\underset{\text{mod }m}{\equiv}1\cdot a^{R_{\phi(m)}(x)}=a^{R_{\phi(m)}(x)}.$$ Because these two numbers are equivalent modulo $m$, their respective remainders after dividing by $m$ are equal, so that $$R_m(a^x)=R_m(a^{R_{\phi(m)}(x)}).$$

-