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)\)

Short answer

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

Step-by-step solution

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\).

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\).

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.

Conclusion

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