# Show that $a^6-1$ is divisible by $168$ whenever $(a,42)=1$.

I have been running into this type of problem a lot:

Show that $a^6-1$ is divisible by $168$ whenever $(a,42)=1$.

First of all, by Euler's theorem, we have that $$a^{\phi(42)}\equiv a^{12}\equiv1\pmod{42}.$$ Notice that $$a^6a^6\equiv1\pmod{42}\text{ and }168=4\cdot42.$$ It follows that $$a^{12}\equiv1\pmod{168},$$ $$a^{12}-a^6\equiv1-a^6\pmod{168},$$ $$a^6(a^6-1)\equiv1-a^6\pmod{168},$$ $$a^6-1\equiv a^6(1-a^6)\pmod{168},$$ $$a^6-1\equiv a^6-a^{12}\pmod{168}.$$ I get stuck here: How can I show that the RHS is congruent to zero modulo $168$?

-
I haven't learned anything like it, but it'd seem as though $a^n\equiv1\pmod{m}$ whenever $n|\phi(m)$. – EsX_Raptor Mar 7 '12 at 3:14
Your last line is the same as your second line, which is the same as your first line. In other words, you haven't actually changed anything yet. – mixedmath Mar 7 '12 at 3:15
I'm just trying to make it very explicit that $a^6-1\equiv0\pmod{168}$. – EsX_Raptor Mar 7 '12 at 3:18
That's Carmichael's theorem: $a^{\lambda(168)}\equiv1\pmod{168}$ and $\lambda(168)=6$. – lhf Mar 7 '12 at 3:21

By Fermat's Theorem, $a^6\equiv 1 \pmod 7$. Also by Fermat's Theorem, or otherwise, $a^2\equiv 1 \pmod 3$. Thus $a^6\equiv 1 \pmod 3$. So far, we have that $$a^6\equiv 1 \pmod {21}.$$ But $a$ is odd, so $a^2\equiv 1 \pmod 8$. It follows that $$a^6 \equiv 1 \pmod {8}.$$ Now it's over.

-
I was just typing this up! – mixedmath Mar 7 '12 at 3:37
I can delete, if a more student-friendly solution appears. – André Nicolas Mar 7 '12 at 3:39

Hint $\$ Either apply Carmichael's generalization of Euler-Fermat, or proceed directly via

$$\rm A^{N_j}\equiv 1\ \ (mod\ M_j)\ \Rightarrow\ A^{lcm\ N_j}\equiv 1\ \ (mod\ lcm\ M_j)$$

for $\rm\ \begin{cases} \:N = (2,2,6)\\ \rm M = (8,3,7)\end{cases}\ \ \ \$ This is what Andre does. It's worth emphasis it is of above general form.

-