Find a prime number $p$ so that $f = \overline{3}x^3+ \overline{2}x^2 - \overline{5}x + \overline{1}$ is divided by $x-\overline{2}$ in $\mathbb Z_p$

Question

Let $f = \overline{3}x^3+ \overline{2}x^2 - \overline{5}x + \overline{1}$ be defined in $\mathbb Z_p$. Find a prime number $p$ so that $f$ can be divided by $g = x-\overline{2}$, then factorize $f$ as product of irreducible factors in the $\mathbb Z_p$ found.

I am really stuck because I can't figure out on which principle should I rely on to solve this exercise, a push in the right direction is definitely greatly appreciated.

Answer 1

$x-a$ divides a polynomial $f(x)$ iff $f(a)=0\implies (x-2)$ divides $f(x)=3x^3+2x^2-5x+1$ iff $f(2)=24+8-10+1\equiv 0\pmod p\implies 23\equiv 0 \pmod p$. The only prime for which $23\equiv 0\pmod p$ is $23$ itself. So, the answer is $23$. Now you can easily factorize $3x^3+2x^2-5x+1$, since after finding one root, it becomes quadratic which is easy to factorize.

Answer 2

Below is a complete solution, to address your questions about the second half (not in avatar's answer). As in your prior question, the key is to use the Factor Theorem over $\Bbb Z_p$ as follows:

$$\rm\ f(x)\ =\ (x\!-\!2)\,g(x)\ \Rightarrow\ 0\, \equiv\, f(2)\, \equiv\, 3\cdot 2^3\! + 2\cdot 2^2\! - 5\cdot 2 + 1\,\equiv\, 23\:\ (mod\ p)$$

Therefore $\rm\:23\equiv 0 \pmod{p}\:\Rightarrow\:p\:|\:23\:\Rightarrow\:p = 23,\:$ since $\rm\:p\:$ is prime. To factor $\rm\:f\:$ we first use the polynomial division algorithm over $\,\Bbb Z_p\:$ to calculate $\rm\:g(x) = f(x)/(x\!-\!2)\ =\, 3\,x^2+8\,x + 11.\:$

Thus it suffices to factor $\rm\:g.\:$ First let's scale it so the leading coefficient is $1$. To do that we need to multiply $\rm\:g\:$ by $\rm\:1/3\equiv 24/3\equiv 8,\:$ yielding $\rm\:8\,g \equiv x^2-5\,x-4.\:$ Now we apply the quadratic formula. The discriminant $\rm\: d \equiv 5^2\! + 4\cdot 4\equiv 41\equiv 18 \equiv 2\cdot 3^2,\:$ so $\rm\:\sqrt{d} \equiv 3\sqrt{2}\equiv 3\sqrt{25}\equiv \pm 15.\:$ Thus $\rm\, 8g\, $ has roots $\rm\,(5\!\pm\! 15)/2 \equiv \color{#C00}{10},\, -\color{#0A0}5,\,$ so $\rm\,g\equiv 3\,(8g) \equiv 3\,(x\!-\!\color{#C00}{10})\,(x\!+\!\color{#0A0}5),\,$ hence

$$\rm\ f\ \equiv\ (x-2)\,g\ \equiv\ 3\,(x-2)\,(x-10)\,(x+5) $$

We were lucky above since it was easy to see how to find $\rm\:\sqrt{2}\:$ via $\rm\:2 \equiv 2 + 23 \equiv 5^2.\:$ Such luck by "law of small numbers" generally won't apply for large $\rm\:p.\:$ Instead, there are reasonably efficient algorithms to compute such square roots mod $\rm\,p,\:$ e.g. the Tonelli-Shanks and Cipolla algorithms.