Recall that if we fix a prime

p, then aprimitive rootmodulopis an integerrsuch that every element ofZ_{p}^{*}(the residue classes relatively prime top) is congruent to a power ofr. As you may have discovered in the previous chapter, every prime has a primitive root. Thus, ifris a primitive root modulop, then every nonzero residue classamodulopcan be written asar(mod^{ j}p)for a unique value of

jbetween 0 andp– 1. In this section, we shall determine which values ofjproduce 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

pFor example, here's the smallest primitive root mod 23:

The third applet takes a prime

pas input, and provides the following output: a list of the quadratic residues modulop; the smallest primitive rootrmodulop; and, a table of the values ofr^{1},r^{2},r^{3}, . . . ,r^{p–1}, each reduced modulop. Go ahead – try it out. (You know you want to!)Note that the table of values

r^{1},r^{2},r^{3}, . . . 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 3

Let

pbe a prime andra primitive root modp. Characterize the exponentsjsuch thatr^{ j}is a quadratic residue modp.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 thatpis an odd prime and thatais an integer not divisible byp. Ifais a quadratic residue modulop, thena^{(p–1)/2}1 (modp),and if

ais a quadratic nonresidue modulop, thena^{(p–1)/2}–1 (modp).

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

Copyright © 2001 by W. H. Freeman and Company