with any modulus n > 2. (So do quadratic residues, e.g., a = 1.) Exercise 6.3. Suppose g is a primitive root modulo n > 2. a) Show that gk is a quadratic residue modulo n if and only if k is even. In particular, it follows that every primitive root is a quadratic nonresidue. b) Prove there are as many quadratic residues as nonresidues modulo n. Chapter 9 Quadratic Residues 9.1 Introduction Deﬁnition 9.1. We say that a2Z is a quadratic residue mod nif there exists b2Z such that a b2 mod n: If there is no such bwe say that ais a quadraticnon-residue mod n.

Article 95 introduces the terminology "quadratic residue" and "quadratic nonresidue", and states that, if the context makes it clear, the adjective "quadratic" may be dropped. For a given n a list of the quadratic residues modulo n may be obtained by simply squaring the numbers 0, 1, …, n − 1. Suppose we have b2 = a. Then ( − b)2 = a as well, and since b ≠ − b (since p > 2) every quadratic residue has at least two square roots (actually we know from studying polynomials there can be at most two), thus at most half the elements of Z ∗ p are quadratic residues.