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 :)

 A: 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.$$
A: 
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.
A: The obstruction is simple: $ $ if $\,3\mid a\,$ then $\,3^n\mid \overbrace{\color{#c00}a(a^6-1)}^{f(a)}\!\iff 3^n\mid a,\, $ by $\,\gcd(a,a^6-1)=1.\,$ Thus when $\,3\mid a,\ 9\nmid a\,$ the same is true for $f(a),\,$ hence $\,9\nmid f(a)\,$ so $\, 63\nmid f(a)$.
Enlarging the factor of $\,\color{#c00}a\,$ to be $\,\color{#0a0}{a^2}\,$ fixes it, since then $\,3\mid a\,\Rightarrow\, 9\mid \color{#0a0}{a^2},\,$ hence
$$63\mid \color{#0a0}{a^2}(a^6-1)\ \ {\rm for\ all}\ \ a\in\Bbb Z,\ \ {\rm i.e}\,\ \ \bbox[5px,border:1px solid #c00]{a^8\equiv a^2\!\!\!\!\pmod{\!63}}$$
Remark $ $ This is a special case of the following  generalization of the Fermat & Euler Theorems. Note that the above "enlarging" makes true the hypothesis $\ \color{#0a0}{e_i\le e}\ $ below.
Theorem $\  $ Suppose that $\ m\in \mathbb N\ $ has the prime factorization $\:m = p_1^{e_{1}}\cdots\:p_k^{e_k}\ $ and suppose that for all $\,i,\,$ $\ \color{#0a0}{e_i\le e}\ $ and $\ \phi(p_i^{e_{i}})\mid f.\ $ Then $\ m\mid \color{#0a0}{a^e}(a^f-1)\ $ for all $\: a\in \mathbb Z.$
Proof $\ $ Notice that if $\ p_i\mid a\ $ then $\:p_i^{e_{i}}\mid \color{#0a0}{a^e}\ $ by $\ \color{#0a0}{e_i \le e}.\: $ Else $\:a\:$ is coprime to $\: p_i\:$ so by Euler's phi theorem, $\!\bmod q = p_i^{e_{i}}:\, \ a^{\phi(q)}\equiv 1 \Rightarrow\ a^f\equiv 1\, $ by $\: \phi(q)\mid f\, $ and  modular order reduction. Therefore,   since all of the prime powers $\ p_i^{e_{i}}\ |\  a^e (a^f - 1)\ $ so too does their lcm = product = $m$.
Examples $\ $ You can find many illuminating examples in prior questions, e.g. below
$\qquad\qquad\quad$ $24\mid a^3(a^2-1)$
$\qquad\qquad\quad$ $40\mid a^3(a^4-1)$
$\qquad\qquad\quad$ $88\mid a^5(a^{20}\!-1)$
$\qquad\qquad\quad$ $6p\mid a\,b^p - b\,a^p$
A: $\gcd(a,7) = 1$ is not necessary. If $\gcd(a,7)=7$ then $a^7\equiv a \equiv 0 \pmod 7$ and no theorem needed.
FLT says if $\gcd(a,7)=1$ then $a^6\equiv 1\pmod 7$ and from that we conclude that $a^7 \equiv a \pmod 7$ ALWAY; trivialy so if $7|a$--- and by FLT if $\gcd(a,7)=1$.
But we need $\gcd(a,3) = 1$.
Note: $3^7 \equiv 45 \pmod {63}$ so that is a failure.
Fermat's Little theorem applies to primes; and $63= 7*3^2$ is not prime.  The prime factor of $7$ is to a single power so we can conlude $a^7\equiv a \pmod 7$.  
But for the factor of $9=3^2$ we use Euler's theorem to note $a^6 \equiv 1\pmod 9$ if $\gcd(a,3)=1$ and $a^7\equiv a\pmod 9$ if $\gcd(a,3)=1$. 
Now if $3|a$ but $9\not \mid a$ we do not have $a^7\equiv a \equiv 0\pmod 9$ trivially.
In fact we have $a^7\equiv 0 \pmod 9$ while $a^7\equiv a\pmod 7$ so
$a^7 \equiv a + 7m\equiv 0 + 9k\pmod {63}$ where $0 \le m < 9; 0\le k< 7$ 
So if $3\mid a$  we do not have $a^7\equiv a\pmod {63}$ unless $9\mid a$.
======
BTW, If $9|a$ we do have $a^7\equiv a\pmod {63}$ and we do have $a^7\equiv a\pmod{21}$ always.....
A: $a^7-a=a\left(a^6-1\right)=a(a^2-1)(a^4+a^2+1)=\underbrace{(a-1)}_{\equiv 0\pmod{3}}a(a+1)(a^4+a^2+1)$ is clearly always divisible by $3$ because it's a product of $3$ consecutive integers.
$(\forall a\in\mathbb Z)$
$a^7\equiv a\pmod{7}$
$$a^7-a\equiv 0\pmod{3}\;\land\;a^7-a\equiv 0\pmod{7}\implies a^7-a\equiv 0\pmod{63}$$
