# 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?

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$.

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}$.