MATH 319 Exploratory Assignment on nth Power Residues

1. Definition: Let p be a prime and let (a,p) = 1. Then a is an nth power residue mod p if there is a solution to .

2. Theorem: Let p be a prime and let (a,p) = 1. Then has either (n,p-1) solutions or no solutions according as or not.

For each of the following pairs of prime p and power n, run the program Power Residues mod p. This will produce a list of a’s that are nth power residues mod p. It will also give you the values of x for each a. Then answer the following questions:

1. How many solutions are there to when a solution exists? Does this agree with the theorem stated above?

2. How many a’s have solutions? That is how many different a’s are nth power residues mod p? How is this number connected to the number found in question 1?

3. Given a primitive root mod p, which powers of the primitive root correspond to the numbers found in question 2?

Pairs of prime p and power n:

i) p = 19 and n = 2

ii) p = 19 and n = 3

iii) p = 19 and n = 5

iv) p = 29 and n = 2

v) p = 29 and n = 7

vi) p = 29 and n = 10

2 is a primitive root of both 19 and 29.