Finding Prime P Such That 3 is a Quadratic Residue (mod p)

[shmoe]

So the question becomes: Primes p such that 3 is a QR mod p are such that (3/p) = +-(1).

?? (3/p)=1 <=> 3 is a QR mod p.

You can find the legendre symbol in all these 4 cases now right? These cases completely cover all possible odd primes greater than 3. There's not much more to do, you might convert these cases into mod 12 conditions, eg. case 1 is p=1 mod 4 and p=1 mod 3, by the Chinese remainder theorem, p=1 mod 12, and so on.

 

[Oxymoron]

Posted by Shmoe

You can find the legendre symbol in all these 4 cases now right?

Indeed I can...

Case 1. (3/p) = 1
Case 2. (3/p) = -1
Case 3. (3/p) = -1
Case 4. (3/p) = 1

Im using the fact that if the Legendre symbol (3/p) = 1 then by definition 3 is a QR mod p.

But how can (3/p) = 1 and -1 at the same time?

 

[shmoe]

But how can (3/p) = 1 and -1 at the same time?

It can't and it doesn't. The 4 cases are all completely seperate.

 

[Oxymoron]

Case 1. p=1(mod 12)
Case 2. p=2(mod 12)
Case 3. p=3(mod 12)
Case 4. p=6(mod 12)

If p=1(mod 12) then p=13,73,97,193,241,etc...
If p=2(mod 12) then there are no primes. Since x=2(mod 12), x will always be even.
If p=3(mod 12) then there are no primes. Because 3 will divide them all.
If p=6(mod 12) then once again, no primes, because 3 divides 6.

 

[shmoe]

Case 1. p=1(mod 12)
Case 2. p=2(mod 12)
Case 3. p=3(mod 12)
Case 4. p=6(mod 12)

Check these again! if p=2 mod 12 then you do not have p=1 mod 4. Have you seen the chinese remainder theorem that tells you about solutions to systems of linear congruences?

 

[Oxymoron]

Um, yes. But I am dumb remember. Let me check again, one sec...

 

[Oxymoron]

Case 1. p=1(mod 12)
Case 2. p=5(mod 12)
Case 3. p=13(mod 12) => p=1(mod 12)
Case 4. p=17(mod 12) => p=5(mod 12)

Do these look any better?

 

[shmoe]

Keep checking. Show you work how you got these.

 

[Oxymoron]

I used the following theorem:

To solve p\equiv a(\mod m) and p\equiv b(\mod n) simultaneously, a corollary to the Chinese Remainder Theorem says the solution is given by

p \equiv a\left(\frac{m\times n}{m}\right)p_1 + b\left(\frac{m\times n}{n}\right)p_2(\mod m\times n)

where p_1(\mod m) is the solution to

\left(\frac{m\times n}{m}\right)p \equiv 1(\mod m)

and p_2(\mod n) is the solution to

\left(\frac{m\times n}{n}\right)p \equiv 1(\mod n)

 

[Oxymoron]

1. p=1 mod 4 and p=1 mod 3
2. p=1 mod 4 and p=2 mod 3
3. p=3 mod 4 and p=1 mod 3
4. p=3 mod 4 and p=2 mod 3

So for case 2
p=1(3)p + 2(4)p(mod 12)

p=3p + 2p(mod 12)
p=5p(mod 12)

 

[shmoe]

That's a complicated way of doing it, but ok. Your case 3 and 4 didn't pan out.

Don't lose the meaning behind the chinese remainder theorem. More important than being able to plug in the numbers is that it is saying for a system of congruences like

p=a mod 4
p=b mod 3

there is a unique solution for p mod 12 that satisfies this. You don't have to go through all your formulas to solve for p mod 12 here, you can pretty much do it by staring. e.g. in case 2 we want to find something mod 12 that is congruent to 1 mod 4 and 2 mod 3. The 1 mod 4 restriction means p is 1, 5, or 9 mod 12. Which of these is congruent to 2 mod 3? Just 5, the chinese remainder theorem tells us this is in fact unique, and the only solution here.

You can also check your answers by going back to your original equations. In case 3 you claimed p=1 mod 12. But 1 is not equal to 3 mod 4, so this can't be correct.

 

[Oxymoron]

Of course! The unique bit. I ignored that part of the theorem.

So case 3.
p=7(mod 12)

because we are looking for something mod 12 congruent to 3 mod 4 and 1 mod 3. 3 mod 4 restricts p to 3,7 and 11. But only 7 is congruent to 1 mod 3.

Case 4.
p=11(mod 12)
by the same argument

So p = 5, 7 and 11.

Let me know if this is right.

 

[Oxymoron]

For the first case.

p=1(mod 4) => p=1,5,9,13.

The only one of these primes congruent to 1(mod 3) is 9.

So for the first case, p=9(mod 12).

 

[Oxymoron]

So now I have all my primes which satisfy our four cases:

p=5,7,9,11

So can I then instantly say here that if p={5,7,9,11} then 3 is a QR (mod p). Or do I have some more work to do before I can claim this?

 

[shmoe]

So case 3.
p=7(mod 12)

because we are looking for something mod 12 congruent to 3 mod 4 and 1 mod 3. 3 mod 4 restricts p to 3,7 and 11. But only 7 is congruent to 1 mod 3.

Case 4.
p=11(mod 12)
by the same argument

Ok, these are good.

So p = 5, 7 and 11.

Where did this come from?

For the first case.

p=1(mod 4) => p=1,5,9,13.

The only one of these primes congruent to 1(mod 3) is 9.

9 isn't prime and it isn't congruent to 1 mod 3.


Recap, you found:

Case 1. (3/p) = 1
Case 2. (3/p) = -1
Case 3. (3/p) = -1
Case 4. (3/p) = 1

and these cases corresponded to:

Case 1. p=1 mod 12
Case 2. p=5 mod 12
Case 3. p=7 mod 12
Case 4. p=11 mod 12

 

[Oxymoron]

Man I make dumb typos! Where there is a 9 I meant 7.

Posted by Shmoe

Where did this come from?

Well, that is meant to correspond to the four cases.

Case 1. p=1 mod 12
Case 2. p=5 mod 12
Case 3. p=7 mod 12
Case 4. p=11 mod 12

but I was writing it quick (and stoopid), like p=1,5,7,11(mod 12).

Yep, so I have the four cases. So are these the prime numbers such that 3 is a QR mod p?

 

[shmoe]

Yep, so I have the four cases. So are these the prime numbers such that 3 is a QR mod p?

The ones that have (3/p)=1 are.

 

[Oxymoron]

Well only (3/11) = 1. All the others equal -1.

EDIT: Except p=1

 

[shmoe]

Well only (3/11) = 1. All the others equal -1.

Didn't you also find if p=1 mod 12 then (3/p)=1??

The cases aren't the numbers p=1, 5, 7, and 11, remember they consist of all primes in these residue classes mod 12.

 

[Oxymoron]

Actually I did, but is 1 a prime?

 

[shmoe]

Actually I did, but is 1 a prime?

No, not by the usual definition of prime. But there are primes that are congruent to 1 mod 12 (infinitely many of them in fact)

 

[Oxymoron]

The question is find primes such that 3 is a QR mod p. So 3 is a QR mod p where p must be congruent to 1 or 11 mod 12.