Question about quadratic residues

[T.Rex]

Hi,
I'd like to know which property proves the following simple result.

Let p be a prime greatest than 3.
r is a quadratic residue of p if there exists a such that: a^2 \equiv r \pmod{p}.
Since p is prime, there are \frac{p-1}{2} different residues (not counting 0).
Now, if you sum them all, you find: S_p=\sum_{i=1}^{\frac{p-1}{2}} r_i \equiv 0 \pmod{p}.
I cannot find any explanation in my Maths books (and remind I'm just an amateur).
If p is not prime, this property is false in general. Often, d \mid p \rightarrow d \mid S_p. And sometimes the property is true.

Examples.
p=7 S7=7
p=10 S10=2*10
p=22 S22=9*11
p=33 S33=22*11
p=35 S35=7*35
p=43 S43=10*43
p=47 S47=9*47
p=48 S48=340

The PARI/gp program I use is:
for(p=5,50,S=0;for(i=1,(p-1)/2,S=S+(i^2%p));print(p," ",S," ",S/p)
wich uses the property that a^2 \equiv (p-a)^2 \pmod{p} .

Thanks,

Tony

 

[Muzza]

There are, as you say, only (p - 1)/2 quadratic residues modulo p. 1^2, 2^2, ..., ((p - 1)/2)^2 is a list of (representatives of) (p - 1)/2 quadratic residues, and this list must therefore be complete.

Thus

\sum_{i=1}^{\frac{p-1}{2}} r_i = \sum_{i=1}^{\frac{p-1}{2}} i^2.

But the sum on right can be worked out with relative ease. In general:

\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}.

Putting n = (p - 1)/2, we get

S_p = \frac{ \frac{p-1}{2}(\frac{p-1}{2}+1)(2\frac{p-1}{2}+1)}{6} } = \frac{p(p+1)(p-1)}{24}.

Note that 24 = 3 * 2^3 and p > 3. Since p is prime, p is either congruent to 1 or 2 modulo 3. Therefore, either p - 1 or p + 1 must be divisible by 3.

Further, note that p is congruent to 1 or 3 modulo 4. Either way, we see that one of p + 1 and p - 1 must be divisible by 4, and the other will then be divisible by (at least) 2, so that (p - 1)(p + 1) is always divisible by 2 * 4 = 2^3.

So \frac{p(p+1)(p-1)}{24} is a multiple of p, and therefore congruent to 0 mod p.

 

[T.Rex]

Partitionning residues

Oooopps !
Thanks Muzza,
Thanks to point this. I looked into Number Theory books and forgot to open my old Maths books !

Now, I have another simple question (and still no answer on the top of my head or in my books) about partitionning the residues.

I've noticed that if \frac{p-1}{2} is even and with \frac{p-1}{4} = q, then we can partition the residues in q pairs of 2 residues (r_i,r_i') such that r_i+r_i' = p .

If \frac{p-1}{2} is odd, we cannot partition the residues into pairs.

I guess that if d is the smallest prime divisor of \frac{p-1}{2}, then we can partition the residues in q groups of d residues, such that r_{i,1}+r_{i,2} + \ldots + r_{i,d} \equiv P. The "equiv" sign here means that the q sums differ only by 1 or 2 .

I've checked this for some primes and here are some examples:
p=13 : 9+4=12+1=10+3=p
p=17 : 16+1=15+2=13+4=9+8=p
p=19 : 17+4+5=11+6+9=26 16+7+1=24
p=73 : 1+72=4+69=9+64=16+57=25+48=36+37=49+24=8+65=27+46=71+2=23+50=6+67=70+3=32+41=35+38=18+55=19+54=12+61

Do you know about an explanation ?

Thanks,

Tony


Here is the PARI/gp program I used for d=2 ((p-1)/2 is even) :

A=vector(1000); B=vector(1000)
p=73; for(i=1,(p-1)/2, A=i^2%p; B=0)
for(i=1,(p-1)/2, for(j=i+1,(p-1)/2, if(A+A[j]==p, B++; B[j]++ ; print(A," ", A[j]))))
for(i=1,(p-1)/2, if(B != 1 , print("FALSE"); break))

 

[shmoe]

I think you can do better. If q is any prime that divides (p-1)/2, then you can partition the quadratic residues into (p-1)/(2q) sets of size q where the sum of each set is 0 mod p. For example,

p=31, the quadratic residues are 1,2,4,5,7,8,9,10,14,16,18,19,20,25,28

sets of 3:
1+5+25=2+10+19=4+20+7=8+9+14=16+18+28=0 mod 31

sets of 5:
1+2+4+8+16=5+10+20+9+18=7+14+28+25+19=0 mod 31


Note that the set of quadratic residues form a multiplicative group mod p with (p-1)/2 elements. Call this set Q

First assume q is not 2. We know the group of units has order p-1, so we have an element r of order q, since q divides p-1. Since q is prime and not 2, we also know r^2 will have order q as well so

0\equiv(r^2)^q-1\equiv ((r^2)^{q-1}+(r^2)^{q-2}+\ldots+1)(r^2-1)\text{ mod q}

since q is not 2, r^2 is not 1 mod p so we must have

0\equiv (r^2)^{q-1}+(r^2)^{q-2}+\ldots+1\text{ mod q}

So (r^2)^{q-1},\ (r^2)^{q-2},\ \ldots,\ 1 are all distinct, form a multiplicative subgroup of order q of Q and have sum 0 mod p. This subgroup is normal and partitions Q into (p-1)/(2q) equivalence classes, all of which have sum 0 mod p since they are given by multiplying this subgroup by any representative of that class.

If q is 2, then p is congruent to 1 mod 4 and -1 is a quadratic residue. Take {1,-1} as your subgroup of Q and proceed as above.

 

[T.Rex]

Crystal clear

Thanks shmoe !
It took me some minutes, but now it is crystal clear.
I'm always staggered by all one can do with the idea of "order".

Do you know about a free book or course that explains all known theory about residues ?
I have a French one describing many things about residues, but it does not talk about that.

Thanks again !
Tony

 

[shmoe]

I can't think of any good free books, sorry.

I realized shortly afterwards that I was unnecessarily complicating things (and probably still am!). You know q divides the order of Q, so the group of quadratic residues has an element of order q, this can be our r^2. No need to even mention properties of r (though it is interesting r ends up being a quadratic residue). Also this handles the q=2 case as well, no need to separate them. This partitioning into q-sets can be extended to all residues of course.