Showing $a^{19} \bmod 7 = a$.

Question

By brute force I'm noticing that for all $a ∈ _7$, we have $a^{19}\bmod 7 \equiv a $. Now this looks very much like Fermat's Little Theorem, but this theorem should hold if the primes are the same, whereas 19 and 7 are clearly not. Is this just a coincidence?

Answer 1

Since $7$ is prime, $\varphi(7)=6$, so $$a^6=1\pmod{7}$$ by Euler's Theorem, where $\varphi $ is Euler's totient function.

Answer 2

By Fermat's Little Theorem:

$a^{6}\equiv 1\pmod{7}$

Thus:

$(a^{6})^{3}\equiv 1^{3}\pmod{7}$

$a^{18}\equiv 1\pmod{7}$

Multiplying by $a$ on both dies, we have:

$\boxed{a^{19}\equiv a\pmod{7}}$

The above argument works only for $a$ relatively prime to $7$. For $a$ not relatively prime to $7$, this means $a\equiv 0\pmod{7}$ because $7$ is prime. Then, it can be demonstrated that

$0^{19}\equiv 0\pmod{7}$