PRINT LINKED RELATED

Law of Quadratic Reciprocity

(1) Explain why it suffices to know when is solvable.

(2) Define quadaratic residues, the Lendegre symbol, and determine the quadratic residues of
    
(3) Use the quadratic residues for 17 to state and use Euler's Criterion.

(4)

    Consider the congruence



where is an odd prime and Inspired by completing the square, we have











Let and then we have a simplified version of the original namely;



Here is an example which illustrates how to take advantage of this.

Example (Quadratic Congruence) Solve the quadratic congruence

    Solution. Let and . First we will solve the quadratic congruence, By trial and error we find, and Therefore we solve,
    
     and    

We find, and   

    Solving linear equations can be accomplished by Euler's Theorem; however, solving the quadratic congruence is something else. Solving this type of congruence equation: becomes the impetus.

Definition (Quadratic Residue) Let   be a positive integer with     
    
    (i) If has a solution then is a quadratic residue of
    
    (ii) If does not have solution then is a quadratic nonresidue of
        

Example (Quadratic Residue) Determine the quadratic residues of

    Solution. We compute the squares of the positive integers less than 13 namely: and Therefore, the quadratic residues of 13 are and the quadratic nonresidues of 13 are

    From this example we notice, if is a solution for then so is If then and so since is odd. Clearly, this can not happen and so if there are any solutions there are at least two incongruent solutions. If and are both solutions then and so either or Thus there can be only two incongruent solutions for if there are any at all.

Proposition (Quadratic Residue) Let be an odd prime.

    (i)  If then either has no solutions or exactly two incongruent solutions modulo
    
    (ii) There are exactly quadratic residues of and quadratic nonresidues of among
    

Definition (Legendre Symbol) Let be an odd prime with The Legendre symbol is defined as follows:

Example (Legendre Symbol)  Since the quadratic residues of 13 are and the quadratic nonresidues of 13 are We find that

