# Prime factor of $A=14^7+14^2+1$ [closed]

Find a prime factor of $A=14^7+14^2+1$. Obviously without just computing it.

[Update: see the method of simpler multiples for a more general perspective]

It's a special case of $$\ \bbox[5px,border:1px solid #c00]{x^{2}\!+\!x\!+\!1\mid x^A\! +\! x^B\! +\! x^C\ \ {\rm if} \ \ \{A,B,C\}\equiv \{2,1,0\}\pmod{\!3}}$$

Hint $$\$$ Notice: $$\ {\rm mod}\,\ x^2\!+\!x\!+\!1\!:\ \color{#c00}{x^3\equiv 1}\,\Rightarrow\ x(\color{#c00}{x^6})\!+\!x^2\!+\!1\equiv x\!+\!x^2\!+\!1\equiv 0$$

Remark  i.e. replacing $$\,\color{#0a0}x\,$$ by $$\,x^7\,$$ in $$\, f = x^2+\color{#0a0}x+1 = (\color{#c00}{x^3\!-\!1})/(x\!-\!1)$$ it remains divisible by $$f$$ because $$\,{\rm mod}\ f\!:\ \color{#c00}{x^3\equiv 1}\,\Rightarrow\, x^7 \equiv\, x(\color{#c00}{x^3})^2\equiv\color{#0a0} x$$

More generally if we replace $$\,x^{\large k}\,$$ by $$\, x^{\large k+jn}\,$$ in $$\, f = (\color{#c00}{x^n\!-1})/(x\!-\!1)\,$$ it remains divisible by $$f$$ since $$\,{\rm mod}\ f\!:\ \color{#c00}{x^n\equiv 1}\,\Rightarrow\, x^{\large k+jn} = x^{\large k}(\color{#c00}{x^{\large n}})^{\large j}\equiv x^k$$

This viewpoint naturally leads to the following

Theorem  If $$\ f = \sum_k f_k x^k\,$$ divides $$\,\color{#c00}{x^n-1}$$ then $$\,f\,$$ divides $$\, \sum_k f_k x^{\large h_k}\,$$ if $$\,h_k \equiv k\pmod{\! n}$$

Proof $$\$$ As above $$\!\bmod f\!:\ x^{\large h_k}\! = x^{\large k+jn}\equiv x^k\$$ so $$\ \sum_k f_k x^{\large h_k}\equiv \sum_k f_kx^k\equiv f\equiv 0.\ \$$ QED

For example $$\ x^2\!+\!x\!+\!1 \mid x^{\large 2+3i}\!+x^{\large 1+3j}\!+x^{\large 3k}\$$ generalizes the OP  (where $$\,i,j,k = 0,2,0)$$

This method often helps one to recognize multiples of (cyclotomic) factors of $$\,x^n-1\,$$ having such "tweaked terms". Similarly for factors of binomials or other "few monomial" polynomials.

• Doing everything modulo $x^2+x+1$ makes things very clear. Nov 13 '16 at 20:12
• For an older example of this technique see here. Jan 2 '19 at 23:26

Hint: I've seen the 3rd cyclotomic polynomial too many times.

\begin{aligned} x^7+x^2+1&=(x^7-x^4)+(x^4+x^2+1)\\ &=x^4(x^3-1)+\frac{x^6-1}{x^2-1}\\ &=x^4(x+1)(x^2+x+1)+\frac{(x^3-1)(x^3+1)}{(x-1)(x+1)}\\ &=x^4(x+1)(x^2+x+1)+(x^2+x+1)(x^2-x+1) \end{aligned}

• You can equally well go with $$x^7+x^2+1=(x^7-x)+(x^2+x+1)$$ to show that $x^2+x+1$ is a factor. Nov 13 '16 at 19:01
• Indeed, and that way lends itself to the "term tweaking" view that I explain in my remark. Nice to see multiple views presented. Nov 13 '16 at 20:09
• Jyrki, I like saying $7 \equiv 1 \pmod 3,$ so both complex roots of $x+x^2 + 1$ are roots of your polynomial, therefore it is divisible by $(x - \omega)(x - \omega^2) = x^2 + x + 1$ where $\omega$ is a cube root of $1.$ Nov 13 '16 at 21:13

Same solution as Jyrki's, written differently $$A=14^7+14^2+1=14^7-14+(14^2+14+1)\\ =14(14^6-1)+(14^2+14+1)=14(14-1)(14^2+14+1)(14^3+1)+(14^2+14+1)$$