# $\gcd(a, 63) = 1$ implies $a^7 \equiv a \mod 63$?

Let $a$ be an integer. Suppose that $\gcd(a,63) = 1$. Prove then that $$a^7 \equiv a \mod 63.$$

Attempt: Since $gcd(a,63) = 1$, by Fermat little theorem we have that $$a^{\phi(63)} \equiv 1 \mod 63.$$ Now I found a prime factorization of $63$. We have $63 = 3^2 \cdot 7$. Hence $$\phi(63) = (3-1)3 \cdot 6 = 36.$$ So I got $$a^{36} \equiv 1 \mod 63.$$ Now I'm not sure how to proceed.

• Hint: look $\mod 3^2$ and $\mod 7$ separately. – Wojowu May 19 '16 at 9:28

Note. $(a,63)=1 \implies (a,7)=1$. And by FLT you have $$a^{6} \equiv 1 \pmod{7} \implies a^{7}\equiv a \pmod{7}$$ And since $(a,9)=1 \implies a^{\phi(9)}=a^{6} \equiv 1 \pmod{9} \implies a^{7}\equiv a \pmod{9}$. Now use CRT.