NTIC Exercises

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.)