Question:
---------

Show that if $\gcd(a,3)=1$ then $a^7 \equiv a\pmod{63} $. Why is this assumption necessary?

---

Proof:
------

Since $\gcd(a,3)=1$ $\Leftrightarrow a\equiv 1\pmod 3$ $\Leftrightarrow a^7\equiv 1\pmod3\equiv a\pmod3$

Then using Fermat's Little Theorem:

If $a,p\in\mathbb N$ and $p$ is prime then $a^7\equiv a\pmod7$

$\Rightarrow 3 |a^7-a$ and $7 |a^7-a$

$\Leftrightarrow a^7-a=3k\_1$ and $a^7-a=7k\_2$

$\Rightarrow (a^7-a)^3=63(k\_1)^2k\_2$ $\Rightarrow (a^7-a)^3\pmod{63}\equiv 0$

Since $x^m\pmod n\equiv x\pmod n$

$\Rightarrow (a^7-a)^3\pmod{63}\equiv a^7-a\pmod{63}\equiv 0$

$\Leftrightarrow a^7\equiv a\pmod{63}$

The thing I am struggling with is that the question says that the only assumption necessary is that $\gcd(a,3)=1$. Surely there are two assumptions neccessary, since to use Fermat's Little Theorem (in this situation) we need $a\neq 0 \pmod7 \space\space\space(\gcd(a,7)=1)$. I am sure there is something obvious I'm missing -would be great if someone could check over what I have done and point out any mistakes :)

---