the 1 = m a + n b theorem

Given two integers a and b such that 0 < a <= b and their greatest common divisor d = gcd(a, b).

Consider the special case where d = 1.
Consider the set B of equivalence classes modulo b. This set has a cardinality of b and consists of the elements {1, 2, 3 …, b=0}.
Consider the set A of multiples of a in the foregoing set. It has the elements {a, 2a, 3a, 4a, …, ba = 0}.

Lemma: The zero element is unique.

Proof by contradiction: Assume that there is an integer n, such that 0 < n < b, for which we have na = 0 mod(b). That is, we would have an integer k such that

n a = k b.

Since the left-hand side has a factor of a, so must the right-hand side. Since d = 1, b cannot have any factors in common with a. Hence, it is the k which must be divisible by a. Perform this division, to obtain

n = (k / a) b,

where (k / a) is an integer. Since the right-hand side has a factor of b, so must the left-hand side. But, since n is less than b, it cannot possibly be divisible by b. We have obtained a contradiction. QED.

Lemma: There are no repeated elements. That is, the elements are distinct.

Proof by contradiction. Assume that there are two integers m and n, such that 0 < m < n <= b, for which we have ma = na mod(b). Subtract the ma, to obtain

0 = n a – m a = (n – m) a mod(b).

Since we know that (n – m) is an integer such that 0 < n – m <= b – m < b, by the previous lemma, we have obtained a contradiction. QED.

Theorem: The sets A and B are equal.

Proof: By the preceding lemma, we have shown that these two sets have the same cardinality. Since we have taken A as a subset of B, we have A = B. QED.

Corollary: There exists an integer n, such that 0 < n <= b, for which na = 1 mod(b). Alternatively, we may say that there exist two integers n and k for which 1 = na + kb.

Proof: Since B has an element 1, so must its equal set A. QED.

Theorem 1: There exist two integers n and k such that d = na + kb.

Proof: By the preceding corollary, we have the integers n and k for which 1 = n (a / d) + k (b / d). Observe that since d is the greatest common divisor of a and b, each of the "factors" a/d and b/d actually is an integer. Multiply through by d, to obtain the desired result. QED.

Obviously, this theorem is true regardless of which of a or b is larger. However, each has to be strictly positive.

There are two ways for finding the greatest common divisor (sometimes called the highest common factor):

Algorithm 1: Obtain the prime factorization of the two integers a and b. Multiply their common factors, to obtain the d = gcd(a, b).

While this algorithm is obvious in concept, obtaining a prime factorization is very difficult.

Algorithm 2: If b = a; then the gcd(a, b) is a and exit. Otherwise, let m be the largest integer such that b – m a > 0. Then let r = b – m a. By the definition of m, we have that a >= r > 0. Furthermore, by the definition of r; since each term on its right-hand side is divisible by d, we have gcd(r, a) = d. Now, simultaneously replace b by a and a by r. Del capo al fine.

This is an ancient algorithm, which easily and quickly provides the greatest common divisor.

One may compute the integers n and k required for the preceding theorem 1 by working backwards through this algorithm 2.

Theorem 2: Given three strictly positive integers a, b, and c. The gcd(a, b, c) = gcd(gcd(a, b), c).

Proof:
Let d = gcd(a, b, c). Clearly, d divides a, b, and c. Hence, the gcd(a, b) is a multiple of d. Write it as gcd(a, b) = e d, where e is some strictly positive integer. Also, c is a multiple of d. Write it as c = f d, where f is some strictly positive integer. Then, we have gcd(gcd(a, b), c) = gcd(e d, f d) = d gcd(e, f).
Let g = gcd(gcd(a, b), c). Clearly, g divides the gcd(a, b) and also divides c. Since g divides the gcd(a, b), it clearly divides a and b. Hence, we have that g divides a, b, and c. Then, we may write gcd(a, b, c) = h g, where h is some strictly positive integer.
Taken together, we have d = h g and g = d gcd(e, f). Substitute the latter into the former, to obtain d = h d gcd(e, f). Divide by d, to obtain 1 = h gcd(e, f). Hence, h = 1 and gcd(e, f) = 1. Therefore, from the first of these, we have d = 1 * g = g. The second of these gives us g = d * 1 = d. Same thing.
QED.

Corollary: Given a set of n > 0 strictly positive integers {a1, a2, a3, …, an}. Their gcd may be computed recursively from the formula gcd(a1, a2, a3, …, an) =gcd(gcd(a1, a2, a3, …, a(n-1)), an).

Proof by Mathematical Induction.

Theorem 3: Given three strictly positive integers a, b, and c. If the gcd(a, b, c) = d; then there exist three integers s, t, and u such that d = s a + t b + u c. It often is convenient to divide this conclusion through by d, to obtain 1 = s (a / d) + t (b / d) + u (c / d). Of course, each of these “fractions” actually is an integer.

Proof; By the theorem 1, we have that there exist two integers m and n such that gcd(a, b) = m a + n b. Substitute into the theorem 2, to obtain d = gcd(m a + n b, c). Then, by the theorem 1, we have that there exist two integers p and u such that d = p (m a + n b) + u c. Now, let s = p m and t = p n. Substitute, to obtain d = s a + t b + u c. QED.

