<s>[INST] 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?
 [/INST] 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}$.
</s>