Trying to understand Gauss's Lemma

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

 

[Oxymoron]

1. Let p=1(mod 8). => p=8n+1

exponent = 8n/4 - floor((8n+1)/4) = 4n - 2n = 2n (EVEN)

2. Let p=-1(mod 8) => p=8n-1

exponent = (8n-2)/2 - floor((8n-1)/4) = 4n - 1 - 2n = 2n-1 (ODD)

3. Let p=3(mod 8) => p=8n+3

exponent = (8n+2)/2 - floor((8n+3)/4) = 4n - 1 - 2n = 2n-1 (ODD)

4. Let p=-3(mod 8) => p=8n-3

exponent = (8n-4)/2 - floor((8n-3)/4) = 4n - 2 - 2n = 2n-2 (EVEN)

 

[Oxymoron]

But shouldn't the first two exponents be EVEN and the last two ODD?

 

[shmoe]

You have floor((8n-1)/4)=2n, this isn't correct.

 

[Oxymoron]

Sorry, where do I have that?

floor((8n-1)/4) = floor(2n-1/4) which is always going to be 1 less than an even number => ODD

n=1 RHS = 1
n=2 RHS = 3
n=3 RHS = 5
etc...

 

[shmoe]

2. Let p=-1(mod 8) => p=8n-1

exponent = (8n-2)/2 - floor((8n-1)/4) = 4n - 1 - 2n = 2n-1 (ODD)

(8n-2)/2=4n-1 so

(8n-2)/2 - floor((8n-1)/4) = 4n - 1 - 2n

tells me you have

floor((8n-1)/4) = 2n

 

[Oxymoron]

Ah, I see. Well floor((8n-1)/4) is certainly not 2n. ;)

floor((8n-1)/4) = 2n-1 So we should have

4n - 1 - (2n - 1) = 2n => EVEN


And fixing the mistake in the last case yields ODD

 

[Oxymoron]

Well, if this is all correct then I have shown what I needed to show. :)