Here we consider some very important algebraic notions including the Euclidean algorithm just mentioned and issues related to whether two numbers are relatively prime, prime numbers and so forth. The following definition describes what is meant by a prime number and also what is meant by the word “divides”.
Definition 2.8.1 The number, a divides the number, b if in Theorem 2.7.11, r = 0. That is there is zero remainder. The notation for this is ab, read a divides b and a is called a factor of b. A prime number is one which has the property that the only numbers which divide it are itself and 1 and it is at least 2. The greatest common divisor of two positive integers, m,n is that number, p which has the property that p divides both m and n and also if q divides both m and n, then q divides p. Two integers are relatively prime if their greatest common divisor is one. The greatest common divisor of m and n is denoted as
There is a phenomenal and amazing theorem which relates the greatest common divisor to the smallest number in a certain set. Suppose m,n are two positive integers. Then if x,y are integers, so is xm + yn. Consider all integers which are of this form. Some are positive such as 1m + 1n and some are not. The set S in the following theorem consists of exactly those integers of this form which are positive. Then the greatest common divisor of m and n will be the smallest number in S. This is what the following theorem says.
Theorem 2.8.2 Let m,n be two positive integers and define

Then the smallest number in S is the greatest common divisor, denoted by
Proof: First note that both m and n are in S so it is a nonempty set of positive integers. By well ordering, there is a smallest element of S, called p = x_{0}m + y_{0}n. Either p divides m or it does not. If p does not divide m, then by Theorem 2.7.11,

where 0 < r < p. Thus m =

However, this is a contradiction because p was the smallest element of S. Thus pm. Similarly pn.
Now suppose q divides both m and n. Then m = qx and n = qy for integers, x and y. Therefore,

showing qp. Therefore, p =
This amazing theorem will now be used to prove a fundamental property of prime numbers which leads to the fundamental theorem of arithmetic, the major theorem which says every integer can be factored as a product of primes.
Proof: Suppose p does not divide a. Then since p is prime, the only factors of p are 1 and p so follows

Multiplying this equation by b yields

Since pab, ab = pz for some integer z. Therefore,

and this shows p divides b. ■
Theorem 2.8.4 (Fundamental theorem of arithmetic) Let a ∈ ℕ∖
Proof: If a equals a prime number, the prime factorization clearly exists. In particular the prime factorization exists for the prime number 2. Assume this theorem is true for all a ≤ n − 1. If n is a prime, then it has a prime factorization. On the other hand, if n is not a prime, then there exist two integers k and m such that n = km where each of k and m are less than n. Therefore, each of these is no larger than n − 1 and consequently, each has a prime factorization. Thus so does n. It remains to argue the prime factorization is unique except for order of the factors.
Suppose

where the p_{i} and q_{j} are all prime, there is no way to reorder the q_{k} such that m = n and p_{i} = q_{i} for all i, and n + m is the smallest positive integer such that this happens. Then by Theorem 2.8.3, p_{1}q_{j} for some j. Since these are prime numbers this requires p_{1} = q_{j}. Reordering if necessary it can be assumed that q_{j} = q_{1}. Then dividing both sides by p_{1} = q_{1},

Since n + m was as small as possible for the theorem to fail, it follows that n− 1 = m− 1 and the prime numbers, q_{2},