Section10.6Exercises

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.)
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 theorem (the polynomial one).)
Find the orders of all elements of $U_{13}$, including of course the primitive roots, if they exist. Then verify the above statement.
Challenge: assuming $p$ is prime, prove that there are exactly $\phi(p-1)$ primitive roots of $p$ if there is at least one.
Find primitive roots of 18, 23, and 27 using the criterion above to test various numbers.
If $a$ is a primitive root of $n$, prove that $a^{-1}$ is also a primitive root of $n$.
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$.
Prove that an odd primitive root modulo an odd prime power is still a primitive root for twice that modulus.
Solve $x^6\equiv 4$ mod ($23$).
Solve $x^4\equiv 4$ mod ($99$) by using the backwards CRT to write this as the product of two congruences which CAN be solved with primitive roots, and then putting them back together.
Find all primitive roots of 18, 23, and 27.
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)
For which positive integers $a$ is the congruence $ax^4\equiv 2$ mod (13) solvable?
Conjecture what the product of all primitive roots modulo $p$ (for an odd prime $p$) is, modulo $p$. Prove it! (Hint: one of the lemmas and thinking in terms of the computational homeworks might help.)
Find two primitive roots of $81$ using the Euler $\phi$ criterion we used before (that is, by hand).