NTIC Exercises

Prove Lemma 10.3.4. 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. 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 $ϕ (d)$ incongruent integers modulo $p$ have order $d$ modulo $p .$ Hint: Lagrange's (polynomial) Theorem 7.4.1.

🔗

8.

Find the orders of all elements of $U_{13},$ including of course the primitive roots, if they exist. Then verify Claim 10.4.4 for $p = 13 .$

🔗

9.

Challenge: Assuming $p$ is prime, and without using Claim 10.4.4, prove that there are exactly $ϕ (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 .$

🔗

11.

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 $2 p^{e} .$

🔗

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 $ϕ (n)$ ) and $gcd (a, n) = 1,$ 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.

$3 x^{5} \equiv 1$ (mod $23$ )

🔗

20.

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

🔗

21.

For which positive integers $a$ is the congruence $a x^{4} \equiv 2$ (mod $13$ ) solvable?

🔗

22.

Conjecture what the product of all primitive roots modulo $p$ (for a prime $p > 3$ ) 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.)