Solving roots of a polynomial on $\mathbb{Z}_p$

Question

This is probably a simple question. and I would like to work out an example.

How do we solve $x^2 + x + [1] = 0$ over the field $\mathbb{Z}_7$?

I tried a simple case, for example: $[4] x - [3] = 0$, where I find $x = [3][4]^{-1}$ where we find $[4]^{-1} = [2]$ so $x = [6]$

But I get confused in the quadratic case! Any insight would be great!

Answer 1

It's not hard to show that the quadratic formula still works over a field not of characteristic $2$. For the quadratic $ax^2+bx+c$ it may be helpful to think of the roots given by the QF as $$ (2a)^{-1}\left(-b + \sqrt{b^2-4ac}\right). $$ But, you will have two square roots generally (a good exercise!) so you should apply that formula for all square roots (explaining why you have the $\pm$ in the familiar real/complex case). You could also write it in the familiar form $$ (2a)^{-1}\left(-b \pm \sqrt{b^2-4ac}\right) $$ but this assumes you've preferred a square root, which rarely makes sense. But that's a little nitpicky.

In your example, you need all square roots of $4 \bmod 7$, which are $2$ and $-2=5$. Now $2^{-1}=4$ and the formulas give solutions $$ x = 4(-1+2) = 4 $$ and $$ x=4(-1+5) = 16=2. $$

To believe in the quadratic formula, you can plug it in and check that it works. Since a quadratic over a field will have at most two roots, this likely does it.

I'm also not really joking about my "try them all" comment. This can be really effective, especially for higher degree polynomials and especially over finite fields (the smaller the better). Once you start root-hunting by brute force, if you find that $x=r$ is a root, long divide your polynomial $f(x)$ by $x-r$. You will get $$ f(x) = (x-r)q(x) $$ for some polynomial $q(x)$ of SMALLER degree. The other roots of $f(x)$, if any, are hidden in $q(x)$. But $q(x)$ is of lower degree, so you've made your life easier. Now continue.

Answer 2

My way of looking at this particular polynomial, $X^2+X+1$, is this: it’s the defining polynomial for the primitive cube roots of unity in whatever field you’re considering of characteristic $\ne3$.

But I know what the primitive cube roots of $1$ are in $\Bbb F_7$, they’re $2$ and $4$. That is, over $\Bbb F_7$, we get $(X-2)(X-4)=X^2+X+1$. And there you are.

Answer 3

Suppose $F$ is any field with

$\text{char}(F) \ne 2, \tag 1$

and

$q(x) = x^2 + ax + b \in F[x] \tag 2$

is a quadratic polynomial with coefficients in $F$; we wish to find the zeroes of $q(x)$; short of simply evaluating $q(x)$ for succesive elements $x \in F$ (which in any event will in principle only be guaranteed to succeed when $\vert F \vert < \infty$), what can be done?

Well, it is worth noting that certain well-known, ordinary procedures such as completing the square and its cousin the quadratic formula may be implemented as long as (1) applies. Indeed, with

$q(x) = 0 \tag 3$

we may write

$x^2 + ax = -b, \tag 4$

and then add $a^2/4$ to each side; by (1), this is a well-defined element of $F$; we obtain

$\left (x + \dfrac{a}{2} \right )^2 = a^2 + ax + \dfrac{a^2}{4} = \dfrac{a^2}{4} - b; \tag 5$

if then there exists $c \in F$ with

$c^2 = \dfrac{a^2}{4} - b, \tag 6$

(4) becomes

$\left (x + \dfrac{a}{2} \right )^2 = c^2, \tag 7$

whence

$x + \dfrac{a}{2} = \pm c, \tag 8$

or

$x = -\dfrac{a}{2} \pm c. \tag 9$

So the problem of finding solutions to (3) is tantamount to discovering if $a^2/4 - b$ is a perfect square in $F$; indeed, we may even write (9) in the form

$x = -\dfrac{a}{2} \pm \sqrt{\dfrac{a^2}{4} - b} = \dfrac{-a \pm \sqrt{a^2 -4b}}{2}, \tag{10}$

familiar to us as the famous "quadratic formula", assuming of course such a $c \in F$ as in (6) exists.

In the present case of $F = \Bbb Z_7$, the non-zero squares are

$1 = 1^2 = 6^2, \; 2 = 3^2 = 4^2, \; 4 = 2^2 = 5^2; \tag{11}$

if

$q(x) = x^2 + x + 1, \tag{12}$

we have

$a = b = 1, \tag{13}$

whence

$c^2 = \dfrac{a^2}{4} - b = \dfrac{1}{4} - 1 = 2 - 1 = 1; \tag{14}$

thus

$c = 1, 6, \tag{15}$

and

$x = -\dfrac{1}{2} \pm 1 = 3 \pm 1 = 2, 4; \tag{16}$

both these results are easily checked.

Of course, if we are searching for roots by systematic evaluation of $q(x)$ at different elements of $F$, once we have discovered one of them, such as $2$, we may find the other via dividing $q(x)$ by $x - 2$, or (much less work!) recalling that $-a$ must be their sum, whence the second zero is $-1 - 2 = -3 = 4$ in $\Bbb Z_7$.

If we encounter a quadratic for which $a^2/4 - b$ is not a perfect square, then such a $q(x)$ will not split over $F$, and we must consider the extension field $F[x]/(q(x))$ to split $q(x)$; but that is another chapter in a long, long story.