Trying to understand Gauss's Lemma

[Oxymoron]

Let p be an odd prime and gcd(a,p) = 1. Let n be the number of residues of the set S = {a,2a,3a,...,(p-1)/2*a} (only half the multiples) which are greater than p/2. Then (a/p) = (-1)^n.

But what if a=2 Is there an analogous lemma?

EDIT: I was right the first time

 

[shmoe]

Gauss's lemma works just fine when a=2. You can use it to find (2/p) for any odd prime p.

 

[Oxymoron]

What I would like to do is show that

$$(2/p) = (-1)^{\frac{p-1}{2} - \left\lfloor\frac{p}{4}\right\rfloor}$$

but before I do, I would like to first understand the p odd prime case.

 

[shmoe]

Gauss's lemma is about an alternate way of finding (a/p). If p=2, you don't need an alternate way.

 

[Oxymoron]

Ok, what I wrote the first time is what I meant (I promise!). Now that I have all that behind me, I would like to start to show (via Gauss's Lemma for any a) that in particular (2/p) is as I have stated above...

 

[Oxymoron]

Im assuming that once I can show that (2/p) = (-1)^etc... then I can show that 2 is a QR for all primes p = +-1(mod 8) and that 2 is NOT a QR for all primes p=+-3(mod 8). This is my aim, but first I would like to show the expression first.

 

[Oxymoron]

The only problem, I can only find the following relations in my books and online:

$$(2/p) = (-1)^{\frac{p^2-1}{8}}$$

which is not exactly what my problem wants.

 

[Oxymoron]

Would I be correct in assuming that

$$\frac{p-1}{2} - \left\lfloor\frac{p}{4}\right\rfloor$$

is meant to be the number of lattice points inside the triangle AHK?

 

[shmoe]

That lattice is probably coming from a proof of quadratic reciprocity, see the q on vertical axis?

You're looking at even integers S={2, 2*2, 2*3, 2*4, ..., 2*(p-1)/2} there's no need to reduce mod p here (why?). You need to count how many are greater than p/2.

Maybe you should try a few sample p's and do this manually. It should give you an idea where their exponent comes from. Remember also that p is odd, so (p-1)/2 is not an integer.

 

[Oxymoron]

(p-1)/2 should be an integer. p is a prime, p-1 is always even (unless p=2) so (p-1)/2 is always an integer because 2 is a divisor of every even number (unless p=2).


p exponent
3 1
5 1
7 2
11 3
13 3
17 4
19 5

Oh, and you are right That was for (p/q) = (-1)^some exp. But my point was, is the exponent related to the points in the lattice?

 

[shmoe]

p exponent
3 1
5 1
7 2
11 3
13 3
17 4
19 5

How about S? S has (p-1)/2 elements in it. To find how many are greater than p/2, you can instead find how many are less than p/2.

 

[Oxymoron]

p exp |S| #<p/2
3 1 1 1
5 1 2 1
7 2 3 1
11 3 5 2
13 3 6 3
17 4 8 4
19 5 9 4

Ok, I am seeing a pattern

The number of elements in S, denoted |S| will always be equal to (p-1)/2 as you said, and the number of these elements less than p/2, denoted by #<p/2 is always equal to the floor of |S|/2.

 

[Oxymoron]

Can I guess that the exponent is meant to resemble the number of negative least residues less than p/2?

 

[Oxymoron]

So this becomes a problem about showing that the number of elements in the set of negative least residues less than p.

 

[shmoe]

The number of elements in S, denoted |S| will always be equal to (p-1)/2 as you said, and the number of these elements less than p/2, denoted by #<p/2 is always equal to the floor of |S|/2.

Yes. Now can you write the floor of |S|/2 in a nother way? You know |S|=(p-1)/2.

So this becomes a problem about showing that the number of elements in the set of negative least residues less than p.

I don't know what you mean by "negative least residue". In the Gauss Lemma, you take the least positive residues of the elements of S, but when p=2 they are already reduced.

 

[Oxymoron]

Ok so the number of elements less than p/2 in S is floor((p-1)/4).

 

[shmoe]

Right. Now how does floor((p-1)/4) compare with floor(p/4)?

 

[Oxymoron]

That, I do not know. I've been staring at it for 20 minutes.

 

[shmoe]

Try considering the two cases p=1 or 3 mod 4 seperately, in the form p=4n+1 or +3. If p=4n+1 then what is floor(p/4) and floor((p-1)/4)?

 

[Oxymoron]

For p=1(mod 4) => p=4n+1 for some integer n. Then

floor((p-1)/4) = floor(n)
floor(p/4) = floor((4n+1)/4)

If p=3(mod 4) => p=4n+3 for some integer n. Then

floor((p-1)/4) = floor((4n+2)/4)
floor(p/4) = floor((4n+3)/4)

Still, I see no relationship between the two.

 

[shmoe]

For p=1(mod 4) => p=4n+1 for some integer n. Then

floor((p-1)/4) = floor(n)
floor(p/4) = floor((4n+1)/4)

Just this for now.

n is an integer so floor(n)=n

floor((4n+1)/4)=floor(n+1/4)=??

 

[Oxymoron]

Well, I do see that floor((p-1)/4) is always an integer as long as p=1 or 3 (mod 4)

 

[Oxymoron]

...=n+1/4

So for the other case

floor((4n+2)/4) = floor(n+1/2) = n+1/2

 

[matt grime]

Well, I do see that floor((p-1)/4) is always an integer as long as p=1 or 3 (mod 4)

floor anything is always an integer because that is what the floor function returns.

 

[Oxymoron]

May I ask why we are in mod 4?

 

[Oxymoron]

Posted by Matt Grime

floor anything is always an integer because that is what the floor function returns.

Of course, what I meant was (p-1)/4 is an integer so long as p=1 or 3(mod 4).

 

[shmoe]

...=n+1/4

I think you are losing the meaning behind the floor function. n is an integer, n<n+1/4<n+1 so we must have floor(n+1/4)=n.


mod 4 because it makes it simpler to evaluate floor(p/4) and floor((p-1)/4). You could just use p is odd, p=2n+1, but then you're left with comparing floor(n/2) and floor(n/2+1/4), and you'd probably want to break it up into n even or odd so you may as well have just looked at p mod 4 in the first place.


(p-1)/4 isn't an integer if p=3 mod 4

 

[Oxymoron]

Posted by Shmoe

I think you are losing the meaning behind the floor function. n is an integer, n<n+1/4<n+1 so we must have floor(n+1/4)=n.

Yes. I was guilty of posting before checking.

Ok, so we have a link between floor((p-1)/4) and floor(p/4). That is if p=1 or 3(mod 4) then

floor((p-1)/4) = floor(p/4)

 

[shmoe]

So you essentially have their exponent now.

Looking back, you claimed that there were floor(|S|/2) values less than p/2. Can you actually prove this, or is it just based on the numerical evidence from your table?

If not, it may have been easier to proceed in a slightly different way. The elements of S less than p/2 are exactly the even integers less than p/2. You can count these directly, right?

 

[Oxymoron]

Yeah, I basically counted them.

But I want to prove the exponent is

(p-1)/2 - floor(p/4)

which we now know is

(p-1)/2 - floor((p-1)/4)

So all I can do is rewrite the exponent, not show it. (or at least I can't show it)

[Usually books write the exponent as n. Has this any relationship with our n? Probably not.]

 

[shmoe]

If not, it may have been easier to proceed in a slightly different way. The elements of S less than p/2 are exactly the even integers less than p/2. You can count these directly, right?

By this I mean prove a statement in general.

Given a positive real number x, in terms of the floor function can you answer:

1) how many positive integers are less than or equal to x? (<= this is a warm up)
2) how many even positive integers are less than or equal to x?

