1
$\begingroup$

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.

  • 0
    check your $f(x)$, i think there is $3x^3$ instead of $3x^2$2012-07-13
  • 0
    @avatar oops... you're right, sorry, promptly fixed.2012-07-13

2 Answers 2

5

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

  • 0
    Now that we know that $(x-2)$ divides $f$ in $\mathbb Z_{23}$this means that $(x-2)$ is one of its irreducible factors, right? So what if I actually perform the division between $f$ and $g$ in order to find the other factors?2012-07-13
  • 0
    yes, you can now divide $f$ by $g$ which gives $f=(x-2)(3x^2+8x+11)$. Now find the roots of $(3x^2+8x+11)\pmod {23}$.2012-07-13
  • 0
    $(x-10)$ and $(x-18)$ are coming out to be the other factors.2012-07-13
  • 0
    (very stupid question coming...) How so? $\Delta < 0$2012-07-13
  • 3
    $D=64-132=-68\equiv 1\pmod {23}$. Use $D=1$.2012-07-13
  • 0
    what if by some remote chance $-68 \equiv_{p} 2$ how do I deal with the $\sqrt{2}\text{ } (mod \text{ } p)$?2012-07-13
  • 0
    Then, try to find some $x$ such that $x^2\equiv 2\pmod {23}$. $2$ should be quadratic residue of $23$ for existence of such $x$.2012-07-13
  • 0
    so I need to look for such $x$ value or is there any calculation I can do to find that?2012-07-13
  • 0
    It depends on $a$ of $x^2\equiv a\pmod p$. see http://en.wikipedia.org/wiki/Quadratic_reciprocity2012-07-13
  • 0
    @haunted85 There are algorithms for computing sqrts mod p, e.g. google "Tonelli's algorithm". But your example is easier: mod $23\!: x^2 \equiv 2\equiv 25\iff x\equiv \pm 5.\ $2012-07-13
5

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.