Exercise 5.4.11 (The congruence $(x^2 - 17)(x^2 - 19)(x^2 -323) \equiv 0 \pmod m$ has always a solution)

Proof. Let $p$ be any prime number.

• Suppose that $p\ne 2,p\ne 17,p\ne 19$.

  If $\left(\frac{17}{p}\right)=-1$ and $\left(\frac{19}{p}\right)=-1$, then $\left(\frac{323}{p}\right)=\left(\frac{17}{p}\right)\left(\frac{19}{p}\right)=1$. This shows that $\left(\frac{17}{p}\right)=1$, or $\left(\frac{19}{p}\right)=1$, or $\left(\frac{323}{p}\right)=1$, thus at least one of the congruences $x^2-17\equiv 0(\mathit{mod}p)$, $x^2-19\equiv 0(\mathit{mod}p)$, $x^2-323\equiv 0(\mathit{mod}p)$ has an integer solution $x_1$.

  Suppose that $x_1^2\equiv 17(\mathit{mod}p)$. Then $x_1\not\equiv 0(\mathit{mod}17)$, since $p\ne 17$. Write $f(x)=x^2-17$. Then $f^{\prime }(x_1)=2x_1\not\equiv 0(\mathit{mod}p)$ since $p$ is odd and $x_1\not\equiv 0(\mathit{mod}p)$. By Hensel’s lemma (Theorem 2.23), for all $k\ge 1$, there exists some $x_k$ such that $x_k^2\equiv 17(\mathit{mod}{p}^k)$. Then $F(x_k)\equiv 0(\mathit{mod}{p}^k)$. We obtain similar results if $x_1^2-19\equiv 0(\mathit{mod}p)$ or $x_1^2-323\equiv 0(\mathit{mod}p)$. Therefore, there is some integer $x$ such that

  $$F(x)\equiv 0(\mathit{mod}{p}^k)(k\ge 1).$$

• Suppose that $p=2$. There are four solutions $a\in \{1,3,5,7\}$ to the congruence $x^2\equiv 17(\mathit{mod}{2}^3)$. By Theorem 2.24, where $p^1\mid \mid f^{\prime }(a)=2a$, so $\tau =1$ and $j\ge 2\tau +1$ for $j\ge 3$, we obtain for all $k\ge 3$ exactly 4 solutions to the congruence $x^2\equiv 17(\mathit{mod}{2}^k)$. Therefore, there is some integer $x$ such that

  $$F(x)\equiv 0(\mathit{mod}{2}^k)(k\ge 1).$$

• Suppose that $p=17$. Since $\left(\frac{19}{17}\right)=1$, there are solutions to the congruence $x^2\equiv 19(\mathit{mod}17^k)$ for all $k\ge 1$, by Hensel’s lemma. Similarly, since $\left(\frac{17}{19}\right)=1$, there are solutions to $x^2\equiv 17(\mathit{mod}19^k)$.

In conclusion, for any prime number $p$, and for any positive integer $k$, there is some integer $x$ such that

Let $m$ be any integer such that $m>1$. Let $m=p_1^{a_1}\cdots p_l^{a^l}$ be the decomposition of $m$ into prime factors. We have proved that there are integers $x_1,x_2,\dots ,x_l$ such that

By the Chinese Remainder Theorem, there exists some integer $x$ such that $x_i\equiv x(\mathit{mod}{p}_i^{a_i})$ for all $i$. Then

(If $m=1$, every $x$ satisfies $F(x)\equiv 0(\mathit{mod}1)$.)

In conclusion, for every positive integer $m$, the congruence $F(x)\equiv 0(\mathit{mod}m)$ has a solution. □