# Cyclic groups under mod p multiplication?

I have a quick question:

How does a cyclic group form under $\bmod {p}$ multiplication?

I really think I should know this, but, I really don't understand it, at the moment.

-
How many elements do you think this group has? –  Dilip Sarwate Dec 15 '11 at 18:30
@DilipSarwate, I'm thinking p-1 –  Dhaivat Pandya Dec 15 '11 at 19:37

Let $p$ be a prime. Recall that an integer $g$ is said to be a primitive root for $p$ (or more concretely for $(\mathbb{Z}/p\mathbb{Z})^\times$) if the multiplicative order of $g$ modulo $p$ is $\phi(p)=p-1$. In other words, $g$ is a generator of the cyclic group $(\mathbb{Z}/p\mathbb{Z})^\times$, i.e. $$(\mathbb{Z}/p\mathbb{Z})^\times =\{1,2,3,\ldots,p-1\}= \{ 1, g, g^2,\ldots,g^{p-2}\}.$$ Before we go into the proof of the main theorem, we define the term least universal exponent'' and prove a lemma.

Definition. Let $N>2$ be a natural number. We say that $n$ is the least universal exponent for $\mathbb{Z}/N\mathbb{Z}$ if $a^n\equiv 1\bmod N$ for all $a\in (\mathbb{Z}/N\mathbb{Z})^\times$ and $n$ is the least positive integer with this property.

It follows from Euler's theorem that the least universal exponent $n$ of $\mathbb{Z}/N\mathbb{Z}$ is less or equal to the value of Euler's phi function $\phi(n)$, and in fact, the least universal exponent should divide $\phi(n)$.

Lemma. Let $p$ be a prime and let $n$ be the least universal exponent of $\mathbb{Z}/p\mathbb{Z}$. Then there is a number $a\in (\mathbb{Z}/p\mathbb{Z})^\times$ whose order is precisely $n$.

Proof. In this proof we will use the properties of the multiplicative order of an integer. We shall prove that (a) the least universal exponent is the least common multiple of all the orders of all the elements of $(\mathbb{Z}/N\mathbb{Z})^\times$, and (b) there is an element whose order is exactly the least common multiple. In order to show (a) and (b), it suffices to show that if $a$ and $b$ have orders $\operatorname{ord}(a)=h$ and $\operatorname{ord}(b)=k$ then there is an element $c$ whose order is $\operatorname{ord}(c)=\operatorname{lcm}(h,k)$. This is clear: if $q$ is a prime and $q^i$ divides $h=\operatorname{ord}(a)$ then, there is an element whose order is $p^i$ (namely $a^{h/q^i}$ has such order); and if $h'=\operatorname{ord}(c)$ and $k'=\operatorname{ord}(d)$ are relatively prime then $\operatorname{ord}(cd)=h'k'$. Finally, suppose that $\operatorname{lcm}(h,k)=q_1^{i_1}\cdots q_t^{i_t}$, for some distinct primes $q_1,\ldots, q_t$ and positive integers $i_1,\ldots,i_t$. Then, each $q_j^{i_j}$ divides either $h$ or $k$ and there is an element $c_j$ of order exactly $q_j^{i_j}$. Thus, the element $c=c_1\cdots c_t$ has exact order $\operatorname{lcm}(h,k)$.

Theorem. Every prime $p$ has a primitive root.

The following proof is due to Legendre.

Proof. If $p=2$ then $g=1$ is a primitive root. Let us assume that $p>2$ is prime and let $n$ be the least universal exponent for $p$, i.e. $n$ is the smallest positive integer such that $x^n\equiv 1 \bmod p$, for all non-zero $x\in \mathbb{Z}/p\mathbb{Z}$. Notice that, in particular by the Lemma, there is some element $g\in \mathbb{Z}/p\mathbb{Z}$ such that $g^n\equiv 1$ but $g^m\neq 1 \bmod p$ for any $m<n$, i.e. the multiplicative order of $g$ is precisely $n$. Also, notice that by Fermat's little theorem, $n\leq p-1$.