Corollary: Given a set of n > 0 strictly positive integers {a1, a2, a3, …, an}. Let their gcd(a1, a2, a3, …, an) = d. There exists a set of n non-negative integers {m1, m2, m3, …, mn} such that d = m1 a1 + m2 a2 + m3 a3 + … + mn an. It often is convenient to divide this conclusion through by d, to obtain 1 = m1(a1 / d) + m2 (a2 / d) + m3 (a3 / d) + … + mn (an / d). Of course, each of these “fractions” actually is an integer.

Proof by Mathematical Induction.

Example: a = 91, b = 903, c = 1792.

Step 1: Compute the gcd(a, b) = gcd(91, 903) and express it in terms of the a and b.

903 – 9 * 91 = 84. è 903 = 9 * (13 * 7) + (12 * 7) = 129 * 7.
91 – 1 * 84 = 7. è 91 = (12 * 7) + 7 = 13 * 7.
84 – 12 * 7 = 0. è 84 = 12 * 7.

Hence, the gcd(a, b) = gcd(91, 903) = 7.

Step 2: Factor out the 7 from the step 1.

129 – 9 * 13 = 12 è 129 = 9 * (13 * 1) + (12 * 1) = 129 * 1.
13 – 1 * 12 = 1 è 13 = (1 * 12) + 1 = 13 * 1.
12 – 12 * 1 = 0. è 12 = 12 * 1.

From the foregoing, we have 129 – 9 * 13 = 12 = 13 – 1. Hence, 129 – 10 * 13 = -1. Multiply by -1, to obtain 1 = 10 * 13 – 129. Multiply through by 7, to obtain 7 = 10 * 91 – 903.

Step 3: Compute the gcd(gcd(a, b), c) = gcd(7, 1792) and express it in terms of gcd(a, b) and c.

1792 – 256 * 7 = 0. è 1792 = 256 * 7.

Hence, the gcd(gcd(a, b), c) = gcd(7, 1792) = 7.

From the foregoing, we, have 1 = 1 * 1 – 0 * 256. Multiply through by 7, to obtain 7 = 1 * 7 – 0 * 256.

Step 3. Combine these results.

Substitute the expression for 7 (at the end of step 1) into the expression for 7 (at the end of step 2), to obtain 7 = 1 * (10 * 91 – 903) – 0 * 256 = 10 * 91 – 1 * 903 – 0 * 256. Therefore, the s, t, and u are, respectively, s = 10, t = -1, u = 0. This result is unusual in as much as u turned out to be zero; but, why not? After all, zero is an integer.

Lemma: The least common multiple of the two strictly positive integers a and b is given by the formula lcm(a, b) = a b / d, where d = gcd(a, b).

Proof: Let alpha and beta be defined as

alpha = a / d
beta = b / d.

Each is an integer; because d = gcd(a, b) divides a or b. Divide the defining equation for the greatest common divisor by d, to obtain

1 = gcd(alpha, beta).

It is obvious that the least common multiple of alpha nd beta is their product

lcm(alpha, beta) = alpha beta.

Multiply through by d, to obtain

lcm(a, b) = lcm(alpha, d, beta d) = alpha beta d = (alpha d) (beta d) / d = a b / d.

QED.

Lemma: The least common multiple of the three strictly positive integers a, b, and c is given by the formula lcm(a, b, c) = lcm(lcm(a, b), c).

The proof is obvious.

Theorem: Given a set of n > 0 strictly positive integers. Their least common multiple may be computed recursively from the function lcm(a1, a2, a3, ..., an) = lcm(lcm(a1, a2, a3, ..., a(n-1)), an).

Proof by Mathematical Induction.

Euclidean domain

Let us generalize the foregoing. We axiomatize the Euclidean domain E as

the domain E is a commutative ring with identity
cancellation: for non-zero c and any a and b in E, a c = b c implies a = b.
for every a in E, there is a metric g(a) such that
- g(0) is undefined; but instead may be taken as g(0) = -oo.
- for any non-zero b in E, we have g(a) <= g(a b).
- for any non-zero a and b in E with g(a) > g(b), there exists a quotient q and a remainder r such that a = q b + r.
[intentional place-holder]

For any a and b in E such that g(a) > g(b) we want to find the greatest common divisor GCD(a, b) and solve (without backtracking) the equation s a + t b = GCD(a, b). The extended Euclid algorithm to do so follows:

initialize old-r = a, r = b, old-s = 1, s = 0, old-t = 0, t = 1, temp = 1.
perform the loop ---
- assert s a + t b = r. [always true.]
- take q in E, such that temp = old-r - q r has g(temp) < g(r). [always possible, by the foregoing set of axioms.]
- if temp is zero then quit the loop.
- set r = temp.
- set temp = old-s - q s, old-s = s, s = temp.
- set temp = old-t - q t, old-t = t, t = temp.
return the r, s, t.

We have obtained the GCD(a, b) as the value of r and the equation s a + t b = GCD(a, b) is satisfied. The values of s and t are not unique.
Lemma: The assertion is true, initially.
Lemma: The q exists (and is easy to find).
Lemma: If the assertion was true before; it is true now.
Theorem: For any a and b in E such that g(a) > g(b), we have: 1) A greatest common divisor of a and b GCD(a, b) exists. 2) Values of s and t exist, such that the equation s a + t b = GCD(a, b) exist.
Proof: By the foregoing algorithm and Mathematical Induction.