Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Question about quadratic residues

  1. Jun 17, 2005 #1
    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: [tex]a^2 \equiv r \pmod{p}[/tex].
    Since p is prime, there are [tex]\frac{p-1}{2}[/tex] different residues (not counting 0).
    Now, if you sum them all, you find: [tex]S_p=\sum_{i=1}^{\frac{p-1}{2}} r_i \equiv 0 \pmod{p}[/tex].
    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, [tex]d \mid p \rightarrow d \mid S_p[/tex]. And sometimes the property is true.

    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 [tex]a^2 \equiv (p-a)^2 \pmod{p}[/tex] .


  2. jcsd
  3. Jun 17, 2005 #2
    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.


    [tex]\sum_{i=1}^{\frac{p-1}{2}} r_i = \sum_{i=1}^{\frac{p-1}{2}} i^2.[/tex]

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

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

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

    [tex]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}.[/tex]

    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 [tex]\frac{p(p+1)(p-1)}{24}[/tex] is a multiple of p, and therefore congruent to 0 mod p.
    Last edited: Jun 17, 2005
  4. Jun 18, 2005 #3
    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 [tex]\frac{p-1}{2}[/tex] is even and with [tex]\frac{p-1}{4} = q[/tex], then we can partition the residues in q pairs of 2 residues [tex](r_i,r_i')[/tex] such that [tex]r_i+r_i' = p[/tex] .

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

    I guess that if d is the smallest prime divisor of [tex]\frac{p-1}{2}[/tex], then we can partition the residues in q groups of d residues, such that [tex]r_{i,1}+r_{i,2} + \ldots + r_{i,d} \equiv P[/tex]. 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 ?



    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))
  5. Jun 18, 2005 #4


    User Avatar
    Science Advisor
    Homework Helper

    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

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

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

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

    So [tex](r^2)^{q-1},\ (r^2)^{q-2},\ \ldots,\ 1[/tex] 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.
  6. Jun 18, 2005 #5
    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 !
  7. Jun 18, 2005 #6


    User Avatar
    Science Advisor
    Homework Helper

    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 seperate them. This partitioning into q-sets can be extended to all residues of course.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook