What is the most motivating way to introduce primitive roots?

Question

I am teaching elementary number theory to first year undergraduate students. How do introduce the order of an integer modulo n and primitive roots? How do I make this a motivating topic and are there any applications of this area? I am looking at something which will have an impact.

Answer 1

Take a cyclic group of prime order minus one this is $C_{p-1}$. Then the cyclic group $C_{p-1}$ is isomorphic to the group of integers mod p. This is $C_{p-1} \cong (\mathbb{Z}/\mathbb{pZ})^{x}$. Other notations include $\mathbb{F_p}$ and $\mathbb{Z}_p^{*}$.

A primitive root $g \in \mathbb{Z_p^*}$ is an element (generator) that generates the whole group thus its order is the order of the group. Since the order of $G$ is $p-1$, we say that the order of $g$ in the group $G$ must be $p-1$ too. It results that there are $\varphi(\varphi(p))$ of them.

The concept of order can be described as:

$Ord_G(g) = n$ and is read as: the order of element $g$ in $G$ is $n$. This means that the element $g$ will generate a subgroup $H \leqslant G$ of order $n$. This is the subgroup $H = <g>$.

A further explanation on Cryptography as noted in comments can be useful to understand the role of Number Theory and Group Theory on Computer Security, concretely on Cryptosystems.

On Diffie-Hellman the modulus is prime, and the generator $g$ generates a large subgroup of order $q$ where $q$ is large enough, giving a sufficient size of residues mod p. As seen above, these concepts work well with my explanation.

After explaining Diffie-Hellman key exchange you can show how to encipher or compute digital signatures with a slight change on the scheme (Elgamal).

As for me I got interested on these branches since Crypto. Making it easy to other people may raise the chance to bring them to the field.