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

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.$$

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.

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$