Question

Prove the following statements using either direct or contrapositive proof. If integers \(a\) and \(b\) are not both zero, then \(\operatorname{gcd}(a, b)=\operatorname{gcd}(a-b, b)\).

Short answer

Both direct and contrapositive proofs validate the given statement - if two integers aren't both zero, then the greatest common divisor of these two integers equals the greatest common divisor of their difference and the second integer.

Step-by-step solution

Understanding the Task

The task is to prove the following statement: If two integer values \(a\) and \(b\) aren't both zero, then the greatest common divisor of these two integers (gcd) equals to the gcd of \(a-b\) and \(b\). Two approaches can be taken: a direct proof or a contrapositive proof.

Direct Proof

To initiate the direct proof, first consider two integers \(a\) and \(b\), where either \(a\) or \(b\), or both are not zero. Next, assume that \(d\) is a common divisor of \(a\) and \(b\), which implies that there exist integers \(x\) and \(y\) such that \(a=dx\) and \(b=dy\). From these equalities, it follows that \(a-b= dx-dy = d(x-y)\), which means that \(d\) is a divisor of \(a-b\) as well. Furthermore, every common divisor of \(a\) and \(b\) is also a divisor of \(a-b\) and \(b\), so gcd\((a,b)\)=gcd\((a-b,b)\)

Contrapositive Proof

Approaching a contrapositive proof, consider the contrapositive of the given statement is: If gcd\((a, b) ≠ gcd(a-b, b)\), then both \(a\) and \(b\) are zero. If both \(a\) and \(b\) are zero, then there can't be any deviation since the GCD of 0 and 0 is undefined. Thus, the contrapositive statement is true which further validates the original statement.

Key concepts

Contrapositive Proof

Contrapositive proof is a logical proof technique where you show that if the converse of the conclusion is false, then the converse of the hypothesis must also be false. This way, the original statement is proven true.

For example, in the provided exercise, the contrapositive of the statement 'If integers a and b are not both zero, then \(\gcd(a, b)=\gcd(a-b, b)\)' is 'If \(\gcd(a, b) eq \gcd(a-b, b)\), then both a and b are zero.' By showing the truth of this contrapositive statement, the original claim is indirectly established as true.

When using contrapositive proof, it's important to clearly define the contrapositive statement and use logical steps to demonstrate its validity. Through this method, you avoid direct confrontation with the original statement and instead work with a statement that might be easier to prove.

Direct Proof

Direct proof is a fundamental technique often used to establish a mathematical statement's truth by direct application of definitions and theorems. The idea is to assume the truth of the given hypothesis and then logically deduce the conclusion.

In the context of the exercise, the hypothesis is that a and b are integers that are not both zero and we want to show that \(\gcd(a, b) = \gcd(a-b, b)\). By assuming there exists a common divisor d of a and b, you would use algebraic manipulation to show that d also divides \(a-b\). This straightforward approach takes you incrementally from the hypothesis to the desired conclusion.

Direct proof often requires meticulous justification for each step. Students are encouraged to clearly explain how the definition of the greatest common divisor applies and ensure every deduction clearly follows from the previous one.

Greatest Common Divisor

The greatest common divisor (GCD) of two integers is the largest integer that divides both of them without leaving a remainder. Understanding this concept is critical for numerous areas of mathematics, including number theory and algebra.

The key property used in the exercise is that if d is a common divisor of a and b, then it's also a divisor of any integer combination of a and b. This includes the difference \(a-b\). Therefore, the set of common divisors for a and b is the same as the set for \(a-b\) and b, thus their greatest common divisors are equal.

It's helpful to note that the GCD can be computed with algorithms such as the Euclidean algorithm, which systematically reduces the problem of finding a GCD through division until the remainder is zero. This concept of GCD is foundational in understanding the structure of integers and in solving problems involving divisibility.