Therefore n2 + 3n + 4 = (2a + 1)2 + 3(2a + 1) + 4 = 4a2 + 4a + 1 + 6a + 3 + 4 = 4a2 + 10a + 8
= 2(2a2 +5a+4). So n2 +3n+4 = 2b where b = 2a2 +5a+4 ∈ Z, so n2 +3n+4 is even.
In either case n2 + 3n + 4 is even.
■
17. If two integers have opposite parity, then their product is even.
Proof. Suppose a and b are two integers with opposite parity. Thus one is even
and the other is odd. Without loss of generality, suppose a is even and b is
odd. Therefore there are integers c and d for which a = 2c and b = 2d + 1. Then
the product of a and b is ab = 2c(2d + 1) = 2(2cd + c). Therefore ab = 2k where
k = 2cd + c ∈ Z. Therefore the product ab is even.
■
19. Suppose a, b, c ∈ Z. If a2 | b and b3 | c then a6 | c.
Proof. Since a2 | b we have b = ka2 for some k ∈ Z. Since b3 | c we have c = hb3
for some h ∈ Z. Thus c = h(ka2)3 = hk3a6. Hence a6 | c.
■
21.
¢
If p is prime and 0 < k < p then p | ¡p .
k
Proof.
¡ p¢
p!
¢
From the formula
(p
k = (p
− k)!k!
−k)!k! , we get p! = ¡p
k
. Now, since the
¡ p¢
prime number p is a factor of p! on the left, it must also be a factor of
(p
k
−k)!k!
on the right. Thus the prime number p appears in the prime factorization of
¡ p¢(p
k
− k)!k!.
Now, k! is a product of numbers smaller than p, so its prime factorization
contains no p’s. Similarly the prime factorization of (p − k)! contains no p’s.
¡ p¢
But we noted that the prime factorization of
(p
k
− k)!k! must contain a p, so it
¡ p¢
¡ p¢
follows that the prime factorization of k contains a p. Thus k is a multiple
¡ p¢
of p, so p divides k .
■
23.
¡2n¢
If n ∈ N then
n
is even.
Proof.
¡2n¢
By definition,
n
is the number of n-element subsets of a set A with 2n
elements. For each subset X ⊆ A with |X | = n, the complement X is a different
set, but it also has 2n − n = n elements. Imagine listing out all the n-elements
subset of a set A. It could be done in such a way that the list has form
X1, X1, X2, X2, X3, X3, X4, X4, X5, X5 . . .
¡2n¢
This list has an even number of items, for they are grouped in pairs. Thus
n
is even.
■
259
25.
¡a¢¡b¢
¢¡a−b+c¢
If a, b, c ∈ N and c ≤ b ≤ a then
.
b
c = ¡ a
b−c
c
Proof.
¡a¢¡b¢
b!
Assume a, b, c ∈ N with c ≤ b ≤ a. Then we have b c =
a!
(a−b)!b! (b−c)!c! =
a!
(a−b+c)!
(a−b+c)!
¢¡a−b+c¢.
(a
■
−b+c)!(a−b)! (b−c)!c! =
a!
(b−c)!(a−b+c)! (a−b)!c! = ¡ a
b−c
c
27. Suppose a, b ∈ N. If gcd(a, b) > 1, then b | a or b is not prime.
Proof. Suppose gcd(a, b) > 1. Let c = gcd(a, b) > 1. Then since c is a divisor of
both a and b, we have a = cx and b = c y for integers x and y. We divide into
two cases according to whether or not b is prime.
Case I. Suppose b is prime. Then the above equation b = c y with c > 1 forces
c = b and y = 1. Then a = cx becomes a = bx, which means b | a. We conclude
that the statement “b | a or b is not prime, ” is true.
Case II. Suppose b is not prime. Then the statement “b | a or b is not prime, ”
is automatically true.
■
Chapter 5 Exercises
1. Proposition Suppose n ∈ Z. If n2 is even, then n is even.
Proof. (Contrapositive) Suppose n is not even. Then n is odd, so n = 2a + 1 for
some integer a, by definition of an odd number. Thus n2 = (2a+1)2 = 4a2 +4a+1 =
2(2a2 + 2a) + 1. Consequently n2 = 2b +1, where b is the integer 2a2 +2a, so n2 is
odd. Therefore n2 is not even.
■
3. Proposition Suppose a, b ∈ Z. If a2(b2 − 2b) is odd, then a and b are odd.
Proof. (Contrapositive) Suppose it is not the case that a and b are odd. Then,
by DeMorgan’s law, at least one of a and b is even. Let us look at these cases
separately.
Case 1. Suppose a is even. Then a = 2c for some integer c. Thus a2(b2 − 2b)
= (2c)2(b2 − 2b) = 2(2c2(b2 − 2b)), which is even.
Case 2. Suppose b is even. Then b = 2c for some integer c. Thus a2(b2 − 2b)
= a2((2c)2 − 2(2c)) = 2(a2(2c2 − 2c)), which is even.
(A third case involving a and b both even is unnecessary, for either of the two
cases above cover this case.) Thus in either case a2(b2 − 2b) is even, so it is not
odd.
■
5. Proposition Suppose x ∈ R. If x2 + 5x < 0 then x < 0.
Proof. (Contrapositive) Suppose it is not the case that x < 0, so x ≥ 0. Then
neither x2 nor 5x is negative, so x2 +5x ≥ 0. Thus it is not true that x2 +5x < 0.
■
260
Solutions
7. Proposition Suppose a, b ∈ Z. If both ab and a + b are even, then both a and
b are even.
Proof. (Contrapositive) Suppose it is not the case that both a and b are even.
Then at least one of them is odd. There are three cases to consider.
Case 1. Suppose a is even and b is odd. Then there are integers c and
d for which a = 2c and b = 2d + 1. Then ab = 2c(2d + 1), which is even; and
a + b = 2c + 2d + 1 = 2(c + d) + 1, which is odd. Thus it is not the case that both
ab and a + b are even.
Case 2. Suppose a is odd and b is even. Then there are integers c and d for
which a = 2c + 1 and b = 2d. Then ab = (2c + 1)(2d) = 2(d(2c + 1)), which is even;
and a + b = 2c + 1 + 2d = 2(c + d) + 1, which is odd. Thus it is not the case that
both ab and a + b are even.
Case 3. Suppose a is odd and b is odd. Then there are integers c and d for
which a = 2c + 1 and b = 2d + 1. Then ab = (2c + 1)(2d + 1) = 4cd + 2c + 2d + 1 =
2(2cd + c + d) + 1, which is odd; and a + b = 2c + 1 + 2d + 1 = 2(c + d + 1), which is
even. Thus it is not the case that both ab and a + b are even.
These cases show that it is not the case that ab and a + b are both even. (Note
that unlike Exercise 3 above, we really did need all three cases here, for each
case involved specific parities for both a and b.)
■
9. Proposition Suppose n ∈ Z. If 3 - n2, then 3 - n.
Proof. (Contrapositive) Suppose it is not the case that 3 - n, so 3 | n. This means
that n = 3a for some integer a. Consequently n2 = 9a2, from which we get
n2 = 3(3a2). This shows that there in an integer b = 3a2 for which n2 = 3b, which
means 3 | n2. Therefore it is not the case that 3 - n2.
■
11. Proposition Suppose x, y ∈ Z. If x2(y + 3) is even, then x is even or y is odd.
Proof. (Contrapositive) Suppose it is not the case that x is even or y is odd.
Using DeMorgan’s law, this means x is not even and y is not odd, which is to
say x is odd and y is even. Thus there are integers a and b for which x = 2a + 1
and y = 2b. Consequently x2( y + 3) = (2a + 1)2(2b + 3) = (4a2 + 4a + 1)(2b + 3) =
8a2b + 8ab + 2b + 12a2 + 12a + 3 = 8a2b + 8ab + 2b + 12a2 + 12a + 2 + 1 =
2(4a2b + 4ab + b + 6a2 + 6a + 1) + 1. This shows x2(y + 3) = 2c + 1 for c = 4a2b + 4ab +
b + 6a2 + 6a + 1 ∈ Z. Consequently, x2(y + 3) is not even.
■
13. Proposition Suppose x ∈ R. If x5 + 7x3 + 5x ≥ x4 + x2 + 8, then x ≥ 0.
Proof. (Contrapositive) Suppose it is not true that x ≥ 0. Then x < 0, that is
x is negative. Consequently, the expressions x5, 7x3 and 5x are all negative
(note the odd powers) so x5 + 7x3 + 5x < 0. Similarly the terms x4, x2, and 8
are all positive (note the even powers), so 0 < x4 + x2 + 8. From this we get
x5 + 7x3 + 5x < x4 + x2 + 8, so it is not true that x5 + 7x3 + 5x ≥ x4 + x2 + 8.
■
261
15. Proposition Suppose x ∈ Z. If x3 − 1 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 x3 − 1 = (2a)3 − 1 = 8a3 − 1 = 8a3 − 2 + 1 = 2(4a3 − 1) + 1. Therefore
x3 − 1 = 2b + 1 where b = 4a3 − 1 ∈ Z, so x3 − 1 is odd. Thus x3 − 1 is not even.
■
17. Proposition If n is odd, then 8 | (n2 − 1).
Proof. (Direct) Suppose n is odd, so n = 2a + 1 for some integer a. Then n2 − 1 =
(2a + 1)2 − 1 = 4a2 + 4a = 4(a2 + a) = 4a(a + 1). So far we have n2 − 1 = 4a(a + 1), but
we want a factor of 8, not 4. But notice that one of a or a + 1 must be even, so
a(a + 1) is even and hence a(a + 1) = 2c for some integer c. Now we have n2 − 1 =
4a(a + 1) = 4(2c) = 8c. But n2 − 1 = 8c means 8 | (n2 − 1).
■
19. Proposition Let a, b ∈ Z and n ∈ N. If a ≡ b (mod n) and a ≡ c (mod n), then
c ≡ b (mod n).
Proof. (Direct) Suppose a ≡ b (mod n) and a ≡ c (mod n).
This means n | (a − b) and n | (a − c).
Thus there are integers d and e for which a − b = nd and a − c = ne.
Subtracting the second equation from the first gives c − b = nd − ne.
Thus c − b = n(d − e), so n | (c − b) by definition of divisibility.
Therefore c ≡ b (mod n) by definition of congruence modulo n.
■
21. Proposition Let a, b ∈ Z and n ∈ N. If a ≡ b (mod n), then a3 ≡ b3 (mod n).
Proof. (Direct) Suppose a ≡ b (mod n). This means n | (a − b), so there is an
integer c for which a − b = nc. Then:
a − b
=
nc
(a − b)(a2 + ab + b2) =
nc(a2 + ab + b2)
a3 + a2b + ab2 − ba2 − ab2 − b3
=
nc(a2 + ab + b2)
a3 − b3
=
nc(a2 + ab + b2).
Since a2 + ab + b2 ∈ Z, the equation a3 − b3 = nc(a2 + ab + b2) implies n | (a3 − b3),
and therefore a3 ≡ b3 (mod n).
■
23. Proposition Let a, b, c ∈ Z and n ∈ N. If a ≡ b (mod n), then ca ≡ cb (mod n).
Proof. (Direct) Suppose a ≡ b (mod n). This means n | (a − b), so there is an
integer d for which a−b = nd. Multiply both sides of this by c to get ac−bc = nd c.
Consequently, there is an integer e = d c for which ac − bc = ne, so n | (ac − bc)
and consequently ac ≡ bc (mod n).
■
25. If n ∈ N and 2n − 1 is prime, then n is prime.
Proof. Assume n is not prime. Write n = ab for some a, b > 1. Then 2n − 1 =
2ab −1 = ¡2b −1¢¡2ab−b +2ab−2b +2ab−3b +···+2ab−ab¢. Hence 2n −1 is composite. ■
262
Solutions
27.
¡a¢
If a ≡ 0 (mod 4) or a ≡ 1 (mod 4) then 2 is even.
Proof.
¡a¢
We prove this directly. Assume a ≡ 0 (mod 4). Then
.
2 = a(a−1)
2
Since
a = 4k
¡a¢
¡a¢
for some k ∈ N, we have 2 = 4k(4k−1)
2
= 2k(4k − 1). Hence 2 is even.
¡a¢
Now assume a ≡ 1 (mod 4). Then a = 4k + 1 for some k ∈ N. Hence 2 = (4k+1)(4k)
2
=
2k(4k + 1).
¡a¢
Hence, 2 is even. This proves the result.
■
29. If integers a and b are not both zero, then gcd(a, b) = gcd(a − b, b).
Proof. (Direct) Suppose integers a and b are not both zero. Let d = gcd(a, b).
Because d is a divisor of both a and b, we have a = dx and b = d y for some
integers x and y. Then a − b = dx − d y = d(x − y), so it follows that d is also a
common divisor of a − b and b. Therefore it can’t be greater than the greatest
common divisor of a − b and b, which is to say gcd(a, b) = d ≤ gcd(a − b, b).
Now let e = gcd(a − b, b). Then e divides both a − b and b, that is, a − b = ex and
b = e y for integers x and y. Then a = (a − b) + b = ex + e y = e(x + y), so now we see
that e is a divisor of both a and b. Thus it is not more than their greatest
common divisor, that is, gcd(a − b, b) = e ≤ gcd(a, b).
The above two paragraphs have given gcd(a, b) ≤ gcd(a − b, b) and gcd(a − b, b) ≤
gcd(a, b). Thus gcd(a, b) = gcd(a − b, b).
■
31. Suppose the division algorithm applied to a and b yields a = qb + r. Then
gcd(a, b) = gcd(r, b).
Proof. Suppose a = qb + r. Let d = gcd(a, b), so d is a common divisor of a and b;
thus a = dx and b = d y for some integers x and y. Then dx = a = qb + r = qd y + r,
hence dx = qd y + r, and so r = dx − qd y = d(x − q y). Thus d is a divisor of r (and
also of b), so gcd(a, b) = d ≤ gcd(r, b).
On the other hand, let e = gcd(r, b), so r = ex and b = e y for some integers x and
y. Then a = qb + r = qe y + ex = e(q y + x). Hence e is a divisor of a (and of course
also of b) so gcd(r, b) = e ≤ gcd(a, b).
We’ve now shown gcd(a, b) ≤ gcd(r, b) and gcd(r, b) ≤ gcd(a, b), so gcd(r, b) = gcd(a, b).
■
Chapter 6 Exercises
1. Suppose n is an integer. If n is odd, then n2 is odd.
Proof. Suppose for the sake of contradiction that n is odd and n2 is not odd.
Then n2 is even. Now, since n is odd, we have n = 2a + 1 for some integer a.
Thus n2 = (2a + 1)2 = 4a2 + 4a + 1 = 2(2a2 + 2a) + 1. This shows n2 = 2b + 1, where
b is the integer b = 2a2 + 2a. Therefore we have n2 is odd and n2 is even, a
contradiction.
■
263
p
3.
3
Prove that
2 is irrational.
p
Proof.
3
Suppose for the sake of contradiction that
2 is not irrational. Therefore
p
3
it is rational, so there exist integers a and b for which
2 = ab . Let us assume
that this fraction is reduced, so a and b are not both even. Now we have
p
3
3
2 = ¡ a ¢3
b
, which gives 2 = a3
b3 , or 2b3 = a3. From this we see that a3 is even,
from which we deduce that a is even. (For if a were odd, then a3 = (2c + 1)3 =
8c3 + 12c2 + 6c + 1 = 2(4c3 + 6c2 + 3c) + 1 would be odd, not even.) Since a is even,
it follows that a = 2d for some integer d. The equation 2b3 = a3 from above then
becomes 2b3 = (2d)3, or 2b3 = 8d3. Dividing by 2, we get b3 = 4d3, and it follows
that b3 is even. Thus b is even also. (Using the same argument we used when
a3 was even.) At this point we have discovered that both a and b are even,
contradicting the fact (observed above) that the a and b are not both even.
■
Here is an alternative proof.
p
Proof.
3
Suppose for the sake of contradiction that
2 is not irrational. Therefore
p
3
there exist integers a and b for which
2 = ab . Cubing both sides, we get 2 = a3
b3 .
From this, a3 = b3 + b3, which contradicts Fermat’s last theorem.
■
p
5. Prove that
3 is irrational.
p
Proof. Suppose for the sake of contradiction that 3 is not irrational. Therefore
p
it is rational, so there exist integers a and b for which
3 = ab . Let us assume
that this fraction is reduced, so a and b have no common factor. Notice that
p 2
3 = ¡ a ¢2
b
, so 3 = a2
b2 , or 3b2 = a2. This means 3 | a2.
Now we are going to show that if a ∈ Z and 3 | a2, then 3 | a. (This is a proof-
within-a-proof.) We will use contrapositive proof to prove this conditional
statement. Suppose 3 - a. Then there is a remainder of either 1 or 2 when 3 is
divided into a.
Case 1. There is a remainder of 1 when 3 is divided into a. Then a = 3m + 1
for some integer m. Consequently, a2 = 9m2 + 6m + 1 = 3(3m2 + 2m) + 1, and this
means 3 divides into a2 with a remainder of 1. Thus 3 - a2.
Case 2. There is a remainder of 2 when 3 is divided into a. Then a = 3m + 2
for some integer m.
Consequently, a2 = 9m2 + 12m + 4 = 9m2 + 12m + 3 + 1 =
3(3m2 +4m+1)+1, and this means 3 divides into a2 with a remainder of 1. Thus
3 - a2.
In either case we have 3 - a2, so we’ve shown 3 - a implies 3 - a2. Therefore, if
3 | a2, then 3 | a.
Now go back to 3 | a2 in the first paragraph. This combined with the result of
the second paragraph implies 3 | a, so a = 3d for some integer d. Now also in the
first paragraph we had 3b2 = a2, which now becomes 3b2 = (3d)2 or 3b2 = 9d2, so
Book of Proof Page 37