The main tools used in this proof are the division algorithm and the Principle of Well-Ordering. Let
be a cyclic group generated by
and suppose that
is a subgroup of
If
then trivially
is cyclic. Suppose that
contains some other element
distinct from the identity. Then
can be written as
for some integer
Since
is a subgroup,
must also be in
Since either
or
is positive, we can assume that
contains positive powers of
and
Let
be the smallest natural number such that
Such an
exists by the Principle of Well-Ordering.
We claim that is a generator for We must show that every can be written as a power of Since and is a subgroup of for some integer Using the division algorithm, we can find numbers and such that where hence,
So Since and are in must also be in However, was the smallest positive number such that was in consequently, and so Therefore,
and is generated by