1
$\begingroup$

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?

  • 0
    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.2011-01-24
  • 0
    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)2011-01-24
  • 1
    They objects are usually called "polynomials" in English, and not "polynoms".2011-01-25
  • 0
    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](http://mathworld.wolfram.com/ChevalleysTheorem.html) 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.2011-01-25

1 Answers 1