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 \(18 a+6 b=1\).

Short answer

There exist no integers \(a\) and \(b\) for which \(18a + 6b = 1\) because supposing such integers do exist leads to a contradiction, when after simplifying, the equation involves an incorrectly non-integer.

Step-by-step solution

Assume the Opposite

First, assume that there exist integers \(a\) and \(b\) such that \(18a + 6b = 1\). This is the opposite to the statement that needs to be proved true.

Simplify the Equation

The equation can be simplified by dividing each term by 6, a common factor. The resulting equation is \(3a + b = \frac{1}{6}\). Since the result is not an integer, it contradicts the assumption that \(a\) and \(b\) are integers because the sum of two integers always results in another integer.

Identify the Contradiction

The contradiction here is that the assumption (that there exist integers \(a\) and \(b\) such that \(3a + b = \frac{1}{6}\)) led to a non-integer result. This is impossible because the sum of two integers is always an integer. Therefore, the assumption was false and it must be the case that no integers \(a\) and \(b\) exist for the equation \(18a + 6b = 1\).

Key concepts

Integers

When we talk about integers, we are referring to the set of whole numbers that include all the positive numbers, negative numbers, and zero, without any fractions or decimals. Think of them as stepping stones on an endless number line that only allow you to jump from one stone to the next without standing in between. This set is often denoted by the symbol \( \textbf{Z} \), which comes from the German word 'Zahlen' meaning 'numbers'.

Understanding integers is fundamental when dealing with equations and proofs in mathematics because equations often require solutions that are specifically integers. As seen in the original exercise that stated there exist no integers \(a\) and \(b\) for which \(18a + 6b = 1\), the solution hinges on the fact that any operation performed on integers, like addition or multiplication, must result in another integer. The contradiction in the exercise arises because dividing by 6 yields a fraction, not an integer, thus violating this basic property of integers.

Direct Proof

Direct proof is a straightforward method of demonstrating the truth of a statement by using established facts, definitions, and logical reasoning. It involves a series of logical steps that lead from the hypothesis to the conclusion. For example, if one needs to prove that the sum of two even numbers is always even, a direct proof would start by letting the two even numbers be \(2m\) and \(2n\), where \(m\) and \(n\) are integers. Then, adding them together, we get \(2m + 2n = 2(m + n)\), which is clearly an even number since \(m + n\) is an integer.

Direct proof is often used when the path from assumptions to the conclusion is clear and causally linked. It can be less convoluted than other proof techniques, making it a powerful tool when applicable. However, not all mathematical statements lend themselves to direct proofs; some are more naturally proven using techniques like proof by contradiction or contrapositive proof.

Contrapositive Proof

Contrapositive proof is a technique that involves proving that the contrapositive of the statement is true in order to prove the original statement. The contrapositive of a statement has the form 'If not Q, then not P', where the original statement is 'If P, then Q'. To understand this concept, consider a door that can only be opened with a key. The statement 'If the door is open, then the key was used' has the contrapositive 'If the key was not used, then the door is not open'. Proving that the door cannot be open without the key directly supports the original statement.

In the context of the integer problem, if one were to use contrapositive proof, we would start with the statement 'If \(18a + 6b\) is an integer, then \(a\) and \(b\) are integers.' The contrapositive of this statement is 'If either \(a\) or \(b\) is not an integer, then \(18a + 6b\) is not an integer.' Since the result from the equation in the original problem changes to a fraction when divided by 6, it validates the contrapositive which in turn affirms the original statement. Despite the effectiveness of contrapositive proof, it can sometimes be less intuitive than direct proof and may not always be the simplest approach to solving a problem.