How to solve $10x^{39 }+ 8x^{20} + 9x^3 + 7x ≡ 0\pmod {19}$

Question

I guess I'm supposed to solve it with Euclidian ring (or Euclidian domain), but I'm not even sure about that.

$$10x^{39 }+ 8x^{20} + 9x^3 + 7x ≡ 0\pmod {19}$$

I've managed to turn it into $(10x^{19}+8)x^{17}+9)x^2+7)x$ But after that I have no clue what I'm supposed to do.

Answer 1

$19$ is prime.

There are no zero divisors in the ring $\mathbb Z_p$

From what you have above either $x\equiv 0 \pmod {19}$ or $(10x^{19}+8)x^{17}+9)x^2+7)\equiv 0\pmod{19}$

What else can we say? By Fermats little theorem $x^p = x\pmod p$

$10x^{39} + 8x^{20} + 9x^3 + 7x\equiv 10x^3 + 8x^2 + 9x^3 + 7x\equiv (19x^2 +9x + 7)x \pmod {19}$

$19x^2\equiv 0 \pmod {19}$ so we can drop this term.

$9x + 7 \equiv 0\\ 18 x + 14 \equiv 0\\ -x + 14 \equiv 0\\ x \equiv 14$

We have two solutions $x\equiv 0, x\equiv 14 \pmod 14$

Answer 2

By Fermat's Theorem $$10x^{39}+8x^{20}+9x^3+7x\equiv 10x^3+8x^2+9x^3+7x\equiv 8x^2+7x\equiv 0\;(\textsf{mod}\; 19).$$ Therefore, for 19 being a prime number: $x\equiv 0\;(\textsf{mod}\; 19)$ or $8x+7\equiv 0\;(\textsf{mod}\; 19)\Rightarrow x\equiv -84\equiv 11\;(\textsf{mod}\; 19)$.

Answer 3

Let's look for the roots of this polynomial in $F := \mathbb{Z} / 19 \mathbb{Z}$. This polynomial can be seen as a polynomial in $F[X]$.
Since $19$ is prime, $F$ is a field. A most enjoyable property of $F$ is that the map $x \mapsto x^{19}$ is the identity. In other words, for any $x \in F$, we have $x^{19} = x$. This allows us to simplify for $x \in F$:

$$\begin{eqnarray} 10x^{39 }+ 8x^{20} + 9x^3 + 7x &=& 10x^{20 }+ 8x^{20} + 9x^3 + 7x \\ =10 x + 8x+ 9x^3 + 7x &=& 9x^3 + 25 x\\ = 9x^3 + 6x\end{eqnarray}$$

Let's factorize this expression : $9 x^3 + 6x = 3 \cdot x \cdot (3x^2 +2)$. Here, we see an obvious solution, $0$ and maybe two other solutions that correspond to the solutions of $3x^2 +2 = 0$.

Now we want the leading coefficient to be $1$, so we multiply by the inverse of $3$ in $F$ : $13$.

$$3x^2 +2 = 0\Longleftrightarrow x^2 + 16= 0 \\ \Longleftrightarrow x^2 = -16 \\ \Longleftrightarrow x^2 = 3$$

Since $3$ isn't a square in $F$, $0$ is the only solution.

Answer 4

Little Fermat says $x^{19}\equiv x\pmod{19}$. Therefore, $$ \begin{align} 0 &=\overbrace{\ \ 10x^{39}\ \ }^{\substack{10x^3\\\text{cancels}\\9x^3}}+\overbrace{\ \ \ 8x^{20}\ \ \ }^{8x^2}+9x^3+7x\\ &\equiv8x^2+7x\pmod{19}\tag1 \end{align} $$ which means $x\equiv0\pmod{19}$ or $x\equiv-\frac78\pmod{19}$

We can compute $\frac18\pmod{19}$ using the Extended Euclidean Algorithm (as implemented in this answer): $$ \begin{array}{r} &&2&2&1&2\\\hline 1&0&1&-2&3&-8\\ 0&1&-2&5&-7&19\\ 19&8&3&2&1&0\\ \end{array}\tag2 $$ which says that $3\cdot19-7\cdot8=1$; therefore, $\frac18\equiv-7\pmod{19}$.

Applying the result from $(2)$ to the result from $(1)$ gives $$ x\in\{0,11\}\pmod{19}\tag3 $$