Prove that for every integer $n$ that is not a multiple of $3$ we have $3 | (4n^{12}+3n^6+2)$
So I know this has something to do with fermat/euler's theorem which says:
For some $a^x \equiv y \pmod{n}$, if $gcd(a,n)=1$ then $a^{\phi{(n)}} \equiv 1 \pmod{n}$
However I don't see how we are suppose to apply the theorem?