7
$\begingroup$

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:

$$\left(\frac{34}{p}\right)=\left(\frac{2}{p}\right)\left(\frac{17}{p}\right)=(-1)^{(p^2-1)/8}\left(\frac{p}{17}\right).$$

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.

  • 0
    You mean for which $p$ there exists an $a$ such that $a^2=34 \mod p$ ? $p=47$. But maybe I misunderstood your question.2010-12-12
  • 0
    @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](http://ocw.mit.edu/courses/mathematics/18-781-theory-of-numbers-spring-2003/exams/mid2.pdf) 2 also on the MIT's OCW.2010-12-12
  • 0
    I understand, I was just trying to figure out if I got the question correctly.2010-12-12
  • 0
    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.2010-12-12
  • 2
    @xdfm: Your method is fine. And I am unable to think of other (better) ways to solve this problem.2010-12-12

1 Answers 1

8

You have all that you need right there:

$$\left(\frac{34}{p}\right)=\left(\frac{2}{p}\right)\left(\frac{17}{p}\right)=(-1)^{(p^2-1)/8}\left(\frac{p}{17}\right).$$

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!)

  • 0
    Whoops, you're right, my mistake. I didn't see the negative in my scratchwork before posting.2010-12-12