Scribd Logo
Upload

Welcome to Scribd!

  • 41 views

    Section 12 Quadratic Reciprocity

    Uploaded by

    don
    The document discusses quadratic reciprocity and Gauss's lemma. It contains examples of calculating quadratic residues and non-residues. The key points are: 1) Gauss's lemma provides a method to determine the quadratic residue of 2 modulo a prime p by forming the products of all integers less than or equal to (p-1)/2. 2) If p is congruent to 1 or 7 modulo 8, then the quadratic residue of 2 modulo p is 1. If p is congruent to 3 or 5 modulo 8, then the quadratic residue of 2 modulo p is -1. 3) The sums of the integers formed using Gauss's lemma are equal to (p2-1)/8, allowing

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Section 12 Quadratic Reciprocity

    Uploaded by

    don
    41 views21 pages
    The document discusses quadratic reciprocity and Gauss's lemma. It contains examples of calculating quadratic residues and non-residues. The key points are: 1) Gauss's lemma provides a method to determine the quadratic residue of 2 modulo a prime p by forming the products of all integers less than or equal to (p-1)/2. 2) If p is congruent to 1 or 7 modulo 8, then the quadratic residue of 2 modulo p is 1. If p is congruent to 3 or 5 modulo 8, then the quadratic residue of 2 modulo p is -1. 3) The sums of the integers formed using Gauss's lemma are equal to (p2-1)/8, allowing

    Original Description:

    Quadratic Reciprocity

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses quadratic reciprocity and Gauss's lemma. It contains examples of calculating quadratic residues and non-residues. The key points are: 1) Gauss's lemma provides a method to determine the quadratic residue of 2 modulo a prime p by forming the products of all integers less than or equal to (p-1)/2. 2) If p is congruent to 1 or 7 modulo 8, then the quadratic residue of 2 modulo p is 1. If p is congruent to 3 or 5 modulo 8, then the quadratic residue of 2 modulo p is -1. 3) The sums of the integers formed using Gauss's lemma are equal to (p2-1)/8, allowing

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    41 views21 pages

    Section 12 Quadratic Reciprocity

    Uploaded by

    don
    The document discusses quadratic reciprocity and Gauss's lemma. It contains examples of calculating quadratic residues and non-residues. The key points are: 1) Gauss's lemma provides a method to determine the quadratic residue of 2 modulo a prime p by forming the products of all integers less than or equal to (p-1)/2. 2) If p is congruent to 1 or 7 modulo 8, then the quadratic residue of 2 modulo p is 1. If p is congruent to 3 or 5 modulo 8, then the quadratic residue of 2 modulo p is -1. 3) The sums of the integers formed using Gauss's lemma are equal to (p2-1)/8, allowing

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    You are on page 1of 21

    Section 12 Quadratic Reciprocity

    • Gauss’s Lemma
    • Orbit of elements in (Z17,*)
    Powers 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
    1
    2 4 8 16 15 13 9 1 2 4 8 16 15 13 9 1
    3 9 10 13 5 15 11 16 14 8 7 4 12 2 6 1
    4 16 13 1 4 16 13 1 4 16 13 1 4 16 13 1
    5 8 6 13 14 2 10 16 12 9 11 4 3 15 7 1
    6 2 12 4 7 8 14 16 11 15 5 13 10 9 3 1
    7 15 3 4 11 9 12 16 10 2 14 13 6 8 5 1
    8 13 2 16 9 4 15 1 8 13 2 16 9 4 15 1
    9 13 15 16 8 4 2 1 9 13 15 16 8 4 2 1
    10 15 14 4 6 9 5 16 7 2 3 13 11 8 12 1
    11 2 5 4 10 8 3 16 6 15 12 13 7 9 14 1
    12 8 11 13 3 2 7 16 5 9 6 4 14 15 10 1
    13 16 4 1 13 16 4 1 13 16 4 1 13 16 4 1
    14 9 7 13 12 15 6 16 3 8 10 4 5 2 11 1
    15 4 9 16 2 13 8 1 15 4 9 16 2 13 8 1
    16 1 16 1 16 1 16 1 16 1 16 1 16 1 16 1
    Recall that since (a,p)=1 multiplying the least residues of p by a just permutes them.
    Since ak1≡ak2 mod p implies k1≡k2 mod p and both k1 and k2 are less than p, gives k1=k2.
    This means that the all the rs and ss are distinct. Next observe for any s we have
    p>s > (p-1)/2 so 0<p-s<(p-1)/2. Following Gauss we show that r1, …rk, (p-s1), …(p-sg)
    are all distinct and since they are all less than or equal to (p-1)/2 they must be exactly
    the least residues of p that are less or equal to (p-1)/2.
    To see they are distinct, suppose that ri≡ p-sj mod p for some i and j,
    then ri +sj ≡0 mod p and ti/a + uj/a ≡ 0 mod p for some ti and uj
    which is impossible since both ti and uj are distinct numbers less than or equal to (p-1)/2.
    Finally consider the product 1*2*…(p-1)/2 which by the preceding is r1, …rk, (p-s1), …(p-sg).
    Thus (p-1)/2 ! = r1* …rk *(p-s1)* …*(p-sg) and since p-s ≡ -s mod p
    (p-1)/2 ! ≡ r1*…*rk*(-1)g*s1*…*sg mod p ≡ (p-1)/ 2!*a(p-1)/2(-1)g mod p
    But this last congruence can only hold if a(p-1)/2 *(-1)g ≡ 1 mod p. QED
    Example 2
    x≡ 5 mod 17
    Example 2
    x≡ 7 mod 23

    (p-1)/2 1 2 3 4 5 6 7 8 9 10 11

    7* 7 14 21 28 35 42 49 56 63 70 77

    mod 23 7 14 21 5 12 19 3 10 17 1 8

    There are 5 numbers larger than 11 so 7 is a non residue mod 23


    Use Gauss’s Lemma to find (2/p)
    • We form 2, 4, 6, …,2((p-1)/2) and thus get the even integers less than
    or equal to p-1. There are (p-1)/2 such integers we then subtract the
    number less than or equal to (p-1)/2.
    • Now if (p-1)/2 is odd then (p-1)/4 is not an integer, the number of
    integers less than this value is (p-3)/4 so g is (p-1)/2-(p-3)/4 =(p+1)/4
    If (p-1)/2 is even then (p-1)/4 is an integer and maps to (p-1)/2 so we
    have g is (p-1)/2 –(p-1)/4= (p-1)/4
    Example
    • Suppose p = 1+8k then (p-1)/4=2k so this is g.
    • And (-1)g = 1 so by Gauss’s Lemma (2/p) =1 if p≡ 1 mod 8.
    • Suppose p =3 +8k then (p-1)/4 2k +1/2 and thus g= (p+1)/4 = 2k +1
    • And (-1)g = -1 so (2/p) =-1
    Exercise 4
    • Check the cases p≡ 5 mod 8 and p≡ 7 mod 8
    • Suppose p = 5+8k then (p-1)/4=2k+1 so this is g.
    • And (-1)g = -1 so by Gauss’s Lemma (2/p) =-1 if p≡ 5 mod 8.
    • Suppose p =7 +8k then (p-1)/4 2k +6/4 and thus g= (p+1)/4 = 2(k +1)
    • And (-1)g = 1 so (2/p) =1 for p ≡ 7 mod 8.
    •
    Theorem 2
    • If p is an odd prime
    • (2/p) =1 if p is congruent to 1 or 7 mod 8
    • (2/p) = -1 if p is congruent to 3 or 5 mod 8
    Theorem 3

    2(q-1)/2
    Last time we equated products now equate sums

    Now we have a formula for the sum of terms in (9) = [(p-1)/2 * (p-1)/2 +1]/2= (p2-1)/8
    Since the elements listed in (8) are the same they sum to the same and to

    Now if tj denotes the least residue of jq mod p

    You might also like