# 7. Explore The Least Positive Element in Subsets of Integers

The integers, denoted ${\mathbb{Z}}$, are {… -3 -2 -1 0 1 2 3 …}. The natural numbers are the strictly positive integers, denoted ${\mathbb{N}}$. The non-negative integers are denoted ${\mathbb{Z}^+=\mathbb{N}\bigcup \{0\}}$. Subsets of ${\mathbb{Z}^+}$ are guaranteed to have a least positive element by the well-ordering principle for subsets of ${\mathbb{Z}}$.

Below are descriptions of two subsets of ${\mathbb{Z}}$. The two cases are explored for structure, then compared for common structure and put in a larger context.

a) Let ${S}$ be a non-empty set of integers such that ${x, y \in S \Longrightarrow x-y \in S}$ and for all ${n\in \mathbb{Z}}$, ${nx \in S}$. Show there is an ${s\in S}$ such that all elements of ${S}$ are multiples of ${s}$.

For arbitrary ${s\in S}$ and ${n\in \mathbb{Z}}$, one can show elements of form ${ns}$ exist by constructing them: ${s-s=0}$, ${0-s=-s}$, ${s-(-s)=2s}$. Endless similar operations produce the set of elements ${ns\in S}$.

Our objective is to show that all elements in ${S}$ are multiples of some ${s\in S}$, accomplished by choosing ${s}$ as the least positive integer in ${S}$. Let’s assume contrarily there is a positive element ${z\in S}$ such that ${z\neq qs}$ for any integer ${q}$ and derive a contradiction. Consider the sequence of elements of ${S}$ of the form ${z-qs}$, where ${q}$ ranges over the integers. Pick the value ${\bar{q}}$ such that ${r=z-\bar{q}s}$ is the least positive integer in the sequence. [This equation is called the ‘division algorithm’.] The proof is complete when we show ${0, contradicting that ${s}$ is the smallest positive integer in ${S}$. Arguing contrarily, if ${r\geq s}$, ${r-s. Since ${r-s=z-(\bar{q}+1)s}$, it is a member of the sequence, but less than the hypothesized least member ${r}$, a contradiction. Hence ${0, which in turn contradicts that ${s}$ is the least member of ${S}$. Hence, all elements in ${S}$ are of form ${ns}$, ${n\in \mathbb{Z}}$. ${\hfill \mbox{\raggedright \rule{.07in}{.1in}}}$

b) Let ${S=\{ma+nb\mbox{ \textbar } m,n,a,b\in\mathbb{Z}, m,n>0; a,b \mbox{ not both }0\}}$. Show that any element of ${S}$ is a multiple of ${gcd(a,b)}$.

Let ${\bar{m}, \bar{n}}$ be such that ${s=\bar{m}a+\bar{n}b}$ is the least positive integer in ${S}$. Since ${S}$ contains positive integers, ${s}$ exists. We want to show that ${s=gcd(a,b)}$ and thus ${s|a}$ and ${s|b}$.

Assume ${s\nmid a}$, so that ${a=sq+r}$ and ${0, by the division algorithm. Then ${r=a-sq=a-q(\bar{m}a+\bar{n}b)=a(1-q\bar{m})+b(-q\bar{n})}$. Thus ${r}$ is of the form ${ma+nb}$, in contradiction to the hypothesis that ${s}$ is the smallest such integer. The symmetric argument shows also that ${s|b}$.

Let ${g=(a,b)}$ and show ${s=g}$. Since ${a=g\bar{a}}$ and ${b=g\bar{b}}$, ${s=\bar{m}a+\bar{n}b=g(\bar{m}\bar{a}+\bar{n}\bar{b})}$. Thus ${g|s}$. Since ${g is impossible by definition of ${g=gcd(a,b)}$, we must have ${g=s}$. Hence by the abstract argument from part(a), all elements of ${S}$ are multiples of its least positive element ${g}$. ${\hfill \mbox{\raggedright \rule{.07in}{.1in}}}$

Case (b) provides a proof that there exist integers ${m, n}$ such that ${ma+nb=gcd(a,b)}$, by showing that of all such combinations of ${a, b}$, the smallest positive one is the ${gcd(a,b)}$.

Abstract algebra provides a structure for describing subsets of ${\mathbb{Z}}$ as encountered in the cases above. ${\mathbb{Z}}$ is most generally a commutative ring with identity, meaning that it is both an additive group and a multiplicative group with identity for which ${1.a=a, a+b=b+a, ab=ba, 1,a,b\in \mathbb{Z}}$.

A ring ${R}$ can have subsets, called ideals, which are additive subgroups of ${R}$, such that if ${I}$ is an ideal in ${R}$, then ${i\in I, r\in R \Longrightarrow ri\in I}$. Every ring has two improper ideals, the set ${\{0\}}$ and ${R}$ itself. Some rings, such as ${\mathbb{Z}}$, have other proper ideals such as those described herein. In Case (a), candidates for ${S}$ are of course ${\mathbb{Z}}$ itself, but also the ideals formed by the even integers ${2\mathbb{Z}}$, or ${3\mathbb{Z}}$ (multiples of 3), etc. To further characterize multiplication in such ideals, ${s=1s\in 2\mathbb{Z}}$ and ${s+s+s=3s\in 2\mathbb{Z}}$, but ${1\mbox{ and }3\notin 2\mathbb{Z}}$.

An ideal of ${\mathbb{Z}}$ is further described as a principal ideal when each of its elements is an integer multiple of the least positive element of that ideal. We denote principal ideals as ${I(a)}$ where ${a}$ is the least positive element. Thus over ${\mathbb{Z}}$, ${I(2)}$ is another label for ${2\mathbb{Z}}$. Every ideal ${I(a)}$ is by definition a group. Conversely, in ${\mathbb{Z}}$, it is easy to show that every additive group is an ideal.

More specifically, ${\mathbb{Z}}$ is algebraically an integral domain, a commutative ring with distinct additive and multiplicative identity and no zero divisors ${(ab=0\Longrightarrow a=0 \mbox{ or }b=0)}$. At the final level of qualification, ${\mathbb{Z}}$ is a principal ideal domain (PID), an integral domain in which every ideal is a principal ideal. Every PID is also a UFD as discussed in Problem 5.

Note that set ${S}$ in Case (b) is also an ideal of ${\mathbb{Z}}$, the ideal generated by two non-zero integers ${a}$ and ${b}$ via their linear combinations. This concept can be generalized to ideal generators. Let ${\emptyset\neq A\mbox{ \textbackslash } \{0\}\subseteq\mathbb{Z}}$. Define ${I(A)}$ as the set of all finite linear combinations of elements of ${A}$ with integer coefficients. Then it can be shown that ${I(A)}$ is identical to the intersection of all ideals containing ${A}$. ${I(A)}$ is thus the smallest ideal containing ${A}$. Define the ${gcd(A)}$ to be the ${gcd}$ of all elements of ${A}$. Then ${gcd(A)}$ is the smallest positive element of ${I(A)}$ and ${I(A) = I(gcd(A))}$. This shows a connection between the ideals in Cases (a) and (b), consistent with all ideals of ${\mathbb{Z}}$ being principal.