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

Quadratic Nonresidues

  1. May 25, 2008 #1
    Morning everybody!:smile:

    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.
     
  2. jcsd
  3. May 26, 2008 #2
    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.
     
    Last edited: May 26, 2008
  4. May 26, 2008 #3
    Morning huba :smile:

    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 [tex]1^2, 2^2, \dots, \left(\frac{p-1}{2}\right)^2 \mbox{ (mod } p)[/tex], and so the sum is p(p-1)(p+1)/24. Because p>3 is a prime it's quite clear that [tex]24|p^2-1[/tex] 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.
     
  5. May 26, 2008 #4
    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?
     
  6. May 26, 2008 #5
    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 [tex]{2^3\cdot3^2}|{p(p-1)(p+1)}[/tex], where p>5 is a prime, the rest would follow. However, I didn't succeed proving it :frown:

    Thanks again for your time,
    R.C.
     
  7. May 26, 2008 #6
    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.
     
  8. May 26, 2008 #7
    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 [tex]r^2, r^4, \dots, r^{p-1}[/tex]) and the quadratic nonresidues to the odd powers of r.

    So, basically, we want to prove that [tex]p|r^2 + r^6 + r^{10} + \dots + r^{2p}[/tex] 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...
     
  9. May 26, 2008 #8

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It seems clear to me; just sum the series and simplify modulo p.
     
  10. May 26, 2008 #9
    Thank-you Hurkyl, for your time :smile:
    I did try to do it, of course, I got [tex]\frac{r^4(r^{2(p-1)}-1)}{r^4-1}[/tex] and couldn't get rid of the fraction :frown:
     
  11. May 26, 2008 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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?
     
  12. May 26, 2008 #11
    r is a primitive root of p and therfore 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?:biggrin:

    [you're right, of course, it should be r^2 in the numerator]
     
  13. May 26, 2008 #12

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    That sounds plausible. :)
     
  14. May 26, 2008 #13
    Dear Hurkyl, thank you very much for all your help :biggrin:. 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.
     
  15. May 26, 2008 #14

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  16. May 26, 2008 #15
    I get it! Is it because [tex]\phi(5) = 4[/tex] and therfore the denominator is equivalent to 0 (mod 5) ? It's only so with p=5!:biggrin:

    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 :smile:
    R.C.
     
  17. May 28, 2008 #16
    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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Quadratic Nonresidues
  1. Quadratic numbers (Replies: 2)

  2. Quadratic forms (Replies: 2)

  3. Quadratic forms (Replies: 1)

  4. Quadratic Reciprocity (Replies: 2)

  5. Quadratic Forms (Replies: 5)

Loading...