Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

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$.

share|improve this answer
add comment

$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

share|improve this answer
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.