Question

Let n be an integer divisible by 9. Prove that n^7 = n mod 63

Answer 1

Theorem 1 (Fermat’s little theorem).

If $p$ is a prime number, then for any positive integer $n$ we have $n^{p}\equiv n\mod p$.

Question 1.

Let $n$ be an integer divisible by $9$. Prove that $n^{7}\equiv n\mod 63$.

Solution. We need to prove that $n^{7}-n$ is divisible by $63$. Since $n^{7}-n=n(n^{6}-1)$ and $n$ is divisible by $9$, then $n^{7}-n$ is divisible by $9$. As $7$ and $9$ are relatively prime, it is sufficient to prove that $n^{7}-n$ is divisible by $7$. But this immediately follows from Fermat’s little theorem, because $7$ is a prime number. $\Box$