Section 2.4 Number Theory
145
The Euclidean algorithm gives us a way to express gcd(a, b) as a linear combination of a and b, but there is another way to characterize this linear combination.
tHeoReM oN gCD(a, b)
Given positive integers a and b, gcd(a, b) is the linear combination of a and b
that has the smallest positive value.
To prove this result, we need to make use of the principle of well-ordering
that we mentioned in Section 2.2, namely, that every collection of positive integers that contains any members at all has a smallest member. The collection we
have in mind consists of all positive linear combinations of a and b, and certainly
such numbers exist (as a trivial example, 1 # a + 1 # b). By the principle of wellordering, there is a least such number c = ia + jb where i and j are integers. The
theorem claims that c = gcd(a, b), that is, that c 0 a, c 0 b, and c is the largest integer
that divides both a and b.
To prove that c 0 a, we’ll use a proof by contradiction. Suppose c | a. Then
when we divide a by c there is a nonzero remainder
a = mc + r
with m an integer and 0 < r < c
Rewriting this equation,
r = a − mc
= a − m(ia + jb)
= (1 − mi)a − (mj)b
which makes r a positive linear combination of a and b, that is, r is a member of
our collection, but r < c, which is a contradiction because c was the least member
of this collection. Therefore c 0 a. In the same way we can show that c 0 b. Consequently c is a common divisor of a and b; by Practice 11, c is the greatest common
divisor of a and b, which completes the proof of the theorem.
Rewriting the first three equations from the bottom up,
6 = 24 − 1 # 18
18 = 66 − 2 # 24
24 = 420 − 6 # 66
Now we use these equations in a series of substitutions:
6 = 24 − 1 # 18 = 24 − 1 # (66 − 2 # 24) (substituting for 18)
= 3 # 24 − 66
= 3 # (420 − 6 # 66) − 66 (substituting for 24)
= 3 # 420 − 19 # 66
which reveals the linear combination of 420 and 66 that gives the value 6.
145
The Euclidean algorithm gives us a way to express gcd(a, b) as a linear combination of a and b, but there is another way to characterize this linear combination.
tHeoReM oN gCD(a, b)
Given positive integers a and b, gcd(a, b) is the linear combination of a and b
that has the smallest positive value.
To prove this result, we need to make use of the principle of well-ordering
that we mentioned in Section 2.2, namely, that every collection of positive integers that contains any members at all has a smallest member. The collection we
have in mind consists of all positive linear combinations of a and b, and certainly
such numbers exist (as a trivial example, 1 # a + 1 # b). By the principle of wellordering, there is a least such number c = ia + jb where i and j are integers. The
theorem claims that c = gcd(a, b), that is, that c 0 a, c 0 b, and c is the largest integer
that divides both a and b.
To prove that c 0 a, we’ll use a proof by contradiction. Suppose c | a. Then
when we divide a by c there is a nonzero remainder
a = mc + r
with m an integer and 0 < r < c
Rewriting this equation,
r = a − mc
= a − m(ia + jb)
= (1 − mi)a − (mj)b
which makes r a positive linear combination of a and b, that is, r is a member of
our collection, but r < c, which is a contradiction because c was the least member
of this collection. Therefore c 0 a. In the same way we can show that c 0 b. Consequently c is a common divisor of a and b; by Practice 11, c is the greatest common
divisor of a and b, which completes the proof of the theorem.
Rewriting the first three equations from the bottom up,
6 = 24 − 1 # 18
18 = 66 − 2 # 24
24 = 420 − 6 # 66
Now we use these equations in a series of substitutions:
6 = 24 − 1 # 18 = 24 − 1 # (66 − 2 # 24) (substituting for 18)
= 3 # 24 − 66
= 3 # (420 − 6 # 66) − 66 (substituting for 24)
= 3 # 420 − 19 # 66
which reveals the linear combination of 420 and 66 that gives the value 6.