3
$\begingroup$

Is $x^2 ≡ 295$ (mod 2717) solvable?

-Having a tough time with this problem, currently covering a section on Quadratic Reciprocity Law of Gauss. After coming back to my professor, his hint was to consider 2717 ≡ 11*13*19. This wasn't much help unfortunately, any help is really appreciated.

$\endgroup$
3
$\begingroup$

Solving for $x^2\equiv 295\pmod{2717}$, you can instead solve the system for $\begin{cases}x^2\equiv 295\pmod{11}\\x^2\equiv 295\pmod{13}\\x^2\equiv 295\pmod{19}\end{cases}$

Simplifying:

$\begin{cases}x^2\equiv 9\pmod{11}\\x^2\equiv 9\pmod{13}\\x^2\equiv 10\pmod{19}\end{cases}$

This implies that $x\equiv 3\pmod{11}$ or $x\equiv 8\pmod{11}$

$x\equiv 3\pmod{13}$ or $x\equiv 10\pmod{13}$

What about for modulo $19$?

Table of remainders squared modulo 19.

The only squares modulo 19 are $1,4,5,6,7,9,11,16,17$

What does quadratic reciprocity and residue theorems have to say about this situation?

$10$ is a quadratic residue only for primes $p\equiv 1,3,9,13,27,31,37,39\pmod{40}$

For each choice of outcome, one may apply the Chinese-Remainder Theorem to find what $x$ is modulo $2717$ uniquely. The results will be different depending on which triple is selected.

But in this case, there is no result for what $x$ can be modulo $19$, so $x$ does not exist.

$\endgroup$

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.