1

I have a question about solving polynomial equations modulo some number.

Say we were to solve the following quadratic congruence equation: $$x^2+x + 2 = 0 \quad mod \quad 4$$ We could of course just try the values $0, 1, 2, 3$ and check wheater or not they solve the equation. But what is the proper procedure for something to the likes of: $$x^4+x^3+7x^2+x+3=0 \quad mod \quad 45$$ Do we keep using a brute force method or is there a more simple way of thinking about this that I don't know of.

I have seen that for instance, quadratic congruence equations, can be solved using the quadratic formula given that you can find values to satisfiy the root and division parts. However, according to a teacher this does not work in every case. An example is the aforementioned quadratic equation.

Using the quadratic formula we would arrive at $$x=\frac{-b\pm\sqrt{b^2-4c}}{2}$$ Firstly to find the multiplicative inverse of $2$ would require solving $2y = 1 \quad mod \quad 4$ which has no solutions. This in the face of the fact that the original quadratic congruence equation does have solutions.

To clarify my question, what is the best way to go about solving these kinds of equations when we cannot simply relay on checking every single case? Is there anyway to reduce these equations? Also, does it matter if we use modulo a prime or a composite number in these equations?

Sinbad The Sailor
  • 948
  • 3
    The quadratic formula works modulo primes besides $2$; for composite moduli, consider the Chinese remainder theorem – J. W. Tanner Oct 08 '20 at 17:22
  • You can reduce to looking at prime power modulae, which can be combined using the Chinese Remainder Theorem. So for $45$ you can look modulo $9$ and modulo $5$ to start with (fewer cases). For higher degree polynomials the Fermat-Euler theorem can potentially be used to reduce the higher powers of $x$. – Mark Bennet Oct 08 '20 at 17:25

1 Answers1

0

Here’s a trick that helps when your modulus $m$ is composite (for example, in your example, $m=45=5\cdot 9$).

Suppose $P(x)$ is some polynomial and the modulus $m=ab$ is composite, and you wish to solve the congruence

$$P(x) \equiv 0 \pmod m \tag{i}$$

It follows that any solution $x$ to this congruence also satisfies

$$P(x) \equiv 0 \pmod a \tag{ii}$$

To find the solutions to this equation by brute force, you only need to test $a$ numbers. Once you’ve found those solutions, you know that every solution to (i) must take the form $x=ay+x’$ where $x’$ is a solution to (ii), and $y$ ranges from $0$ to $b$. Now you only need to check $b$ possible values of $x$ in (i).

So if you’re dealing with a composite modulus $m=ab$, you can use this method to reduce the number of brute force checks from $ab$ to $a+b$. (In your example, you would only need to make $5+9 = 14$ calculations rather than $45$.)

When $m$ is prime, on the other hand...

Franklin Pezzuti Dyer
  • 39,754
  • 9
  • 73
  • 166