Question

Use the method of proof by contradiction to prove the following statements. (In each case, you should also think about how a direct or contrapositive proof would work. You will find in most cases that proof by contradiction is easier.) There exist no integers \(a\) and \(b\) for which \(21 a+30 b=1\).

Short answer

By contradiction, the initial assumption that integers \(a\) and \(b\) exist such that \(21a + 30b = 1\) leads to a contradiction as 1 is not a multiple of 3 (gcd of 21 and 30). Therefore, it is indeed true that no such integers \(a\) and \(b\) exist.

Step-by-step solution

Assumption

Start by assuming that the proposition is false. So, suppose we believe that there do exist integers \(a\) and \(b\) such that \(21a + 30b = 1\)

Identify Greatest Common Divisor

We know that the greatest common divisor (gcd) of 21 and 30 is 3. This means that any integer that can be expressed as \(21a + 30b\) must be a multiple of 3 because gcd(21, 30) divides \(21a + 30b\).

Derive a Contradiction

However, our initial assumption leads us to believe there exists integers \(a\) and \(b\) such that \(21a + 30b = 1\). But 1 is not a multiple of 3, therefore we have arrived at a contradiction.

Conclusion

Seeing this contradiction, we conclude that our initial assumption was false - it is indeed true that there exist no integers \(a\) and \(b\) for which \(21a + 30b = 1\). This is proof by contradiction.

Key concepts

Greatest Common Divisor

Understanding the concept of the greatest common divisor (gcd) is fundamental to various areas of mathematics, including number theory and algebra. The gcd of two integers is the largest positive integer that divides both numbers without leaving a remainder. For instance, the gcd of 21 and 30 is 3, meaning that 3 is the largest number that can be divided into both 21 and 30 without producing any fractional parts.

Properties relating to the gcd play a critical role in solving problems through proofs and deductions. When dealing with linear combinations of integers—in our context, an equation of the form \(21a + 30b\)—it can be inferred that the result will always be divisible by the gcd of the coefficients, here being 21 and 30. This inference is employed in the given exercise to point out a logical inconsistency when assuming the existence of integer solutions to the equation \(21a + 30b = 1\), where 1 is not a multiple of the gcd 3, thereby leading to a contradiction.

Integer Properties

Integers are the set of whole numbers, both positive and negative, including zero. They have distinct properties that are integral to understanding how they interact under various operations, such as addition, subtraction, and multiplication. A key integer property is that they are closed under these operations, meaning performing these operations on any two integers always results in another integer.

An important aspect of integer properties in the context of the given exercise is the division algorithm. It states that if an integer \(d\) divides another integer \(n\), then there exist unique integers \(q\) and \(r\) such that \(n = dq + r\) and \(0 \leq r < |d|\). Since our equation does not have a remainder when considering the gcd, it must follow that \(21a + 30b\) must be a multiple of the gcd. This property is used in the proof by contradiction method to resolve the exercise.

Mathematical Proof Methods

Mathematical proofs are rigorous arguments used to establish the truthfulness of mathematical statements. There are several proof methods such as direct proof, proof by contrapositive, and proof by contradiction, which was applied in our exercise.

In a proof by contradiction, also known as indirect proof, one starts by assuming the opposite of the statement to be proven. The goal is to demonstrate that this assumption leads to a contradiction with established facts or theorems, thus the original statement must be true. This method is often easier to use when the direct proof is not readily apparent.

The elegance of this method rests on the logical principle of contradiction; if a proposition leads to an absurdity under the assumption that its negation is true, then the original proposition must be correct. Used thoughtfully, proof by contradiction can be a powerful tool for validating mathematical propositions, especially when dealing with integer solutions and divisibility, as in the exercise about integers \(a\) and \(b\) for which \(21a + 30b = 1\).