Case 2. Suppose n is odd. Then n = 2k + 1 for some k ∈ Z, and (−1)n = −1.
Thus 1 + (−1)n(2n − 1) = 1 − (2(2k + 1) − 1) = −4k, which is a multiple of 4.
These cases show that 1 + (−1)n(2n − 1) is always a multiple of 4.
■
Now let’s examine the flip side of the question. We just proved that
1 +(−1)n(2n −1) is always a multiple of 4, but can we get every multiple of 4
this way? The following proposition and proof give an affirmative answer.
Treating Similar Cases
99
Proposition
Every multiple of 4 equals 1 + (−1)n(2n − 1) for some n ∈ N.
Proof. In conditional form, the proposition is as follows:
If k is a multiple of 4, then there is an n ∈ N for which 1 + (−1)n(2n − 1) = k.
What follows is a proof of this conditional statement.
Suppose k is a multiple of 4.
This means k = 4a for some integer a.
We must produce an n ∈ N for which 1 + (−1)n(2n − 1) = k.
This is done by cases, depending on whether a is zero, positive or negative.
Case 1. Suppose a = 0. Let n = 1. Then 1 + (−1)n(2n − 1) = 1 + (−1)1(2 − 1) = 0
= 4 · 0 = 4a = k.
Case 2. Suppose a > 0. Let n = 2a, which is in N because a is positive. Also
n is even, so (−1)n = 1. Thus 1+(−1)n(2n−1) = 1+(2n−1) = 2n = 2(2a) = 4a = k.
Case 3. Suppose a < 0. Let n = 1 − 2a, which is an element of N because
a is negative, making 1 − 2a positive. Also n is odd, so (−1)n = −1. Thus
1 + (−1)n(2n − 1) = 1 − (2n − 1) = 1 − (2(1 − 2a) − 1) = 4a = k.
The above cases show that no matter whether a multiple k = 4a of 4 is
zero, positive or negative, k = 1 + (−1)n(2n − 1) for some n ∈ N.
■
4.5 Treating Similar Cases
Occasionally two or more cases in a proof will be so similar that writing
them separately seems tedious or unnecessary. Here is an example.
Proposition
If two integers have opposite parity, then their sum is odd.
Proof. Suppose m and n are two integers with opposite parity.
We need to show that m + n is odd. This is done in two cases, as follows.
Case 1. Suppose m is even and n is odd. Thus m = 2a and n = 2b + 1 for
some integers a and b. Therefore m + n = 2a + 2b + 1 = 2(a + b) + 1, which is
odd (by Definition 4.2).
Case 2. Suppose m is odd and n is even. Thus m = 2a + 1 and n = 2b for
some integers a and b. Therefore m + n = 2a + 1 + 2b = 2(a + b) + 1, which is
odd (by Definition 4.2).
In either case, m + n is odd.
■
The two cases in this proof are entirely alike except for the order in
which the even and odd terms occur. It is entirely appropriate to just do
one case and indicate that the other case is nearly identical. The phrase
“Without loss of generality...” is a common way of signaling that the proof is
treating just one of several nearly identical cases. Here is a second version
of the above example.
100
Direct Proof
Proposition
If two integers have opposite parity, then their sum is odd.
Proof. Suppose m and n are two integers with opposite parity.
We need to show that m + n is odd.
Without loss of generality, suppose m is even and n is odd.
Thus m = 2a and n = 2b + 1 for some integers a and b.
Therefore m+n = 2a+2b+1 = 2(a+b)+1, which is odd (by Definition 4.2).
■
In reading proofs in other texts, you may sometimes see the phrase
“Without loss of generality” abbreviated as “WLOG.” However, in the
interest of transparency we will avoid writing it this way. In a similar
spirit, it is advisable—at least until you become more experienced in proof
writing—that you write out all cases, no matter how similar they appear
to be.
Please check your understanding by doing the following exercises. The
odd numbered problems have complete proofs in the Solutions section in
the back of the text.
Exercises for Chapter 4
Use the method of direct proof to prove the following statements.
1. If x is an even integer, then x2 is even.
2. If x is an odd integer, then x3 is odd.
3. If a is an odd integer, then a2 + 3a + 5 is odd.
4. Suppose x, y ∈ Z. If x and y are odd, then xy is odd.
5. Suppose x, y ∈ Z. If x is even, then xy is even.
6. Suppose a, b, c ∈ Z. If a | b and a | c, then a | (b + c).
7. Suppose a, b ∈ Z. If a | b, then a2 | b2.
8. Suppose a is an integer. If 5 | 2a, then 5 | a.
9. Suppose a is an integer. If 7 | 4a, then 7 | a.
10. Suppose a and b are integers. If a | b, then a | (3b3 − b2 + 5b).
11. Suppose a, b, c, d ∈ Z. If a | b and c | d, then ac | bd.
12.
4
If x ∈ R and 0 < x < 4, then x(4−x) ≥ 1.
13. Suppose x, y ∈ R. If x2 + 5y = y2 + 5x, then x = y or x + y = 5.
14. If n ∈ Z, then 5n2 + 3n + 7 is odd. (Try cases.)
15. If n ∈ Z, then n2 + 3n + 4 is even. (Try cases.)
16. If two integers have the same parity, then their sum is even. (Try cases.)
17. If two integers have opposite parity, then their product is even.
18. Suppose x and y are positive real numbers. If x < y, then x2 < y2.
Treating Similar Cases
101
19. Suppose a, b and c are integers. If a2 | b and b3 | c, then a6 | c.
20. If a is an integer and a2 | a, then a ∈ © − 1,0,1ª.
21.
¡ p¢
If p is prime and k is an integer for which 0 < k < p, then p divides k .
22.
¢
¢
If n ∈ N, then n2 = 2¡n
2 + ¡n
1 . (You may need a separate case for n = 1.)
23.
¡2n¢
If n ∈ N, then
n
is even.
24. If n ∈ N and n ≥ 2, then the numbers n! + 2, n! + 3, n! + 4, n! + 5, ..., n! + n are all
composite. (Thus for any n ≥ 2, one can find n consecutive composite numbers.
This means there are arbitrarily large “gaps” between prime numbers.)
25.
¡a¢¡b¢
¢¡a−b+c¢
If a, b, c ∈ N and c ≤ b ≤ a, then b c = ¡ a
b−c
c
.
26. Every odd integer is a difference of two squares. (Example 7 = 42 − 32, etc.)
27. Suppose a, b ∈ N. If gcd(a, b) > 1, then b | a or b is not prime.
28. If a, b, c ∈ Z, then c · gcd(a, b) ≤ gcd(ca, cb).
CHAPTER
5
Contrapositive Proof
e now examine an alternative to direct proof called contrapositive
W proof. Like direct proof, the technique of contrapositive proof is
used to prove conditional statements of the form “If P , then Q .” Although
it is possible to use direct proof exclusively, there are occasions where
contrapositive proof is much easier.
5.1 Contrapositive Proof
To understand how contrapositive proof works, imagine that you need to
prove a proposition of the following form.
Proposition
If P, then Q.
This is a conditional statement of form P ⇒ Q. Our goal is to show
that this conditional statement is tr
ue. Recall that in Section 2.6 we
observed that P ⇒ Q is logically equivalent to ∼ Q ⇒∼ P. For convenience,
we duplicate the truth table that verifies this fact.
P
Q
∼ Q
∼ P
P ⇒ Q
∼ Q ⇒∼ P
T
T
F
F
T
T
T
F
T
F
F
F
F
T
F
T
T
T
F
F
T
T
T
T
According to the table, statements P ⇒ Q and ∼ Q ⇒∼ P are different
ways of expressing exactly the same thing. The expression ∼ Q ⇒∼ P is
called the contrapositive form of P ⇒ Q.1
1Do not confuse the words contrapositive and converse. Recall from Section 2.4 that the
converse of P ⇒ Q is the statement Q ⇒ P, which is not logically equivalent to P ⇒ Q.
Contrapositive Proof
103
Since P ⇒ Q is logically equivalent to ∼ Q ⇒∼ P, it follows that to prove
P ⇒ Q is true, it suffices to instead prove that ∼ Q ⇒∼ P is true. If we were
to use direct proof to show ∼ Q ⇒∼ P is true, we would assume ∼ Q is true
use this to deduce that ∼ P is true. This in fact is the basic approach of
contrapositive proof, summarized as follows.
Outline for Contrapositive Proof
Proposition
If P, then Q.
Proof. Suppose ∼ Q.
...
Therefore ∼ P.
■
So the setup for contrapositive proof is very simple. The first line of the
proof is the sentence “Suppose Q is not true.” (Or something to that effect.)
The last line is the sentence “Therefore P is not true.” Between the first
and last line we use logic and definitions to transform the statement ∼ Q
to the statement ∼ P.
To illustrate this new technique, and to contrast it with direct proof,
we now prove a proposition in two ways: first with direct proof and then
with contrapositive proof.
Proposition
Suppose x ∈ Z. If 7x + 9 is even, then x is odd.
Proof. (Direct) Suppose 7x + 9 is even.
Thus 7x + 9 = 2a for some integer a.
Subtracting 6x + 9 from both sides, we get x = 2a − 6x − 9.
Thus x = 2a − 6x − 9 = 2a − 6x − 10 + 1 = 2(a − 3x − 5) + 1.
Consequently x = 2b + 1, where b = a − 3x − 5 ∈ Z.
Therefore x is odd.
■
Here is a contrapositive proof of the same statement:
Proposition
Suppose x ∈ Z. If 7x + 9 is even, then x is odd.
Proof. (Contrapositive) Suppose x is not odd.
Thus x is even, so x = 2a for some integer a.
Then 7x + 9 = 7(2a) + 9 = 14a + 8 + 1 = 2(7a + 4) + 1.
Therefore 7x + 9 = 2b + 1, where b is the integer 7a + 4.
Consequently 7x + 9 is odd.
Therefore 7x + 9 is not even.
■
104
Contrapositive Proof
Though the proofs are of equal length, you may feel that the con-
trapositive proof flowed more smoothly. This is because it is easier to
transform information about x into information about 7x + 9 than the other
way around. For our next example, consider the following proposition
concerning an integer x:
Proposition
If x2 − 6x + 5 is even, then x is odd.
A direct proof would be problematic. We would begin by assuming that
x2 −6x +5 is even, so x2 −6x +5 = 2a. Then we would need to transform this
into x = 2b + 1 for b ∈ Z. But it is not quite clear how that could be done,
for it would involve isolating an x from the quadratic expression. However
the proof becomes very simple if we use contrapositive proof.
Proposition
Suppose x ∈ Z. If x2 − 6x + 5 is even, then x is odd.
Proof. (Contrapositive) Suppose x is not odd.
Thus x is even, so x = 2a for some integer a.
So x2−6x+5 = (2a)2−6(2a)+5 = 4a2−12a+5 = 4a2−12a+4+1 = 2(2a2−6a+2)+1.
Therefore x2 − 6x + 5 = 2b + 1, where b is the integer 2a2 − 6a + 2.
Consequently x2 − 6x + 5 is odd.
Therefore x2 − 6x + 5 is not even.
■
In summary, since x being not odd (∼ Q) resulted in x2 − 6x + 5 being not
even (∼ P), then x2 − 6x + 5 being even (P) means that x is odd (Q). Thus
we have proved P ⇒ Q by proving ∼ Q ⇒∼ P. Here is another example:
Proposition
Suppose x, y ∈ R. If y3 + yx2 ≤ x3 + x y2, then y ≤ x.
Proof. (Contrapositive) Suppose it is not true that y ≤ x, so y > x.
Then y − x > 0. Multiply both sides of y − x > 0 by the positive value x2 + y2.
( y − x)(x2 + y2) > 0(x2 + y2)
yx2 + y3 − x3 − xy2 > 0
y3 + yx2 > x3 + xy2
Therefore y3 + yx2 > x3 + x y2, so it is not true that y3 + yx2 ≤ x3 + x y2.
■
Proving “If P , then Q ,” with the contrapositive approach necessarily
involves the negated statements ∼ P and ∼ Q. In working with these we
may have to use the techniques for negating statements (e.g., DeMorgan’s
laws) discussed in Section 2.10. We consider such an example next.
Congruence of Integers
105
Proposition
Suppose x, y ∈ Z. If 5 - x y, then 5 - x and 5 - y.
Proof. (Contrapositive) Suppose it is not true that 5 - x and 5 - y.
By DeMorgan’s law, it is not true that 5 - x or it is not true that 5 - y.
Therefore 5 | x or 5 | y. We consider these possibilities separately.
Case 1. Suppose 5 | x. Then x = 5a for some a ∈ Z.
From this we get x y = 5(a y), and that means 5 | x y.
Case 2. Suppose 5 | y. Then y = 5a for some a ∈ Z.
From this we get x y = 5(ax), and that means 5 | x y.
The above cases show that 5 | x y, so it is not true that 5 - x y.
■
5.2 Congruence of Integers
This is a good time to introduce a new definition. It is not necessarily
related to contrapositive proof, but introducing it now ensures that we
have a sufficient variety of exercises to practice all our proof techniques on.
This new definition occurs in many branches of mathematics, and it will
surely play a role in some of your later courses. But our primary reason
for introducing it is that it will give us more practice in writing proofs.
Definition 5.1
Given integers a and b and an n ∈ N, we say that a and b
are congruent modulo n if n | (a − b). We express this as a ≡ b (mod n).
If a and b are not congruent modulo n, we write this as a 6≡ b (mod n).
Example 5.1
Here are some examples:
1. 9 ≡ 1 (mod 4) because 4 | (9 − 1).
2. 6 ≡ 10 (mod 4) because 4 | (6 − 10).
3. 14 6≡ 8 (mod 4) because 4 - (14 − 8).
4. 20 ≡ 4 (mod 8) because 8 | (20 − 4).
5. 17 ≡ −4 (mod 3) because 3 | (17 − (−4)).
In practical terms, a ≡ b (mod n) means that a and b have the same
remainder when divided by n. For example, we saw above that 6 ≡ 10
&nb
sp; (mod 4) and indeed 6 and 10 both have remainder 2 when divided by 4.
Also we saw 14 6≡ 8 (mod 4), and sure enough 14 has remainder 2 when
divided by 4, while 8 has remainder 0.
To see that this is true in general, note that if a and b both have the
same remainder r when divided by n, then it follows that a = kn + r and
b = ` n + r for some k, ` ∈ Z. Then a − b = (kn + r) − ( ` n + r) = n(k − `). But
a − b = n(k − `) means n | (a − b), so a ≡ b (mod n). Conversely, one of the
exercises for this chapter asks you to show that if a ≡ b (mod n), then a
and b have the same remainder when divided by n.
106
Contrapositive Proof
We conclude this section with several proofs involving congruence of
integers, but you will also test your skills with other proofs in the exercises.
Proposition
Let a, b ∈ Z and n ∈ N. If a ≡ b (mod n), then a2 ≡ b2 (mod n).
Proof. We will use direct proof. Suppose a ≡ b (mod n).
By definition of congruence of integers, this means n | (a − b).
Then by definition of divisibility, there is an integer c for which a − b = nc.
Now multiply both sides of this equation by a + b.
a − b = nc
(a − b)(a + b) = nc(a + b)
a2 − b2 = nc(a + b)
Since c(a + b) ∈ Z, the above equation tells us n | (a2 − b2).
According to Definition 5.1, this gives a2 ≡ b2 (mod n).
■
Let’s pause to consider this proposition’s meaning. It says a ≡ b (mod n)
implies a2 ≡ b2 (mod n). In other words, it says that if integers a and b
have the same remainder when divided by n, then a2 and b2 also have
the same remainder when divided by n. As an example of this, 6 and 10
have the same remainder (2) when divided by n = 4, and their squares
36 and 100 also have the same remainder (0) when divided by n = 4. The
proposition promises this will happen for all a, b and n. In our examples
we tend to concentrate more on how to prove propositions than on what
the propositions mean. This is reasonable since our main goal is to learn
how to prove statements. But it is helpful to sometimes also think about
the meaning of what we prove.
Proposition
Let a, b, c ∈ Z and n ∈ N. If a ≡ b (mod n), then ac ≡ bc (mod n).
Proof. We employ direct proof. Suppose a ≡ b (mod n). By Definition 5.1,
it follows that n | (a − b). Therefore, by definition of divisibility, there exists
an integer k for which a − b = nk. Multiply both sides of this equation
by c to get ac − bc = nkc. Thus ac − bc = n(kc) where kc ∈ Z, which means
n | (ac − bc). By Definition 5.1, we have ac ≡ bc (mod n).
Book of Proof Page 15
