# Find all $x$ such that $x^{35} + 5x^{19} + 11x^3$ is divisible by 17.

Find all $x$ such that $x^{35} + 5x^{19} + 11x^3$ is divisible by 17.

I think we can use the fact that we can mod everything by 17 and want 0. But how exactly should we go about doing this?

\begin{align}x^{35}+5x^{19}+11x^3 &= x^{17}\cdot x^{17} \cdot x + 5 x^{17}\cdot x^2 + 11 x^3\\ &\equiv x\cdot x \cdot x + 5x \cdot x^2 + 11 x^3 \;(\mathrm{mod}\;17) = 17x^3\\ &\equiv 0\;(\mathrm{mod}\; 17) \end{align} where we apply Fermat's little theorem a few times ($a^p \equiv a \;(\mathrm{mod}\; p)$). Therefore it works for all integers $x$.

$$x^{17}+5x^{19}+11x^3=(x^{18}+6x^2)(x^{17}-x)+17x^3$$

Since $x^{17}-x$ is divisible by $17$ and so is $17x^3$, so is the original polynomial.

Any integer value for $x$ will do !

Observe that \begin{eqnarray*} x^{16} \equiv 1 \pmod{17} \end{eqnarray*} and the expression can be written as $x^3(11+5x^{16}+x^{32})$ so the bracket will always be divisible by $17$.

Lil' Fermat says this is the same as solving the equation in the field $\mathbf Z/17\mathbf Z$ $$x\cdot (x^{17})^2+5x^{17}\cdot x^2+11x^3+=(1+5+11)x^3=0.$$

Thus the given expression is divisible by $17$ for all $x$.

• 2 other users stated the expression is divisible for any integer x. Which is true? – John Locke Jul 25 '17 at 23:13
• @JohnLocke (from David Hume…): I'll check my computation. – Bernard Jul 25 '17 at 23:16
• @JohnLocke: Checked. I had erroneously applied Fermat for one exponent (it's beginning to be late…). Thanks for pointing it! – Bernard Jul 25 '17 at 23:22

\begin{align}{\rm mod}\ 17\!:\,\ x\not\equiv 0\,\Rightarrow\, x^{\large 16}\!\equiv 1\,\Rightarrow\, &\ x^{\large\color{#c00}{n}}\equiv\, x^{\large\color{#c00}{ n\bmod 16}}\ \ \text{by little Fermat, hence}\\[.3em] &\ x^{\large\color{#c00}{35}}\!+5 x^{\large\color{#0a0}{19}}\!+ 11 x^{\large 3}\\[.2em] \equiv\ &\ x^{\large\color{#c00}3}\ + 5 x^{\large\color{#0a0}3} +\, 11 x^{\large 3}\ \ \,{\rm by}\,\ \ {\rm mod}\ 16\!:\ \color{#c00}{35\equiv 3},\ \color{#0a0}{19\equiv 3}\\[.2em] \equiv\ & 17x^{\large 3}\equiv\, 0 \end{align}