Proving GCD Properties: gcd(a, b) 1 if and only if gcd(a - b, ab) 1

Introduction

In the domain of elementary number theory, the greatest common divisor (GCD)

is a fundamental concept with wide-ranging applications. One interesting and oft-discussed property involves proving that for all integers a and b, gcd(a, b) 1 if and only if gcd(a - b, ab) 1.

This article delves into the intricacies of proving two directions of this statement, offering a detailed elementary number theory proof for verification and clarity.

Forward Direction: gcd(a, b) 1 Implies gcd(a - b, ab) 1

Assume that gcd(a, b) 1. This means that the only common divisor of a and b is 1. Let us denote the greatest common divisor of a - b and ab as d, such that d gcd(a - b, ab).

Since d divides both a - b and ab, it follows that d must also divide the product a * b. Now, if d divides a * b, then d must potentially divide either a, b, or both.

If d divides a: Since d divides a and ab, and d divides a - b, then d must divide b. This is because d divides the sum a b and a - b, implying that d divides both a and b. If d divides b: This case mirrors the previous one, as d must then divide a, leading to the same conclusion that d divides both a and b.

Since gcd(a, b) 1, the only common divisor of a and b can be 1. Therefore, the only possible value for d is 1, which implies that gcd(a - b, ab) 1.

Converse Direction: gcd(a - b, ab) 1 Implies gcd(a, b) 1

Assume that gcd(a - b, ab) 1. This means that a - b and ab share no common divisors other than 1. Let us denote the greatest common divisor of a and b as d, such that d gcd(a, b).

Since d divides both a and b, it follows that d also divides their sum a b and their difference a - b. Therefore, d divides both a - b and ab.

Given that gcd(a - b, ab) 1, the only common divisor of a - b and ab can be 1. Hence, d 1, which implies that gcd(a, b) 1.

Conclusion

We have established both directions of the statement:

If gcd(a, b) 1, then gcd(a - b, ab) 1. If gcd(a - b, ab) 1, then gcd(a, b) 1.

Therefore, we can conclude that:

gcd(a, b) 1 if and only if gcd(a - b, ab) 1

This completes the proof.