Abstract Algebra: Preliminaries

1 Natural numbers
- 1.1 Well-ordering principle
- 1.2 Induction
  - 1.2.1 Description
  - 1.2.2 Example
2 Integers
- 2.1 Algebraic properties
- 2.2 Construction
3 Division algorithm
4 Congruence modulo m
5 Algebra on $\mathbb {Z} _{m}$
6 GCD, LCM, and Bézout's identity
7 Primes
- 7.1 Euclid's Lemma
8 Fundamental Theorem of Arithmetic
9 Licensing

Natural numbers

The natural numbers are those numbers used for counting (as in "there are six coins on the table") and ordering (as in "this is the third largest city in the country"). In common mathematical terminology, words colloquially used for counting are "cardinal numbers", and words used for ordering are "ordinal numbers". The natural numbers can, at times, appear as a convenient set of codes (labels or "names"), that is, as what linguists call nominal numbers, forgoing many or all of the properties of being a number in a mathematical sense.

Some definitions begin the natural numbers with 0, corresponding to the non-negative integers {0, 1, 2, 3, ...}, whereas others start with 1, corresponding to the positive integers {1, 2, 3, ...}. Texts that exclude zero from the natural numbers sometimes refer to the natural numbers together with zero as the whole numbers, while in other writings, that term is used instead for the integers (including negative integers).

The natural numbers are a basis from which many other number sets may be built by extension: the integers, by including (if not yet in) the neutral element 0 and an additive inverse ( $- n$ ) for each nonzero natural number $n$ ; the rational numbers, by including a multiplicative inverse ( ${\tfrac {1}{n}}$ ) for each nonzero integer $n$ (and also the product of these inverses by integers); the real numbers by including with the rationals the limits of (converging) Cauchy sequences of rationals; the complex numbers, by including with the real numbers the unresolved square root of minus one (and also the sums and products thereof); and so on. This chain of extensions make the natural numbers canonically embedded (identified) in the other number systems.

In common language, particularly in primary school education, natural numbers may be called counting numbers to intuitively exclude the negative integers and zero, and also to contrast the discreteness of counting to the continuity of measurement — a hallmark characteristic of real numbers.

Well-ordering principle

Consider the following set which we define to be the set of natural numbers:

{\begin{aligned}\quad \mathbb {N} =\{1,2,3,...\}\end{aligned}}

Now consider any subset $A$ of $\mathbb {N}$ . For example, let us consider the subsets $A_{1}=\{7,29\}$ , $A_{2}=\{1,3,5,...\}$ , and $A_{3}=\{2,4,6,...\}$ . The subset $A_{1}$ describes a finite set containing two integers. The subset $A_{2}$ describes the infinite set of all odd natural numbers, and the subset $A_{3}$ describes the infinite set of all even natural numbers. Notice that in each of these cases we can identify a least element of the subset. For example, the least element in $A_{1}$ is $7$ , the least element in $A_{2}$ is $1$ , and the least element in $A_{3}$ is $2$ .

In fact, it is impossible to construct a nonempty subset $A$ of $\mathbb {N}$ that does not contain a least element. We describe this very important result below in the following theorem.

Theorem 1 (The Well-Ordering Principle of the Natural Numbers): Let $A$ be a nonempty subset of the natural numbers $\mathbb {N} =\{1,2,3,...\}$ . Then there exists a least element $x\in A$ , that is, $x\leq y$ for all $y\in A$ .

We do not have the tools to prove Theorem 1 although it is a rather intuitively obvious result. Nevertheless, we should note that while Theorem 1 holds true for the set of natural numbers, it does not hold true for all sets of real numbers. For example, consider the set of rational numbers $\mathbb {Q}$ :

{\begin{aligned}\quad \mathbb {Q} =\left\{{\frac {a}{b}}:a,b\in \mathbb {Z} ,b\neq 0\right\}\end{aligned}}

Any subset of the rational numbers need not have a least element. For example, consider the following subset of rational numbers between $0$ and $1$ noninclusive, that is, $A=\{x\in \mathbb {Q} :0<x<1\}$ . We claim that $A$ has no least element. To prove this, assume that $A$ does have a least element, say $x\in A$ is such that $x\leq y$ for all $y\in A$ . Since $x\in A$ we have that $x={\frac {a}{b}}$ where $a,b\in \mathbb {Z}$ Since $x\in A$ we must have that $x>0$ too since $0<x<1$ and so:

{\begin{aligned}\quad 0<{\frac {a}{b}}<1\end{aligned}}

