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}}$ with ${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<r<s}$ , contradicting that ${s}$ is the smallest positive integer in ${S}$ . Arguing contrarily, if ${r\geq s}$ , ${r-s<r}$ . 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.

b) Show that any element of ${S}$ is a multiple of ${gcd(a,b);a,b \mbox{ not both }0}$ .

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<r<s}$ , 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<s}$ 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.