1. Apr 2, 2006

### Oxymoron

I have this problem Ive 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!

2. Apr 2, 2006

### devious_

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

3. Apr 2, 2006

### 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}}$$

Last edited: Apr 2, 2006
4. Apr 2, 2006

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

Last edited: Apr 2, 2006
5. Apr 2, 2006

### 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 lets 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).

6. Apr 2, 2006

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

7. Apr 3, 2006

### Oxymoron

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.

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?

Last edited: Apr 3, 2006
8. Apr 3, 2006

### shmoe

yes, and -1 if it's not.

No need for Euler's criterea here.

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

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?

9. Apr 3, 2006

### Oxymoron

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

10. Apr 3, 2006

### shmoe

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

11. Apr 3, 2006

### Oxymoron

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

Last edited: Apr 3, 2006
12. Apr 3, 2006

### shmoe

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.

13. Apr 3, 2006

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

14. Apr 3, 2006

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

15. Apr 3, 2006

### 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 havent said anywhere that p=2(mod 3).

16. Apr 3, 2006

### shmoe

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

17. Apr 3, 2006

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

Last edited: Apr 3, 2006
18. Apr 3, 2006

### Oxymoron

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

19. Apr 3, 2006

### shmoe

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

20. Apr 3, 2006

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

21. Apr 3, 2006

### 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

22. Apr 3, 2006

### Oxymoron

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

...and thats 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)$$

Last edited: Apr 3, 2006
23. Apr 3, 2006

### 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

24. Apr 4, 2006

### shmoe

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.

25. Apr 4, 2006

### 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