Abstract Algebra: Preliminaries

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 ≥ 0 or 1) holds for all values of n. The proof consists of two steps:

1. The initial or base case: prove that the statement holds for 0, or 1.
2. 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, 0), $\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 is an integer	a × b is an integer
Associativity:	a + (b + c) $=$ (a + b) + c	a × (b × c) $=$ (a × b) × c
Commutativity:	a + b $=$ b + a	a × b $=$ b × a
Existence of an identity element:	a + 0 $=$ a	a × 1 $=$ a
Existence of inverse elements:	a + (−a) $=$ 0	The only invertible integers (called units) are −1 and 1.
Distributivity:	a × (b + c) $=$ (a × b) + (a × c) and (a + b) × c $=$ (a × c) + (b × c)
No zero divisors:		If a × b $=$ 0, then a $=$ 0 or b $=$ 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 1 + 1 + ... + 1 or (−1) + (−1) + ... + (−1). 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 ≠ 0, there exist unique integers q and r such that a $=$ q × b + r and 0 ≤ 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. To confirm our expectation that 1 − 2 and 4 − 5 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; 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 $=$ 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

One rather important aspect of the divisibility of integers is that if $a,b\in \mathbb {Z}$ then $a$ can be written as the product of some quotient $q$ with $b$ plus a remainder $r$. For example, if $a=11$ and $b=3$, then $a=3(b)+2$ where $q=3$ and $r=2$.

The following theorem known as the Division Algorithm shows us that for any pair of integers $a,b\in \mathbb {Z}$ where $b>0$ that the form $a=bq+r$ exists and is unique.

Theorem 1 (The Division Algorithm): Let $a,b\in \mathbb {Z}$ with $b>0$. Then there exists unique $q,r\in \mathbb {Z}$ where $0\leq r<b$ and such that $a=bq+r$.

The value of $r$ is often called the Remainder when $a$ is divided by $b$. That is, $a$ is equal to some multiple $q$, known as the Quotient of $b$, plus a remainder $r$ for which $0\leq r<b$.

• Proof: Let $a,b\in \mathbb {Z}$ with $b>0$ and consider the following set $A$:

${\begin{aligned}\quad A=\{a-bq:q\in \mathbb {N} \}=\{a,a-b,a-2b,...\}.\end{aligned}}$

• Consider $B\subset A$ of nonnegative elements in $A$. If $a>0$ then $a\in B$ and if $a<0$ then $a-ba=a(1-b)\in B$, so $B$ is a nonempty set. Moreover, $B$ is a nonempty subset of integers and so by the Well-Ordering principle there exists a least element of $B$, say $r\in B$ is this least element. Since $r\in B$ we have that $r=a-bn$ for some $n\in \mathbb {N}$ and so:

${\begin{aligned}\quad a=bq+r\end{aligned}}$

• So $a$ if of the form we desire. Now since $r\in B$ and every element in $B$ is nonnegative then we have that $0\leq r$. Suppose that $r\geq b$. Then $r=b+p$ where $p\geq 0$ and so:

${\begin{aligned}\quad a=bq+r=bq+(b+p)=b(q+1)+p\end{aligned}}$

• Therefore $p=a-b(q+1)\geq 0$ and so $p\in B$. Since $b>0$ and $q+1>q$ we have that $0\leq p<r$. But this implies that $r$ is not the least element of $B$ which is a contradiction, so our assumption that $r\geq b$ is false, and so $0\leq r<b$.

• We lastly show that $q$ and $r$ are unique for $a=bq+r$ and $0\leq r<b$. Suppose that $a=bq_{1}+r_{1}$ and $a=bq_{2}+r_{2}$ where $0\leq r_{1},r_{2}<b$. Then by subtracting these two equations we get:

${\begin{aligned}\quad 0=bq_{1}-bq_{2}+r_{1}-r_{2}\\\quad 0=b(q_{1}-q_{2})+r_{1}-r_{2}\\\quad r_{2}-r_{1}=b(q_{1}-q_{2})\end{aligned}}$

• Therefore $r_{2}-r_{1}$ is a multiple of $b$. Since $0\leq r_{1}<b$ and $0\leq r_{2}<b$ we must have that $-b<r_{2}-r_{1}<b$. The only multiple of $b$ such that $-b<r_{2}-r_{1}<b$ is $0$, so:

${\begin{aligned}\quad r_{2}-r_{1}=0\\\quad r_{1}=r_{2}\end{aligned}}$

