My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum

Thanks Tree2Thanks
  • 1 Post By CRGreathouse
  • 1 Post By Olinguito
LinkBack Thread Tools Display Modes
March 9th, 2015, 09:51 AM   #1
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?


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
MadSoulz is offline  
March 9th, 2015, 10:53 AM   #2
Global Moderator
CRGreathouse's Avatar
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
CRGreathouse is offline  
March 10th, 2015, 07:09 AM   #3
Senior Member
Olinguito's Avatar
Joined: Apr 2014
From: Greater London, England, UK

Posts: 320
Thanks: 156

Math Focus: Abstract algebra
Originally Posted by MadSoulz View Post
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$.
Thanks from MadSoulz
Olinguito is offline  

  My Math Forum > College Math Forum > Number Theory

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

Copyright © 2019 My Math Forum. All rights reserved.