Basic Number Theory 15: Lagrange's theorem, cyclic groups and modular arithmetic

[Nick]

Last time, we introduced the idea of a group, which is any set that comes with a binary operation satisfying 3 conditions:
the operation is associative, the set has a neutral/identity element, and each element of the set has an inverse.
This time, we develop a little more Group Theory and then see how it gives us extra insight into Number Theory.

Let \(G\) be a group and \(g\in G\) an element.
Using the group's binary operation, we can combine \(g\) with itself, getting \(gg\) which we write as \(g^2\), \(ggg\) which we write as \(g^3\), etc.
Similarly, we write \(g^{-2}\) for \(g^{-1}g^{-1}\), \(g^{-3}\) for \(g^{-1}g^{-1}g^{-1}\), etc.
More formally, for each integer \(n\), we define \(g^n\) to be the following element of \(G\):
if \(n=0\) then \(g^n=1\) (i.e. the neutral element of the group \(G\));
if \(n>0\) then \(g^n=g^{n-1}g\);
if \(n<0\) then \(g^n=(g^{-1})^{-n}\).

Note that this is consistent with our notation of \(g^{-1}\) for the inverse of \(g\), and agrees with the usual definition of powers if the elements are numbers.

Proposition 74
Let \(G\) be a group and \(a\in G\). Then, for all integers \(m,n\),
i) \(a^{m+n}=a^ma^n\); and
ii) \(a^{(mn)}=(a^m)^n\).

proof
We first claim that, for all integers \(n\), \((a^{-1})^n=a^{-n}\).
If \(n=0\) then \((a^{-1})^n=1=a^{-n}\).
If \(n>0\) then (by definition) \(a^{-n}=(a^{-1})^{--n}=(a^{-1})^n\).
And if \(n<0\) then \((a^{-1})^n=((a^{-1})^{-1})^{-n}=a^{-n}\).
This proves the claim.
i) Suppose \(m\geq 0\) and \(n\geq 0\).
Induction on \(n\).
In the case \(n=0\): \(a^ma^n=a^ma^0=a^m\cdot 1=a^m=a^{m+0}=a^{m+n}\).
Take any integer \(N>0\) and suppose (i) holds for all non-negative \(n<N\).
Then, in the case \(n=N\), \(a^ma^n=a^ma^{n-1}a=a^{m+n-1}a=a^{m+n}\).
By mathematical induction, (i) holds for all non-negative integers \(m,n\).

Suppose now that \(m\geq 0\) but \(n<0\).
Induction on \(m\).
In the case \(m=0\): \(a^ma^n=a^0a^n=1\cdot a^n=a^n=a^{0+n}=a^{m+n}\).
Take any integer \(M>0\) and suppose (i) holds for all \(m<M\).
In the case \(m=M\), by (i) for non-negative integers we have \(a^m=aa^{m-1}\) so \(a^ma^n=aa^{m-1}a^n=aa^{m+n-1}\) by our assumption.
If \(m+n-1\geq 0\) then \(aa^{m+n-1}=a^{m+n}\) by (i) for non-negative integers, as required.
Otherwise \(-(m+n)\geq 0\) so, by (i) for non-negative integers and by the claim,
\[ aa^{m+n-1}=a(a^{-1})^{-(m+n)+1}=a(a^{-1})^1(a^{-1})^{-(m+n)}=(a^{-1})^{-(m+n)}=a^{m+n}. \]
By mathematical induction, (i) holds for all \(m\geq 0\) with \(n<0\) too.

Suppose instead \(m<0\).
Then in the same way \(a^ma^n=(a^{-1})^m(a^{-1})^{-n}=(a^{-1})^{-m-n}=a^{m+n}\).

ii) Suppose \(n\geq 0\).
Induction on \(n\).
In the case \(n=0\): \(a^{(mn)}=a^0=1=(a^m)^0=(a^m)^n\).
Take any integer \(N>0\) and suppose (ii) holds for all non-negative \(n<N\).
Then, in the case \(n=N\), using part (i) and our assumption,
\[ a^{(mn)}=a^{m(n-1)+m}=a^{m(n-1)}a^m=(a^m)^{n-1}a^m=(a^m)^n. \]
By mathematical induction, (ii) holds for all \(n\geq 0\).

