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$

GCD, LCM, and Bézout's identity

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\mid b$ then it's not hard to verify that $\gcd(a,b)=\mid a\mid$.

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)$.

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