Problem 17 - Discrete Mathematics with Applications

Question

Prove each using the law of the contrapositive. If the product of two integers is even, then at least one of them must be an even integer.

Step-by-Step Solution

Answer

We need to prove the contrapositive of the given statement: If neither of the two integers is even (both are odd), then the product of the two integers is not even (it is odd). Let x and y be odd integers, so \(x = 2a + 1\) and \(y = 2b + 1\) for some integers a and b. Then, the product \(x \cdot y = (2a + 1)(2b + 1) = 4ab + 2a + 2b + 1 = 2(2ab + a + b) + 1\), which is in the form of an odd integer. Thus, if neither x nor y is even (both are odd), then their product is not even (it is odd). By the law of the contrapositive, the original statement, "If the product of two integers is even, then at least one of them must be an even integer," is also true.

Step 1: Rewrite the given statement using contrapositive rule

Using the law of the contrapositive, we need to prove the contrapositive version of the given statement: If neither of the two integers is even (they are both odd), then the product of the two integers is not even (it is odd).

Step 2: Assume both integers are odd

Let x and y be two integers such that x and y are both odd. By definition, an odd integer can be written in the form 2k + 1, where k is any integer. So, we have:\(x = 2a + 1\) and \(y = 2b + 1\) for some integers a and b.

Step 3: Compute the product

Now we compute the product of x and y:\(x \cdot y = (2a + 1)(2b + 1)\)

Step 4: Expand the product and simplify

Let's expand the product and simplify:\(x \cdot y = 4ab + 2a + 2b + 1\) Notice that 4ab, 2a, and 2b are all even because they are multiples of 2. Thus, we can rewrite the above expression as: \(x \cdot y = 2(2ab + a + b) + 1\)

Step 5: Prove the contrapositive

The expression for \(x \cdot y\) can be written as \(2(2ab + a + b) + 1\), which is in the form of an odd integer (2k + 1). Therefore, if neither of the two integers x and y is even (both are odd), then their product is not even (it is odd). This proves the contrapositive. Since we have proven the contrapositive, the original statement, "If the product of two integers is even, then at least one of them must be an even integer," is also true according to the law of the contrapositive.

Key Concepts

Understanding Mathematical Proofs

In mathematics, proofs are crucial for demonstrating the truth of various statements or theorems. They are used to establish the certainty of mathematical truths, ensuring that they rely on already accepted facts or logical steps. A mathematical proof involves a sequence of logical arguments that lead from known truths to the statement being proven.

There are several types of proofs, including:

• Direct Proof: This method involves assuming the premise is true, and then showing the conclusion follows logically.
• Indirect Proof: It includes proof by contradiction where you assume the opposite of what you want to prove, and proof by contrapositive which is discussed here.
• Constructive Proof: It involves constructing an example to demonstrate a statement's validity.

For instance, the contrapositive proof method, which is used in the given problem, is particularly useful when the direct approach is complex. It involves proving that if the conclusion is false, then the premise must also be false. This form of reasoning can often simplify problems and make them more approachable.

Even and Odd Integers

The concepts of even and odd integers are fundamental topics in discrete mathematics. An integer is any whole number, either positive, negative, or zero. Specifically:

• Even Integers: These are numbers divisible by 2 with no remainder. Examples include -4, 0, 8, and so on. In general, any integer can be represented as \(2k\) where \(k\) is an integer.
• Odd Integers: Unlike even integers, odd integers are those that have a remainder of 1 when divided by 2. Examples include -3, 1, 7, etc. Formally, an odd number can be expressed as \(2k + 1\), again where \(k\) is an integer.

In the exercise, understanding the properties of even and odd numbers is key because they determine the nature of the product of two integers. Specifically, the solution shows that two odd integers multiplied together result in an odd integer. Recognizing these patterns is crucial in constructing mathematical arguments and understanding proofs.

Fundamentals of Discrete Mathematics

Discrete mathematics deals with distinct and separate elements, which makes it particularly suitable for studying properties of integers, graphs, and other structures. It differs significantly from continuous mathematics, such as calculus. In the context of the given problem, discrete math concepts provide the tools needed to rigorously reason about numbers.

Some core topics in discrete mathematics include:

• Number Theory: Focuses on properties of integers, such as evenness and oddness.
• Logic: Includes propositional logic and proof techniques such as contrapositive, which are fundamental in mathematical reasoning.
• Combinatorics: Studies combinations of objects, often related to counting and arranging.

In discrete mathematics, proofs about numbers, such as those involving even and odd properties, often help develop an understanding essential for computer science and cryptography. Discrete math not only establishes the foundational logic for computing but also influences various algorithms and processes in technology.