# Product of three primes that is a square modulo 389

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?

• "$n$ is a square modulo $n$"? Isn't $n=0$ modulo $n$ and trivially $0=0^2$?. Something seems very off about the question statement. – JMoravitz Oct 17 '16 at 4:05
• @JMoravitz My bad. I just fixed it. – Cure Oct 17 '16 at 4:08
• Since $389$ is a prime, you just need to get that $\left(\frac n{329}\right)=1$. You could try to use some basic properties of Legendre symbol. – Martin Sleziak Oct 17 '16 at 5:36
• @Martin seems to have typoed 389 into 329. – Gerry Myerson Oct 17 '16 at 6:29

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}$
• Any particular reason to choose those numbers? Say, for example, if I run an algorithm that squares prime numbers module 389, can't I pick any three of those numbers and reach a similar conclusion? For example, $13\equiv 169^2$, $17\equiv 289^2$, $23\equiv 140^2$. Isn't then $13\cdot 17\cdot 23 \equiv (169\cdot 289\cdot 140)^2 \pmod {389}$ ? – Cure Oct 17 '16 at 20:32
• I just scanned down the list for primes. I know most of the primes below $100$, so these were easy to find. Any three primes would work fine. In your example the square goes the wrong way. You don't want to square primes, you want the square of some number to be prime \bmod 389$– Ross Millikan Oct 17 '16 at 20:37 By quadratic reciprocity, 2 and 3 are not squares modulo 389, but 5 is, so you can take$n=30\$.