Book of Proof

Home > Other > Book of Proof > Page 37
Book of Proof Page 37

by Richard Hammack


  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

 

‹ Prev