Problem 17 - Book of Proof

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.) For every \(n \in \mathbb{Z}, 4 \nmid\left(n^{2}+2\right)\)

Step-by-Step Solution

Answer

By contradiction, it has been proven that for every \(n \in \mathbb{Z}, 4 \nmid\left(n^{2}+2\right)\).

Step 1: Assumption

Assume the opposite of what is to be proven: there exists an integer \(n\) such that \(4\) divides \(n^{2}+2\), which means there exists a \(k \in \mathbb{Z}\) such that \(n^{2}+2 = 4k\).

Step 2: Identify possible values of \(n^{2}\mod 4\)

We know that for every integer \(n\), \(n^{2} = 0 \mod 4\) or \(n^{2} = 1 \mod 4\). Therefore, \(n^{2}+2 = 2\mod 4\) or \(n^{2}+2 = 3\mod 4\).

Step 3: Search for Contradiction

We can see that the results we got in the last step contradict with our assumption in Step 1. Therefore, our assumption is false and the initial statement is proven.

Step 4: Conclusion

Hence, by contradiction, it has been proven that for every \(n \in \mathbb{Z}, 4 \nmid\left(n^{2}+2\right)\).

Key Concepts

Integer Division

In mathematics, integer division is the process of dividing two integers and getting an integer result, disregarding any present remainder. When we say "4 divides", we mean there is some integer that, when multiplied by 4, gives us the number in question. Consider a simple example where 8 divided by 4 gives us exactly 2, with no remainder.
In the context of the exercise, we are tasked with proving that for any integer \( n \), 4 cannot divide \( n^2 + 2 \). If 4 divides \( n^2 + 2 \), then there exists some integer \( k \) such that \( n^2 + 2 = 4k \).
This assumption sets the groundwork for a proof by contradiction, which helps us explore whether this argument holds or if we can find inconsistencies.

• Integer division strictly deals with whole numbers.
• Any remainder is disregarded in the calculations.
• This concept is crucial for understanding divisibility in proofs.

Modular Arithmetic

Modular arithmetic is often described as "clock arithmetic" due to its cyclical nature. It involves the remainder when an integer is divided by another integer, referred to as the modulus. For instance, when we say \( n^2 \mod 4 \), we're looking at whether \( n^2 \) leaves a remainder of 0, 1, 2, or 3 when divided by 4.
In this exercise, we only examine the cases where \( n^2 \equiv 0 \mod 4 \) or \( n^2 \equiv 1 \mod 4 \), since squaring an integer results in a residue of either 0 or 1 with modulus 4.
This allows us to evaluate \( n^2 + 2 \mod 4 \), which simplifies further:

• If \( n^2 \equiv 0 \mod 4 \), then \( n^2 + 2 \equiv 2 \mod 4 \).
• If \( n^2 \equiv 1 \mod 4 \), then \( n^2 + 2 \equiv 3 \mod 4 \).

Highlighting these results helps identify the requisite contradiction, as neither outcome is congruent to 0 modulo 4, which means 4 cannot divide \( n^2 + 2 \).

Logical Reasoning

Logical reasoning is the backbone of mathematical proof techniques such as proof by contradiction. When engaging in a proof by contradiction, we start by assuming the opposite of what we aim to prove. In our problem, we assumed that there is an integer \( n \) such that 4 divides \( n^2 + 2 \).
This assumption allows us to use logical reasoning involving the properties of dividers and modular arithmetic to test our hypothesis. By evaluating \( n^2 + 2 \) under possible values of \( n^2 \mod 4 \), we observed results that challenge our initial assumption.
The contradiction arises because our results (\( n^2 + 2 \equiv 2 \mod 4 \) or \( \equiv 3 \mod 4 \)) never align with \( n^2 + 2 \equiv 0 \mod 4 \), nullifying our assumption.

• Proof by contradiction demonstrates the impossibility of a false premise.
• This reasoning solidifies the truth of the statement through elimination.
• It leverages intrinsic properties of integers and remainders.

Through this careful reasoning, the statement that 4 does not divide \( n^2 + 2 \) for any integer \( n \) stands validated.