# Prove that for every integer $n$ that is not a multiple of $3$ we have $3 | (4n^{12}+3n^6+2)$

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?

-
All that matters here is that $12$ is even. Squares are either $0$ or $1 \pmod 3.$ – Will Jagy Nov 9 '12 at 7:25

Note that $4n^{12} + 3n^6 + 2 = (3n^{12} + 3n^6) + n^{12} + 2$.

Further note that $3 \vert (3n^{12} + 3n^6)$. Hence, it is enough to prove that $$3 \vert (n^{12} + 2)$$ Since $n \equiv \pm \pmod{3}$, we have that $n^{2} \equiv 1 \pmod{3} \implies n^{12} \equiv 1 \pmod{3}$. Hence, $$n^{12} +2 \equiv (1+2) \pmod{3} \equiv 0 \pmod{3}$$

-
Sorry, I'm a little slow - how can we see that $3|3n^{12}+3n^6$? And did you mean $4n$ instead of $3n$? – Arvin Nov 9 '12 at 7:35
@Arvin $3n^{12} + 3n^6 = 3(n^{12} + n^6)$. – user17762 Nov 9 '12 at 7:36
Ahh of course. Thanks heaps – Arvin Nov 9 '12 at 7:43

By Fermat's theorem $n^3 ≡ n$ (mod $3$) , so , $4n^{12} ≡ 4n^4$ (mod $3$) and $3n^6 ≡ 3n^2$(mod $3$)

so , $3 |4n^{12} + 3n^6 +2$ $\longleftrightarrow$ $3| 4n^4 + 3n^2 + 2$ $\longleftrightarrow$ $3|n^4 + 2$ $\longleftrightarrow$ $3|n^4 -1$ $\longleftrightarrow$ $3|(n^2+1)(n^2-1)$ , which is obvious in view of Fermat's theorem $n^2 ≡ 1$(mod$3$) , since $3$ is given to not divde $n$.

-

Hint $\rm\,\ mod\ 3\!:\ n\not\equiv0\:\Rightarrow\:n\equiv\pm1\:\Rightarrow\:\color{#C00}{n^2}\!\equiv1\:\Rightarrow\: 4\,(\color{#C00}{n^2})^6\!+3\,(\color{#C00}{n^2})^3\!+2\equiv 4+3+2\equiv 0$

-