Proving the Invariance of the Greatest Common Divisor: gcd(a-b, b) gcd(a, b)

Understanding the greatest common divisor (gcd) and its properties is a fundamental concept in number theory. One intriguing property of the gcd is its invariance under certain transformations. Specifically, we can prove that gcd(a ? b, b) gcd(a, b). This invariance highlights the robustness and versatility of the gcd concept and has wide-ranging applications in various fields of mathematics and computer science. In this article, we will explore the proof step-by-step, discussing the properties of gcd, divisibility, and the linear combination of numbers.

Understanding the Properties of the Greatest Common Divisor (GCD)

The greatest common divisor (gcd) of two integers, say a and b, is the largest positive integer that divides both a and b without leaving a remainder. The notation for the gcd is gcd(a, b). Important properties of the gcd include its invariance under adding multiples of one number to another. This property forms the basis of our proof.

Step-by-Step Proof of gcd(a - b, b) gcd(a, b)

Step 1: Notation and Initial Setup

Let d gcd(a, b). By definition, d divides both a and b. This means that:

a kd for some integer k b md for some integer m

Step 2: Divisibility of a - b

Using the expressions for a and b, we can express a - b as:

a - b kd - md (k - m)d

This implies that d also divides a - b. Thus, d is a common divisor of both a - b and b.

Step 3: Definition of gcd(a - b, b)

Let g gcd(a - b, b). By definition, g divides both a - b and b. Since g divides b, it can be expressed as:

b mg for some integer m a - b kg for some integer k

Step 4: Invariance Using the Linear Combination

Since g divides both a - b and b, it must also divide any linear combination of these two numbers. Specifically:

g divides (a - b)b g divides ab

This implies that g divides a, because:

(a - b)b a

Step 5: Conclusion about g

Given that g divides both a and b, we can conclude that:

g ≤ gcd(a, b) d

Step 6: Reversing the Argument

Conversely, since d divides both a and b, it also divides a - b. Therefore:

d divides (a - b)b d divides ab

This implies that d divides g, because:

d divides (a - b)b a d divides ab

Hence, we have:

d ≤ gcd(a - b, b) g

Step 7: Equality

Since g ≤ d and d ≤ g, we conclude that:

g d

Therefore, we have proven that:

gcd(a - b, b) gcd(a, b)

Alternative Approach: Common Divisors

The property of the gcd being the greatest common divisor can also be understood through the lens of common divisors. Suppose d is a common divisor of a and b. Then there exist integers m and n such that:

a dm b dn

Given this, we can express a - b as:

a - b dm - dn d(m - n)

Since m - n is an integer, it follows that d is a divisor of a - b. Therefore, d is a common divisor of a - b and b.

Conversely, if e is a common divisor of a - b and b, then:

a - b em b en

Substituting these into the expression for a, we get:

a (a - b) b em en e(m n)

Thus, e divides a. Therefore, e is a common divisor of a and b.

Since all common divisors of a and b are also common divisors of a - b and b, and vice versa, the greatest common divisor of a and b must be the same as the greatest common divisor of a - b and b. Therefore: