Determine if $-42$ is a quadratic residue of $\pmod{61}$

Question

This is what I have so far:

Using Legendre symbol, we have $(\frac{-42}{61})\equiv(\frac{19}{61}).$ Since $\mathrm{gcd}(19,61)=1,$ $(\frac{19}{61})\equiv1.$

Is this correct?

Answer 1

By Euler's Criterion, $\left( \frac{19}{61} \right) \equiv 19^{30} \pmod {61} \equiv (-5)^{15} \equiv -3^5 \equiv 1$ so you are correct.

However, the gcd condition will not always work, for example, take $18$ which by Euler, is not a QR.

Answer 2

The answer happens to be correct, the "method" is not. We have by Quadratic Reciprocity that $(19/61)=(61/19)$. But $61\equiv 4\pmod{19}$, so $(61/19)=(4/19)$.

But $4$ is a perfect square, so $(4/19)=1$.

Remark: Note that $\gcd(7,61)=1$. But $(7/61)=(61/7)=(5/7)=(2/5)=-1$. The fact that $19$ and $61$ are relatively prime has no reals connection with the quadratic character of $19$ modulo $61$.