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

3 Answers

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

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$

-

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 40, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9551595449447632, "perplexity_flag": "head"}