Quadratic residues ap1-1=(ap)2-1)(ap)2+1)=0modp We define the legendre symbol by (+1 if a (p-1)/2=+1 mod p and a#o mod p 3-1 if a(p-1)/2=-1 mod p and a#0 mod p LO if a=0 mod p This implies that a(p-1)2= a mod p More generally, given the prime factorization n=p,p p we define the Jacob Symbol n)(p八(P2)(pQuadratic Residues • a p-1 -1=(a(p-1)/2 -1) (a(p-1)/2+1) = 0 mod p • We define the Legendre symbol by: +1 if a(p-1)/2 = +1 mod p and a  0 mod p = -1 if a(p-1)/2 = -1 mod p and a  0 mod p 0 if a = 0 mod p • This implies that a(p-1)/2 = mod p • More generally, given the prime factorization we define the Jacobi Symbol         p a         p a p p p r r r n k k ... 1 2 1 2 = r a r a r a n a k p p pk                          =      ... 1 2 1 2