Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
You mean for which $p$ there exists an $a$ such that $a^2=34 \mod p$ ? $p=47$. But maybe I misunderstood your question. –  Raskolnikov Dec 12 '10 at 12:19
    
@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. –  yunone Dec 12 '10 at 12:33
    
I understand, I was just trying to figure out if I got the question correctly. –  Raskolnikov Dec 12 '10 at 12:36
    
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. –  yunone Dec 12 '10 at 12:37
2  
@xdfm: Your method is fine. And I am unable to think of other (better) ways to solve this problem. –  user17762 Dec 12 '10 at 13:59

1 Answer 1

up vote 8 down vote accepted

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

share|improve this answer
    
Whoops, you're right, my mistake. I didn't see the negative in my scratchwork before posting. –  yunone Dec 12 '10 at 18:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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