Use quadratic reciprocity to decide whether the following congruences are solvable

Question

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.

Answer 1

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.

Answer 2

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}$

Answer 3

$$\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.