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 🙂
Best Answer
Fermat's Little Theorem states an integer $a$ and prime $p$ satisfy $p|a^p-a$, and if further $p\nmid a$ we can cancel this to $p|a^{p-1}-1$. So we always have $7|a^7-a$, but if $3\nmid a$ we can reason$$3|a^2-1\implies 3^2|(a^3+2a)(a^2-1)^2+3(a^3-a)=a^7-a.$$