Consider the number $y$ in the middle of $0$ and ${\frac {a}{b}}$ . This number is $y={\frac {a}{2b}}$ . Since $b\in \mathbb {Z}$ and $b\neq 0$ we have that $2b\in \mathbb {Z}$ and $2b\neq 0$ , so indeed, $y={\frac {a}{2b}}\in A$ and $0<y<x<1$ which is a contradiction to our assumption that a least element exists in $A$ .

It's important to note that while not every subset of the rational numbers $\mathbb {Q}$ contains a least element, there are still subsets of $\mathbb {Q}$ that do contain a least element.

Induction

Mathematical induction is a mathematical proof technique. It is essentially used to prove that a statement P(n) holds for every natural number n = 0, 1, 2, 3, . . . ; that is, the overall statement is a sequence of infinitely many cases P(0), P(1), P(2), P(3), . . . . Informal metaphors help to explain this technique, such as falling dominoes or climbing a ladder:

"Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the step)."

— Concrete Mathematics, page 3 margins.

A proof by induction consists of two cases. The first, the base case (or basis), proves the statement for n = 0 without assuming any knowledge of other cases. The second case, the induction step, proves that if the statement holds for any given case n = k, then it must also hold for the next case n = k + 1. These two steps establish that the statement holds for every natural number n. The base case does not necessarily begin with n = 0, but often with n = 1, and possibly with any fixed natural number n = N, establishing the truth of the statement for all natural numbers n ≥ N.

Description

The simplest and most common form of mathematical induction infers that a statement involving a natural number $n$ (that is, an integer $n \geq 0$ or 1) holds for all values of $n$ . The proof consists of two steps:

The initial or base case: prove that the statement holds for 0, or 1.
The induction step, inductive step, or step case: prove that for every $n$ , if the statement holds for $n$ , then it holds for $n + 1$ . In other words, assume that the statement holds for some arbitrary natural number $n$ , and prove that the statement holds for $n + 1$ .

The hypothesis in the inductive step, that the statement holds for a particular $n$ , is called the induction hypothesis or inductive hypothesis. To prove the inductive step, one assumes the induction hypothesis for $n$ and then uses this assumption to prove that the statement holds for $n + 1$ .

Authors who prefer to define natural numbers to begin at 0 use that value in the base case; those who define natural numbers to begin at 1 use that value.

Example

Mathematical induction can be used to prove the following statement P(n) for all natural numbers n.

P(n)\!:\ \ 0+1+2+\cdots +n\,=\,{\frac {n(n+1)}{2}}.

This states a general formula for the sum of the natural numbers less than or equal to a given number; in fact an infinite sequence of statements: $0={\tfrac {(0)(0+1)}{2}}$ , $0+1={\tfrac {(1)(1+1)}{2}}$ , $0+1+2={\tfrac {(2)(2+1)}{2}}$ , etc.

Proposition. For any $n\in \mathbb {N}$ , $0+1+2+\cdots +n={\tfrac {n(n+1)}{2}}.$

Proof. Let P(n) be the statement $0+1+2+\cdots +n={\tfrac {n(n+1)}{2}}.$ We give a proof by induction on n.

Base case: Show that the statement holds for the smallest natural number n = 0.

P(0) is clearly true: $0={\tfrac {0(0+1)}{2}}\,.$

Inductive step: Show that for any k ≥ 0, if P(k) holds, then P(k+1) also holds.

Assume the induction hypothesis that for a particular k, the single case n = k holds, meaning P(k) is true:

$0+1+\cdots +k\ =\ {\frac {k(k{+}1)}{2}}.$

It follows that:

(0+1+2+\cdots +k)+(k{+}1)\ =\ {\frac {k(k{+}1)}{2}}+(k{+}1).

Algebraically, the right hand side simplifies as:

{\begin{aligned}{\frac {k(k{+}1)}{2}}+(k{+}1)&\ =\ {\frac {k(k{+}1)+2(k{+}1)}{2}}\\&\ =\ {\frac {(k{+}1)(k{+}2)}{2}}\\&\ =\ {\frac {(k{+}1)((k{+}1)+1)}{2}}.\end{aligned}}

Equating the extreme left hand and right hand sides, we deduce that:

$0+1+2+\cdots +k+(k{+}1)\ =\ {\frac {(k{+}1)((k{+}1)+1)}{2}}.$

That is, the statement P(k+1) also holds true, establishing the inductive step.

Conclusion: Since both the base case and the inductive step have been proved as true, by mathematical induction the statement P(n) holds for every natural number n. ∎

Integers

The set of integers consists of zero (0), the positive natural numbers (1, 2, 3, ...), also called whole numbers or counting numbers, and their additive inverses (the negative integers, i.e., −1, −2, −3, ...). The set of integers is often denoted by the boldface ( $Z$ ) or blackboard bold $(\mathbb {Z} )$ letter "Z"—standing originally for the German word Zahlen ("numbers").