• Since $r_{1}=r_{2}=r$, we have that $0=b(q_{1}-q_{2})$. Since $b>0$ this implies that $q_{1}-q_{2}=0$ and so $q_{1}=q_{2}$. Therefore $a$ can be uniquely expressed in the form $a=bq+r$ where $0\leq r<b$. $\blacksquare$

Congruence modulo m

Definition: If $a,b,m\in \mathbb {Z}$ then we say that $a$ is Congruent to $b$ modulo $m$ denoted $a\equiv b{\pmod {m}}$ if $m\mid (a-b)$.

The congruence of two integers is an equivalence relation which we can describe in other words. We say that $a$ and $b$ are said to be congruent modulo $m$ if $a$ divided by $m$ leaves the same remaining as $b$ divided by $m$.

For example, $3\equiv 7{\pmod {2}}$ since $2\mid (3-7)=-4$. Notice also that when $3$ and $7$ are divided by $2$ they both leave the same remainder, $1$.

We can denote the remainder of an integer $a$ when divided by $m$ as simply $a{\pmod {m}}$. For example, $1=3{\pmod {2}}$ since the remaining of $3$ when divided by $2$ is $1$. We should note that from <a href="/the-division-algorithm">The Division Algorithm</a> that the remainder $r$ when an integer $a$ is divided by $m$ satisfies the inequality $0\leq r<m$. Therefore we note that for all nonnegative integers $a$ and positive integers $m$ that:

${\begin{aligned}\quad 0\leq a{\pmod {m}}<m\end{aligned}}$

In other words, for all nonnegative integers $a$ and positive integers $m$, the set of possible remainders when $a$ is divided by $m$ is $\{0,1,2,...,m-1\}$.

Consequentially, we can define the set of odd integers and the set of even numbers in terms of these elements in the set of even integers being congruent to one another and elements in the set of odd numbers being congruent to one another.

Definition: An integer $z\in \mathbb {Z}$ is said to be Odd if $z\equiv 1{\pmod {2}}$ or Even if $z\equiv 0{\pmod {2}}$.

We will now look at some basic theorems regarding integer congruence modulo $m$.

Theorem 1: Let $a,b,c,d,m\in \mathbb {Z}$. Then:

a) If $a\equiv b{\pmod {m}}$ then $b\equiv a{\pmod {m}}$.
b) $a\equiv a{\pmod {m}}$.
c) If $a\equiv b{\pmod {m}}$ and $b\equiv c{\pmod {m}}$ then $a\equiv c{\pmod {m}}$.
d) If $a\equiv b{\pmod {m}}$ and $c\equiv d{\pmod {m}}$ then $(a+c)\equiv (b+d){\pmod {m}}$.

e) If $a\equiv b{\pmod {m}}$ and $c\equiv d{\pmod {m}}$ then $ac\equiv bd{\pmod {m}}$.

• Proof of a) Suppose that $a\equiv b{\pmod {m}}$. Then $m\mid (a-b)$ so there exists an integer $k$ such that:

${\begin{aligned}\quad mk=a-b\\\quad -mk=b-a\\\quad m(-k)=b-a\end{aligned}}$

• Therefore $m\mid (b-a)$ so $b\equiv a{\pmod {m}}$. $\blacksquare$

• We have that $m\mid 0=(a-a)$ for any integer $a$. Therefore $a\equiv a{\pmod {m}}$. $\blacksquare$

• Proof of c) Suppose that $a\equiv b{\pmod {m}}$ and $b\equiv c{\pmod {m}}$. Then $m\mid (a-b)$ and $m\mid (b-c)$ and there exists integers $k_{1}$ and $k_{2}$ such that:

${\begin{aligned}\quad mk_{1}=a-b\quad \mathrm {and} \quad mk_{2}=b-c\end{aligned}}$

• From the second equation we have that $b=mk_{2}+c$. Substituting this into the first equation gives us:

${\begin{aligned}\quad mk_{1}=a-(mk_{2}+c)\\\quad mk_{1}+mk_{2}=a-c\\\quad m(k_{1}+k_{2})=a-c\end{aligned}}$

• Therefore $m\mid (a-c)$ so $a\equiv c{\pmod {m}}$. $\blacksquare$

• Proof of d): Suppose that $a\equiv b{\pmod {m}}$ and $c\equiv d{\pmod {m}}$. Then $m\mid (a-b)$ and $m\mid (c-d)$, so there exists integers $k_{1}$ and $k_{2}$ such that:

