Problem 18 - Discrete Mathematics with Applications

Question

Prove each using the law of the contrapositive. If the product of two integers is odd, then both must be odd integers.

Step-by-Step Solution

Answer

Assuming that at least one of the integers, a or b, is even, and without loss of generality, let \(a=2p\) where p is an integer. The product of a and b would then be \(ab = (2p)b = 2(pb)\), where pb is also an integer. Since the product ab cannot be expressed in the form of an odd integer, we have proven the contrapositive statement. Thus, the original statement, "If the product of two integers is odd, then both must be odd integers," is also true.

Step 1: Assume one integer is even

Let's suppose we have two integers, a and b. We will assume that at least one of these integers is even. Without loss of generality, let's assume that a is an even integer (if it turns out that b is also even, our proof will still hold). So, our assumption for integer a can be represented as: \(a = 2p\), where p is an integer.

Step 2: Evaluate the product of a and b

Now let's evaluate the product of our two integers, a and b: \[ ab = (2p)b = 2(pb), \] where 'pb' is also an integer.

Step 3: Prove the product is not odd

Remember, an odd integer can be represented as \(2q + 1\), where q is an integer. So let's try to express the product ab in this form: \[ 2(pb) = 2q+1, \] which implies that \((pb) = q + \frac{1}{2}\). Since pb is an integer, q + 1/2 cannot be an integer. Therefore, the product ab cannot be expressed in the form of an odd integer.

Step 4: Conclude the proof using contrapositive

We have proven that if at least one of the integers, a or b, is even, then their product is not odd, i.e., we proved the contrapositive statement. According to the law of contrapositive, this implies that the original statement is also true, which is: "If the product of two integers is odd, then both must be odd integers." Hence, we have proven the statement using the law of the contrapositive.

Key Concepts

Odd and Even Integers

Understanding the nature of integers is fundamental to many mathematical concepts. Integers can be categorized as either odd or even. An even integer is any integer that can be divided by two without leaving a remainder. In other words, it is a multiple of two. Mathematically, an even integer can be expressed as 2n, where n is any integer.

An odd integer, on the other hand, is an integer that gives a remainder of one when divided by two. It can be represented by the formula 2m+1, where m is any integer. The concept of odd and even integers is crucial when analyzing integer products, especially when proving statements related to their properties, such as their parity (oddness or evenness) after multiplication.

Integer Products

When we talk about the product of two integers, we are referring to the result of multiplying them together. The product of even and odd integers follows certain rules:

• The product of two even integers is always even.
• The product of an even integer and an odd integer is always even.
• The product of two odd integers is always odd.

Understanding these principles allows us to predict the result of integer multiplication without actual computation. For example, if we are told that an integer product is odd, we can conclude that both factors must be odd integers. This fact underlies many mathematical proofs, including those that rely on the law of contrapositive to establish their validity.

Proof by Contradiction

Proof by contradiction is a widely used method in mathematics that starts by assuming the opposite of what we want to prove is true. Then we show that this assumption leads to a contradiction, something that is obviously false or goes against an established fact. This contradiction implies that the original assumption must be incorrect, thus confirming the truth of the statement we intended to prove.

For example, let's say we want to prove that the square root of 2 is irrational. We start by assuming the opposite, that the square root of 2 is rational. Through a series of logical steps, this assumption leads to a contradiction, proving that our initial assumption must be false and, therefore, that the square root of 2 is indeed irrational.

How It Applies to Our Integer Product Problem

When proving a statement about the parity of integer products, we can assume that if the product is odd, then one of the integers is even (the opposite of the statement we want to prove). Showing this leads to a contradiction confirms that both integers must be odd if their product is, reinforcing our original statement.

Mathematical Proofs

Mathematical proofs are logical arguments that use deductive reasoning to show a statement is true. Proofs are fundamental to mathematics as they provide the basis for mathematical theory development. There are various types of proofs, including direct proof, proof by contradiction, proof by induction, and proof using the law of the contrapositive.

Different proof techniques are suitable for different kinds of problems. A direct proof establishes the truth of a proposition by a straightforward chain of logical deductions from known truths. In contrast, the proof by induction is often used for propositions involving positive integers and involves proving a base case and an inductive step that shows if the proposition holds for one case, it holds for the next. Understanding the nature of mathematical proofs is essential for anyone looking to delve deeper into mathematical theory and its applications.