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

[Oxymoron]

I have this problem I've been looking at for about 6 hours. It requires me to find all primes p such that 3 is a quadratic residue (mod p).

All I could come up with is that every prime p ending in a 1 makes 3 a QR mod p. But this came after using excel and computing all primes. Surely there must be an easier way (assuming that my assumption is correct). The question does give a hint to use the Quadratic reciprocity law, but I have no idea what that is!

 

[devious_]

Looking up that law wouldn't be a bad idea, don't you think?

 

[Oxymoron]

This is my version of the QRL, there may be others written differently.

$$\mbox{Let }p\mbox{ and }q\mbox{ be distinct odd prime numbers. Then}$$

$$(p/q)(q/p) = (-1)^{(p-1)(q-1)/4}}$$

 

[Oxymoron]

The first thing I did was realize that the question was also asking that

$$3 \mbox{ is a Quadratic Residue } \Leftrightarrow 3^{\frac{p-1}{2}} \equiv 1(\mod p)$$

which means that all primes p such that 3 is a QR mod p will be a solution to the above congruence. So I started testing

p=3
$$3^1 = 3 \equiv 0(\mod 3)$$
p=5
$$3^2 = 9 \equiv 4(\mod 5)$$
p=7
$$3^3 = 27 \equiv 6(\mod 7)$$
p=11
$$3^5 = 243 \equiv 1(\mod 11)$$

I was doing all the calculations in excel, and when I filled the columns in, I got equivalent to 1 mod p whenever my prime p ended in a 1.

But I realize this method used only Euler's Criterion, nowhere did I use the QRL.

 

[shmoe]

What did you get for 13? 41? Something is wrong with your calculations if you went this far and ended up with that conclusion.

In any case, a finite number of calculations like this would never be able to prove a general result. It can point towards a general conjecture, but not prove it.

Try using the law of quadratic reciprocity. It let's you turn a question about whether 3 is a quadratic residue mod p to a question about whether p is a quadratic residue mod 3 (and there's a simple congruence critera for this).

 

[AKG]

Let a and b be odd numbers. Then:

(a/b) = (b/a) if a = 1 (mod 4) or b = 1 (mod 4)
...= -(b/a) if a = b = 3 (mod 4)

Also, if p is an odd prime, a and b are integers, then

(a/p)(b/p) = (ab/p)

Of course, you also know that:

(a/p) = ([a modulo p]/p)

So with all these facts, you should be able to find the answer.

 

[Oxymoron]

Posted by Shmoe

In any case, a finite number of calculations like this would never be able to prove a general result. It can point towards a general conjecture, but not prove it.

You're absolutely right, my aim in doing that was to find a pattern which could motivate a possible line of attack in solving it. Unfortunately it didnt work, as we all now know.

Posted by Shmoe

Try using the law of quadratic reciprocity. It let's you turn a question about whether 3 is a quadratic residue mod p to a question about whether p is a quadratic residue mod 3 (and there's a simple congruence critera for this).

Ok, so now I have to determine whether or not a prime p is a QR mod 3.

The Legendre symbol $(3/p)$ equals 1 if 3 is a QR mod p right?

Then Euler's criterion says that if $(3/p) = 1$ then

$$3^{(p-1)/2} \equiv 1(\mod p)$$

Then the QRL says that if $3,p$ are odd primes, and if $3,p \equiv 3(\mod 4)$, then

$$(3/p) = -(p/3)$$

Working backwards now, we have that if $(p/3) = 1$ then

$$p^{(3-1)/2} \equiv 1(\mod p)$$

which equals

$$p\equiv 1(\mod p)$$

So p is a QR mod 3 if $p\equiv 1(\mod 3)$

This looks sketchy to me, I may have forgotten a negative sign too. hmmm Am I close?

 

[shmoe]

The Legendre symbol $(3/p)$ equals 1 if 3 is a QR mod p right?

yes, and -1 if it's not.

Then Euler's criterion says that if $(3/p) = 1$ then

$$3^{(p-1)/2} \equiv 1(\mod p)$$

No need for Euler's criterea here.

Then the QRL says that if $3,p$ are odd primes, and if $3,p \equiv 3(\mod 4)$, then

$$(3/p) = -(p/3)$$

Yes. Another case to consider is when p is 1 mod 4.

Working backwards now, we have that if $(p/3) = 1$ then

$$p^{(3-1)/2} \equiv 1(\mod 3)$$