${\begin{aligned}\quad mk_{1}=a-b\quad \mathrm {and} \quad mk_{2}=c-d\end{aligned}}$

• Adding these equations together gives us:

${\begin{aligned}\quad mk_{1}+mk_{2}=(a-b)+(c-d)\\\quad m(k_{1}+k_{2})=(a+c)-(b+d)\end{aligned}}$

• Therefore $m\mid (a+c)-(b+d)$ so $(a+c)\equiv (b+d){\pmod {m}}$ $\blacksquare$

• Proof of e): Suppose that $a\equiv b{\pmod {m}}$ and $c\equiv d{\pmod {m}}$. Then $m\mid (a-b)$ and $m\mid (c-d)$, so there exists integers $k_{1}$ and $k_{2}$ such that:

${\begin{aligned}\quad mk_{1}=a-b\quad \mathrm {and} \quad mk_{2}=c-d\\\quad a=b+mk_{1}\quad \mathrm {and} \quad c=d+mk_{2}\end{aligned}}$

• Multiplying these equations together yields:

${\begin{aligned}\quad ac=(b+mk_{1})(d+mk_{2})\\\quad ac=bd+bmk_{2}+dmk_{1}+m^{2}k_{1}k_{2}\\\quad ac-bd=m(bk_{2}+dk_{1}+mk_{1}k_{2})\end{aligned}}$

• Therefore $m\mid (ac-bd)$ so $ac\equiv bd{\pmod {m}}$. $\blacksquare$

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

Let $n\in \mathbb {N}$. Since the relation of congruence modulo n is an equivalence relation on $\mathbb {Z}$, we can discuss its equivalence classes. Recall that in this situation, we refer to the equivalence classes as congruence classes.

Definition of the integers modulo $n$: Let $n\in \mathbb {N}$. The set of congruence classes for the relation of congruence modulo $n$ on $\mathbb {Z}$ is the set of integers modulo $n$, or the set of integers mod $n$. We will denote this set of congruence classes by $\mathbb {Z} _{n}$.

$\mathbb {Z} =[0]\cup [1]\cup [2]\cup \cdot \cdot \cdot \cup [n-1]$.

In addition, we know that each integer is congruent to precisely one of the integers 0, 1, 2, ..., $n-1$. This tells us that one way to represent $\mathbb {Z} _{n}$ is

$\mathbb {Z} _{n}=\{[0],[1],[2],...[n-1]\}$.

Consequently, even though each integer has a congruence class, the set $\mathbb {Z} _{n}$ has only $n$ distinct congruence classes.

The set of integers $\mathbb {Z}$ is more than a set. We can add and multiply integers. That is, there are the arithmetic operations of addition and multiplication on the set $\mathbb {Z}$, and we know that $\mathbb {Z}$ is closed with respect to these two operations.

One of the basic problems dealt with in modern algebra is to determine if the arithmetic operations on one set “transfer” to a related set. In this case, the related set is $\mathbb {Z} _{n}$. For example, in the integers modulo 5, $\mathbb {Z} _{5}$, is it possible to add the congruence classes [4] and [2] as follows?

${\begin{array}{rcl}{[4]\oplus [2]}&=&{[4+2]}\\{}&=&{[6]}\\{}&=&{[1].}\end{array}}$

We have used the symbol ̊ to denote addition in $\mathbb {Z} _{5}$ so that we do not confuse it with addition in $\mathbb {Z}$. This looks simple enough, but there is a problem. The congruence classes [4] and [2] are not numbers, they are infinite sets. We have to make sure that we get the same answer no matter what element of [4] we use and no matter what element of [2] we use. For example,

$9\equiv 4$ (mod 5) and so [9] = [4]. Also,
$7\equiv 2$ (mod 5) and so [7] = [2].

Do we get the same result if we add [9] and [7] in the way we did when we added [4] and [2]? The following computation confirms that we do:

${\begin{array}{rcl}{[9]\oplus [7]}&=&{[9+7]}\\{}&=&{[16]}\\{}&=&{[1].}\end{array}}$

The left side shows the properties in terms of the congruence relation and the right side shows the properties in terms of the congruence classes.

If $a\equiv 3$ (mod 6) and $b\equiv 4$ (mod 6), then $(a+b)\equiv (3+4)$ (mod 6); $(a\cdot b)\equiv (3\cdot 4)$ (mod 6).