$\mathbb {Z}$ is a subset of the set of all rational numbers $\mathbb {Q}$ , which in turn is a subset of the real numbers $\mathbb {R}$ . Like the natural numbers, $\mathbb {Z}$ is countably infinite.

Algebraic properties

Like the natural numbers, $\mathbb {Z}$ is closed under the operations of addition and multiplication, that is, the sum and product of any two integers is an integer. However, with the inclusion of the negative natural numbers (and importantly, Template:Num), $\mathbb {Z}$ , unlike the natural numbers, is also closed under subtraction.

The integers form a unital ring which is the most basic one, in the following sense: for any unital ring, there is a unique ring homomorphism from the integers into this ring. This universal property, namely to be an initial object in the category of rings, characterizes the ring $\mathbb {Z}$ .

$\mathbb {Z}$ is not closed under division, since the quotient of two integers (e.g., 1 divided by 2) need not be an integer. Although the natural numbers are closed under exponentiation, the integers are not (since the result can be a fraction when the exponent is negative).

The following table lists some of the basic properties of addition and multiplication for any integers $a$ , $b$ and $c$ :

Properties of addition and multiplication on integers
	Addition	Multiplication
Closure:	$a + b$ Template:Padis an integer	$a \times b$ Template:Padis an integer
Associativity:	$a + (b + c) Template:= (a + b) + c$	$a \times (b \times c) Template:= (a \times b) \times c$
Commutativity:	$a + b Template:= b + a$	$a \times b Template:= b \times a$
Existence of an identity element:	$a + 0 Template:= a$	$a \times 1 Template:= a$
Existence of inverse elements:	$a + (- a) Template:= 0$	The only invertible integers (called units) are $-1$ and $1$ .
Distributivity:	$a \times (b + c) Template:= (a \times b) + (a \times c)$ Template:Padand Template:Pad $(a + b) \times c Template:= (a \times c) + (b \times c)$
No zero divisors:		If $a \times b Template:= 0$ , then $a Template:= 0$ or $b Template:= 0$ (or both)

The first five properties listed above for addition say that $\mathbb {Z}$ , under addition, is an abelian group. It is also a cyclic group, since every non-zero integer can be written as a finite sum Template:Nowrap or Template:Nowrap. In fact, $\mathbb {Z}$ under addition is the only infinite cyclic group—in the sense that any infinite cyclic group is isomorphic to $\mathbb {Z}$ .

The first four properties listed above for multiplication say that $\mathbb {Z}$ under multiplication is a commutative monoid. However, not every integer has a multiplicative inverse (as is the case of the number 2), which means that $\mathbb {Z}$ under multiplication is not a group.

All the rules from the above property table (except for the last), when taken together, say that $\mathbb {Z}$ together with addition and multiplication is a commutative ring with unity. It is the prototype of all objects of such algebraic structure. Only those equalities of expressions are true in $\mathbb {Z}$ for all values of variables, which are true in any unital commutative ring. Certain non-zero integers map to zero in certain rings.

The lack of zero divisors in the integers (last property in the table) means that the commutative ring $\mathbb {Z}$ is an integral domain.

The lack of multiplicative inverses, which is equivalent to the fact that $\mathbb {Z}$ is not closed under division, means that $\mathbb {Z}$ is not a field. The smallest field containing the integers as a subring is the field of rational numbers. The process of constructing the rationals from the integers can be mimicked to form the field of fractions of any integral domain. And back, starting from an algebraic number field (an extension of rational numbers), its ring of integers can be extracted, which includes $\mathbb {Z}$ as its subring.

Although ordinary division is not defined on $\mathbb {Z}$ , the division "with remainder" is defined on them. It is called Euclidean division, and possesses the following important property: given two integers $a$ and $b$ with $b \neq 0$ , there exist unique integers $q$ and $r$ such that $a Template:= q \times b + r$ and $0 \leq r < | b |$ , where $| b |$ denotes the absolute value of $b$ . The integer $q$ is called the quotient and $r$ is called the remainder of the division of $a$ by $b$ . The Euclidean algorithm for computing greatest common divisors works by a sequence of Euclidean divisions.

The above says that $\mathbb {Z}$ is a Euclidean domain. This implies that $\mathbb {Z}$ is a principal ideal domain, and any positive integer can be written as the products of primes in an essentially unique way. This is the fundamental theorem of arithmetic.

Construction

Red points represent ordered pairs of natural numbers. Linked red points are equivalence classes representing the blue integers at the end of the line.

