I'm going through an old final from 2003 on MIT's Opencourseware, and problem 6b is giving me a little trouble.

It asks for which primes $p$ is $34$ a square modulo $p$. I approached it like this:


I figure I can break it down into cases where $p\equiv 1,3,5,7\pmod{8}$. So if $p\equiv 1\pmod{8}$, then $(2|p)=1$, and thus I want $(p|17)=1$ as well. I calculated all the squares modulo $17$, and found them to be $1,2,4,8,9,13,15,16$. I suppose I could then go through all cases where $p\equiv 1\pmod{8}$, and $p\equiv 1,2,4,8,\dots\pmod{17}$, and then use the Chinese remainder theorem to find what $p$ is congruent to modulo $8\cdot 17$, but this seems very tedious to do for each case. First of all, is my method correct, and also, is there a better way to solve this question? Thank you.

  • $\begingroup$ You mean for which $p$ there exists an $a$ such that $a^2=34 \mod p$ ? $p=47$. But maybe I misunderstood your question. $\endgroup$ – Raskolnikov Dec 12 '10 at 12:19
  • $\begingroup$ @Raskolnikov, I want to be able to describe all such primes up to saying what they are congruent to modulo some number. This type of answer is given in problem 2 of midterm 2 also on the MIT's OCW. $\endgroup$ – yunone Dec 12 '10 at 12:33
  • $\begingroup$ I understand, I was just trying to figure out if I got the question correctly. $\endgroup$ – Raskolnikov Dec 12 '10 at 12:36
  • $\begingroup$ Ah ok, thanks for taking a look. I know the first time I read it I wasn't quite sure what type of answer was wanted. $\endgroup$ – yunone Dec 12 '10 at 12:37
  • 2
    $\begingroup$ @xdfm: Your method is fine. And I am unable to think of other (better) ways to solve this problem. $\endgroup$ – user17762 Dec 12 '10 at 13:59

You have all that you need right there:


So if $p \equiv \pm 1 \pmod{8}$ then $p$ must be a quadratic residue mod 17, otherwise it must be a quadratic non-residue mod 17. (But delete 14 from your list first!)

  • $\begingroup$ Whoops, you're right, my mistake. I didn't see the negative in my scratchwork before posting. $\endgroup$ – yunone Dec 12 '10 at 18:14

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.