Section 4.6 More Proof by Contradiction and Contrapositive
In this section we will use contradiction and contrapositive to prove two classical theorems in mathematics.
In Activity 4.5.2 you used contrapositive to prove if \(n^2\) is even, then \(n\) is even. This statement is an important step in our first big theorem. We state it here formally as a lemma.
Proof.
We will prove this by contrapositive. Assume \(n\) is odd. Show \(n^2\) is odd. Since \(n\) is odd, \(n=2k+1\) for some \(k\in \mathbb{Z}\text{.}\) Then
\begin{equation*}
n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1.
\end{equation*}
Since \(2k^2+2k\in \mathbb{Z}\text{,}\) \(n^2\) is odd.
Theorem 4.6.2.
\(\sqrt{2}\) is irrational.
Proof.
We will prove this by contradiction. Assume \(\sqrt{2}\) is rational. Then \(\sqrt{2}=\frac{p}{q}\) with \(p, q\in\mathbb{Z}, q\neq 0\text{.}\) We will additionally assume \(p\) and \(q\) have no common factors. [Note, this additional assumption just makes the proof simpler. You should convince yourself that it is reasonable to add this assumption--that given any fraction, we can always reduce so \(p\) and \(q\) have no common factors.]
Now, using algebra on the equations,
\begin{align*}
\sqrt{2}&=\frac{p}{q}\\
2&=\frac{p^2}{q^2}\\
2q^2&=p^2.
\end{align*}
Since \(p\) is even, \(p=2k\) for some \(k\in \mathbb{Z}\text{.}\) Thus, we can substitute into the above equation.
\begin{align*}
2q^2&=(2k)^2\\
2q^2&=4k^2\\
q^2&=2k^2.
\end{align*}
But now we have \(p\) and \(q\) both even, which means they both have a common factor of 2. This contradicts our assumption that \(p\) and \(q\) have no common factors. Since we reached a contradiction, we can conclude that \(\sqrt{2}\) is irrational.
Make sure you can read through the above proof and follow from one step to the next.
Activity 4.6.1.
In Lemma 4.6.1 and Activity 4.5.2, we proved if \(n^2\) is even then \(n\) is even. Now suppose you want to prove if \(n^2\) is divisible by 3 then \(n\) is divisible by 3.
(a)
To prove the statement by contrapositive, what should you assume?
(b)
To prove the statement by contrapositive, what should you show?
(c)
The problem with now giving a direct proof of the contrapositive, is that we need to know what we mean by “\(n\) is not divisible by 3.” Recall the Quotient-Remainder Theorem, Theorem 4.4.1. If \(n\) is not divisible by 3, what are the possible forms for \(n\text{?}\)
Hint.
Think of the forms for \(n=3q+r\text{.}\)
(d)
Now write a proof by cases using the cases for \(n\) from (c) to show if \(n\) is not divisible by 3, then \(n^2\) is not divisible by 3.
Our second classical theorem is to prove there are infinitely many prime numbers. We previously proved there are infinitely many integers. In that proof, if we had a biggest integer, \(N\text{,}\) we were able to construct an integer that was greater than \(N\text{,}\) namely \(N+1\text{.}\) However, primes are not that nice. If you were to list out several prime numbers, it would be impossible to find a pattern for the “next” prime. Sometimes primes are close together, like 17 and 19, and sometimes they are far apart. In fact, it is possible to prove that we can find a list of \(n\) consecutive integers where none of the consecutive integers are prime for any positive integer \(n\text{.}\) This means there are arbitrarily long sequences of consecutive integers with no primes, or there are primes that are arbitrarily far apart.
First we need to understand a bit more about divisibilty with primes.
Activity 4.6.2.
Consider the statement: For all \(a\in \mathbb{Z}\) and primes \(p\text{,}\) if \(p\mid a\) then \(p \nmid (a+1)\text{.}\)
(a)
Write the contrapositive of the statement.
(b)
Write the negation of the statement.
(c)
Based on the contrapositive and the negation, which seem easier to use in a proof?
(d)
Assume \(p\mid a\) and \(p \mid (a+1)\text{.}\) Can you find a contradiction?
(e)
If you were able to find a contradiction, try to write a careful proof by contradiction for the statement.
The statement in Activity 4.6.2 is an important lemma for proving there are infinitely many primes.
Lemma 4.6.3.
For all \(n\in\mathbb{Z}\) and all primes \(p\text{,}\) if \(p\mid n\) then \(p\nmid n+1\text{.}\)
Proof.
We will prove this by contradiction. Let \(n\in\mathbb{Z}\text{,}\) \(p\) prime. Assume \(p\mid n\) and \(p\mid n+1\text{.}\) Since \(p\mid n\text{,}\) \(n=pk\) for some \(k\in \mathbb{Z}\text{.}\) Since \(p\mid n+1\text{,}\) \(n+1=pj\) for some \(j\in \mathbb{Z}\text{.}\) Thus,
\begin{align*}
n+1&=pj\\
pk+1&=pj\\
1&=pj-pk=p(k-j).
\end{align*}
Since \(k-j\in\mathbb{Z}, p\mid 1\text{,}\) and \(p\) is a factor of 1. However, the only factors of 1 are 1 and -1, which are not prime. Thus, we have a contradiction.
Theorem 4.6.4.
There are infinitely many primes.
Proof.
Assume there are finitely many primes. Since there are finitely many, we can list them all, say, \(p_1, p_2, \ldots, p_n\text{.}\) Now let \(N=p_1\cdot p_2\cdot p_3\cdots p_n\text{,}\) the product of all the primes. Consider \(N+1\text{.}\) We know \(p_i\mid N\) for each prime \(p_i\text{.}\) By Lemma 4.6.3, \(p_i\nmid N+1\text{.}\) This means \(N+1\) is an integer greater than 1 with no prime divisor, which contradicts Theorem 4.3.5.
Reading Questions Check Your Understanding
1.
Let \(n\in\mathbb{Z}\text{.}\) Give the contrapositive for the statement: if \(3\mid n^2\text{,}\) then \(3 \mid n\text{.}\)
2.
Suppose you are given that \(3\nmid n\text{.}\) Use the Quotient-Remainder Theorem (Theorem 4.4.1) to list the possible cases for \(n\text{.}\)
Hint.
What are the possible values for the remainder, \(r\text{?}\)
3.
If \(n=3q+1\) for some \(q\in \mathbb{Z}\text{,}\) show \(3\nmid n^2\text{.}\)
Hint.
Multiply out \(n^2=(3q+1)^2\text{.}\)
4.
If \(n=3q+2\) for some \(q\in \mathbb{Z}\text{,}\) show \(3\nmid n^2\text{.}\)
Hint.
Multiply out \(n^2=(3q+2)^2\text{.}\)
5.
True.
- \(\sqrt{4}=2\) is rational.
False.
- \(\sqrt{4}=2\) is rational.
True or false: for every \(n\in \mathbb{Z}\text{,}\) \(\sqrt{n}\) is irrational.
6.
True.
- Try \(n=2\text{.}\)
False.
- Try \(n=2\text{.}\)
True or false: if \(4\mid n^2\text{,}\) then \(4\mid n\text{.}\)
7.
True.
- Try \(n=1\text{.}\)
False.
- Try \(n=1\text{.}\)
True or false: for all \(n, m\in \mathbb{Z}\text{,}\) if \(n\mid m\text{,}\) then \(n\nmid m+1\text{.}\)
8.
True.
- Try \(n=5\text{.}\)
False.
- Try \(n=5\text{.}\)
True or false: for all \(n\in \mathbb{Z}\text{,}\) \(n!+1\) is prime.
Exercises Exercises
1.
Prove or disprove \(\sqrt{4}\) is irrational.
2.
Prove or disprove the difference of any two irrational numbers is irrational.
3.
Prove or disprove if \(r\) is any rational number and \(s\) is any irrational number, then \(r/s\) is irrational.
4.
Prove or disprove the product of any two irrational numbers is irrational.
5.
Give an example to show that if \(d\) is not prime and \(n^2\) is divisible by \(d\text{,}\) then \(n\) need not be divisible by \(d\text{.}\)
6.
Adapt the proofs of Lemma 4.6.1 and Theorem 4.6.2 to prove the following statements.
- Prove that for all integers \(a\text{,}\) if \(a^3\) is even then \(a\) is even.
- Prove that \(\sqrt[3]{2}\) is irrational.
Hint.
For (b), adapt the steps in the proof that \(\sqrt{2}\) is irrational to \(\sqrt[3]{2}\) and use (a).
7.
Prove \(\sqrt{3}\) is irrational.
Hint.
You might find Activity 4.6.1 very helpful.
You have attempted of activities on this page.
