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 pi and ri, i = 1,2, both work and r2 > r1. Then a little algebra shows
|
Thus p1 − p2 is an integer between 0 and 1, and there are no such integers. The case that r1 > r2 cannot occur either by similar reasoning. Thus r1 = r2 and it follows that p1 = p2. ■
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 p2 − p1 is an integer. Hence r1 = r2 and so also p1 = p2. ■
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 a|b, 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 = x0m + y0n. 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 p|m. Similarly p|n.
Now suppose q divides both m and n. Then m = qx and n = qy for integers, x and y. Therefore,
|
showing q|p. 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 p|ab, 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 pi and qj are all prime, there is no way to reorder the qk such that m = n and pi = qi for all i, and n + m is the smallest positive integer such that this happens. Then by Theorem 1.13.6, p1|qj for some j. Since these are prime numbers this requires p1 = qj. Reordering if necessary it can be assumed that qj = q1. Then dividing both sides by p1 = q1,
|
Since n + m was as small as possible for the theorem to fail, it follows that n − 1 = m − 1 and the prime numbers, q2,