Why are primitive roots called generators?

Question

I learned recently that the reason that g is commonly used to denote a primitive root is because it stands for "generator". I also know that this has something to do with the non-zero residues. However I don't understand how a g could be used to "generate" all non-zero residues.

Answer 1

The relevant (and cool) fact is this: if $g$ is a primitive root modulo $n$ (so that $g$ has multiplicative order $\phi(n)$ modulo $n$), then every integer in the world that is relatively prime to $n$ is congruent modulo $n$ to some power of $g$. In other words, the powers of $g$ "generate" the entire set of reduced residue classes modulo $n$. (In terms of groups: the multiplicative group of reduced residue classes modulo $n$ is cyclic, and $g$ is a generator for that cyclic group.)

Answer 2

Let $p$ be a prime number. Consider all non-zero residues modulo $p$. We can multiply two non-zero residues and obtain a non-zero residue as well, also there is a trivial non-zero residue (equal to $1$), and, finally, each non-zero residue has an inverse. In other words, the set of non-zero residues modulo $p$ is a group over multiplication (it's often denoted by $\mathbb{Z}_p^*$). Let $g$ be any primitive root now. One can see that $g$ is a generator of this group (and hence this group is cyclic), that is, each non-zero residue equals $g^k$ for some integer $k$.

If we consider a composite base $m$, it's not enough to consider non-zero residues since they are not a group (for example, $2\times3=0$ modulo $6$). One should instead consider all residues coprime with $m$ (the set of such residues is also a group over multiplication and it's also denoted by $\mathbb{Z}_m^*$). Again, if there is a primitive root modulo $m$, it generates this group.