Quadratic Nonresidues

[RichardCypher]

Morning everybody!

I'm trying to prove a curious little property of quadratic nonresidues:
Let p>5 be a prime number. p|S where S is the sum of the squares of its [p's, that is] quadratic nonresidues.

However, I didn't make any headway with this problem. I will very much appreciate your help.

Have a nice weekend!
R.C.

 

[huba]

Hi

(1) I wonder if it is right to say that, for a prime p > 5 (actually, p >=5), p divides the sum of the quadratic residues of p (if right, it should not be difficult to prove but I haven't done it).

Further, a^2 = (p-a)^2 mod p, if 1 <= a <= (p-1)/2, and so the first (p-1)/2 integers, as well as the integers from (p-1)/2 +1 to p-1 "generate" all the quadratic residues of p, as they provide all the solutions of x^2 = q mod p (as there are (p-1)/2 quadratic residues of prime p). For instance, for p=7, 1^2 = 1 mod 7, 2^2 = 4 mod 7, 3^2 = 2 mod 7, and the quadratic residues of 7 are 1,2, and 4.


Therefore, if (1) is right, p divides the sum of the squares of the first (p-1)/2 integers as well as the sum of the squares of the "second" (p-1)/2 integers, and so p actually divides the sum of the squares of all integers 1, 2, ..., p-1. Therefore if p divides the sum of the squares of the quadratic nonresidues of p, then p also divides the sum of the squares of the quadratic residues.

I know this hasn't answered your problem, but I hope it helps. And I hope that it makes mathematical sense - math is a sort of "recreational activity" for me.

 

[RichardCypher]

Morning huba

Thanks for your reply. Hmmpf, I think it can be shown that for any prime, p>3, p divides the sum of its quadratic residues.

For example, it's a well-known fact that the quadratic residues of p equals to $$1^2, 2^2, \dots, \left(\frac{p-1}{2}\right)^2 \mbox{ (mod } p)$$, and so the sum is p(p-1)(p+1)/24. Because p>3 is a prime it's quite clear that $$24|p^2-1$$ and therefore p divides the appropriate sum.

However, I do not see how it can help. It may be that I don't quite understand your message. If it is so, I'm sorry; would you please be so kind as to explain it to me again?

Many thanks for your time,
R.C.

 

[huba]

Is it possible to show that if p divides the sum of the quadratic residues of p then p also divides the sum of the squares of the quadratic residues of p?
Then it would follow that, as p divides the sum of the squares of integers 1 to p-1, p also divides the sum of the squares of the quadratic nonresidues of p?

 

[RichardCypher]

Is it possible to show that if p divides the sum of the quadratic residues of p then p also divides the sum of the squares of the quadratic residues of p?
Then it would follow that, as p divides the sum of the squares of integers 1 to p-1, p also divides the sum of the squares of the quadratic nonresidues of p?

You are correct, it would follow. However, I am not sure how to prove such a thing. It is easy enough to show that in order to get to the formula of the sum of the squares from the formula of the "regular" sum, one needs only to multiply by a factor of (2n+1)/3, or p/3, in our case. Meaning that if one can show that $${2^3\cdot3^2}|{p(p-1)(p+1)}$$, where p>5 is a prime, the rest would follow. However, I didn't succeed proving it

Thanks again for your time,
R.C.

 

[RichardCypher]

Not so. I was wrong. We can multiply the formula by (2n+1)/3 provided that it's an arithmetic progression. So it won't necessarily work in our case. Hmmpf, I don't have any idea how to prove that p divides the sum of squares of its quadratic residues, given that it divides the sum of its quadratic residues.

 

[RichardCypher]

I remembered a thing that may help:
If r is a primitive root of p, then the quadratic residues of p are equivalent to the even powers of r (that is $$r^2, r^4, \dots, r^{p-1}$$) and the quadratic nonresidues to the odd powers of r.

So, basically, we want to prove that $$p|r^2 + r^6 + r^{10} + \dots + r^{2p}$$ where p>5 is a prime and r is one of p's primitive roots.

However, I didn't get anywhere going down this path...

 

[Hurkyl]

However, I didn't get anywhere going down this path...

It seems clear to me; just sum the series and simplify modulo p.

 

[RichardCypher]

It seems clear to me; just sum the series and simplify mod p.

Thank-you Hurkyl, for your time
I did try to do it, of course, I got $$\frac{r^4(r^{2(p-1)}-1)}{r^4-1}$$ and couldn't get rid of the fraction

 

[Hurkyl]

Thank-you Hurkyl, for your time
I did try to do it, of course, I got $$\frac{r^4(r^{2(p-1)}-1)}{r^4-1}$$ and couldn't get rid of the fraction

Your numerator's wrong. But the main thing is that you can still simplify; you know things about things to the power of p, don't you?

 

[RichardCypher]

It seems clear to me; just sum the series and simplify modulo p.

r is a primitive root of p and therefore r^(p-1)=1(modp) so the numerator is 0 and the whole thing is 0 mod p, meaning p|S. Is that right? Is that it?

[you're right, of course, it should be r^2 in the numerator]

 

[Hurkyl]

That sounds plausible. :)

 

[RichardCypher]

That sounds plausible. :)

Dear Hurkyl, thank you very much for all your help . There is just a tiny detail I don't quite get. Why wouldn't the exact same proof work for p=5?

Thanks again!
R.C.

 

[Hurkyl]

There is just a tiny detail I don't quite get. Why wouldn't the exact same proof work for p=5?

The most algorithmic to see it for yourself is to actually choose an appropraite r, and plug it into the argument to see what happens. You'd also catch it if you were paying attention to the little details.

 

[RichardCypher]

The most algorithmic to see it for yourself is to actually choose an appropraite r, and plug it into the argument to see what happens. You'd also catch it if you were paying attention to the little details.

I get it! Is it because $$\phi(5) = 4$$ and therefore the denominator is equivalent to 0 (mod 5) ? It's only so with p=5!

Hurkyl, thank you so much! Your hints are perfect, exactly in the suitable level. They helped me get to it "by myself" but weren't so easy as to not make me think at all
R.C.

 

[huba]

Is it possible to extend this theorem by saying that
n divides the sum of the squares of the quadratic residues of n if and only if n can be written as p^m where p is a prime > 5 and m is any natural number?