My Math Forum Questions about QRs and Legendre symbol

 Number Theory Number Theory Math Forum

 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 (p-1)/2$ QRs modulo p and exactly $\displaystyle (p-1)/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 (p-1)/2 nonresidues, (p-1)/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.) Thanks from MadSoulz
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
Quote:
 Originally Posted by MadSoulz 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}$
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

### solved question of legrendre symbol

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Kaotico57 Number Theory 2 February 21st, 2015 11:52 AM mathbalarka Calculus 1 April 25th, 2012 06:25 AM Scooter Number Theory 0 October 14th, 2010 05:53 AM tinynerdi Number Theory 8 September 14th, 2010 04:58 PM randarrthebarbarian Number Theory 3 October 8th, 2009 05:51 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top