# The equation $F(x) \equiv 0 \pmod m$ has integer solution for x

Let $F(x)=(x^2-17)(x^2-19)(x^2-323)$ and let $m$ be a positive integer. How can one show that the equation $F(x) \equiv 0 \pmod m$ has an integer solution?

-

For $p=2$ and using Hensel's lemma, you can show that for odd $k$, $k$ is a square mod $2^n$ for $n\ge 3$ if and only if $k$ is a square mod $8$, that is when $k = 1 \mod 8$. Here this tells us that $17$ is always a square mod $2^n$, so you can always find some $x$ for which $(x^2-17) = 0 \mod 2^n$.

For odd prime $p$, Hensel's lemma makes things simpler : if $p$ doesn't divide $k$, $k$ is a square mod $p^n$ if and only if $k$ is a square mod $p$, and in $(\mathbb{F}_p^*,\times)$, the subgroup of squares, ${\mathbb{F}_p^*}^2$, is a subgroup of index 2, and $\mathbb{F}_p^* / {\mathbb{F}_p^*}^2 = \mathbb{Z}/2\mathbb{Z}$ This means that if $k_1$ and $k_2$ are not squares in $\mathbb{F}_p^*$ , then $k_1 k_2$ is a square in $\mathbb{F}_p^*$.

Thus for all primes $p$ other than $2,17,19$, one or all three of $17, 19, 17*19$ will always be a square mod $p$, so will be a square mod $p^n$.

And finally, we can check that $19$ is a square mod $17$ (and mod $17^n$) and $17$ is a square mod $19$ (and mod $19^n$).

It's not necessary, but using the quadratic reciprocity law, you can even predict in which case you are according to $p \mod 4*17*19$.

-

$17\times 19=323$. If $m=p$ is a prime then $\bigl(\frac{17}{p})\bigl(\frac{19}{p})=\bigl(\frac{323}{p})$, hence at least one of $17,19,323$ is a square modulo $p$.

If $m=p^n$ is a power of a prime. Use a solution of $x^2=k$ modulo $p$ (for $k$ one of $17,19,323$) and extend it to a solution modulo $p^n$ (see Hensel's lemma).

Finally if $m$ is a product of powers of primes, use solutions modulo those indidual powers of primes and then Chinese remainder theorem

-
With these numbers, everything works out fine. But look at the similar-looking $(x^2-5)(x^2-7)(x^2-35)\equiv 0$ modulo $2^k$ where $k \ge 5$. There is no solution, because the $x^2-5$ term can contribute at most two $2$'s and the other two terms can only contribute one each. (With $17$, the prime $2$ causes no problem, since $17 \equiv 1 \pmod{8}$.) – André Nicolas Apr 13 '11 at 13:07
@user6312: thanks, you are of course right (my answer was really just a sketch - one should check applicability of Hensel's lemma) – user8268 Apr 13 '11 at 13:59