Proposition (Euler's Criterion) Let be an odd prime and Then



    Proof. The only values for are So it suffices to consider the cases and
    If then has a solution say Then by Fermat's Little theorem,  
    


since Conversely, if then has no solution. The key idea is that we can group together the integers into pairs each with product of . Then multiplying these pairs together, and using Wilson's theorem, we have:



To see why we can do this, note that means has exactly one solution say and this must happen precisely when     

Example (Euler's Criterion) Determine and

    Solution. Since we have, by Euler's criterion,
    


and so is a quadratic nonresidue of 23. Similarly,



and so is a quadratic residue of 53.

Proposition (Properties of the Legendre Symbol) Let be an odd prime with and Then

    (i) if then
    
    (ii)  
    
    (iii)  
    
    (iv)
    
    (v) if has prime factorization



and is a prime not dividing , then
    

        
    Proof. (i) The congruence has a solution if and only if does because
    (ii) By Euler's Criterion we know

, and

Therefore,



Because the only values are we have, as desired.
    (iii) Since , part (ii) yields as desired.
    (iv) By (ii) and (iii): as desired.
    (v) By (iv) we have,
    
    

By (iii), we see that

    

as desired.  

Example (Quadratic Character of -1) If is an odd prime, then



    Solution. Every odd prime is of the form (that is ) or of the form   (that is ). In the first case, Euler's Criterion yields



because is even. In the latter case,   is odd and so Euler's Criterion yields

Proposition (Gauss's Lemma) Let be an odd prime with If is the number of least positive residues of the integers that exceed then
    Proof. Let be those least positive residues of that exceed , and be those least positive residues of that do not exceed It follows that



is a permutation of the set [[show it]] and so  



Simplifying with modulus we have



By definition of the and we know,







By appealing to Euler's Criterion.



as desired.

Example (Gauss's Lemma) Find and by using Gauss's Lemma.

    Solution. Since we look at the first 6 multiples of 7 namely: The least positive residues are The number of them that exceed is 3 namely: Therefore,
    Since we look at the first 26 multiples of 9 (mod 53) namely

    

The number of them that exceed is 12. Therefore,      

Proposition (Quadratic Character of 2) If is an odd prime, then



    Proof. Applying Gauss's Lemma, we look at the first multiples of namely These positive integers are all less than and so they are their own least positive residues modulo Let denote the set of least positive residues that exceed as in Gauss's lemma. Since is odd one of the follow cases must hold.

for

for

for



In the first two cases the number of elements in is even and so when In the last two cases the number of elements in is odd and so when   Finally, because is even when and   odd when it follows that as desired.

Proposition (Quadratic Reciprocity) Let and be distinct odd primes, then

Proposition (Quadratic Reciprocity -Alternate Form) Let and be distinct odd primes, then

Example (Quadratic Reciprocity) Evaluate the following Legendre symbols

(a)

    Solution. Since we have Since and we have




(b)

    Solution. To evaluate we note that So we have and since we see that



Finally since and we have




(c)

    Solution.  Since we have



So we break these down into cases as follows

  since

  since

  since

  since

  since

  since

  since

since
and

since

since

















Therefore,

Number Theory Books

A Beginner's Guide to Constructing the Universe: Mathematical Archetypes of N... List Price: $18.95 Buy New: $7.50 You Save: $11.45 (60%) New (32) Used (23) from $7.50The Universe May Be a Mystery,But It's No SecretMichael Schneider leads us on a spectacular, lavishly illustrated journey along the numbers one through ten to explore the mathematical principles made visible (more)

Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathem... List Price: $16.00 Buy New: $8.75 You Save: $7.25 (45%) New (38) Used (19) from $7.49In 1859, Bernhard Riemann, a little-known thirty-two year old mathematician, made a hypothesis while presenting a paper to the Berlin Academy titled "On the Number of Prime Numbers Less Than a Given Quantity." (more)

Bayesian Computation with R (Use R) List Price: $49.95 Buy New: $37.86 You Save: $12.09 (24%) New (36) Used (13) from $35.00There has been a dramatic growth in the development and application of Bayesian inferential methods. Some of this growth is due to the availability of powerful simulation-based algorithms to summarize (more)

Euler's Gem: The Polyhedron Formula and the Birth of Topology List Price: $27.95 Buy New: $16.98 You Save: $10.97 (39%) New (31) Used (4) from $16.98Leonhard Euler's polyhedron formula describes the structure of many objects--from soccer balls and gemstones to Buckminster Fuller's buildings and giant all-carbon molecules. Yet Euler's formula is so (more)

e: The Story of a Number List Price: $19.95 Buy Used: $2.94 You Save: $17.01 (85%) New (11) Used (37) Collectible (1) from $2.94The interest earned on a bank account, the arrangement of seeds in a sunflower, and the shape of the Gateway Arch in St. Louis are all intimately connected with the mysterious number e. In this informal (more)

Not Even Wrong: The Failure of String Theory and the Search for Unity in Phys... List Price: $16.95 Buy New: $7.61 You Save: $9.34 (55%) New (33) Used (11) from $7.27When does physics depart the realm of testable hypothesis and come to resemble theology? Peter Woit argues that string theory isn't just going in the wrong direction, it's not even science. Not Even Wrong (more)

Killer Poker By the Numbers: Mathematical Edge for Winning Play List Price: $14.95 Buy New: $6.99 You Save: $7.96 (53%) New (34) Used (13) from $6.99Killer Poker By the Numbers: Mathematical Edge for Winning Play (more)

Elementary Number Theory (5th Edition) List Price: $124.00 Buy New: $99.20 You Save: $24.80 (20%) New (10) Used (17) from $95.50Elementary Number Theory and Its Applications is noted for its outstanding exercise sets, including basic exercises, exercises designed to help students explore key concepts, and challenging exercises. (more)

Complex Analysis for Mathematics and Engineering List Price: $124.95 Buy New: $44.94 You Save: $80.01 (64%) New (14) Used (14) from $44.94Revised and updated, the new Fifth Edition of Complex Analysis for Mathematics and Engineering presents a comprehensive, student-friendly introduction to Complex Analysis. It's clear, concise writing (more)

Dr. Euler's Fabulous Formula: Cures Many Mathematical Ills List Price: $29.95 Buy New: $14.75 You Save: $15.20 (51%) New (42) Used (16) from $14.49I used to think math was no fun'Cause I couldn't see how it was doneNow Euler's my heroFor I now see why zeroEquals e[pi] i+1--Paul Nahin, electrical engineer In the mid-eighteenth century, Swiss-born (more)