If $[a]=[3]$ and $[b]=[4]$ in $\mathbb {Z} _{6}$, then $[a+b]=[3+4]$; $[a\cdot b]=[3\cdot 4]$.

These are illustrations of general properties that we have already proved in Theorem 3.28. We repeat the statement of the theorem here because it is so important for defining the operations of addition and multiplication in $\mathbb {Z} _{n}$.

Let $n$ be a natural number and let $a$, $b$, $c$, and $d$ be integers. Then

1. If $a\equiv b$ (mod $n$) and $c\equiv d$ (mod $n$), then $(a+c)\equiv (b+d)$ (mod $n$).
2. If $a\equiv b$ (mod $n$) and $c\equiv d$ (mod $n$), then $ac\equiv bd$ (mod $n$).
3. If $a\equiv b$ (mod $n$) and $m\in \mathbb {N}$, then $a^{m}\equiv b^{m}$ (mod $n$).

Since $x\equiv y$ (mod $n$) if and only if $[x]=[y]$, we can restate the result of this Theorem 3.28 in terms of congruence classes in $\mathbb {Z} _{n}$.

Let $n$ be a natural number and let $a$, $b$, $c$, and $d$ be integers. Then, in $\mathbb {Z} _{n}$.

1. If $[a]=[b]$ and $[c]=[d]$, then $[a+c]=[b+d]$.
2. If $[a]=[b]$ and $[c]=[d]$, then $[a\cdot c]=[b\cdot d]$.
3. If $[a]=[b]$ and $m\in \mathbb {N}$, then $[a]^{m}=[b]^{m}$.

Now, we know that the following formal definition of addition and multiplication of congruence classes in $\mathbb {Z} _{n}$ is independent of the choice of the elements we choose from each class. We say that these definitions of addition and multiplication are well defined.

GCD, LCM, and Bézout's identity

Greatest Common Divisor

Definition: If $a,b\in \mathbb {Z}$ then the Greatest Common Divisor of $a$ and $b$ denoted $\gcd(a,b)$ or $(a,b)$ is an integer $d\in \mathbb {Z}$ such that:

1. $d\mid a$ and $d\mid b$.

2. If $c\in \mathbb {Z}$, $c\mid a$, and $c\mid b$ then $c\leq d$.

Note that the number $1\in \mathbb {Z}$ has the property such that $1\mid a$ and $1\mid b$ for all $a,b\in \mathbb {Z}$ and so we see that the greatest common divisor of any two integers is always at least $1$. As a result, we only need to compare positive divisors of $a$ and $b$. Furthermore, if $a|b$ then it's not hard to verify that ${\text{gcd}}(a,b)=|a|$.

Let's look at an example of finding the greatest common divisor among two integers $a,b\in \mathbb {Z}$.

Consider the integers $a=14$ and $b=35$. The factors of $a$ are $1,2,7,14$ and the factors of $b$ are $1,5,7,35$. Both $a$ and $b$ share the factor $7$ and it is the largest factor they share, and so:

${\begin{aligned}\quad \gcd(14,35)=7\end{aligned}}$

As we elaborated on just moments ago, the greatest common divisor of any two integers is always at least $1$. We give a special name to pairs of integers for which their greatest common divisor is $1$ which we define below.

Definition: If $a,b\in \mathbb {Z}$ and $\gcd(a,b)=1$ then $a$ and $b$ are said to be Relatively Prime to each other.

For example, consider the numbers $a=5$ and $b=8$. The greatest common divisor between these numbers is:

${\begin{aligned}\quad \gcd(5,8)=1\end{aligned}}$

Therefore $5$ and $8$ are relatively prime to each other.

Theorem 1: If $a,b,c\in \mathbb {Z}$, $c\mid a$, and $c\mid b$ then $c\mid \gcd(a,b)$.

Lowest Common Multiple

For all $a,b\in \mathbb {Z} :ab\neq 0$, there exists a smallest $m\in \mathbb {Z} :m>0$ such that $a|m$ and $b|m$.

This $m$ is called the lowest common multiple of $a$ and $b$, and denoted ${\text{lcm}}\{a,b\}$.

Finding GCD and LCM with Prime Decomposition

Let $m,n\in \mathbb {Z}$.

Let:

$m=p_{1}^{k_{1}}p_{2}^{k_{2}}\dotsm p_{r}^{k_{r}}$

$n=p_{1}^{l_{1}}p_{2}^{l_{2}}\dotsm p_{r}^{l_{r}}$

