Showing a polynomial has a solution in $ \mathbb{Z}/n\mathbb{Z} $ Show that the following equation has a solution in $ \mathbb{Z}/n\mathbb{Z} $ for every $n > 1$:
\begin{align}
(x^2-2)(x^2-17)(x^2-34)=0
\end{align}
I know you can cite Chinese Remainder Theorem so it suffices to find solutions for powers of primes. Then you can somehow choose to consider only solutions $\pmod{2^e}$ * or $\pmod{8}$?* and $\pmod{p}$ for odd $p$. But I don't know how to get there or farther to solve the problem. I know the Legendre symbol can be used since $34 = 2 \cdot 17$.
 A: 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.
A: *

*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$.
A: *

*Pick a prime $p$ dividing $n$. For this $p$, check the values of the Legendre symbol $(2|p),(17|p),(34|p)$. 

*If we show anyone of the above is a quadratic residue $\pmod{p}$, then we are done. 

*Assume $(2|p)=-1$, then either $(17|p)=1$ or $(17|p)=-1$. If $(17|p)=1$, we are done. If $(17|p)=-1$, then note that $(34|p)=(2|p) \cdot (17|p) = -1 \times -1 = 1$, which says $34$ is a quadratic residue for that prime $p$.
A: For $p$ odd we can in fact can show that $a$ [and in [particular $a=2,34,17$] is a square in $\mathbb{Z}/p\mathbb{Z}$ then $a$ is a square in $\mathbb{Z}/p^r\mathbb{Z}$, for any positive integer $r$.
Indeed, use induction on $r$. Let $A=a+\sum_{i=1}^{r}a_ip^i$, for any choice you please of $a_i$ w $a_i \in \{0,1,\ldots, p-1\}$ that is. Let $C$ be such that $C^2 \equiv A$ mod $p^r$. Then $(C+c_rp^r) \equiv_{p^{r+1}} C^2+2c_rp^r \equiv_{p^{r+1}} (A+sp^r)+2c_rp^r$ for some $s,c_r \in \{0,1,\ldots, p-1\}$. So pick $c_r$ so that s+2c_r \equiv 0$ mod $p$.
And 17 is always a square mod $2^r$; use induction on $r$. Indeed, let $C^2 \equiv 17$ mod $2^r$. Then either $[C + 2^{r-1}]$ or $C$ squares to 17 mod $2^{r+1}$ [for $r \ge 4$].
Anyway, this is to add to the other answers, in the case that the OP does not want to use Hansel's Lemma and wants to bypass by elementary methods.
