# Trying to understand Gauss's Lemma

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
Homework Helper
Oxymoron said:
...=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

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
Homework Helper
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?

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 cant show it)

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

Last edited:
shmoe
Homework Helper
shmoe said:
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.

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
Homework Helper
Oxymoron said:
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.

Oxymoron said:
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.

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
Homework Helper
Oxymoron said:
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.

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)

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

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

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

Last edited:
shmoe
Homework Helper
Oxymoron said:
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

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

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