1

Find primitive roots of 18, 23, and 27 using Lemma 10.2.3 to test various numbers.

2

If \(a\) is a primitive root of \(n\), prove that \(a^{-1}\) is also a primitive root of \(n\).

3

Show that there is no primitive root for \(n=8\).

4

Find two primitive roots of \(81\) using the Euler \(\phi\) criterion Lemma 10.2.3 (that is, by hand).

5

Suppose \(p\) is prime and the order of \(a\) modulo \(p\) is \(d\). Prove that if \(b\) and \(d\) are coprime, then \(a^b\) also has order \(d\) modulo \(p\). (Hint: actually write down the powers of \(a^b\), and figure out which ones could actually be 1.)

6

Suppose \(p\) is prime and \(d\) divides \(p-1\) (and hence is a possible order of an element of \(U_p\)). Prove that at most \(\phi(d)\) incongruent integers modulo \(p\) have order \(d\) modulo \(p\). Hint: Lagrange's (polynomial) Theorem 7.4.1.

7

Find the orders of all elements of \(U_{13}\), including of course the primitive roots, if they exist. Then verify Claim 10.4.2.

8

Challenge: assuming \(p\) is prime, prove that there are exactly \(\phi(p-1)\) primitive roots of \(p\) if there is at least one. (Don't use Claim 10.4.2.)

9

Challenge: Assume that \(a\) is an odd primitive root modulo \(p^e\), where \(p\) is an odd prime (that is, both \(a\) and \(p\) are odd). Prove that \(a\) is also a primitive root modulo \(2p^e\).

10

Solve \(x^6\equiv 4\) (mod \(23\)).

11

Solve \(x^4\equiv 4\) (mod \(99\)) by writing this as the combination of two congruences which can be solved with primitive roots, and then using Subsection 5.4.1 to put them back together.

12

If \(x\equiv y\) (mod \(\phi(n)\)), show that \(a^x\equiv a^y\) (mod \(n\)). Hint: Theorem 9.2.3.

13

Find all solutions to the following. Making a little table of powers of a primitive root modulo 23 first would be a good idea.

• \(3x^5\equiv 1\) (mod \(23\))

• \(3x^{14}\equiv 2\) (mod \(23\))

• \(3^x\equiv 2\) (mod \(23\))

• \(13^x\equiv 5\) (mod \(23\))

14

For which positive integers \(a\) is the congruence \(ax^4\equiv 2\) (mod \(13\)) solvable?

15

Conjecture what the product of all primitive roots modulo \(p\) (for an odd prime \(p\)) is, modulo \(p\). Prove it! (Hint: one of the results in Subsection 10.3.2 and thinking in terms of the computational exercises might help.)