First of all, recall the Archimedean property of the real numbers which says that if x is any real number, and if a > 0 then there exists a positive integer n such that na > x. Geometrically, it is essentially the following: For any a > 0, the succession of disjoint intervals [0,a),[a,2a),[2a,3a),
Then the version of the Euclidean algorithm presented here says that, for an arbitrary nonnegative real number b, it is in exactly one interval

where p is some nonnegative integer. This seems obvious from the picture, but here is a proof.
Theorem 1.13.1 Suppose 0 < a and let b ≥ 0. Then there exists a unique integer p and real number r such that 0 ≤ r < a and b = pa + r.
Proof: Let S ≡

If r ≥ a then b − pa ≥ a and so b ≥
To verify uniqueness of p and r, suppose p_{i} and r_{i}, i = 1,2, both work and r_{2} > r_{1}. Then a little algebra shows

Thus p_{1} − p_{2} is an integer between 0 and 1, and there are no such integers. The case that r_{1} > r_{2} cannot occur either by similar reasoning. Thus r_{1} = r_{2} and it follows that p_{1} = p_{2}. ■
Note that if a,b are integers, then so is r.
Corollary 1.13.2 The same conclusion is reached if b < 0.
Proof: In this case, S ≡

which is impossible because p_{2} − p_{1} is an integer. Hence r_{1} = r_{2} and so also p_{1} = p_{2}. ■
Corollary 1.13.3 Suppose a,b≠0, then there exists r such that

Proof: This is done in the above except for the case where a < 0. So suppose this is the case. Then b = p
This theorem is called the Euclidean algorithm when a and b are integers and this is the case of most interest here. Note that if a,b are integers, then so is r. Note that

so in this last corollary, the p and r are not unique.
The following definition describes what is meant by a prime number and also what is meant by the word “divides”.
Definition 1.13.4 The number, a divides the number, b if in Theorem 1.13.1, 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 a number at least 2 which has the property that the only numbers which divide it are itself and 1. 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 1.13.5 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 1.13.1,

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 1.13.7 (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 1.13.6, 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},