Now, the polynomial $f(x)=x^n-1$ has at most $n$ roots over the field $\mathbb{Z}/p\mathbb{Z}$, and $f(x)\equiv 0 \bmod p$ for all non-zero $x \bmod p$. Thus $n\geq p-1$. Hence, $n=p-1$ and $g$ is of exact order $p-1$, therefore $g$ is a primitive root.

-
It is not clear to me why ord(cd)=h'k' just because ord(c)=h' and ord(d)=k' and these are relatively prime. It is clear that (cd)^(h'k')=1 but not that h'k' is the smallest number with this property. –  Erland Gadde Aug 21 '13 at 12:09
@ErlandGadde, you are right, that step is not obvious and needs some explanation. Suppose $\gcd(h',k')=1$, and let $t=\operatorname{ord}(cd)$. Clearly, $(cd)^{h'k'}=1$ so $t$ is a divisor of $h'k'$. In addition, $c^{tk'}=c^{tk'}\cdot 1=c^{tk'}d^{tk'}=(cd)^{tk'}=((cd)^t)^{k'}=1^{k'}=1$. Thus, $h'$ divides $tk'$. Since $h'$ and $k'$ are relatively prime, it follows that $h'$ divides $t$. By symmetry, the same argument shows that $k'$ divides $t$. Again, since they $\gcd(h',k')=1$, it follows that $h'k'$ divides $t$, which is also a divisor of $h't'$... so $t=h'k'$ and we are done. –  Álvaro Lozano-Robledo Aug 22 '13 at 2:56

This is stated a little awkwardly: I think what you are asking is "Why do the integers modulo $p$, excluding the zero element (i.e. the integers divisible by $p$), form a cyclic group under multiplication?"

The key to showing that this is a group is Bezout's lemma, which states that if $m$ and $n$ are integers with greatest common divisor $d$, then there exist integers $r$ and $s$ such that $rm + sn = d$. In particular, if $m = p$ and $n$ is not divisible by $p$, then $d = 1$ and this says precisely that $n$ has a multiplicative inverse modulo $p$.

As for proving that this group is cyclic, the point is that all the nonzero elements of $\mathbb{Z}/p\mathbb{Z}$ are roots of unity (meaning some power is $1$). Try proving that any finite subgroup of the nonzero complex numbers $\mathbb{C}^{\times}$ under multiplication is cyclic: the argument is identical. If you need more hints, let me know.

-
I still don't understand what the generator of this group would be :( –  Dhaivat Pandya Dec 15 '11 at 19:36
I don't understand your last paragraph. If $(G,\cdot)$ is a finite group (in this case $G=(\mathbb{Z}/p\mathbb{Z})^\times)$, then it is always true that $g^{|G|}=1$, but that does not mean that $G$ is necessarily cyclic - not even if you assume that $G$ is abelian. –  Álvaro Lozano-Robledo Dec 15 '11 at 19:53
Wait, but, how is + even defined if its a group with only one operation on it? –  Dhaivat Pandya Dec 15 '11 at 19:58
@DhaivatPandya Everything here is constructed from the integers. The integers have addition, and the addition is used to define the equivalence relation that yields $\mathbf Z/p\mathbf Z$ and hence $(\mathbf Z/p\mathbf Z)^*$. I admit that this is a little confusing, but in the end Justin's suggestion will produce an inverse $s$ for $n$ mod $p$. –  Dylan Moreland Dec 15 '11 at 20:26
@Álvaro Lozano-Robledo: certainly I was being a bit vague. The key point is that $x^n - 1$ has at most $n$ roots in any field: one does not have an analogue of this fact in an arbitrary finite group. However, I am pretty sure one could prove that if $G$ is a finite group such that $x^n = 1$ has at most $n$ solutions for all $n$, then $G$ is cyclic. –  Justin Campbell Dec 15 '11 at 20:46