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

  • $\begingroup$ We have $251\equiv 169\pmod{41}$. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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