# Existence of Integer Solutions

Prove that there exist integer solutions for the equation x^2 ≡ 251 mod 779. [Note that 779 = 19 · 41.]

I know there are properties that can be used when both 251 and 779 are prime but I'm not sure what to do seeing as 779 is composite

• We have $251\equiv 169\pmod{41}$. – André Nicolas May 18 '14 at 23:59

Solve it for both modulo $19$ and $41$, then conclude by Chinese Remainder Theorem.
Assume $x^2\equiv251\pmod{19}$ and $y^2\equiv251\pmod{41}$, then there is $z\in\Bbb Z$ such that $z\equiv x\pmod{19}$ and $z\equiv y\pmod{41}$, and then consider $z^2-251$.