b2 = 3d2. But this means 3 | b2, and the second paragraph implies 3 | b. Thus
we have concluded that 3 | a and 3 | b, but this contradicts the fact that the
a
fraction b is reduced.
■
264
Solutions
7. If a, b ∈ Z, then a2 − 4b − 3 6= 0.
Proof. Suppose for the sake of contradiction that a, b ∈ Z but a2−4b−3 = 0. Then
we have a2 = 4b +3 = 2(2b +1)+1, which means a2 is odd. Therefore a is odd also,
so a = 2c + 1 for some integer c. Plugging this back into a2 − 4b − 3 = 0 gives us
(2c + 1)2 − 4b − 3 = 0
4c2 + 4c + 1 − 4b − 3 = 0
4c2 + 4c − 4b
=
2
2c2 + 2c − 2b
=
1
2(c2 + c − b) = 1.
From this last equation, we see that 1 is an even number, a contradiction.
■
9. Suppose a, b ∈ R and a 6= 0. If a is rational and ab is irrational, then b is
irrational.
Proof. Suppose for the sake of contradiction that a is rational and ab is irra-
tional and b is not irrational. Thus we have a and b rational, and ab irrational.
Since a and b are rational, we know there are integers c, d, e, f for which a = cd
and b = ef . Then ab = ce
d f , and since both c e and d f are integers, it follows
that ab is rational. But this is a contradiction because we started out with ab
irrational.
■
11. There exist no integers a and b for which 18a + 6b = 1.
Proof. Suppose for the sake of contradiction that there do exist integers a
and b for which 18a + 6b = 1. Then 1 = 2(9a + 3b), which means 1 is even, a
contradiction.
■
13. For every x ∈ [ π/2, π], sin x − cos x ≥ 1.
Proof. Suppose for the sake of contradiction that x ∈ [ π/2, π], but sin x − cos x < 1.
Since x ∈ [ π/2, π], we know sin x ≥ 0 and cos x ≤ 0, so sin x − cos x ≥ 0. Therefore
we have 0 ≤ sin x − cos x < 1. Now the square of any number between 0 and
1 is still a number between 0 and 1, so we have 0 ≤ (sin x − cos x)2 < 1, or 0 ≤
sin2 x − 2sin x cos x + cos2 x < 1. Using the fact that sin2 x + cos2 x = 1, this becomes
0 ≤ −2sin x cos x + 1 < 1. Subtracting 1, we obtain −2sin x cos x < 0. But above we
remarked that sin x ≥ 0 and cos x ≤ 0, and hence −2 sin x cos x ≥ 0. We now have
the contradiction −2 sin x cos x < 0 and −2 sin x cos x ≥ 0.
■
15. If b ∈ Z and b - k for every k ∈ N, then b = 0.
Proof. Suppose for the sake of contradiction that b ∈ Z and b - k for every k ∈ N,
but b 6= 0.
Case 1. Suppose b > 0. Then b ∈ N, so b|b, contradicting b - k for every k ∈ N.
Case 2. Suppose b < 0. Then −b ∈ N, so b|(−b), again a contradiction
■
265
17. For every n ∈ Z, 4 - (n2 + 2).
Proof. Assume there exists n ∈ Z with 4 | (n2 +2). Then for some k ∈ Z, 4k = n2 +2
or 2k = n2 + 2(1 − k). If n is odd, this means 2k is odd, and we’ve reached a
contradiction. If n is even then n = 2 j and we get k = 2 j2 + 1 − k for some j ∈ Z.
Hence 2(k − j2) = 1, so 1 is even, a contradiction.
■
Remark. It is fairly easy to see that two more than a perfect square is always
either 2 (mod 4) or 3 (mod 4). This would end the proof immediately.
19. The product of 5 consecutive integers is a multiple of 120.
Proof. Given any collection of 5 consecutive integers, at least one must be a
multiple of two, at least one must be a multiple of three, at least one must be
a multiple of four and at least one must be a multiple of 5. Hence the product
is a multiple of 5 · 4 · 3 · 2 = 120. In particular, the product is a multiple of 60.
■
21. Hints for Exercises 20–23. For Exercises 20, first show that the equation
a2 + b2 = 3c2 has no solutions (other than the trivial solution (a, b, c) = (0,0,0))
in the integers. To do this, investigate the remainders of a sum of squares
(mod 4). After you’ve done this, prove that the only solution is indeed the trivial
solution.
Now, assume that the equation x2 + y2 − 3 = 0 has a rational solution. Use the
definition of rational numbers to yield a contradiction.
Chapter 7 Exercises
1. Suppose x ∈ Z. Then x is even if and only if 3x + 5 is odd.
Proof. We first use direct proof to show that if x is even, then 3x + 5 is odd.
Suppose x is even. Then x = 2n for some integer n. Thus 3x + 5 = 3(2n) + 5 =
6n + 5 = 6n + 4 + 1 = 2(3n + 2) + 1. Thus 3x + 5 is odd because it has form 2k + 1,
where k = 3n + 2 ∈ Z.
Conversely, we need to show that if 3x + 5 is odd, then x is even. We will
prove this using contrapositive proof. Suppose x is not even. Then x is odd, so
x = 2n + 1 for some integer n. Thus 3x + 5 = 3(2n + 1) + 5 = 6n + 8 = 2(3n + 4). This
means says 3x + 5 is twice the integer 3n + 4, so 3x + 5 is even, not odd.
■
3. Given an integer a, then a3 + a2 + a is even if and only if a is even.
Proof. First we will prove that if a3 + a2 + a is even then a is even. This is done
with contrapositive proof. Suppose a is not even. Then a is odd, so there is an
integer n for which a = 2n + 1. Then
a3 + a2 + a = (2n + 1)3 + (2n + 1)2 + (2n + 1)
=
8n3 + 12n2 + 6n + 1 + 4n2 + 4n + 1 + 2n + 1
=
8n3 + 16n2 + 12n + 2 + 1
=
2(4n3 + 8n2 + 6n + 1) + 1.
266
Solutions
This expresses a3 + a2 + a as twice an integer plus 1, so a3 + a2 + a is odd, not
even. We have now shown that if a3 + a2 + a is even then a is even.
Conversely, we need to show that if a is even, then a3 +a2 +a is even. We will use
direct proof. Suppose a is even, so a = 2n for some integer n. Then a3 + a2 + a =
(2n)3 + (2n)2 + 2n = 8n3 + 4n2 + 2n = 2(4n3 + 2n2 + n). Therefore, a3 + a2 + a is even
because it’s twice an integer.
■
5. An integer a is odd if and only if a3 is odd.
Proof. Suppose that a is odd. Then a = 2n + 1 for some integer n, and a3 =
(2n + 1)3 = 8n3 + 12n2 + 6n + 1 = 2(4n3 + 6n2 + 3n) + 1. This shows that a3 is twice
an integer, plus 1, so a3 is odd. Thus we’ve proved that if a is odd then a3 is
odd.
Conversely we need to show that if a3 is odd, then a is odd. For this we employ
contrapositive proof. Suppose a is not odd. Thus a is even, so a = 2n for some
integer n. Then a3 = (2n)3 = 8n3 = 2(4n3) is even (not odd).
■
7. Suppose x, y ∈ R. Then (x + y)2 = x2 + y2 if and only if x = 0 or y = 0.
Proof. First we prove with direct proof that if (x + y)2 = x2 + y2, then x = 0 or
y = 0. Suppose (x+ y)2 = x2 + y2. From this we get x2 +2xy+ y2 = x2 + y2, so 2xy = 0,
and hence x y = 0. Thus x = 0 or y = 0.
Conversely, we need to show that if x = 0 or y = 0, then (x + y)2 = x2 + y2. This
will be done with cases.
Case 1. If x = 0 then (x + y)2 = (0 + y)2 = y2 = 02 + y2 = x2 + y2.
Case 2. If y = 0 then (x + y)2 = (x + 0)2 = x2 = x2 + 02 = x2 + y2.
Either way, we have (x + y)2 = x2 + y2.
■
9. Suppose a ∈ Z. Prove that 14 | a if and only if 7 | a and 2 | a.<
br />
Proof. First we prove that if 14 | a, then 7 | a and 2 | a. Direct proof is used.
Suppose 14 | a. This means a = 14m for some integer m. Therefore a = 7(2m),
which means 7 | a, and also a = 2(7m), which means 2 | a. Thus 7 | a and 2 | a.
Conversely, we need to prove that if 7 | a and 2 | a, then 14 | a. Once again direct
proof if used. Suppose 7 | a and 2 | a. Since 2 | a it follows that a = 2m for some
integer m, and that in turn implies that a is even. Since 7 | a it follows that
a = 7n for some integer n. Now, since a is known to be even, and a = 7n, it
follows that n is even (if it were odd, then a = 7n would be odd). Thus n = 2p for
an appropriate integer p, and plugging n = 2p back into a = 7n gives a = 7(2p),
so a = 14p. Therefore 14 | a.
■
267
11. Suppose a, b ∈ Z. Prove that (a − 3)b2 is even if and only if a is odd or b is even.
Proof. First we will prove that if (a − 3)b2 is even, then a is odd or b is even.
For this we use contrapositive proof. Suppose it is not the case that a is
odd or b is even. Then by DeMorgan’s law, a is even and b is odd. Thus
there are integers m and n for which a = 2m and b = 2n + 1. Now observe
(a−3)b2 = (2m−3)(2n+1)2 = (2m−3)(4n2+4n+1) = 8mn2+8mn+2m−12n2−12n−3 =
8mn2 + 8mn + 2m − 12n2 − 12n − 4 + 1 = 2(4mn2 + 4mn + m − 6n2 − 6n − 2) + 1. This
shows (a − 3)b2 is odd, so it’s not even.
Conversely, we need to show that if a is odd or b is even, then (a − 3)b2 is even.
For this we use direct proof, with cases.
Case 1. Suppose a is odd. Then a = 2m + 1 for some integer m. Thus (a − 3)b2 =
(2m + 1 − 3)b2 = (2m − 2)b2 = 2(m − 1)b2. Thus in this case (a − 3)b2 is even.
Case 2. Suppose b is even. Then b = 2n for some integer n. Thus (a − 3)b2 =
(a − 3)(2n)2 = (a − 3)4n2 = 2(a − 3)2n2 =. Thus in this case (a − 3)b2 is even.
Therefore, in any event, (a − 3)b2 is even.
■
13. Suppose a, b ∈ Z. If a + b is odd, then a2 + b2 is odd.
Hint: Use direct proof. Suppose a + b is odd. Argue that this means a and b
have opposite parity. Then use cases.
15. Suppose a, b ∈ Z. Prove that a + b is even if and only if a and b have the same
parity.
Proof. First we will show that if a+b is even, then a and b have the same parity.
For this we use contrapositive proof. Suppose it is not the case that a and b
have the same parity. Then one of a and b is even and the other is odd. Without
loss of generality, let’s say that a is even and b is odd. Thus there are integers
m and n for which a = 2m and b = 2n + 1. Then a + b = 2m + 2n + 1 = 2(m + n) + 1,
so a + b is odd, not even.
Conversely, we need to show that if a and b have the same parity, then a + b is
even. For this, we use direct proof with cases. Suppose a and b have the same
parity.
Case 1. Both a and b are even. Then there are integers m and n for which
a = 2m and b = 2n, so a + b = 2m + 2n = 2(m + n) is clearly even.
Case 2. Both a and b are odd. Then there are integers m and n for which
a = 2m + 1 and b = 2n + 1, so a + b = 2m + 1 + 2n + 1 = 2(m + n + 1) is clearly even.
Either way, a + b is even. This completes the proof.
■
17. There is a prime number between 90 and 100.
Proof. Simply observe that 97 is prime.
■
268
Solutions
19. If n ∈ N, then 20 + 21 + 22 + 23 + 24 + ··· + 2n = 2n+1 − 1.
Proof. We use direct proof. Suppose n ∈ N. Let S be the number
S = 20 + 21 + 22 + 23 + 24 + ··· + 2n−1 + 2n.
(1)
In what follows, we will solve for S and show S = 2n+1 − 1. Multiplying both
sides of (1) by 2 gives
2S = 21 + 22 + 23 + 24 + 25 + ··· + 2n + 2n+1.
(2)
Now subtract Equation (1) from Equation (2) to obtain 2S − S = −20 + 2n+1,
which simplifies to S = 2n+1 − 1. Combining this with Equation (1) produces
20 + 21 + 22 + 23 + 24 + ··· + 2n = 2n+1 − 1, so the proof is complete.
■
21. Every real solution of x3 + x + 3 = 0 is irrational.
Proof. Suppose for the sake of contradiction that this polynomial has a rational
a
solution b . We may assume that this fraction is fully reduced, so a and b are
¡ a ¢3
not both even. We have
b
+ ab + 3 = 0. Clearing the denominator gives
a3 + ab2 + 3b3 = 0.
Consider two cases: First, if both a and b are odd, the left-hand side is a sum
of three odds, which is odd, meaning 0 is odd, a contradiction. Second, if one
of a and b is odd and the other is even, then the middle term of a3 + ab2 + 3b3
is even, while a3 and 3b2 have opposite parity. Then a3 + ab2 + 3b3 is the sum
of two evens and an odd, which is odd, again contradicting the fact that 0 is
even.
■
23. Suppose a, b and c are integers. If a | b and a | (b2 − c), then a | c.
Proof. (Direct) Suppose a | b and a | (b2 − c). This means that b = ad and
b2 − c = ae for some integers d and e. Squaring the first equation produces
b2 = a2d2. Subtracting b2 − c = ae from b2 = a2d2 gives c = a2d2 − ae = a(ad2 − e).
As ad2 − e ∈ Z, it follows that a | c.
■
p
25. If p > 1 is an integer and n - p for each integer n for which 2 ≤ n ≤ p, then p is
prime.
Proof. (Contrapositive) Suppose that p is not prime, so it factors as p = mn for
1 < m, n < p.
p
p
Observe that it is not the case that both m >
p and n > p, because if this were
p p
true the inequalities would multiply to give mn >
p
p = p, which contradicts
p = mn.
p
p
p
Therefore m ≤
p or n ≤ p. Without loss of generality, say n ≤ p. Then the
p
equation p = mn gives n | p, with 1 < n ≤
p. Therefore it is not true that n - p
p
for each integer n for which 2 ≤ n ≤
p.
■
269
27. Suppose a, b ∈ Z. If a2 + b2 is a perfect square, then a and b are not both odd.
Proof. (Contradiction) Suppose a2 + b2 is a perfect square, and a and b are both
odd. As a2 + b2 is a perfect square, say c is the integer for which c2 = a2 + b2. As
a and b are odd, we have a = 2m + 1 and b = 2n + 1 for integers m and n. Then
c2 = a2 + b2 = (2m + 1)2 + (2n + 1)2 = 4(m2 + n2 + mn) + 2.
This is even, so c is even also; let c = 2k. Now the above equation results in
(2k)2 = 4(m2 + n2 + mn) + 2, which simplifies to 2k2 = 2(m2 + n2 + mn)+1. Thus 2k2
is both even and odd, a contradiction.
■
29. If a | bc and gcd(a, b) = 1, then a | c.
Proof. (Direct) Suppose a | bc and gcd(a, b) = 1. The fact that a | bc means bc = az
for some integer z. The fact that gcd(a, b) = 1 means that ax + b y = 1 for some
integers x and y (by Proposition 7.1 on page 126). From this we get acx+ bc y = c;
substituting bc = az yields acx+az y = c, that is, a(cx+ z y) = c. Therefore a | c.
■
31. If n ∈ Z, then gcd(n, n + 1) = 1.
&n
bsp; Proof. Suppose d is a positive integer that is a common divisor of n and n + 1.
Then n = dx and n + 1 = d y for integers x and y. Then 1 = (n + 1) − n = d y − dx =
d( y − x). Now, 1 = d(y − x) is only possible if d = ±1 and y − x = ±1. Thus the
greatest common divisor of n and n + 1 can be no greater than 1. But 1 does
divide both n and n + 1, so gcd(n, n + 1) = 1.
■
33. If n ∈ Z, then gcd(2n + 1,4n2 + 1) = 1.
Proof. Note that 4n2 + 1 = (2n + 1)(2n − 1) + 2. Therefore, it suffices to show that
gcd(2n + 1,(2n + 1)(2n − 1) + 2) = 1. Let d be a common positive divisor of both
2n+1 and (2n+1)(2n−1)+2, so 2n+1 = dx and (2n+1)(2n−1)+2 = d y for integers
x and y. Substituting the first equation into the second gives dx(2n −1)+2 = d y,
so 2 = d y − dx(2n − 1) = d( y − 2nx − x). This means d divides 2, so d equals 1 or
2. But the equation 2n + 1 = dx means d must be odd. Therefore d = 1, that is,
gcd(2n + 1,(2n + 1)(2n − 1) + 2) = 1.
■
35. Suppose a, b ∈ N. Then a = gcd(a, b) if and only if a | b.
Proof. Suppose a = gcd(a, b). This means a is a divisor of both a and b. In
particular a | b.
Conversely, suppose a | b. Then a divides both a and b, so a ≤ gcd(a, b). On the
other hand, since gcd(a, b) divides a, we have a = gcd(a, b) · x for some integer x.
As all integers involved are positive, it follows that a ≥ gcd(a, b).
It has been established that a ≤ gcd(a, b) and a ≥ gcd(a, b). Thus a = gcd(a, b).
■
270
Solutions
Chapter 8 Exercises
1. Prove that {12n : n ∈ Z} ⊆ {2n : n ∈ Z} ∩ {3n : n ∈ Z}.
Proof. Suppose a ∈ {12n : n ∈ Z}. This means a = 12n for some n ∈ Z. Therefore
a = 2(6n) and a = 3(4n). From a = 2(6n), it follows that a is multiple of 2, so
a ∈ {2n : n ∈ Z}. From a = 3(4n), it follows that a is multiple of 3, so a ∈ {3n : n ∈ Z}.
Thus by definition of the intersection of two sets, we have a ∈ {2n : n ∈ Z} ∩
{3n : n ∈ Z}. Thus {12n : n ∈ Z} ⊆ {2n : n ∈ Z} ∩ {3n : n ∈ Z}.
■
3. If k ∈ Z, then {n ∈ Z : n | k} ⊆ ©n ∈ Z : n | k2ª.
Proof. Suppose k ∈ Z. We now need to show {n ∈ Z : n | k} ⊆ ©n ∈ Z : n | k2ª.
Suppose a ∈ {n ∈ Z : n | k}. Then it follows that a | k, so there is an integer c for
which k = ac. Then k2 = a2 c2. Therefore k2 = a(ac2), and from this the definition
of divisibility gives a | k2. But a | k2 means that a ∈ ©n ∈ Z : n | k2ª. We have now
Book of Proof Page 38
