5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ "$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. $\endgroup$ – JMoravitz Oct 17 '16 at 4:05
  • $\begingroup$ @JMoravitz My bad. I just fixed it. $\endgroup$ – Cure Oct 17 '16 at 4:08
  • $\begingroup$ 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. $\endgroup$ – Martin Sleziak Oct 17 '16 at 5:36
  • $\begingroup$ @Martin seems to have typoed 389 into 329. $\endgroup$ – Gerry Myerson Oct 17 '16 at 6:29
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ He fixed it so that it is no longer trivial. $\endgroup$ – AlgorithmsX Oct 17 '16 at 4:22
  • $\begingroup$ 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}$ ? $\endgroup$ – Cure Oct 17 '16 at 20:32
  • $\begingroup$ 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$ $\endgroup$ – Ross Millikan Oct 17 '16 at 20:37
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I'm sorry, but could you elaborate further? I don't see how this follows from quadratic reciprocity. $\endgroup$ – Cure Oct 17 '16 at 11:01
  • $\begingroup$ Quadratic reciprocity tells you that 2 and 3 aren't, but 5 is, square modulo 389. Then group theory (or, if you'd rather, the existence of a primitive root) tells you the product of two nonsquares is a square, as is the product of two squares. $\endgroup$ – Gerry Myerson Oct 17 '16 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.