1. ## how to show that a quadratic congruence is solvable

Verify that $x^2 \equiv 10 \mbox{ (mod 89)}$ is solvable. Thanks in advance!

2. Originally Posted by rsvp mx
Verify that $x^2 \equiv 10 \mbox{ (mod 89)}$ is solvable. Thanks in advance!
$(\frac{10}{89})=(\frac{2}{89})(\frac{5}{89})$

$(\frac{2}{89})=(-1)^\frac{89^2-1}{8}=1$

$(\frac{5}{89})=(\frac{89}{5})(-1)^{\frac{4}{2}\frac{88}{2}}$

$= (\frac{-1}{5})$

$= (-1)^\frac{5-1}{2}$

$= 1$

Hence $(\frac{10}{89})=1$

So $x^2 \equiv 10 \mbox{ (mod 89)}$ is solvable.

3. Originally Posted by rsvp mx
Verify that $x^2 \equiv 10 \mbox{ (mod 89)}$ is solvable. Thanks in advance!

This follows at once from the properties of Legendre's symbol and Gauss' Quadratic Reciprocity Law.
But if you haven't yet studied this or if you can't use it then I know of no methods but "wise" brutal force: for example, it's not too hard to

check that $5=19^2\!\!\pmod {89}$ (just taking multiples of 89 and checking which one summed to 5 is a perfect square. In this case it was $89\cdot 4=356=361-5=19^2-5$)

Then, as $2 = 36\cdot 5\!\!\pmod {89}=(6\cdot 19)^2\!\!\pmod {89}=25\!\!\pmod {89}\,,\,\,we\,\,get$ $10=2\cdot 5=(25\cdot 19)^2=30^2\!\!\pmod {89}$

Tonio

4. Thank you all so much! My understanding of the Legendre symbol was a little unclear, but not anymore

So if I wanted to show that for what primes p would make $x^2 \equiv 13 \mbox{ (mod p)}$ solvable, I would set $(\frac{13}{p}) = 1$.

Then, $(\frac{13}{p}) = (\frac{p}{13})(-1)^{\frac{p-1}{2} * \frac{13-1}{2}} = (\frac{p}{13})$

Besides "brute force", how can I find values of p that satisfy the equation $(\frac{p}{13}) = 1$?