Prime Numbers and Generators

Prime num­bers, de­not­ed by $p$ (pro­nounced "pee"), are in­te­gers greater than $1$ whose only pos­i­tive di­vi­sors are $1$ and $p$ itself. Primes are fun­da­men­tal in group theory, par­tic­u­lar­ly when study­ing the group $\mathbb{Z}_n$ under ad­di­tion modulo $n$.

A group is cyclic (pro­nounced "sigh-click") if it can be gen­er­at­ed by a single el­e­ment, called a gen­er­a­tor. In other words, every el­e­ment of the group can be ob­tained by re­peat­ed­ly ap­ply­ing the group op­er­a­tion to the gen­er­a­tor.

For $\mathbb{Z}_n$ under ad­di­tion, an el­e­ment $k$ is a gen­er­a­tor if the set:

con­tains every el­e­ment of $\mathbb{Z}_n$. Here, $\mod n$ means we take the re­main­der after di­vi­sion by $n$.

The cri­te­ri­on for $k$ to be a gen­er­a­tor is that it is co­prime (shares no common fac­tors except $1$) with $n$. This is ex­pressed using the great­est common di­vi­sor func­tion, $\gcd(k, n)$ (pro­nounced "gee-cee-dee of k and n"). Thus,

When $n$ is a prime number $p$, every nonze­ro el­e­ment $k$ in $\mathbb{Z}_p$ is a gen­er­a­tor, since $\gcd(k, p) = 1$ for all $1 \leq k < p$.

Ex­am­ple: $\mathbb{Z}_5$ (In­te­gers Modulo 5)

Let $n = 5$, which is prime.

• The el­e­ments are $\{ 0, 1, 2, 3, 4 \}$.
• Each $k$ in $\{1, 2, 3, 4\}$ is co­prime to $5$.

Thus, every nonze­ro el­e­ment is a gen­er­a­tor.

Ex­am­ple: $\mathbb{Z}_6$ (In­te­gers Modulo 6)

Let $n = 6$, which is not prime.

• The el­e­ments are $\{ 0, 1, 2, 3, 4, 5 \}$.
• Only $k = 1$ and $k = 5$ are co­prime to $6$.

Thus, only $1$ and $5$ are gen­er­a­tors in $\mathbb{Z}_6$.