0

Solve $3x^2+x+1 = 0$ over $Z_5$.

Essentially, the equation needs to be solved over $\mod5$.

Frankly, I don't really have an idea how to start. The problem is that I have and $x$ and $x^2$ and I don't see how to single the $x$ out. I could've mutiplied $3x^2$ by the inverse of $3$ which is $2$ over $Z_5$ but then I'd have a coefficient next to $x$. Do you have any suggestions?

Yos
  • 2,663

3 Answers3

3

You can complete the square, and adjust mod 5 when you get the opportunity to do so.

$$\begin{align}\\ 3x^2 + x + 1 & = 0 \\ 6x^2 + 2x + 2 & = 0 \\ x^2 + 2x + 1 & = -1 = 4 \\ (x + 1)^2 & = 2^2 \\ x + 1 & = \pm 2 = 2 \text{ or } 3\\ x & = 1 \text{ or } 2\\ \end{align}$$

We are working in a prime modulus, so we don't need to worry about pesky divisors of zero.

However, I should admit that we were lucky here that we could solve $y^2 \equiv -1 \pmod 5$ (where $y = x + 1$) by inspection. In general, quadratic congruences can be tricky. There is a nice discussion at Solving quadratic congruences by John D. Cook.

PM 2Ring
  • 4,844
2

You can start be multiplying by $2$, this is ok because it is inversible modulo $5$.

You get $x^2+2x+2\equiv 0\pmod{5}\iff x(x+2)\equiv -2\equiv 3\pmod{5}$

Now plugging $x=0,1,2,3,4$ is a a bit simpler than original equation and you find solution $x=1\text{ or }2$. Anyway, at the end, it often comes to plug the values in the equation.

zwim
  • 28,563
0

Since there are two roots over the field $\mathbb{F_5}$, we are done. We have $$ 3x^2+x+1= 3(x + 4)(x + 3). $$ A quadratic polynomial with a root over a field already splits into linear factors. Now $x=1$ obviously is a root.

Dietrich Burde
  • 130,978
  • can you please explain how you got to the equality $3x^2+x+1= 3(x + 4)(x + 3)$? I tried splitting the original equation into factor over $\mathbb{R}$ but it has no roots in $\mathbb{R}$ – Yos Mar 23 '17 at 10:44
  • @Yos As I said. Try to find a root. We only have five elements, namely $0,1,2,3,4$. Very soon you will see that $x=1$, and $x=2$ is a root (but not over the real numbers, of course). – Dietrich Burde Mar 23 '17 at 10:45
  • this makes complete sense as KajHansen mentioned. What I don't understand is how you got the equation to the right – Yos Mar 23 '17 at 10:46
  • By finding a root $x=1=-4$, which is a linear factor $(x+4)$ and then using polynomial division. Very easy, because it is only a quadratic polynomial. Or, even easier, find the second root $x=2=-3$ and multiply $(x+4)(x+3)$ and see what is missing - the factor $3$. – Dietrich Burde Mar 23 '17 at 10:47