If you can do this, then you can count the even integers in S that are less than or equal to p/2. Then you can count how many are larger than p/2.

 

[Oxymoron]

1) The number of positive integers less than or equal to x is x.
2) The number of even positive integers less than or equal to x is

a) x/2 => x is even
b) floor(x/2) => x is odd

3) The number of even integers in S less than or equal to p/2 is floor(p/4) since p is odd.

The number of even integers in S strictly larger than p/2 is

(p-1)/2 - floor(p/4)

 

[shmoe]

1) The number of positive integers less than or equal to x is x.
2) The number of even positive integers less than or equal to x is

a) x/2 => x is even
b) floor(x/2) => x is odd

Ok that works. You don't have to assume that x is an integer, there are floor(x) positive integers less than x in this case, and so on.

3) The number of even integers in S less than or equal to p/2 is floor(p/4) since p is odd.

The number of even integers in S strictly larger than p/2 is

(p-1)/2 - floor(p/4)

Righty-O. Apply Gauss's lemma and that's what you had set out to prove, minus evaluating this for p=1,3,5, 7 mod 8.

 

[Oxymoron]

So Gauss's lemma implies that if n is the number of integers in S greater than p/2 then

(2/p) = (-1)^n

But we now know that n = (p-1)/2 - floor(p/4) so we have the desired result. Thanks Shmoe! :-)

But now I want to show that 2 is a QR for all primes p congruent to +1,-1 (mod 8) and not for primes congruent to +3,-3 (mod 8).

 

[shmoe]

But now I want to show that 2 is a QR for all primes p congruent to +1,-1 (mod 8) and not for primes congruent to +3,-3 (mod 8).

Yep, so do the cases p=8n+/-1 or 3 seperately and evaluate the exponent in each case. You only care if this is even or odd in the end.