Suppose insted \(n<0\).
By (i), \(a^ma^{-m}=a^{m-m}=1\) so \((a^m)^{-1}=a^{-m}\).
Hence, using this and what we have already proved for \(n\geq 0\),
\[ a^{(mn)}=a^{(-m)(-n)}=(a^{-m})^{-n}=((a^m)^{-1})^{-n}=(a^m)^n. \]
∎

Let \(G\) be a group and \(g\in G\).
If there exists a postive integer \(n\) such that \(g^n=1\in G\) then the smallest such \(n\) is called the order of \(g\).
If no such \(n\) exists, then we say that \(g\) has infinite order.

For example, in the group \(\mathbb{C}\setminus\{0\}\) under multiplication, \(i,i^2\) and \(i^3\) are not equal to 1 but \(i^4=1\) so \(i\) has order 4.
And \(1<2<2^2<2^3<\ldots\) so \(2^n\neq 1\) for all positive integers \(n\), hence 2 has infinite order.
In any group, the neutral element is the unique element with order 1.

If \(G\) is finite, then the number of elements in \(G\) is called the order of \(G\).
We shall see shortly how the order of a finite group is related to the orders of its elements.

Proposition 75
Let \(G\) be a group and \(g\in G\) an element of order \(n\) (a positive integer).
Then the elements \(1,g,g^2,g^3,\ldots,g^{n-1}\) are all distinct (where 1 is the group's neutral element)
and, for all integers \(m\), \(g^m=1\Leftrightarrow n|m\).

proof
Suppose there exist integers \(i,j\in\{0,1,2,\ldots,n-1\}\) such that \(i>j\) but \(g^i=g^j\).
Then \(0<i-j<n\) but, by proposition 74, \(g^{i-j}=g^ig^{-j}=g^{j}g^{-j}=1\) so \(g\) does not have order \(n\), a CONTRADICTION.
Hence the elements \(1,g,g^2,g^3,\ldots,g^{n-1}\) are all distinct.
Take any integer \(m\). By proposition 5, there exist unique integers \(q,r\) such that \(m=qn+r\) and \(0\leq r<n\) (division with remainder).
If \(n\) divides \(m\) then \(r=0\) so, by propostion 74, \(g^m=(g^n)^q=1^q=1\).
If \(n\) does not divide \(m\) then \(0<r<n\) and, again by proposition 74,
\(g^m=g^{nq+r}=(g^n)^qg^r=1^qg^r=g^r\neq 1\) since \(1,g,g^2,g^3,\ldots,g^{n-1}\) are all distinct. ∎

If you are getting dressed, you put on your socks and then your shoes (assuming you dress conventionally).
So, to get undressed, you first take off your shoes and then your socks.
The following lemma is an abstract version of this principle.

Lemma 76
Let \(G\) be a group and \(x,y\in G\).
Then \((xy)^{-1}=y^{-1}x^{-1}\).

proof
We have
\[ (xy)(y^{-1}x^{-1})=x(yy^{-1})x^{-1}=x\cdot 1\cdot x^{-1}=xx^{-1}=1
=(xy)(xy)^{-1} \]
so, by proposition 73, \(y^{-1}x^{-1}=(xy)^{-1}\). ∎

A subgroup of a group \(G\) is a subset \(H\) of \(G\) which itself forms a group under the same binary operation (restricted to \(H\)).

Examples
1. Under addition, \(\mathbb{Q}\) is a subgroup of \(\mathbb{R}\), and \(\mathbb{Z}\) is a subgroup of \(\mathbb{Q}\), hence also a subgroup of \(\mathbb{R}\).
2. Under multiplication, \(\mathbb{Q}\setminus\{0\}\) is a subgroup of \(\mathbb{R}\setminus\{0\}\).
3. For any positive integer \(n\), \(n\mathbb{Z}\) is a subgroup of \(\mathbb{Z}\).
4. For any Gaussian integer \(w\), \(w\mathbb{Z}[i]\) is a subgroup of \(\mathbb{Z}[i]\).
5. Identifying complex numbers with points in a plane in the usual way, let \(L\subset\mathbb{C}\) be the complex numbers corresponding with all points on a straight line through 0.
Then \(L\) is a subgroup of \(\mathbb{C}\) (under addition).
6. Let \(G=\{1,\rho,\rho^2,\sigma,\rho\sigma,\rho^2\sigma\}\), the group of symmetry operations of an equilateral triangle (as explained last time).
Then \(\{1,\rho,\rho^2\}\) is a subgroup of \(G\).
7. The group \(S_3\) of all permutations of the set \(X=\{1,2,3\}\) (also introduced last time) has 6 subgroups in total:
\[ \{i_X\},\{i_X,(1\ 2)\},\{i_X,(1\ 3)\},\{i_X,(2\ 3)\},
\{i_X,(1\ 2\ 3),(1\ 3\ 2)\}, S_3 \]
8. For any group \(G\), \(\{1\}\) is a subgroup of \(G\) (sometimes called the trivial subgroup) and \(G\) itself is a subgroup of \(G\).

Proposition 77
Let \(G\) be a group and \(H\) a subgroup of \(G\).
Then \(H\) has the same neutral element as \(G\) and, for each element \(h\in H\), the inverse of \(h\) is the same in \(H\) as in \(G\).

proof
Let us write \(1\) for the neutral element of \(G\) and \(1'\) for the neutral element of \(H\).
Then \(1'\cdot 1'=1'\) in \(H\), so also in \(G\) (the binary operation is the same in both).
But in \(G\) we have \(1'\cdot 1=1'\) too, so \(1'\cdot 1'=1'\cdot 1\) hence \(1'=1\) (by proposition 73).
Take any \(h\in H\), and let \(x,y\) be the inverses of \(h\) in \(G,H\) respectively.
Then \(hy=1\) in \(H\) so also in \(G\), and in \(G\) we have \(hx=1\) as well,
so \(hy=hx\) and therefore \(y=x\) (by proposition 73). ∎

There is a simple criterion for checking whether a subset of a group is a subgroup:

Proposition 78
Let \(G\) be a group and \(H\) a non-empty subset of \(G\) such that, for all \(x,y\in H\), we also have \(xy^{-1}\in H\).
Then \(H\) is a subgroup of \(G\).

proof
As \(H\) is non-empty, there exists at least one element \(h\in H\) so (putting \(x=h\) and \(y=h\) in the given condition)
\(1=hh^{-1}\in H\), i.e. \(H\) contains the neutral element of the group.
And, for any element \(y\in H\) (putting \(x=1\) in the condition)
\(y^{-1}=1\cdot y^{-1}\in H\) so \(H\) contains the inverse of each of its elements.
Thus, for any \(x,z\in H\), we also have \(z^{-1}\in H\) and therefore (putting \(y=z^{-1}\) in the condition)
\(xz=x(z^{-1})^{-1}\in H\) so \(H\) is closed under the binary operation.
Also, the binary operation is associative for all elements of \(G\) so, in particular, it is associative for all elements of \(H\),
hence \(H\) is a group under this binary operation. ∎

For finite groups, we can make the criterion even simpler:

Proposition 79
Let \(G\) be a finite group and \(H\) a non-empty subset of \(G\) which is closed under \(G\)'s binary operation.
Then \(H\) is a subgroup of \(G\).

proof
Take any element \(h\in H\). We claim that \(h^{-1}\in H\).
As \(H\) is closed under the binary operation, the elements \(h,h^2,h^3,\ldots\) are all elements of \(H\), too.
But \(G\) is finite, so the elements in this infinite list cannot all be different.
Thus there exist positive integers \(i,j\) with \(i>j\) such that \(h^i=h^j\).
Putting \(n=i-j\), we have \(h^n=h^ih^{-j}=h^jh^{-j}=1\) with \(n>0\).
If \(n=1\) then \(h=1\) and \(h^{-1}=h\in H\), as required.
Suppose \(n>1\).
Then \(n-1>0\) so \(h^{n-1}\in H\).
And \(hh^{n-1}=h^n=1=hh^{-1}\) so (by proposition 73) \(h^{-1}=h^{n-1}\in H\).
This proves the claim.
For any \(x,y\in H\), we have \(y^{-1}\in H\) (by the claim) and \(H\) is closed under the binary operation (by assumption) so \(xy^{-1}\in H\).
It follows by proposition 78 that \(H\) is a subgroup of \(G\). ∎

Let \(H\) be a subgroup of a group \(G\). For each element \(g\in G\), we define
\(gH=\{gh:h\in H\}\), called a left coset of \(H\) in \(G\), and
\(Hg=\{hg:h\in H\}\), called a right coset of \(H\) in \(G\).

Proposition 80
Let \(H\) be a subgroup of a group \(G\) and define a relation \(\sim\) on \(G\) by \(x\sim y\Leftrightarrow y^{-1}x\in H\).
Then \(\sim\) is an equivalence relation on \(G\) and, for each \(g\in G\), the equivalence class of \(g\) is precisely \(gH\).

proof
Take any \(x,y,z\in G\).
Then \(x^{-1}x=1\in H\) as \(H\) is a subgroup, so \(x\sim x\).
If \(x\sim y\) then \(y^{-1}x\in H\) and, as a subgroup, \(H\) contains the inverses of all its elements so, by lemma 76, \(x^{-1}y=(y^{-1}x)^{-1}\in H\) and therefore \(y\sim x\).
If \(x\sim y\sim z\) then \(y^{-1}x\in H\) and \(z^{-1}y\in H\), and \(H\) is closed under the group's binary operation (since \(H\) is a subgroup)
so \(z^{-1}x=z^{-1}yy^{-1}x\in H\) hence \(x\sim z\).
Thus \(\sim\) is an equivalence relation on \(G\).
Take any \(g\in G\), and write \([g]\) for the equivalence class of \(g\) under \(\sim\), i.e. \([g]=\{x\in G:x\sim g\}\).
Then, for any \(x\in [g]\), we have \(x\sim g\) so \(g^{-1}x=h\) for some \(h\in H\) and therefore \(x=gh\in gH\). Thus \([g]\subset gH\).
Conversely, for any \(x\in gH\), we have \(x=gh\) for some \(h\in H\) so \(g^{-1}x=g^{-1}gh=h\in H\) and therefore \(x\sim g\) so \(x\in [g]\).
Thus \(gH\subset [g]\) as well,hence \([g]=gH\). ∎

In the same way, if \(H\) is a subgroup of a group \(G\) and \(g\in G\) then the right coset \(Hg\) is the equivalence class of \(g\) under the relation
\(x\sim y\Leftrightarrow xy^{-1}\in H\).

Proposition 81
Let \(H\) be a subgroup of a group \(G\) and \(g\in G\).
Then the function \(f:H\rightarrow gH,x\mapsto gx\) is a bijection.

proof
For any \(x,y\in H\), if \(f(x)=f(y)\) then \(gx=gy\) so, by proposition 73, \(x=y\). Thus \(f\) is injective.
And every element of \(gH\) can be expressed in the form \(gh\) for some \(h\in H\) (by definition) with \(gh=f(h)\)
so \(f\) is surjective as well, and hence bijective. ∎

Notation
Let \(H\) be a subgroup of a group \(G\).
We write \(G/H\) for the set of all left cosets of \(H\) in \(G\),
and \(H\backslash G\) for the set of all right cosets of \(H\) in \(G\).

Proposition 82
Let \(H\) be a subgroup of a group \(G\), and define a function \(f:G/H\rightarrow H\backslash G,gH\mapsto Hg^{-1}\).
Then \(f\) is a well-defined bijection.

proof
For any \(x,y\in G\), if \(xH=yH\) then \(y^{-1}x\in H\) and \(y^{-1}x=y^{-1}(x^{-1})^{-1}\) so \(Hx^{-1}=Hy^{-1}\).
Thus the definition of \(f\) is independent of the chosen representative of the coset, making it well-defined.
For any \(x,y\in G\), if \(f(xH)=f(yH)\) then \(Hx^{-1}=Hy^{-1}\)
so \(y^{-1}x=y^{-1}(x^{-1})^{-1}\in H\) and therefore \(xH=yH\).
Thus \(f\) is injective.
Also, any element of \(H\backslash G\) has the form \(Hy\) for some \(y\in G\) and, putting \(x=y^{-1}\), we have \(f(xH)=Hx^{-1}=H(y^{-1})^{-1}=Hy\).
So \(f\) is surjective, too, making it bijective. ∎

Notation
Let \(H\) be a subgroup of a group \(G\).
By proposition 82, the number of left cosets of \(H\) in \(G\) is finite if and only if the number of right cosets of \(H\) in \(G\) is finite, and then both numbers are equal (exercise 28).
In that case, we call this positive integer the index of \(H\) in \(G\), written \([G:H]\).

Theorem 83 (Lagrange's theorem)
Let \(G\) be a finite group and \(H\) a subgroup of \(G\).
Then \(\#G=\#H\cdot [G:H]\).
In particular, the order of \(H\) divides the order of \(G\).

proof
The left cosets of \(H\) in \(G\) are the equivalence classes under the relation \(\sim\) of propostion 80, so they form a partition of \(G\) (by proposition 35).
And the number of elements in each left coset equals the number of elements in \(H\) by proposition 81, so the number of elements in \(G\) is the number of
elements in \(H\) times the number of left cosets of \(H\) in \(G\). ∎

Corollary 84
Let \(G\) be a finite group and \(g\in G\).
Then the order of the element \(g\) divides the order of the group \(G\).

proof
Let \(n\) be the order of \(g\) in \(G\), which is finite since \(G\) is a finite group, and let \(H=\{1,g,g^2,g^3,\ldots,g^{n-1}\}\).
Then \(H\) is non-empty and closed under the group's binary operation (since \(g^n=1\)) so \(H\) is a subgroup of \(G\) by proposition 79.
And the order of \(H\) is \(n\) (proposition 75) so \(n\) divides \(\#G\) by Lagrange's theorem. ∎

Example
Let \(n\) be a positive integer and \(G\) the unit group \((\mathbb{Z}/n\mathbb{Z})^*\) of the integers modulo \(n\).
Then the order of \(G\) is \(\phi(n)\) (where \(\phi\) is Euler's function) and, for any integer \(a\) with \(\gcd(a,n)=1\), \(\bar{a}\) is an element of \(G\) so the order of \(\bar{a}\) divides \(\phi(n)\) hence \(\bar{a}^{\phi(n)}=1\in G\) (proposition 75).
Thus Fermat's little theorem becomes trivial once we understand Lagrange's theorem.

We call a group \(G\) cyclic if it has an element \(g\in G\) with the following property: for all \(x\in G\) there exists an integer \(n\) such that \(g^n=x\).
Thus, in a cyclic group, every element is simply a power of some fixed element \(g\), and we say that \(G\) is generated by \(g\).

Proposition 85
Let \(p\) be a prime number and \(G\) a group of order \(p\).
Then \(G\) is cyclic.

proof
There exists \(g\in G\) with \(g\neq 1\) (since \(\#G=p\geq 2\)).
By corollary 84, the order of \(g\) divides \(p\), so it is 1 or \(p\) itself, as \(p\) is prime.
But the neutral element \(1\in G\) is the unique element with order 1, so \(g\) has order \(p\).
By proposition 75, the powers of \(g\) give \(p\) distinct elements of \(G\), namely \(1=g^0,g=g^1,g^2,g^3,\ldots,g^{p-1}\).
But \(G\) has only \(p\) elements, so this list includes them all, hence \(G\) is cyclic. ∎

Proposition 86
Let \(G\) be a finite cyclic group of order \(n\) generated by \(g\in G\).
Then, for each positive integer \(d\) which divides \(n\), \(G\) has a subgroup of order \(d\) which is also cyclic, generated by \(g^{\frac{n}{d}}\), and \(G\) has no other subgroups.

proof
We have \(G=\{1,g,g^2,\ldots,g^{n-1}\}\) (all distinct elements) with \(g^n=1\).
Take any positive divisor \(d\) of \(n\) and let \(m\) be the positive integer \(\frac{n}{d}\).
Let \(H=\{1,g^m,g^{2m},\ldots,g^{(d-1)m}\}\).
By proposition 79, \(H\) is a subgroup of \(G\) (since \(g^{dm}=1\)), it has precisely \(d\) distinct elements, and is cyclic, generated by \(g^m=g^{\frac{n}{d}}\).
Now take any subgroup \(K\) of \(G\), and let \(d=\#K\).
By Lagrange's theorem, \(d\) divides \(n\), so \(dm=n\) for some positive integer \(m\).
Each element of \(K\) has the form \(g^i\) for some \(i\in\{0,1,\ldots,n-1\}\)
and \(g^{id}=1\) (corollary 84) so \(n|id\) (proposition 75).
But \(n=dm\) so \(i\) is a multiple of \(m\).
As \(K\) contains \(d\) elements and there are only \(d\) multiples of \(m\) in the set \(\{0,1,\ldots,n-1\}\), it follows that
\(K=\{1,g^m,g^{2m},\ldots,g^{(d-1)m}\}\), which is the cyclic subgroup of \(G\) generated by \(g^m=g^{\frac{n}{d}}\). ∎

A cyclic group may have more than 1 element that generates it.

Proposition 87
Let \(G\) be a finite cyclic group of order \(n\) generated by \(g\in G\).
Then, for all \(i\in\mathbb{Z}\), \(g^i\) also generates \(G\) if and only if \(\gcd(i,n)=1\).

proof
For any integer \(i\), the element \(g^i\) generates \(G\) if and only if \((g^i)^k=g\) for some integer \(k\) (since all elements of \(G\) can be written as powers of \(g\)).
And, for any integer \(k\), \(g^{ik}=g\) if and only if \(g^{ik-1}=1\) which, by proposition 75, holds if and only if \(n|ik-1\), i.e. \(ik\equiv 1\pmod{n}\).
So such a \(k\) exists if and only if \(\bar{i}\) is a unit in the integers modulo \(n\), which is the case if and only if \(\gcd(i,n)=1\) by proposition 32. ∎

Proposition 88
Let \(G\) be a finite cyclic group of order \(n\).
Then, for each positive divisor \(d\) of \(n\), \(G\) contains precisely \(\phi(d)\) distinct elements of order \(d\) (where \(\phi\) is Euler's function).

proof
Take any positive integer \(d\) that divides \(n\).
By proposition 86, \(G\) has a cyclic subgroup \(H\) of order \(d\).
Let \(g\) be a generator of \(H\), giving \(H=\{1,g,g^2,\ldots,g^{d-1}\}\).
For any element \(x\in G\) of order \(d\), the subset \(\{1,x,x^2,\ldots,x^{d-1}\}\) is a subgroup of \(G\) (by proposition 79) but \(H\) is the unique subgroup of \(G\) with order \(d\) (by proposition 86), so this subset is \(H\), and therefore \(H\) is generated by \(x\).
Conversely, any element \(x\in H\) that generates the cyclic subgroup \(H\) has order \(d\), so the elements of \(G\) with order \(d\) are precisely those elements of the cyclic subgroup \(H\) which generate \(H\).
For each \(i\in\{0,1,\ldots,d-1\}\), \(g^i\) is a generator of \(H\) if and only if \(\gcd(i,d)=1\) (by proposition 87), and this holds if and only if \(\bar{i}\) is a unit in the integers modulo \(d\) (by proposition 32),
so the number of elements of \(G\) with order \(d\) equals the number of units in the integers modulo \(d\), which is \(\phi(d)\). ∎

Corollary 89 (Gauss)
Let \(n\) be a positive integer, \(r\) the number of positive integers that divide \(n\), and \(d_1,d_2,\ldots,d_r\) the positive divisors themselves.
Then \(\phi(d_1)+\phi(d_2)+\ldots +\phi(d_r)=n\).

proof
There exists a finite cyclic group \(G\) of order \(n\) (exercise 69 below).
By proposition 88, it has \(\phi(d_1)\) elements of order \(d_1\), \(\phi(d_2)\) elements of order \(d_2\), etc.
As the order of each element of \(G\) divides \(n\) by corollary 84, and the group has precisely \(n\) elements, it follows that \(\phi(d_1)+\phi(d_2)+\ldots +\phi(d_r)=n\). ∎

Theorem 90
For all prime numbers \(p\), the unit group \((\mathbb{Z}/p\mathbb{Z})^*\) of the integers modulo \(p\) is cyclic.

proof
Take any prime number \(p\), and let \(G=(\mathbb{Z}/p\mathbb{Z})^*\), the unit group of the integers modulo \(p\).
Let \(n=\phi(p)\), the order of \(G\) (which is \(p-1\)).
Take any \(a\in G\), let \(d\) be the order of the element \(a\), and define \(H=\{1,a,a^2,\ldots,a^{d-1}\}\).
Then every element of \(H\) satisfies the equation \(x^d-1=0\) (by proposition 75).
But there are no zero divisors in the integers modulo \(p\) (since \(p\) is a prime number) so this equation has at most \(d\) solutions (by propostion 60), and therefore \(H\) contains all of them.
Moreover, any element of \(G\) with order \(d\) satisfies this equation, so \(H\) contains all elements of \(G\) which have order \(d\).
And \(H\) contains precisely \(\phi(d)\) distinct elements of order \(d\) (by proposition 88), so \(G\) has exactly \(\phi(d)\) elements of order \(d\).

Let \(d_1,d_2,\ldots,d_r\) be the distinct positive integers dividing \(n\).
We have shown, for each \(i\in\{1,2,\ldots,r\}\) that if \(G\) contains an element of order \(d_i\) then it contains precisely \(\phi(d_i)\) elements of order \(d_i\).
But the order of every element of \(G\) divides \(n\) (corollary 84)
and \(\phi(d_1)+\phi(d_2)+\ldots +\phi(d_r)=n\) (corollary 89) so,
for each \(i\in\{1,2,\ldots,r\}\), if \(G\) does not contain an element of order \(d_i\) then \(G\) has fewer than \(n\) elements, a CONTRADICTION.
Thus \(G\) has an element of order \(d\) for every positive integer \(d\) that divides \(n\) and, in particular, \(G\) has an element \(g\) of order \(n\).
It follows that \(G=\{1,g,g^2,\ldots,g^{n-1}\}\), making \(G\) cyclic. ∎

Example
Every non-zero integer modulo 7 is a power of 3:
\[\begin{eqnarray*}
\bar{1} & = & \bar{3}^6 \\
\bar{2} & = & \bar{3}^2 \\
\bar{3} & = & \bar{3}^1 \\
\bar{4} & = & \bar{3}^4 \\
\bar{5} & = & \bar{3}^5 \\
\bar{6} & = & \bar{3}^3
\end{eqnarray*}\]


Exercises
69. Let \(n\) be a postive integer. Find a cyclic group of order \(n\).
70. Find an infinite cyclic group.
71. Let \(G\) be a group and \(g\in G\) with order \(n\) (a positive integer). Show that \(g^{-1}\) also has order \(n\).
72. Let \(G\) be an infinite cyclic group. Show that \(G\) has no finite subgroups other than the trivial one \(\{1\}\).
73. Let \(G\) be a group such that \(g^2=1\) for all \(g\in G\). Prove that \(G\) is abelian.
74. Let \(G\) be a group. Show that \(G\) is finite with prime order if and only if \(G\) has exactly 2 subgroups.