Verify that $\displaystyle x^2 \equiv 10 \mbox{ (mod 89)}$ is solvable. Thanks in advance!
$\displaystyle (\frac{10}{89})=(\frac{2}{89})(\frac{5}{89})$
$\displaystyle (\frac{2}{89})=(-1)^\frac{89^2-1}{8}=1$
$\displaystyle (\frac{5}{89})=(\frac{89}{5})(-1)^{\frac{4}{2}\frac{88}{2}}$
$\displaystyle = (\frac{-1}{5})$
$\displaystyle = (-1)^\frac{5-1}{2}$
$\displaystyle = 1$
Hence $\displaystyle (\frac{10}{89})=1$
So $\displaystyle x^2 \equiv 10 \mbox{ (mod 89)}$ is solvable.
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 $\displaystyle 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 $\displaystyle 89\cdot 4=356=361-5=19^2-5$)
Then, as $\displaystyle 2 = 36\cdot 5\!\!\pmod {89}=(6\cdot 19)^2\!\!\pmod {89}=25\!\!\pmod {89}\,,\,\,we\,\,get$ $\displaystyle 10=2\cdot 5=(25\cdot 19)^2=30^2\!\!\pmod {89}$
Tonio
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 $\displaystyle x^2 \equiv 13 \mbox{ (mod p)}$ solvable, I would set $\displaystyle (\frac{13}{p}) = 1$.
Then, $\displaystyle (\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 $\displaystyle (\frac{p}{13}) = 1$?