which equals

$$p\equiv 1(\mod 3)$$

So p is a QR mod 3 if $p\equiv 1(\mod 3)$

This goes both ways, but there's no need to use Euler's critera. 1 is a QR mod 3 and 2 is not, so it's clear which primes mod 3 are quadratic residues.

So if p=3 mod 4 and p=1 mod 3, is 3 a QR mod p or not? And the other cases?

 

[Oxymoron]

Posted by Shmoe

This goes both ways, but there's no need to use Euler's critera. 1 is a QR mod 3 and 2 is not, so it's clear which primes mod 3 are quadratic residues.

So p=1,7,13,19,etc... could be QR because they are all congruent to 1 mod 3, is this right?

 

[shmoe]

So p=1,7,13,19,etc... could be QR because they are all congruent to 1 mod 3, is this right?

Quadratic residues mod p, yes. if a=b mod p then (a/p)=(b/p)

 

[Oxymoron]

Posted by Shmoe

So if p=3 mod 4 and p=1 mod 3, is 3 a QR mod p or not?

Where did "if $p\equiv 3(\mod 4)$" come from?

 

[shmoe]

Where did "if $p\equiv 3(\mod 4)$" come from?

When you applied the law of quadratic reciprocity you had assumed that p=3 mod 4, you have to consider the other case as well.

 

[Oxymoron]

Ok, so I have two cases:

1.

$$p \equiv 1(\mod 3)$$
$$p \equiv 3(\mod 4)$$

2.

$$p \equiv 1(\mod 3)$$
$$p \equiv 1(\mod 4)$$

and using both cases togther I should be able to find exactly what p should be, instead of an (infinite) list of possible primes like I had before?

 

[shmoe]

What if p=2 mod 3?

You need more cases, you have to consider what p is mod 3 and what it is mod 4, 2 possibilities for each.

 

[Oxymoron]

But I found that p=1(mod 3). And the only restrictions I have imposed from the QRL are that p=3(mod 4) and p=1(mod 4). What other restrictions are there? I haven't said anywhere that p=2(mod 3).

 

[shmoe]

But I found that p=1(mod 3).

No you didn't! You found that when (p/3)=1 you must have p=1 mod 3. But you arbitrarily imposed this condition (p/3)=1, why couldn't it have been -1? actually looking back if you were trying to force (3/p) to be 1 then you wanted (p/3)=1 then you should have looked at (3/p)=-1 (this was when you were in the case p=3 mod 4).

There's a couple of things you need to know about to find (3/p),

1)how (3/p) relates to (p/3). this is entirely determined by p=1 or 3 mod 4

2)what is (p/3)? this is entirely determined by p=1 or 2 mod 3

Hence the 4 cases. These will cover all primes

 

[Oxymoron]

STEP 1.

Find all primes p such that 3 is a QR (mod p)

<==> (by the QRL)

Find all primes p such that p is a QR (mod 3)

STEP 2.

When is p a QR (mod 3)?

p is a QR mod 3 precisely when (3/p) = 1.

STEP 4

The QRL says that if 3 and p are odd primes then

1. (3/p) = (p/3) iff p=1(mod 4)

OR

2. (3/p) = -(p/3) iff p=3(mod 4)

STEP 4.

Take (3/p) = (p/3) (when p=1(mod 4))

Then (3/p) = (p/3) = p^((3-1)/2) = 1(mod p)

=> p = 1(mod p)

STEP 5.

Take (3/p) = -(p/3) (when p=3(mod 4))

Then -p=1(mod p) => p=2(mod p)

 

[Oxymoron]

So to answer your questions:

1. (3/p) is related to (p/3) in two ways, each of which has its own restriction.

(3/p) = (p/3) iff p=1(mod 4)
(3/p) = -(p/3) iff p=3(mod 4)

2. What is (p/3)? Not sure yet...

 

[shmoe]

2. What is (p/3)? Not sure yet...

Remember if a= b mod 3 then (a/3)=(b/3)

 

[Oxymoron]

Since $(p/3) \equiv p(\mod 3)$, then let $a = (p/3)$, and $b=p$, then from your last posted identity we have

$$((p/3)/3)=(p/3)$$

Im not sure if this is what you wanted.

 

[shmoe]

To find (p/3) you just have to ask is p=1 or 2 mod 3? If 1, the (p/3)=1, if 2 then (p/3)=-1,

