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

[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.