Exercises 10.6 Exercises
1.
Find primitive roots of 18, 23, and 27 (one for each modulus) using Lemma 10.2.3 to test various numbers.
2.
If \(a\) is a primitive root of \(n\text{,}\) prove that \(a^{-1}\) is also a primitive root of \(n\text{.}\)
3.
Show that there is no primitive root for \(n=8\text{.}\)
4.
Show that there is no primitive root for \(n=12\text{.}\)
5.
Find two primitive roots of \(81\) using the Euler \(\phi\) criterion Lemma 10.2.3 (that is, by hand).
6.
Prove Lemma 10.3.4. Suppose \(p\) is prime and the order of \(a\) modulo \(p\) is \(d\text{.}\) Prove that if \(b\) and \(d\) are coprime, then \(a^b\) also has order \(d\) modulo \(p\text{.}\) Hint: actually write down the powers of \(a^b\text{,}\) and figure out which ones could actually be 1. Lagrange's (group) Theorem 8.3.12 could also be useful.
7.
Prove Lemma 10.3.5. 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\text{.}\) Hint: Lagrange's (polynomial) Theorem 7.4.1.
8.
Find the orders of all elements of \(U_{13}\text{,}\) including of course the primitive roots, if they exist. Then verify Claim 10.4.4 for \(p=13\text{.}\)
9.
Challenge: Assuming \(p\) is prime, and without using Claim 10.4.4, prove that there are exactly \(\phi(p-1)\) primitive roots of \(p\) if there is at least one.
10.
Finish the proof of Fact 10.3.6 for the case of composite \(n\text{.}\)
11.
Challenge: Assume that \(a\) is an odd primitive root modulo \(p^e\text{,}\) 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\text{.}\)
12.
Solve \(x^6\equiv 4\) (mod \(29\)).
13.
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.
14.
Prove this crucial key to solving congruences by looking at the exponents in Section 10.5: If \(x\equiv y\) (mod \(\phi(n)\)) and \(\gcd(a,n)=1\text{,}\) show that \(a^x\equiv a^y\) (mod \(n\)). Hint: Theorem 9.2.5.
Find all solutions to the following. Making a little table of powers of a primitive root modulo 23 first would be a good idea.
15.
\(x^3\equiv 2\) (mod \(23\))
16.
\(3^x\equiv 2\) (mod \(23\))
17.
\(x^4\equiv 2\) (mod \(23\))
18.
\(13^x\equiv 5\) (mod \(23\))
19.
\(3x^5\equiv 1\) (mod \(23\))
20.
\(3x^{14}\equiv 2\) (mod \(23\))
21.
For which positive integers \(a\) is the congruence \(ax^4\equiv 2\) (mod \(13\)) solvable?
22.
Conjecture what the product of all primitive roots modulo \(p\) (for an odd prime \(p\)) is, modulo \(p\text{.}\) Prove it! (Hint: one of the results in Subsection 10.3.2 and thinking in terms of the computational exercises might help.)