Product of three primes that is a square modulo 389

Question

Find $n$ such that

• $n$ is a product of three prime numbers and
• $n$ is a square modulo $389$.

I'm not sure how to begin with this problem. Do I have to use an algorithm involving quadratic reciprocity? How can I apply it?

Answer 1

I just made a spreadsheet squaring numbers $\bmod 389$ and note that $11 \equiv 20^2,67\equiv 49^2,79\equiv 63^2$ are all squares $\bmod {389}$. So $11 \cdot 67 \cdot 79\equiv (20 \cdot 49 \cdot 63)^2 \pmod {389}$

Answer 2

By quadratic reciprocity, 2 and 3 are not squares modulo 389, but 5 is, so you can take $n=30$.