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? :(