# A question on Fermat's Little Theorem

Let $n$ be an integer not divisible by $3$. Show that $n^7 ≡ n (\mod 63)$.

I know that we can split $63$ into $3^2 \cdot 7$ So we have $n^7=n (\mod 7\cdot3^2)$

$n^7=n (\mod 3^2)$ and $n^7 = n (\mod 7)$

And I am stuck how to go about solving this question after this

• Title: not a theory, but a theorem (a little one). – Dietrich Burde Oct 16 '17 at 18:39
• @user236182 "Let $n$ be an integer not divisible by $3$" – Carl Schildkraut Oct 16 '17 at 18:41
• By binomial theorem, if $3\nmid n$, then $n^6\equiv (3k\pm 1)^6\equiv 1\pmod{9}$. – user236182 Oct 16 '17 at 18:45

Hint: If $3\nmid n$, we can say $n^6\equiv 1 \bmod 9$ (why?) If $7\nmid n$, $n^6\equiv 1\bmod 7$ (why?) What happens if $7|n$?

$$n^7-n=n(n^3-1)(n^3+1)=(n-1)n(n+1)(n^2-n+1)(n^2+n+1).$$ Now, it's obvious that $(n-1)n(n+1)$ is divisible by $3$.

Let $n=3k-1$, where $k$ be a natural number.

Thus, $n^2-n+1$ is divisible by $3$.

Let $n=3k+1$, where $k$ be a natural number.

Thus, $n^2+n+1$ is divisible by $3$,

which says that $n^7-n$ is divisible by $9$.

Also, $n^7-n$ is divisible by $7$ for all integer $n$ by the Fermat's little theorem, which says that it's divisible by $7$ for all integers $n$, which not divisible by $3$ and we are done!

Let $n$ be $n=3m\pm1$ $$(3m\pm1)^7\equiv (3m\pm1)\pmod{63}\iff(3m\pm1)((3m\pm1)^6-1)\equiv0\pmod{63}$$

The $LHS$ is divisible by $7$, by either $3m\pm1$ is a multiple of $7$ or because of FLT in the second factor (i.e. $(3m\pm1)^6-1\equiv0\pmod7$ ).

Besides it is clear that $(3m\pm1)^6-1\equiv 0\pmod9$