Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
check your $f(x)$, i think there is $3x^3$ instead of $3x^2$ –  Aang Jul 13 '12 at 8:42
    
@avatar oops... you're right, sorry, promptly fixed. –  haunted85 Jul 13 '12 at 8:48
add comment

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
    
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? –  haunted85 Jul 13 '12 at 8:53
    
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}$. –  Aang Jul 13 '12 at 8:56
    
$(x-10)$ and $(x-18)$ are coming out to be the other factors. –  Aang Jul 13 '12 at 9:05
    
(very stupid question coming...) How so? $\Delta < 0$ –  haunted85 Jul 13 '12 at 9:16
3  
$D=64-132=-68\equiv 1\pmod {23}$. Use $D=1$. –  Aang Jul 13 '12 at 9:18
show 5 more comments

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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