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?
The equation $F(x) \equiv 0 \pmod m$ has integer solution for x
2 Answers
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
-
0@user6312: thanks, you are of course right (my answer was really just a sketch - one should check applicability of Hensel's lemma) – 2011-04-13