i.e. (2/3)=(5/3)=(11/3)=-1 but (7/3)=(13/3)=(19/3)=1

 

[Oxymoron]

Ok, so (p/3) = 1 iff p=1(mod 3) and (p/3) = -1 iff p=2(mod 3)

...and that's our four cases right?


1. $$(3/p) = (p/3) \Leftrightarrow p\equiv 1(\mod 4)$$
2. $$(3/p) = -(p/3) \Leftrightarrow p\equiv 3(\mod 4)$$
3. $$(p/3) = 1 \Leftrightarrow p\equiv 1(\mod 3)$$
4. $$(p/3) = -1 = 2\Leftrightarrow p\equiv 2(\mod 3)$$

 

[Oxymoron]

0 is NOT a QR mod 3.
1 is a QR mod 3
2 is NOT a QR mod 3.

0 is NOT a QR mod 4
1 is a QR mod 4
2 is NOT a QR mod 4
3 IS a QR mod 4

 

[shmoe]

Ok, so (p/3) = 1 iff p=1(mod 3) and (p/3) = -1 iff p=2(mod 3)

...and that's our four cases right?


1. $$(3/p) = (p/3) \Leftrightarrow p\equiv 1(\mod 4)$$
2. $$(3/p) = -(p/3) \Leftrightarrow p\equiv 3(\mod 4)$$
3. $$(p/3) = 1 \Leftrightarrow p\equiv 1(\mod 3)$$
4. $$(p/3) = -1 = 2\Leftrightarrow p\equiv 2(\mod 3)$$

It's 4 cases but not how you have them arranged.

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

In each case you can find (3/p). You can write these cases a little more neatly by what p is mod 12.

0 is a quadratic residue mod anything, 0^2=0.

 

[Oxymoron]

The QR for mod 3 are 0,1, and 2.
The QR for mod 4 are 0,1, and 3. 2 is not a QR mod 4.

Case 1.
(p/3) = (3/p)
(p/3) = (1/3)

(3/p) = (1/3) and since 1 is always a QR mod (a prime) we have p=1

Case 2.
(p/3) = (3/p)
(p/3) = (2/3)

(3/p) = (2/3) and since 2 is a QR mod 3 we have p=2

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

(3/p) = -(1/3) => p=-1 = 2(mod 3)

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

(3/p) = -(2/3) => p=-2 =1(mod 3)

So p=1 and p=2

 

[shmoe]

The QR for mod 3 are 0,1, and 2.
The QR for mod 4 are 0,1, and 3. 2 is not a QR mod 4.

2 is not a QR mod 3. 3 is not a QR mod 4.

These are easy to check just square:

0^2=0 mod 3
1^2=1 mod 3
2^2=1 mod 3

So 0 and 1 are QR mod 3, but 2 is not. There's no real need to check 0 (or 1 really), it's 'free'.

 

[Oxymoron]

Oh, ok I am an idiot. So the only prime which works is 1.

Can I just ask, if 2^2 = 1 mod 3, then isn't it a QR mod 3? Wait, NO! that means 1 is a QR residue mod 3

 

[Oxymoron]

0,1 QR mod 3
0,1 QR mod 4

so p=1

 

[shmoe]

Oh, ok I am an idiot. So the only prime which works is 1.

1 is usually not considered a prime. It may be that you've included 1 in the definition of prime in your course, if so that's ok but be warned the overwhelming majority of authors exclude it.

Can I just ask, if 2^2 = 1 mod 3, then isn't it a QR mod 3? Wait, NO! that means 1 is a QR residue mod 3

Exactly. Y is a QR mod n if there is an x where x^2=y mod n. You can always 'manually' find all the QR by squaring 0,1, ..., n-1 and reducing mod n (actually it's enough to square the first half).

Knowing now that (1/3)=1 and (2/3)=-1, go back to your 4 cases and work out (3/p) for each:

Case 1.
(p/3) = (3/p)
(p/3) = (1/3)

Case 2.
(p/3) = (3/p)
(p/3) = (2/3)

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

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

 

[Oxymoron]

From case 1 we have
(3/p) = (1/3) => (3/p) = 1
From case 2 we have
(3/p) = -1

So the question becomes: Primes p such that 3 is a QR mod p are such that (3/p) = +-(1). So the only primes p such that 3 is a QR mod p are the same primes such that 3 is not a QR mod p. Which tells me that there arent any!? What have I don't wrong now? :(

 

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