
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
March 9th, 2015, 09:51 AM  #1 
Member Joined: Jun 2012 From: San Antonio, TX Posts: 84 Thanks: 3 Math Focus: Differential Equations, Mathematical Modeling, and Dynamical Systems  [SOLVED] Questions about QRs and Legendre symbol
Textbook: A Friendly Introduction to Number Theory 4th by Silverman When $\displaystyle p$ is prime, $\displaystyle a\overwithdelims () p$ = $\displaystyle \begin{cases} 1 & \text{if } a \text{ is a QR modulo p,} \\ 1 & \text{if } a \text{ is a NR modulo p} \end{cases}$ For me, QRs (Quadratic Residues) are numbers whose squares modulo p are perfect squares. For example, 0 > 0 1 > 1 2 > 4 3 > 4, since 9 modulo 5 is congruent to 4 4 > 1, since 16 modulo 5 is congruent to 1 There's a theorem that states that if p is an odd prime, then there are exactly $\displaystyle (p1)/2$ QRs modulo p and exactly $\displaystyle (p1)/2$ NRs modulo p. Doesn't the example above show 4 QRs? EDIT: My definition shows that I didn't understand quadratic residues at all. In the list I have, the QRs modulo 5 are 1 and 4, which makes 2 and 3 NRs. Last edited by MadSoulz; March 9th, 2015 at 10:15 AM. Reason: Answered my own question 
March 9th, 2015, 10:53 AM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms 
There are two kinds of squares mod a given odd prime: those which are coprime to the prime (this is 0) and the rest. There are (p1)/2 nonresidues, (p1)/2 coprime residues, and 0. The Legendre symbol tells you into which camp a given number falls. Note that if you use the Jacobi symbol (n may be composite) the cases are less clear. There are noncoprime residues not equal to 0, and some nonresidues have Jacobi symbol 1. (But no residue has symbol 1.) 
March 10th, 2015, 07:09 AM  #3 
Senior Member Joined: Apr 2014 From: Greater London, England, UK Posts: 320 Thanks: 156 Math Focus: Abstract algebra  This assumes that $a$ is not divisible by $p$. Some authors add that $\displaystyle\left(\frac ap\right)=0$ iff $p\mid a$.


Tags 
legendre, qrs, questions, symbol 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Legendre's Conjecture!  Kaotico57  Number Theory  2  February 21st, 2015 11:52 AM 
Legendre function  mathbalarka  Calculus  1  April 25th, 2012 06:25 AM 
Legendre symbol help...  Scooter  Number Theory  0  October 14th, 2010 05:53 AM 
legendre symbols.  tinynerdi  Number Theory  8  September 14th, 2010 04:58 PM 
the Legendre equation  randarrthebarbarian  Number Theory  3  October 8th, 2009 05:51 AM 