1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Trying to understand Gauss's Lemma

  1. Apr 4, 2006 #1
    Let p be an odd prime and gcd(a,p) = 1. Let n be the number of residues of the set S = {a,2a,3a,...,(p-1)/2*a} (only half the multiples) which are greater than p/2. Then (a/p) = (-1)^n.

    But what if a=2 Is there an analogous lemma?

    EDIT: I was right the first time
     
    Last edited: Apr 4, 2006
  2. jcsd
  3. Apr 4, 2006 #2

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Gauss's lemma works just fine when a=2. You can use it to find (2/p) for any odd prime p.
     
  4. Apr 4, 2006 #3
    What I would like to do is show that

    [tex](2/p) = (-1)^{\frac{p-1}{2} - \left\lfloor\frac{p}{4}\right\rfloor}[/tex]

    but before I do, I would like to first understand the p odd prime case.
     
  5. Apr 4, 2006 #4

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Gauss's lemma is about an alternate way of finding (a/p). If p=2, you don't need an alternate way.
     
  6. Apr 4, 2006 #5
    Ok, what I wrote the first time is what I meant (I promise!). Now that I have all that behind me, I would like to start to show (via Gauss's Lemma for any a) that in particular (2/p) is as I have stated above....
     
  7. Apr 4, 2006 #6
    Im assuming that once I can show that (2/p) = (-1)^etc... then I can show that 2 is a QR for all primes p = +-1(mod 8) and that 2 is NOT a QR for all primes p=+-3(mod 8). This is my aim, but first I would like to show the expression first.
     
  8. Apr 4, 2006 #7
    The only problem, I can only find the following relations in my books and online:

    [tex](2/p) = (-1)^{\frac{p^2-1}{8}}[/tex]

    which is not exactly what my problem wants.
     
  9. Apr 4, 2006 #8
    Would I be correct in assuming that

    [tex]\frac{p-1}{2} - \left\lfloor\frac{p}{4}\right\rfloor[/tex]

    is meant to be the number of lattice points inside the triangle AHK?

    [​IMG]
     
  10. Apr 4, 2006 #9

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    That lattice is probably coming from a proof of quadratic reciprocity, see the q on vertical axis?

    You're looking at even integers S={2, 2*2, 2*3, 2*4, ..., 2*(p-1)/2} there's no need to reduce mod p here (why?). You need to count how many are greater than p/2.

    Maybe you should try a few sample p's and do this manually. It should give you an idea where their exponent comes from. Remember also that p is odd, so (p-1)/2 is not an integer.
     
  11. Apr 4, 2006 #10
    (p-1)/2 should be an integer. p is a prime, p-1 is always even (unless p=2) so (p-1)/2 is always an integer because 2 is a divisor of every even number (unless p=2).


    p exponent
    3 1
    5 1
    7 2
    11 3
    13 3
    17 4
    19 5

    Oh, and you are right That was for (p/q) = (-1)^some exp. But my point was, is the exponent related to the points in the lattice?
     
    Last edited: Apr 5, 2006
  12. Apr 5, 2006 #11

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    How about S? S has (p-1)/2 elements in it. To find how many are greater than p/2, you can instead find how many are less than p/2.
     
  13. Apr 5, 2006 #12
    p exp |S| #<p/2
    3 1 1 1
    5 1 2 1
    7 2 3 1
    11 3 5 2
    13 3 6 3
    17 4 8 4
    19 5 9 4

    Ok, Im seeing a pattern

    The number of elements in S, denoted |S| will always be equal to (p-1)/2 as you said, and the number of these elements less than p/2, denoted by #<p/2 is always equal to the floor of |S|/2.
     
  14. Apr 5, 2006 #13
    Can I guess that the exponent is meant to resemble the number of negative least residues less than p/2?
     
  15. Apr 5, 2006 #14
    So this becomes a problem about showing that the number of elements in the set of negative least residues less than p.
     
  16. Apr 5, 2006 #15

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Yes. Now can you write the floor of |S|/2 in a nother way? You know |S|=(p-1)/2.

    I don't know what you mean by "negative least residue". In the Gauss Lemma, you take the least positive residues of the elements of S, but when p=2 they are already reduced.
     
  17. Apr 5, 2006 #16
    Ok so the number of elements less than p/2 in S is floor((p-1)/4).
     
  18. Apr 5, 2006 #17

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Right. Now how does floor((p-1)/4) compare with floor(p/4)?
     
  19. Apr 5, 2006 #18
    That, I do not know. Ive been staring at it for 20 minutes.
     
  20. Apr 5, 2006 #19

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Try considering the two cases p=1 or 3 mod 4 seperately, in the form p=4n+1 or +3. If p=4n+1 then what is floor(p/4) and floor((p-1)/4)?
     
  21. Apr 5, 2006 #20
    For p=1(mod 4) => p=4n+1 for some integer n. Then

    floor((p-1)/4) = floor(n)
    floor(p/4) = floor((4n+1)/4)

    If p=3(mod 4) => p=4n+3 for some integer n. Then

    floor((p-1)/4) = floor((4n+2)/4)
    floor(p/4) = floor((4n+3)/4)

    Still, I see no relationship between the two.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Trying to understand Gauss's Lemma
Loading...