Use quadratic reciprocity to decide whether the following congruences are solvable The first one is: $x^2 \equiv109(\mod157)$.
The second one is: $x^2 \equiv141(\mod181)$
I tried using some properties but didn't really get anywhere... $ \frac{109}{157} = \frac{157}{109} = \frac{157}{1 \mod 2} \space \text {and} \space 157 \mod{109} = 48 \mod{109}$. If someone could show me how to solve the first, I think I should be able to do the second.
Many thanks.
 A: You start off OK, but I'm not sure what happens later
$\begin{align}
\left(\dfrac{109}{157}\right) 
& =\left(\dfrac{157}{109}\right) &&\text{(both 109 and 157 are $\equiv 1\bmod 4$)} \\
& =\left(\dfrac{48}{109}\right) &&\text{($157 \equiv 48\bmod 109$)} \\
& =\left(\dfrac{3}{109}\right) &&\text{(16 is square)} \\
& =\left(\dfrac{109}{3}\right) &&\text{($109 \equiv 1\bmod 4$)} \\
& =\left(\dfrac{1}{3}\right) &&\text{($109 \equiv 1\bmod 3$)} \\
& =1 &&\text{(1 is square)} \\
\end{align}$
A: We first have to see whether $109$ is a quadratic residue modulo $157$. Using the Legendre symbol; we have $$\Big(\frac{109}{157}\Big)=\Big(\frac{157}{109}\Big)=\Big(\frac{48}{109}\Big)=\Big(\frac{16}{109}\Big)\Big(\frac{3}{109}\Big)=\Big(\frac{3}{109}\Big)=1,$$ where we used, in order


*

*Quadratic reciprocity; $109\equiv 1\bmod 4$.

*Periodicity; $157\equiv 48\bmod 109$.

*Multiplicativity; $48=3\cdot 16$.

*The Legendre symbol of $(x^2/p)=1$ for all $x$.

*The rule for $(3/p)$; $109\equiv 1\bmod 12$.


Since $109$ is a quadratic residue modulo $157$; the congruence $x^2\equiv 109\bmod 157$ is solvable.
A: $$\left(\frac{109}{157}\right)=\left(\frac{157}{109}\right)$$ by quadratic reciprocity and $$=\left(\frac{48}{109}\right)=\left(\frac{3}{109}\right)$$ as $16$ is a perfect square.
Again, 
$$\left(\frac{3}{109}\right)=\left(\frac{109}{3}\right)=\left(\frac{1}{3}\right)=+1$$ thus the first congruence is solvable.