In elementary school teaching, integers are often intuitively defined as the (positive) natural numbers, zero, and the negations of the natural numbers. However, this style of definition leads to many different cases (each arithmetic operation needs to be defined on each combination of types of integer) and makes it tedious to prove that integers obey the various laws of arithmetic. Therefore, in modern set-theoretic mathematics, a more abstract construction allowing one to define arithmetical operations without any case distinction is often used instead. The integers can thus be formally constructed as the equivalence classes of ordered pairs of natural numbers $(a, b)$ .

The intuition is that $(a, b)$ stands for the result of subtracting $b$ from $a$ .^[1] To confirm our expectation that Template:Nowrap and Template:Nowrap denote the same number, we define an equivalence relation $~$ on these pairs with the following rule:

(a,b)\sim (c,d)

precisely when

a+d=b+c.

Addition and multiplication of integers can be defined in terms of the equivalent operations on the natural numbers;^[1] by using $[(a, b)]$ to denote the equivalence class having $(a, b)$ as a member, one has:

[(a,b)]+[(c,d)]:=[(a+c,b+d)].

[(a,b)]\cdot [(c,d)]:=[(ac+bd,ad+bc)].

The negation (or additive inverse) of an integer is obtained by reversing the order of the pair:

-[(a,b)]:=[(b,a)].

Hence subtraction can be defined as the addition of the additive inverse:

[(a,b)]-[(c,d)]:=[(a+d,b+c)].

The standard ordering on the integers is given by:

[(a,b)]<[(c,d)]

if and only if

a+d<b+c.

It is easily verified that these definitions are independent of the choice of representatives of the equivalence classes.

Every equivalence class has a unique member that is of the form $(n,0)$ or $(0, n)$ (or both at once). The natural number $n$ is identified with the class $[(n,0)]$ (i.e., the natural numbers are embedded into the integers by map sending $n$ to $[(n,0)]$ ), and the class $[(0, n)]$ is denoted $- n$ (this covers all remaining classes, and gives the class $[(0,0)]$ a second time since $-0 Template:= 0.$

Thus, $[(a, b)]$ is denoted by

{\begin{cases}a-b,&{\mbox{if }}a\geq b\\-(b-a),&{\mbox{if }}a<b.\end{cases}}

If the natural numbers are identified with the corresponding integers (using the embedding mentioned above), this convention creates no ambiguity.

This notation recovers the familiar representation of the integers as ${..., -2, -1, 0, 1, 2, ...}$ .

Some examples are:

{\begin{aligned}0&=[(0,0)]&=[(1,1)]&=\cdots &&=[(k,k)]\\1&=[(1,0)]&=[(2,1)]&=\cdots &&=[(k+1,k)]\\-1&=[(0,1)]&=[(1,2)]&=\cdots &&=[(k,k+1)]\\2&=[(2,0)]&=[(3,1)]&=\cdots &&=[(k+2,k)]\\-2&=[(0,2)]&=[(1,3)]&=\cdots &&=[(k,k+2)].\end{aligned}}

Division algorithm

Congruence modulo m

Algebra on $\mathbb {Z} _{m}$

GCD, LCM, and Bézout's identity

Primes

Euclid's Lemma

Fundamental Theorem of Arithmetic

Licensing

Content obtained and/or adapted from:

Natural number, Wikipedia under a CC BY-SA license
Integer, Wikipedia under a CC BY-SA license
Mathematical induction, Wikipedia under a CC BY-SA license
Abstract Algebra, mathonline.wikidot.com under a CC BY-SA license

↑ ^1.0 ^1.1 Cite error: Invalid <ref> tag; no text was provided for refs named Campbell-1970-p83

[1]

Abstract Algebra: Preliminaries

Contents

Natural numbers

Well-ordering principle

Induction

Description

Example

Integers

Algebraic properties

Construction

Division algorithm

Congruence modulo m

Algebra on $\mathbb {Z} _{m}$

GCD, LCM, and Bézout's identity

Primes

Euclid's Lemma

Fundamental Theorem of Arithmetic

Licensing

Navigation menu

Personal tools

Namespaces

Variants

Views

More

Search

Navigation

Tools

Abstract Algebra: Preliminaries

Contents

Natural numbers

Well-ordering principle

Induction

Description

Example

Integers

Algebraic properties

Construction

Division algorithm

Congruence modulo m

Algebra on Z m {\displaystyle \mathbb {Z} _{m}}

GCD, LCM, and Bézout's identity

Primes

Euclid's Lemma

Fundamental Theorem of Arithmetic

Licensing

Navigation menu

Search

Algebra on $\mathbb {Z} _{m}$