11.2   Counting Quadratic Residues

It is easy to have Java produce a list of quadratic residues by automating the method used in the Prelab section. Specifically, the applet below computes a2 % n for each value of a satisfying gcd(a, n) = 1 and 1 <= a <= n. The resulting output contains the quadratic residues. Try it out:

Your browser does not support java.

In the very near future, you will want to count the number of quadratic residues modulo a prime. You can do so using a modified version of the previous applet that includes the number of quadratic residues in the list, thus avoiding the tedium of counting them yourself.

Your browser does not support java.

Research Question 1

If p is an odd prime, how many quadratic residues are there mod p?

Hint: The content of the next few sections my be helpful in proving your conjecture.

Section 11.1 | Section 11.2 | Section 11.3 | Section 11.4 | Section 11.5 | Section 11.6

Chapter 11 | DNT Table of Contents

Copyright © 2001 by W. H. Freeman and Company