# Generators in Z_{p}

An Interactive Applet powered by Sage and MathJax.

(By Alyssa Vorpahl and Prof. Gregory V. Bard)

## Overview

This page will discuss what it means for a member of the group Z mod p to be a **generator** of that group.

## Discussion

You may recall from the previous interact that we discussed the idea of analyzing the sequence g^{0}=1, g^{1}=g, g^{2}, g^{3}, ... looking for repetitions, and how it led to the concept of 'generators'. For an element g in a group G to **generate** G, the following two equivalent statements must be true:

- Every element of the group G can be found in the sequence g
^{0}=1, g^{1}=g, g^{2}, g^{3}, ... . Moreover, we can stop checking the first time there is any repetition in that sequence.
- For every integer i such that 0≤i≤Phi(p), we need g
^{i} to be a distinct value. Note, Phi(p) is the **order** of the group - the number of elements in the group.
- Note, for primes p, Phi(p)=p-1, so we always know the size of the group. In other cases it can be more complicated. For example, if N=pq where p and q are distinct primes, then Phi(N)=(p-1)(q-1). Also, if N = p
^{2} the square of a prime, then Phi(N)=p(p-1).

In other words, g^{i} must repeat itself at the last possible moment. Then, since there is a number of distinct g^{i}'s equal to the number of group elements, each element of the group can be written as g^{i} for some i. Thus, by g being raised to increasing powers, the sequence g^{0}=1, g^{1}=g, g^{2}, g^{3}, ... has listed the entire group.

## Instructions

This app will allow you to select a base number (g) and the modulus (p). It will then raise g to each power between 0 and Phi(p), marking any repeated results. If there are no repeats, then it will notify you that the group element g is, in fact, a generator.

Also, notice that we refer to the modulus as p instead of N here. This is because we are only considering prime values for the modulus.

Once you load the applet, there will be two sliders: one to control the g value, and one to control the modulus p.

- g must be < p because it has to be an element of the group Z
_{p}.

Last modified by Alyssa Vorpahl on December 6th, 2018. Updated to Python 3 by Prof. Bard on April 7th, 2020.