1
$\begingroup$

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

$\endgroup$

closed as off-topic by Stefan Mesken, Davide Giraudo, Morgan Rodgers, Henrik, Shailesh Nov 14 '16 at 0:11

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Stefan Mesken, Davide Giraudo, Morgan Rodgers, Henrik, Shailesh
If this question can be reworded to fit the rules in the help center, please edit the question.

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

$\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
19
$\begingroup$

It's a special case of $\ x^{2}\!+\!x\!+\!1\mid x^A\! +\! x^B\! +\! x^C\ $ 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$ since $\,{\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 $\,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.

$\endgroup$
  • 2
    $\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 at 23:26
1
$\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)$$

$\endgroup$

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