Proving that $x^a=x^{a\,\bmod\,{\phi(m)}} \pmod m$

Question

i want to prove $x^a \equiv x^{a\,\bmod\,8} \pmod{15}$.....(1) my logic:

here, since $\mathrm{gcd}(x,15)=1$, and $15$ has prime factors $3$ and $5$ (given) we can apply Euler's theorem.

we know that $a= rem + 8q$, where $8= \phi(15)$,

$x^a \equiv x^{rem}. (x^8)^q \pmod{15}$......(2)

applying Euler's theorem we get:

$x^a \equiv x^{rem} \pmod{15}$......(3)

Is this proof correct or should I end up in getting $x^a \equiv x^a \pmod {15}$...(4)

Answer 1

If $b\equiv a\pmod m, b$ will be equal to $a\iff 0\le a<m$

For example, $m-2\equiv m-2\pmod m, 13\equiv 13\pmod {15}$

but, $m+2\equiv 2\pmod m, 17\equiv 2\pmod {15}$

---

If $b\equiv c\pmod{\phi(m)} ,$i.e., if $b=c+d\phi(m)$

$y^b=y^{c+d\phi(m)}=y^c\cdot(y^{\phi(m)})^d\equiv y^c \pmod m$ for $(y,m)=1$

Here $\phi(15)=\phi(3)\phi(5)=2\cdot4=8$

Observe that this condition is no way necessary as proved below.

If $y^b\equiv y^d\pmod m$ where $b\ge c$

$y^{b-d}\equiv1\pmod m\iff ord_my\mid (b-d)$ does not need to divide $\phi(m)$ unless $ord_my=\phi(m)$ where $y$ is a primitive root of $m$.

Answer 2

Assuming you meant to add the hypothesis that $x$ is relatively prime to $m$, this is indeed immediate from Euler's theorem (stating $x^{\phi(m)}\equiv1\pmod m$ when $\gcd(x,m)=1$). One has $a=\phi(m)q+a\bmod\phi(m)$ for some integer $q$ and then $$ x^a=x^{\phi(m)q+a\bmod\phi(m)} =(x^{(\phi(m)})^qx^{a\,\bmod\,\phi(m)} \equiv1^qx^{a\,\bmod\,\phi(m)}=x^{a\,\bmod\,\phi(m)}\pmod m. $$