$p_{i}|m\lor p_{i}|n,1\leq i\leq r$.

That is, the primes given in these prime decompositions may be divisors of either of the numbers $m$ or $n$.

Note that if one of the primes $p_{i}$ does not appear in the prime decompositions of either one of $m$ or $n$, then its corresponding index $k_{i}$ or $l_{i}$ will be zero.

Then the following results apply:

${\text{gcd}}\{m,n\}=p_{1}^{\min\{k_{1},l_{1}\}}p_{2}^{\min\{k_{2},l_{2}\}}\ldots p_{r}^{\min\{k_{r},l_{r}\}}$

${\text{lcm}}\{m,n\}=p_{1}^{\max\{k_{1},l_{1}\}}p_{2}^{\max\{k_{2},l_{2}\}}\ldots p_{r}^{\max\{k_{r},l_{r}\}}$

Bézout's Identity

Let a and b be integers with greatest common divisor d. Then there exist integers x and y such that ax + by = d. More generally, the integers of the form ax + by are exactly the multiples of d.

Proof

Given any nonzero integers a and b, let $S=\{ax+by\mid x,y\in \mathbb {Z} {\text{ and }}ax+by>0\}.$ The set S is nonempty since it contains either a or –a (with x = ±1 and y = 0). Since S is a nonempty set of positive integers, it has a minimum element $d=as+bt$, by the Well-ordering principle. To prove that d is the greatest common divisor of a and b, it must be proven that d is a common divisor of a and b, and that for any other common divisor c, one has c ≤ d.

The Euclidean division of a by d may be written

$a=dq+r\quad {\text{with}}\quad 0\leq r<d.$

The remainder r is in $S\cup \{0\}$, because

${\begin{aligned}r&=a-qd\\&=a-q(as+bt)\\&=a(1-qs)-bqt.\end{aligned}}$

Thus r is of the form $ax+by$, and hence $r\in S\cup \{0\}$. However, 0 ≤ r < d, and d is the smallest positive integer in S: the remainder r can therefore not be in S, making r necessarily 0. This implies that d is a divisor of a. Similarly d is also a divisor of b, and d is a common divisor of a and b.

Now, let c be any common divisor of a and b; that is, there exist u and v such that a = cu and b = cv. One has thus

${\begin{aligned}d&=as+bt\\&=cus+cvt\\&=c(us+vt).\end{aligned}}$

That is c is a divisor of d, and, therefore c ≤ d.

Primes

Recall that an integer $p>1$ is a prime number if the only divisors of $p$ are $\pm 1$ and $\pm p$, and an integer $p>1$ that is not a prime number is called a composite number.

We will now look at a very famous, simple, and important theorem which states that there exists infinitely many primes.

