Question

Use the method of direct proof to prove the following statements. Let \(a, b, c \in \mathbb{Z} .\) Suppose \(a\) and \(b\) are not both zero, and \(c \neq 0 .\) Prove that \(c \cdot \operatorname{gcd}(a, b) \leq\) \(\operatorname{gcd}(c a, c b)\).

Short answer

The direct proof shows that \(c \cdot \operatorname{gcd}(a, b) \leq \operatorname{gcd}(ca, cb)\) is valid for any integers \(a\), \(b\), \(c\), where \(a\) and \(b\) are not both zero, and \(c\) is not zero.

Step-by-step solution

Establishing Expressions for gcd

By definition of gcd, there exist integers \(x\) and \(y\) such that \(a = x \cdot \operatorname{gcd}(a, b)\) and \(b = y \cdot \operatorname{gcd}(a, b)\).

Assumption and Definition of gcd

Assume \(c \cdot \operatorname{gcd}(a, b)\) is not a divisor for \(ca\) and \(cb\), which means there exists a greater common divisor for \(ca\) and \(cb\), say \(d\). This contradicts the definition of gcd which is the greatest common divisor.

Establish Contradiction

Since \(a = x \cdot \operatorname{gcd}(a, b)\) and \(b = y \cdot \operatorname{gcd}(a, b)\), multiply c we get \(ca = c \cdot x \cdot \operatorname{gcd}(a, b)\) and \(cb = c \cdot y \cdot \operatorname{gcd}(a, b)\). Therefore \(c \cdot \operatorname{gcd}(a, b)\) is a common divisor for both \(ca\) and \(cb\), and it can't be less than \(d\), thus a contradiction.

Conclusion

Based on the contradiction in step 3, the assumption of \(c \cdot \operatorname{gcd}(a, b)\) is not a divisor for \(ca\) and \(cb\) is not valid. Thus, \(c \cdot \operatorname{gcd}(a, b) \leq \operatorname{gcd}(c a, c b)\) is true.