Subgroups of Additive Group of Integers

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\struct {\Z, +}$ be the additive group of integers.

Let $n \Z$ be the additive group of integer multiples of $n$.


Every non-trivial subgroup of $\struct {\Z, +}$ has the form $n \Z$.


Proof

First we note that, from Integer Multiples under Addition form Infinite Cyclic Group, $\struct {n \Z, +}$ is an infinite cyclic group.

From Cyclic Group is Abelian, it follows that $\struct {n \Z, +}$ is an infinite abelian group.


Let $H$ be a non-trivial subgroup of $\struct {\Z, +}$.

Because $H$ is non-trivial:

$\exists m \in \Z: m \in H: m \ne 0$

Because $H$ is itself a group:

$-m \in H$

So either $m$ or $-m$ is positive and therefore in $\Z_{>0}$.

Thus:

$H \cap \Z_{>0} \ne \O$


From the Well-Ordering Principle, $H \cap \Z_{>0}$ has a smallest element, which we can call $n$.

It follows from Subgroup of Infinite Cyclic Group is Infinite Cyclic Group that:

$\forall a \in \Z: a n \in H$

Thus:

$n \Z \subseteq H$


Aiming for a contradiction, suppose:

$\exists m \in \Z: m \in H \setminus n \Z$

Then $m \ne 0$, and also $-m \in H \setminus n \Z$.

Assume $m > 0$, otherwise we consider $-m$.

By the Division Theorem:

$m = q n + r$

If $r = 0$, then $m = q n \in n \Z$, so $0 \le r < n$.

Now this means $r = m - q n \in H$ and $0 \le r < n$.

This would mean $n$ was not the smallest element of $H \cap \Z$.

Hence, by Proof by Contradiction, there can be no such $m \in H \setminus n \Z$.

Thus:

$H \setminus n \Z = \O$

Thus from Set Difference with Superset is Empty Set‎:

$H \subseteq n \Z$


Thus we have $n \Z \subseteq H$ and $H \subseteq n \Z$.

Hence:

$H = n \Z$

$\blacksquare$


Examples

Even Integers

Let $2 \Z$ denote the set of even integers.

Let $\struct {2 \Z, +}$ be the algebraic structure formed from $2 \Z$ with the operation of integer addition.


Then $\struct {2 \Z, +}$ is a subgroup of the additive group of integers $\struct {\Z, +}$.


Sources