2
$\begingroup$

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

$\endgroup$
13
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Nov 13 '16 at 19:01
  • 1
    $\begingroup$ Indeed, and that way lends itself to the "term tweaking" view that I explain in my remark. Nice to see multiple views presented. $\endgroup$ – Bill Dubuque Nov 13 '16 at 20:09
  • 1
    $\begingroup$ 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.$ $\endgroup$ – Will Jagy Nov 13 '16 at 21:13
24
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ Doing everything modulo $x^2+x+1$ makes things very clear. $\endgroup$ – Jyrki Lahtonen Nov 13 '16 at 20:12
  • $\begingroup$ For an older example of this technique see here. $\endgroup$ – Jyrki Lahtonen Jan 2 '19 at 23:26
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.