Prove that $36|n^{12k-6}-n^6$ Prove that if gcd(n,6)=1 and k>0, then  $36|n^{12k-6}-n^6$.
Idea: I want to show that  $2|n^{12k-6}-n^6$ and  $3|n^{12k-6}-n^6$.
For the first part, since gcd(n,6)=1, n must be an odd number, so it is easy to show that $n^{12k-6}-n^6$ is divisible by 2. I am stuck by the second part and i think that I need to use Fermat's little theorem somehow. Anyone can give some hint?
 A: Let $n$ and $k>0$ integers. Notice that
\begin{align*}
n^{12k-6}-n^6&=\left(n^{6k-3}-n^3\right)\left(n^{6k-3}+n^3\right)\\
&=\left(n^{2k-1}-n\right)\left(n^{4k-2}+n^{2k}+n^2\right)\left(n^{2k-1}+n\right)\left(n^{4k-2}-n^{2k}+n^2\right)\\
&=n^6\left(n^{2k-2}-1\right)\left(n^{4k-4}+n^{2k-2}+1\right)\left(n^{2k-2}+1\right)\left(n^{4k-4}-n^{2k-2}+1\right)
\end{align*}


*

*If $n$ is even, then $2^6=64$ divides $n^{12k-6}-n^6$. 

*For $n$ odd we have $4|(n^{2k-2}-1)$ and $2|(n^{2k-2}+1)$, so $8$ divides $n^{12k-6}-n^6$.

*If $3|n$, then $729$ divides $n^{12k-6}-n^6$.

*If $3$ does not divide $n$, then the squares $n^{4k-4}$ and $n^{2k-2}$ gives remainder $1$ under division by $3$, then $3$ divides $n^{2k-2}-1$ and $n^{4k-4}+n^{2k-2}+1$, so $9$ divides $n^{12k-6}-n^6$.


Then, $72$ divides $n^{12k-6}-n^6$ for any integer $n$.
A: We  show that $4$ divides our difference, and that $9$ does.
Recall (or prove) that if $n$ is odd then $n^2\equiv 1\pmod{8}$. It follows that $n^{12k-6}\equiv 1\pmod{8}$, and $n^6\equiv 1\pmod{8}$, so in fact our difference is divisible by $8$, and therefore by $4$.
For divisibility by $9$, note that $n^2\equiv 1\pmod{3}$. So $n^6$ has the shape $(1+3t)^3$, which is $1+3(3t)+3(9t^2)+27t^3$, and is therefore congruent to $1$ modulo $9$. For the same reason, $n^{6(2k-1)}$ is congruent to $0$ modulo $9$, and therefore our difference is divisible by $9$.
Alternately, for divisibility by $9$, use Euler's Theorem. We have $\varphi(9)=6$, and therefore $n^6\equiv 1\pmod{9}$, and also $n^{6(2k-1)}\equiv 1\pmod{9}$.
