mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Number Theory Discussion Group (https://www.mersenneforum.org/forumdisplay.php?f=132)
-   -   Basic Number Theory 15: Lagrange's theorem, cyclic groups and modular arithmetic (https://www.mersenneforum.org/showthread.php?t=21904)

 Nick 2017-01-07 13:15

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

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.

[U]Proposition 74[/U]
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$$.

[U]proof[/U]
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 [B]order[/B] of $$g$$.
If no such $$n$$ exists, then we say that $$g$$ has [B]infinite order[/B].

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 [B]order[/B] of $$G$$.
We shall see shortly how the order of a finite group is related to the orders of its elements.

[U]Proposition 75[/U]
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$$.

[U]proof[/U]
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.

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

[U]proof[/U]
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 [B]subgroup[/B] of a group $$G$$ is a subset $$H$$ of $$G$$ which itself forms a group under the same binary operation (restricted to $$H$$).

[U]Examples[/U]
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 [B]trivial subgroup[/B]) and $$G$$ itself is a subgroup of $$G$$.

[U]Proposition 77[/U]
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$$.

[U]proof[/U]
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:

[U]Proposition 78[/U]
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$$.

[U]proof[/U]
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:

[U]Proposition 79[/U]
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$$.

[U]proof[/U]
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 [B]left coset[/B] of $$H$$ in $$G$$, and
$$Hg=\{hg:h\in H\}$$, called a [B]right coset[/B] of $$H$$ in $$G$$.

[U]Proposition 80[/U]
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$$.

[U]proof[/U]
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$$.

[U]Proposition 81[/U]
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.

[U]proof[/U]
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. ∎

[U]Notation[/U]
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$$.

[U]Proposition 82[/U]
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.

[U]proof[/U]
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. ∎

[U]Notation[/U]
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 [B]index[/B] of $$H$$ in $$G$$, written $$[G:H]$$.

[U]Theorem 83[/U] (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$$.

[U]proof[/U]
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$$. ∎

[U]Corollary 84[/U]
Let $$G$$ be a finite group and $$g\in G$$.
Then the order of the element $$g$$ divides the order of the group $$G$$.

[U]proof[/U]
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. ∎

[U]Example[/U]
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$$ [B]cyclic[/B] 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 [B]generated[/B] by $$g$$.

[U]Proposition 85[/U]
Let $$p$$ be a prime number and $$G$$ a group of order $$p$$.
Then $$G$$ is cyclic.

[U]proof[/U]
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. ∎

[U]Proposition 86[/U]
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.

[U]proof[/U]
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.

[U]Proposition 87[/U]
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$$.

[U]proof[/U]
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. ∎

[U]Proposition 88[/U]
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).

[U]proof[/U]
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)$$. ∎

[U]Corollary 89[/U] (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$$.

[U]proof[/U]
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$$. ∎

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

[U]proof[/U]
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. ∎

[U]Example[/U]
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*}$

[U]Exercises[/U]
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.

 All times are UTC. The time now is 01:30.