# What is the most motivating way to introduce primitive roots?

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.

• How about Diffie-Hellman key exchange? – Lord Shark the Unknown Jun 15 '18 at 4:11
• I have used Diffie-Hellman key exchange for motivation as follows. I lead up to it by designing a homework assignment where the students were asked to solve a discrete logarithm problem modulo a prime like $p=107$ (large enough, but not too large). As an aid I gave them key pieces of a homomorphism from $\Bbb{Z}_{107}^*$ to $\Bbb{Z}_{106}$ (most students, not unpredictably, didn't see how to use the homomorphism, but brute forced the solution instead). Then, in the problem session, after this problem I took the stage and outlined Diffie-Hellman. I did get positive feedback for this in the end. – Jyrki Lahtonen Jun 15 '18 at 5:34
• I like the approach of @JyrkiLahtonen. Giving them a challenge, something to work on without extended knowledge, will make them think about the problem. After the deadline, show them the internals of the algorithm including math concepts. Also a good example for teaching can be a basic implementation, so they can rework on properties. – kub0x Jun 15 '18 at 5:42

## 1 Answer

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.