# 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. Commented Jan 24, 2011 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) Commented Jan 24, 2011 at 22:31
• They objects are usually called "polynomials" in English, and not "polynoms". Commented Jan 25, 2011 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. Commented Jan 25, 2011 at 11:21

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.
• 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$) Commented Jan 24, 2011 at 23:36