Showing a polynomial has a solution in $ \mathbb{Z}/n\mathbb{Z} $

So we consider the equation in $\mathbb Z/q \Bbb Z$ for $q$ a prime. Then, since that is a field, the given polynomial has a root in this field if and only if at least one of the individual factors has a root, if and only if at least one of $2,17$ or $34$ is a quadratic residue mod $q$.

We know that $l$ is a quadratic residue mod $q$ if and only if $l^{\frac{q-1}{2}} \equiv 1 \pmod{q}$ (and $l$ is a quadratic non-residue if and only if $l^{\frac{q-1}2} \equiv -1 \pmod{q} $). Therefore, from here one may conclude that the product of two non-residues is a residue mod $q$.

And therefore, since $34 = 2 \times 17$, it so happens that one of $2,17$ or $34$ must be a quadratic residue mod $q$. Which answers the question for primes.


To go to prime powers, use Hensel's lifting lemma , (a simpler version of) which says that given a polynomial $f$ with integer coefficients and $k \geq 1$, if there is some $r$ such that $f(r) \equiv 0 \mod p^k$ and $f'(r) \not \equiv 0 \mod p$ then there is some $s \equiv r \mod p^k$ such that $f(s) \equiv 0 \mod p^{k+1}$. In other words, we may lift simple roots of a polynomial from a prime power to a higher prime power.

Over here, we claim that $f$ has a solution mod $p^k$ for every prime $p \neq 2$. For this, we consider these primes divided into three not necessarily disjoint classes : those for which $2$ is a quadratic residue, those for which $17$ is a q.r, and those for which $34$ is a q.r.

We will show that if $2$ is a q.r. mod $p$ then it is so mod $p^k$ for every $k \geq 1$, via Hensel lemma. This shows that $f$ has a solution mod $p^k$ for every $k \geq 1$ and for $p$ belonging to the first class.

Now, if $g(x) = x^2 - 2$, then $g$ has a solution mod $p^k$ by induction, with base case $k=1$ the definition of $2$ being a q.r. Let $g(r) \equiv 0 \mod p^k$. Note that $g'(r) = 2r$, which is equivalent to $0$ mod $p$ only if $r = p$, wwhich cannot happen as then $g(r) \not \equiv 0 \mod p$. Hence, by Hensel lifting there is a solution mod $p^{k+1}$ of $g$, and hence of $f$.

Do this for $g(x) = x^2-17$ and $g(x) = x^2 - 34$, there is no difference really.

Therefore, we have covered all prime powers bar $2^k$.

For $2^k$ we want to show that $17$ is a quadratic residue mod $2^k$ for every $k$. For this I struggled so you must see reuns' answer.

EDIT : As reuns points out below, Hensel's lemma has a generalization for multiple derivatives. A slightly different lemma is here in Arturo Magidin's answer. If you 'd like to prove it yourself, try reuns' hint below for a different question : the same "Taylor" logic applies here.

Suppose $f(x)$ is a polynomial with integral coefficients, and there is an $a$ such that $f(a) \equiv 0 \pmod{p^j}$. Suppose that $\tau$ is the largest power of $p$ with $p^\tau$ dividing $f'(a)$. If $j \geq 2\tau + 1$, then there is a $b$ such that $f(b) \equiv 0 \pmod{p^{j+1}}$.

With this result, let us show that $x^2 - 17$ has a solution mod $2^k$ for every $k$. We have seen from $k=1$ to $k=5$ that this is the case. Now, let's go for induction.

Suppose $a^2 -17 = 0$ mod $2^k$ with $k \geq 5$. Then, note that $a$ is odd, so the derivative is $2a$,which gives $\tau = 1$. Now, $2 \tau + 1 = 3$ and $k > 5$, so the lemma applies and gives us $b$ with $b^2 - 17 = 0$ mod $2^{k+1}$.

Finally, noting that $f(b) = 0$ mod $2^{k+1}$ gives us the result.


To finish the matter, consider $n = \prod q_i$ where $q_i$ are prime powers co-prime to one another. By above, there are $x_i \mod q_i$ such that $f(x_i) \equiv 0 \mod q_i$. Now, let $M$ solve $M \equiv x_i \mod q_i$ for each $i$, then $f(M) \equiv f(x_i) \mod q_i$ for all $i$, so $f(M)$ is a multiple of $q_i$ for all $i$, hence of $n$ i.e. $f(M) \equiv 0 \mod n$, as required.


  • For $p$ odd: if $p=17$ let $s=2 \equiv 6^2 \bmod 17$.

    Otherwise let $g$ be a generator of $ \Bbb{Z}/p \Bbb{Z}^\times$, product of quadratic non-residues are quadratic residues, thus one of $s=2,17,34$ is a square $\bmod p$ so that $s = g^{2a} \bmod p$

    • $g^{p^{k-1}}$ is of order $p-1$ in $\Bbb{Z}/p^k\Bbb{Z}$. Let $t = s g^{-2 a p^{k-1}}$, it is $\equiv 1 \bmod p$ thus $t$ is in the subgroup $(1+p \Bbb{Z}) / (1+p^k\Bbb{Z})$, this group has $p^{k-1}$ elements so $x \mapsto x^2$ is an isomorphism and all its elements are square, thus $t = u^2 \bmod p^k$ and $s = (ug^{a p^{k-1}})^2 \bmod p^k$.
  • For $p =2$: go to the ring of formal power series $$(1+2^2 x)^{-1/2} = \sum_{n=0}^\infty {-1/2 \choose n} 2^{2n} x^n= \sum_{n=0}^\infty 2^{-2n}(-1)^n {2n \choose n} 2^{2n} x^n \in \Bbb{Z}[[x]]$$ $$\implies (1+2^2 x)(\sum_{n=0}^\infty {2n \choose n}(-1)^n x^n)^2=1\in \Bbb{Z}[[x]]$$ Look at the quotient ring $\Bbb{Z}[[x]]/(x-2^2,2^k) \cong \Bbb{Z}/2^k \Bbb{Z}[x]/(x-2^2)\cong \Bbb{Z}/2^k \Bbb{Z}$, the reduction of the identity $(1+2^2 x)(\sum_{n=0}^\infty {2n \choose n}(-1)^n x^n)^2=1$ is $17(\sum_{n=0}^{k-1}{2n \choose n}(-1)^n 2^{2n} )^2 = 1 \bmod 2^k$ thus $17$ is a square in $ \Bbb{Z}/2^k \Bbb{Z}^\times$.