Recall that if we fix a prime p, then a primitive root modulo p is an integer r such that every element of Zp* (the residue classes relatively prime to p) is congruent to a power of r. As you may have discovered in the previous chapter, every prime has a primitive root. Thus, if r is a primitive root modulo p, then every nonzero residue class a modulo p can be written as
r j
(mod p)
for a unique value of j between 0 and p – 1. In this section, we shall determine which values of j produce quadratic residues, and which values produce quadratic nonresidues.
To aid you in your explorations, several applets are provided for your use. We begin with one you saw in a previous section:
The next applet will return the smallest primitive root mod p For example, here's the smallest primitive root mod 23:
The third applet takes a prime p as input, and provides the following output: a list of the quadratic residues modulo p; the smallest primitive root r modulo p; and, a table of the values of r1, r2, r3, . . . , rp–1, each reduced modulo p. Go ahead – try it out. (You know you want to!)
Note that the table of values r1, r2, r3, . . . may scroll off of the page to the right; use the scrollbar at the bottom to see the whole list. You should be able to use data collected from this applet to tackle the next research question.
Research Question 3Let p be a prime and r a primitive root mod p. Characterize the exponents j such that r j is a quadratic residue mod p. |
Once you have completed Research Question 3, you should be able to finish off Research Question 1. If you haven't already done so, go back and complete your proof.
We close out this section with an exercise that gives a result that is useful, in certain situations, for determining whether an integer is a quadratic residue modulo a prime. The result is known as Euler's Criterion, and is stated in the exercise below.
Exercise 1
Prove the following: Euler's Criterion: Suppose that p is an odd prime and that a is an integer not divisible by p. If a is a quadratic residue modulo p, then
1 (mod p),
and if a is a quadratic nonresidue modulo p, then
–1 (mod p).
|