Linear Algebra and Analysis

1.13.1 Division Of Numbers

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),

includes all nonnegative real numbers. Here is a picture of some of these intervals.

Then the version of the Euclidean algorithm presented here says that, for an arbitrary nonnegative real number b, it is in exactly one interval

[pa,(p+ 1)a)

where p is some nonnegative integer. This seems obvious from the picture, but here is a proof.

Proof:  Let S ≡

. By the Archimedean property this set is nonempty. Let p + 1 be the smallest element of S. Then pa ≤ b because p + 1 is the smallest in S. Therefore,

r ≡ b− pa ≥ 0.

If r ≥ a then b − pa ≥ a and so b ≥

a contradicting p + 1 ∈ S. Therefore, r < a as desired.

To verify uniqueness of p and r, suppose p_i and r_i, i = 1,2, both work and r₂ > r₁. Then a little algebra shows

p1 − p2 = r2 −-r1∈ (0,1). a

Thus p₁ − p₂ is an integer between 0 and 1, and there are no such integers. The case that r₁ > r₂ cannot occur either by similar reasoning. Thus r₁ = r₂ and it follows that p₁ = p₂. ■

Note that if a,b are integers, then so is r.

Proof: In this case, S ≡

. Let p + 1 be the smallest element of S. Then pa ≤−b < a and so a ≥ b > −a. Let r ≡ b + . Then b = −a + r and a > r ≥ 0. As to uniqueness, say r_i works and r₁ > r₂. Then you would have

and

r1 − r2 p2 − p1 =--a--- ∈ (0,1)

which is impossible because p₂ − p₁ is an integer. Hence r₁ = r₂ and so also p₁ = p₂. ■

Proof: This is done in the above except for the case where a < 0. So suppose this is the case. Then b = p

+ r where r is positive and 0 ≤ r < −a = . Thus b = a + r such that 0 ≤ < . ■

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

7 = 2× 3 + 1, 7 = 3 ×3 − 2, |1| < 3,|− 2| < 3

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”.

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.

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₀m + y₀n. Either p divides m or it does not. If p does not divide m, then by Theorem 1.13.1,

m = pq+ r

where 0 < r < p. Thus m =

q + r and so, solving for r,

r = m (1 − x0)+ (− y0q)n ∈ S.

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,

p = mx0 + ny0 = x0qx+ y0qy = q(x0x + y0y)

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

= 1 and therefore, there exists integers, x and y such that

1 = ax + yp.

Multiplying this equation by b yields

b = abx + ybp.

Since p|ab, ab = pz for some integer z. Therefore,

b = abx + ybp = pzx +ybp = p(xz + yb)

and this shows p divides b. ■

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

n m ∏ p = ∏ q i=1 i j=1 j

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₁|q_j for some j. Since these are prime numbers this requires p₁ = q_j. Reordering if necessary it can be assumed that q_j = q₁. Then dividing both sides by p₁ = q₁,

n∏−1 m∏−1 pi+1 = qj+1. i=1 j=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₂,

,q_m can be reordered in such a way that p_k = q_k for all k = 2,,n. Hence p_i = q_i for all i because it was already argued that p₁ = q₁, and this results in a contradiction. ■