Show that if $\gcd(a,3)=1$ then $a^7 \equiv a\pmod{63}$. Why is this assumption necessary? 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 :)



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

Let's find examples that violate the assumption and see what happens.


*

*$a = 3$: $a^7 \pmod{63}$ is $45 = a + 42$.

*$a = 6$: $a^7 \pmod{63}$ is $27 = a + 21$.

*$a = 9$: $a^7 \pmod{63}$ is $9 = a$.

*$a = 12$: $a^7 \pmod{63}$ is $54 = a+42$.

*$a = 15$: $a^7 \pmod{63}$ is $36 = a+21$.

*$a = 18$: $a^7 \pmod{63}$ is $18 = a$.

*... and the pattern continues, cycling among $a+42$, $a+21$, and $a$.


This suggests that when $\gcd(a,3) = 3$, then $a^7 \cong a \pmod{21}$.  This embodies a fact we know about congruences:  $ka \cong kb \pmod{kc}$ if and only if $a \cong b \pmod{c}$.  So the assumption is necessary to prevent the modulus reducing to $21$, spoiling the relation.
