# Method to find $(x_1, x_2,…,x_n)$ s.t. polynom $p(x_1, x_2,…,x_n) \bmod m = 0$

I have a natural number $m$, and a polynomial $p: \mathbb{Z}^n \rightarrow \mathbb{Z}$, and I need to find a set $(x_1, x_2,...,x_n)$ so that $p(x_1, x_2,...,x_n) \bmod m = 0$.

First: Does every non-constant polynomial have such a set? And more importantly: Does there exist an (efficient) procedure to determine it, in case a set exists?

-
No, a solution does not always exist. Take $p(x) = 2x+1$, and $m=2$; or $p(x)=x^2+x+1$, again with $m=2$. For a two variable example, take $p(x,y) = x^2+y^2+x+y+1$ with $m=2$; since $(x^2+x)+(y^2+y)$ is always even, $p(x,y)$ is never even. –  Arturo Magidin Jan 24 '11 at 22:16
Thank you for that quick answer. That restricts the question for the procedure to the case that such set exists. (I edited the question accordingly) –  Mike B. Jan 24 '11 at 22:31
They objects are usually called "polynomials" in English, and not "polynoms". –  Arturo Magidin Jan 25 '11 at 1:29
A partial answer to the first question: If $m$ is prime and the number of variables $n$ is bigger than the degree of the polynomial $p$ then by Chevalley's Theorem the number of zeros is divisible by $p$. This might be useful if you already know a solution as in the case when there is no constant term. –  Esteban Crespi Jan 25 '11 at 11:21

## 1 Answer

If I am not mistaken, this is not known. When $m = 2$ this problem is equivalent to Boolean satisfiability (SAT for short), which is known to be NP-complete. This is because one can represent logical operations as polynomial operations on the finite field $\mathbb{F}_2$ (with $0$ being false and $1$ being true) as follows:

$$\neg x = 1 - x, x \text{ and } y = xy, x \text{ or } y = x + y + xy.$$

It follows that any Boolean expression in $n$ Boolean variables $x_1, ... x_n$ can be written as a polynomial over $\mathbb{F}_2$, and finding solutions is equivalent to finding a non-satisfying assignment for the Boolean expression (so replacing the expression with its negation we get the usual form of SAT). So the question of whether there exists a polynomial-time algorithm for solving this problem is equivalent to P vs. NP.

I was mistaken! Well, in any case, this paper might be relevant.

-
The size of the polynom resulting from a formula in CNF is not bounded polynomially, therefore this reduction is not in $P$. (Add: The arithmetization of $x \vee y$ is $x + y - xy$) –  Mike B. Jan 24 '11 at 23:36
@Mike: whoops. Very good point. –  Qiaochu Yuan Jan 24 '11 at 23:52