Solution Found!
Quadratic residues. Fix a positive integer N. We say that a is a quadratic residue
Chapter 1, Problem 1.41(choose chapter or problem)
Quadratic residues. Fix a positive integer N. We say that a is a quadratic residue modulo N if there exists x such that .
(a) Let N be an odd prime and a be a non-zero quadratic residue modulo N. Show that there are exactly two values in {0, 1, …, N-1} satisfying .
(b) Show that is N is an odd prime, there are exactly (N+1)/2 quadratic residues in {0, 1, …, N-1}.
(c) Give an example of positive integers a and N such that has more than two solutions in {0, 1, …, N-1}.
Questions & Answers
QUESTION:
Quadratic residues. Fix a positive integer N. We say that a is a quadratic residue modulo N if there exists x such that .
(a) Let N be an odd prime and a be a non-zero quadratic residue modulo N. Show that there are exactly two values in {0, 1, …, N-1} satisfying .
(b) Show that is N is an odd prime, there are exactly (N+1)/2 quadratic residues in {0, 1, …, N-1}.
(c) Give an example of positive integers a and N such that has more than two solutions in {0, 1, …, N-1}.
ANSWER:Step 1 of 4
An integer a is called quadratic residue modulo N if it is congruent to a perfect square modulo N. In other words, it can be written as if there exists an integer x such that
![x squared identical to a space m o d space N](https://lh6.googleusercontent.com/fHaFBfRbCJfeZiIVW3kV4a96ZyvIL2v1CHgk1AgZSjd0dctR_vbkkjCRMMtP11VmBmmYs0xtIxtzQHMiJV287H4iiPAVoVocRoDb3bcY1jBibmaiGZL7sfILIknYH8NFoH-P5J7J "{\"mathml\":\"<math style=\\"font-family:Arial;font-size:11px;\\" xmlns=\\"http://www.w3.org/1998/Math/MathML\\"><mstyle mathsize=\\"11px\\"><msup><mi>x</mi><mn>2</mn></msup><mo>?</mo><mi>a</mi><mo> </mo><mi>m</mi><mi>o</mi><mi>d</mi><mo> </mo><mi>N</mi></mstyle></math>\"}")