Theorem 1 (Euclid's Theorem of the Existence of Infinitely Many Primes): There are infinitely many prime numbers.

• Proof: We will carry this proof out by contradiction. Suppose that instead there are a finite number of primes. Then we can list all of these primes:

${\begin{aligned}\quad p_{1},p_{2},...,p_{k}\end{aligned}}$

• Consider the number $n=p_{1}p_{2}...p_{k}+1$. We have already seen that every integer $n>1$ has a prime divisor. Let this divisor be $p_{i}$ for some $i\in \{1,2,...,k\}$. Then $p_{i}\mid n$ and $p_{i}\mid p_{1}p_{2}...p_{i}...p_{k}$. But this implies that $p_{i}\mid 1$ which is a contradiction since all $p_{i}\geq 2$ and the only divisors of $1$ are $\pm 1$.

• Therefore the assumption that there were finitely many primes was false and so there are infinitely many primes. $\blacksquare$

Euclid's Lemma

Euclid's lemma: If a prime p divides the product ab of two integers a and b, then p must divide at least one of those integers a and b.

For example, if p $=$ 19, a $=$ 133, b $=$ 143, then ab $=$ 133 × 143 $=$ 19019, and since this is divisible by 19, the lemma implies that one or both of 133 or 143 must be as well. In fact, 133 $=$ 19 × 7.

A common proof of Euclid's lemma involves the Bézout's identity, which was unknown at Euclid's time. Bézout's identity states that if x and y are relatively prime integers (i.e. they share no common divisors other than 1 and -1) there exist integers r and s such that

$rx+sy=1.$

Let a and n be relatively prime, and assume that n $=$ab. By Bézout's identity, there are r and s making

$rn+sa=1.$

Multiply both sides by b:

$rnb+sab=b.$

The first term on the left is divisible by n, and the second term is divisible by ab, which by hypothesis is divisible by n. Therefore their sum, b, is also divisible by n. This is the generalization of Euclid's lemma mentioned above.

Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic, also known as the Unique Prime Factorization theorem, is as follows:

Theorem 1 (The Unique Prime Factorization Theorem): If $n\in \mathbb {Z}$ and $n>1$ then $n$ can be written as a product of primes uniquely apart from the ordering of the primes in the product ($n=p_{1}p_{2}...p_{k}$ for unique primes $p_{1},p_{2},...,p_{k}$).

If $n\in \mathbb {Z}$ and $n<-1$ then $n$ can also be written as a product of primes multiplied by $-1$.

• Proof: We first show that if $n\in \mathbb {Z}$ and $n>1$ then $n$ can be written as a product of primes. We saw on the <a href="/prime-and-composite-numbers">Prime and Composite Numbers</a> page that if every $n\in \mathbb {Z}$ and $n>1$ is divisible by a prime number. Let $p_{1}$ be this prime number. Then for some $n_{2}\in \{1,2,...\}$ we have that:

${\begin{aligned}\quad n=p_{1}n_{1}\end{aligned}}$

• If $n_{1}=1$ then $n=p_{1}$ and we're done. If $n_{1}$ is prime then let $p_{2}=n_{1}$ and so $n=p_{1}p_{2}$ and we're done. If $n_{1}$ is composite then $n_{1}>1$ and so once again, $n_{1}$ is divisible by a prime, say $p_{2}$, where $n_{1}=p_{2}n_{2}$. Therefore:

${\begin{aligned}\quad n=p_{1}p_{2}n_{2}\end{aligned}}$

• If $n_{2}=1$ then $n=p_{1}p_{2}$ and we're done. If $n_{2}$ is prime then let $p_{3}=n_{2}$ and so $n=p_{1}p_{2}p_{3}$ and we're done. If $n_{2}$ is composite then $n_{2}>1$ and again, $n_{2}$ is divisible by a prime, say $p_{3}$, where $n_{2}=p_{3}n_{3}$.

• Note that $n_{1}>n_{2}>...\geq 1$. This sequence of integers is bounded below by $1$ and hence must terminate at some point. Therefore, for some $k\in \{1,2,...\}$ we have that:

${\begin{aligned}\quad n=p_{1}p_{2}...p_{k}\end{aligned}}$

• Therefore $n$ can be written as a product of primes. We will now show that this factorization is unique. Suppose that $n=p_{1}p_{2}...p_{k}$ and $n=q_{1}q_{2}...q_{r}$ so that then:

${\begin{aligned}\quad p_{1}p_{2}...p_{k}=q_{1}q_{2}...q_{r}\end{aligned}}$

• Since $p_{1}\mid n$ we must have $p_{1}\mid q_{1}q_{2}...q_{r}$. Therefore $p_{1}=q_{i}$ for some $i\in \{1,2,...r\}$. Without loss of generality, assume that $p_{1}=q_{1}$. Therefore:

${\begin{aligned}\quad p_{2}p_{3}...p_{k}=q_{2}q_{3}...q_{r}\end{aligned}}$

• Since $p_{2}\mid n$ we must also have $p_{2}\mid q_{2}q_{3}...q_{r}$. Therefore $p_{2}=q_{i}$ for some $i\in \{2,3,...r\}$. Without loss of generality, assume that $p_{2}=q_{2}$. Therefore:

${\begin{aligned}\quad p_{3}p_{4}...p_{k}=q_{3}q_{4}...q_{r}\end{aligned}}$

• We continue in this process. We note that we won't run out of primes $p$ before primes $q$, otherwise this implies a prime $q$ is equal to $1$. Furthermore, we won't run out of primes $q$ before primes $p$, otherwise this implies a prime $p$ is equal to $1$. Therefore $k=r$ and we eventually get:

${\begin{aligned}\quad p_{k}=q_{r}\end{aligned}}$

• Therefore the prime factorization $n=p_{1}p_{2}...p_{k}$ is unique. $\blacksquare$

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
• Euclid's lemma, Wikipedia under a CC BY-SA license
• Prime number, Wikipedia under a CC BY-SA license
• Abstract Algebra, mathonline.wikidot.com under a CC BY-SA license
• Modular Arithmetic, LibreTexts: Mathematics under a CC BY-SA license