Skip to main content

Discrete Mathematics: An Active Approach to Mathematical Reasoning

Jennifer Firkins Nordstrom

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 n2 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 n2 is odd. Since n is odd, n=2k+1 for some k∈Z. Then
n2=(2k+1)2=4k2+4k+1=2(2k2+2k)+1.
Since 2k2+2k∈Z, n2 is odd.

Proof.

We will prove this by contradiction. Assume 2 is rational. Then 2=pq with p,q∈Z,q≠0. 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,
2=pq2=p2q22q2=p2.
Since q2∈Z, p2 must be even. Then by Lemma 4.6.1, p must be even.
Since p is even, p=2k for some k∈Z. Thus, we can substitute into the above equation.
2q2=(2k)22q2=4k2q2=2k2.
Since k2∈Z, q2 must be even. Then by Lemma 4.6.1, q must be even.
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 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 n2 is even then n is even. Now suppose you want to prove if n2 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?
🔗
Hint.
Think of the forms for n=3q+r.
🔗

(d)

Now write a proof by cases using the cases for n from (c) to show if n is not divisible by 3, then n2 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, we were able to construct an integer that was greater than N, namely N+1. 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. 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∈Z and primes p, if p∣a then p∤(a+1).
🔗

(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∣a and p∣(a+1). 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.
🔗

Proof.

We will prove this by contradiction. Let n∈Z, p prime. Assume p∣n and p∣n+1. Since p∣n, n=pk for some k∈Z. Since p∣n+1, n+1=pj for some j∈Z. Thus,
n+1=pjpk+1=pj1=pj−pk=p(k−j).
Since k−j∈Z,p∣1, 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.

Proof.

Assume there are finitely many primes. Since there are finitely many, we can list them all, say, p1,p2,…,pn. Now let N=p1⋅p2⋅p3⋯pn, the product of all the primes. Consider N+1. We know pi∣N for each prime pi. By Lemma 4.6.3, pi∤N+1. 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∈Z. Give the contrapositive for the statement: if 3∣n2, then 3∣n.
🔗
🔗

2.

Suppose you are given that 3∤n. Use the Quotient-Remainder Theorem (Theorem 4.4.1) to list the possible cases for n.
🔗
Hint.
What are the possible values for the remainder, r?
🔗

3.

If n=3q+1 for some q∈Z, show 3∤n2.
🔗
Hint.
Multiply out n2=(3q+1)2.
🔗

4.

If n=3q+2 for some q∈Z, show 3∤n2.
🔗
Hint.
Multiply out n2=(3q+2)2.
🔗

5.

    True or false: for every n∈Z, n is irrational.
    🔗

  • True.

  • 4=2 is rational.

  • False.

  • 4=2 is rational.
🔗

6.

    True or false: if 4∣n2, then 4∣n.
    🔗

  • True.

  • Try n=2.

  • False.

  • Try n=2.
🔗

7.

    True or false: for all n,m∈Z, if n∣m, then n∤m+1.
    🔗

  • True.

  • Try n=1.

  • False.

  • Try n=1.
🔗

8.

    True or false: for all n∈Z, n!+1 is prime.
    🔗

  • True.

  • Try n=5.

  • False.

  • Try n=5.
🔗
🔗

Exercises Exercises

1.

Prove or disprove 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 n2 is divisible by d, then n need not be divisible by d.
🔗
🔗

6.

Adapt the proofs of Lemma 4.6.1 and Theorem 4.6.2 to prove the following statements.
🔗
  1. Prove that for all integers a, if a3 is even then a is even.
  2. Prove that 23 is irrational.
🔗
Hint.
223
🔗
🔗
You have attempted 1 of 9 activities on this page.
🔗
PrevTopNext