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<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. Hence {0<r<s}, 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<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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s