How to solve polynomial equations in a field and/or in a ring?

Solution 1:

In a finite ring you can always cop out and simply check all the elements of the ring, and see, whether they are solutions or not. Teacher may not like it, but there's nothing he or she can do about it, because the logic is impeccable. Do realize that you will waste a bit of time, so in an exam you may not afford to do this :-)

If $p$ is a prime, then $\mathbf{Z}_p$ is a field. Then you always have the result that a polynomial of degree $n$ can have at most $n$ zeros (counted with multiplicity). So if you have found $n$, you can stop looking.

The usual factorization tricks always work, if $p$ is a prime. However, note that some rings have zero divisors. For example $2\cdot 4\equiv 0\pmod{8}$, so the polynomial $x^2-1=(x-1)(x+1)$ has 3 as a root in the ring $\mathbf{Z}_8$, even though $(3-1)=2$ and $(3+1)=4$ are both non-zero. In fact, it is not hard to see that this polynomial has exactly 4 zeros in the ring $\mathbf{Z}_8$.

The usual quadratic formula also works in the ring $\mathbf{Z}_p$, $p>2$ prime. You just need to be careful about square roots. For example in the ring $\mathbf{Z}_7$, we have $3^2=9=2$, so if the quadratic formula calls for $\sqrt{2}$, then you can use $\sqrt2=\pm3$, and the formula works the same.

You can also solve a quadratic equation by the technique of completing the square. So if you need to solve the equation $x^2+8x=5$ in the ring $\mathbf{Z}_{17}$, then you can add 16 to both sides to get $x^2+8x+16=5+16=21\equiv 4\pmod{17}$. This you can write in the form $(x+4)^2=4=2^2$. So $x+2$ must be an element with square equal to 4. As 2 and -2 are such elements, and 17 is a prime, there can be only two such elements, and we have found them both. $x+4=2$ gives us the solution $x=2-4=-2\equiv15$ and $x+4=-2$ gives the other solution $x=-2-4=-6\equiv11$.

Note that the quadratic formula does not work with respect to an even modulus. The formula calls for division by $2$ and by one of the coefficients. Both of these need to be units of the ring, because without a multiplicative inverse we cannot do division. Also, if the modulus is not a prime, then the square root may have surprisingly many values. For example in the ring $\mathbf{Z}_{15}$, 1, 4, -1=14 and -4=11 are all square roots of 1.

Finally, if your ring is a direct product of two rings, then you can solve the equation componentwise. After all, in a product ring $R_1\times R_2$ the element $(a,b)$ is the zero element, if and only if both $a=0$ and $b=0$.

Solution 2:

$P(x) := x^2 + 4x + 3 = (x + 3)(x + 1)$. $P(x) = 0$ in ${\mathbb Z}_5$ implies $P(x)$ is multiple of 5, so at least one between $x + 3$ and $x + 1$ must be a multiple of 5. Therefore the solutions are 2 and 4.

Solution 3:

HINT $\rm(3)\:\ $ diagonalize employing Chinese remainder: $\rm\:(m,n)=1\ \Rightarrow\ \mathbb Z/mn \cong \mathbb Z/m\times \mathbb Z/n\:,\:$ hence $\rm\:(x-1)\:(x+3)\:$ has root $\rm\:(1,-3) \ne (1,1),(-3,-3)\in \mathbb Z/m \times \mathbb Z/n\ $ for $\rm\ m,n \ne\cdots$

NOTE $\ $ The ring $\rm\:D\:$ is a domain iff every polynomial $\rm\ f(x)\in D[x]\ $ has at most $\rm\ deg\ f\ $ roots in $\rm\:D\:.\: $ For a simple proof see my post here, where I illustrate it constructively in $\rm\ \mathbb Z/m\ $ by showing that, given any $\rm\:f(x)\:$ with more roots than its degree, we can quickly compute a nontrivial factor of $\rm\:m\:$ via a $\rm\:gcd\:$. The quadratic case of this result is at the heart of many integer factorization algorithms, which attempt to factor $\rm\:m\:$ by searching for a nontrivial square root in $\rm\: \mathbb Z/m\:,\:$ e.g. a square root of $1$ that is not $\:\pm 1$.