If $\gcd(a, 42) = 1$, then $a^6 \equiv 1 \pmod{168}$.

Question

I have just learned Fermat's little theorem.

That is,

If $p$ is a prime and $\gcd(a,p)=1$, then $a^{p-1} \equiv 1 \mod p$

Well, there's nothing more explanation on this theorem in my book.

And there are exercises of this kind

If $\gcd(a,42)=1$, then show that $a^6\equiv 1 \mod 168$

I don't have any idea how to approach this problem.

The only thing I know is that $168=3\cdot 7\cdot 8$.

Hence, I get $[a^2\equiv 1 \mod 3]$ and $[a^6\equiv \mod 7]$ and $[a\equiv 1\mod2]$.

That's it.

I don't know what to do next.

Please help.

Answer 1

If $x \equiv 1 \bmod y$ and $x \equiv 1 \bmod z$, then $x \equiv 1 \bmod yz$ if $y$ and $z$ are coprime.

It also turns out that $a \equiv 1 \bmod 2 \Rightarrow a^2 \equiv 1 \bmod 2^3$. This is because if $a = 2k + 1$, $a^2 = 4(k^2 + k) + 1$. Since $k^2 \equiv k \bmod 2$, $k^2 + k$ is even. Thus $8 \mid 4(k^2+k)$.

Then $a^6 \equiv 1 \bmod 3$, $a^6 \equiv 1 \bmod 7$, and $a^6 \equiv 1 \bmod 8$. Hence $a^6 \equiv 1 \bmod (3 \cdot 7 \cdot 8)$, or $a^6 \equiv 1 \bmod 168$.

Answer 2

Fermat's Little Theorem gives that $a \equiv 1 \pmod 2$, $a^6 \equiv 1 \pmod 3$, and $a^6 \equiv 1 \pmod 7$ immediately.

If $a \equiv 1 \pmod 2$, then $a \equiv \pm 1, \pm 3 \pmod 8$. In either of these, it's immediate that $a^2 \equiv 1 \pmod 8$, and so $a^6 \equiv 1 \pmod 8$.

Now by the Chinese Remainder Theorem, since $a^6 \equiv 1$ in each of the three relatively prime moduli, $a^6 \equiv 1 \pmod{8\cdot 3\cdot 7}$. $\diamondsuit$