discrete_mathematics_with_applications/chapter_4/exercises.md

Page 194

Exercise Set 4.1

In 1-4 justify your answers by using the definitions of even, odd, prime, and composite numbers.

1. Assume that k is a particular integer.

a. Is -17 an odd integer?

 -17 = 2(-9) + 1 

Let k = -9, so our expression becomes by substitution:

 -17 = 2k + 1 

Since -17 can be represented by the form 2k + 1 where k = -9 and k is an integer, by the definition of an odd number, -17 is an odd integer.

b. Is 0 neither even nor odd?

No, 0 can be represented as 0 = 2(0), and let k = 0, so 0 = 2k, where k is an integer, and by definition of an even number, 0 is even.

c. Is 2k - 1 odd?

Yes, 2k - 1 = 2(k - 1) + 1 where k - 1 is an integer by the difference of integers. Let m = k - 1, so our expression becomes 2k - 1 = 2m + 1, and since m is an integer, we can conclude that 2k - 1 is an odd integer by definition of odd integers.

2. Assume that c is a particular integer.

a. Is -6c an even integer?

Yes -6c = 2(-3c), where -3c is an integer by the product of integers, and since -6c can be expressed as 2 \cdot \text{ some integer}, it is even by the definition of even integers.

b. Is 8c + 5 an odd integer?

Yes, 8c + 5 = 8c + 4 + 1 = 2(4c + 2) + 1 where 4c + 2 is an integer by the sum of products of integers. Since 8c + 5 can be expressed as 2(\text{some integer}) + 1, we can conclude that 8c + 5 is an odd integer by the definition of odd integers.

c. Is (c^2 + 1) - (c^2 - 1) - 2 an even integer?

Yes, if evaluate the statement by laws of algebra, we get:

 (c^2 + 1) - (c^2 - 1) - 2 = c^2 + 1 - c^2 + 1 - 2 = 1 + 1 - 2 = 0 

And as established in 1b, 0 is an even integer, so (c^2 + 1) - (c^2 - 1) - 2 can be expressed in the form of 2 \cdot \text{ some integer}, so by the definition of integers, (c^2 + 1) - (c^2 - 1) - 2 is an even integer.

3. Assume that m and n are particular integers?

a. Is 6m + 8n even?

Yes, 6m + 8n = 2(3m + 4n). 3m + 4n is an integer by the sum of products of integers. Since 6m + 8n can be expressed as 2 \cdot \text{ some integer}, by the definition of even integers, 6m + 8n is even.

b. Is 10mn + 7 odd?

10mn + 7 = 10mn + 6 + 1 = 2(5mn + 3) + 1. 5mn + 3 is an integer by the product and sum of integers. Since 10mn + 7 can be expressed as 2(\text{some integer}) + 1, 10mn + 7 is an odd integer.

c. If m > n > 0, is m^2 - n^2 composite?

Not necessarily. Consider m = 3 and n = 2, then m^2 - n^2 = 9 - 4 = 5, which is a prime number.

4. Assume that r and s are particular integers.

a. Is 4rs even?

Yes, 4rs = 2(2rs), where 2rs is an integer by the product of integers. Since 4rs = 2(\text{ some integer}), by the definition of an even integer, 4rs is an even integer.

b. Is 6r + 4s^2 + 3 odd?

6r + 4s^2 + 3 = 6r + 4s^2 + 2 + 1 = 2(3r + 2s^2 + 1) + 1. 3r + 2s^2 + 1 is an integer by product and sum of integers. Let k = 3r + 2s^2 + 1, and so 6r + 4s^2 + 3 = 2k + 1. By definition of an odd integer, 6r + 4s^2 + 3 is an odd integer.

c. If r and s are both positive, is r^2 + 2rs + s^2 composite?

Since r^2 + 2rs + s^2 = (r + s)^2 = (r + s)(r + s) and r + s \geq 2. And since r + s > 1, the product of (r + s)(r + s) is composite.

Prove the statements in 5-11.

5. There are integers m and n such that m > 1 and n > 1 and \dfrac{1}{m} + \dfrac{1}{n} is an integer.

For example, let m = 2 and n = 2, then \dfrac{1}{2} + \dfrac{1}{2} = 1, and 1 is an integer.

6. There are distinct integers m and n such that \dfrac{1}{m} + \dfrac{1}{n} is an integer.

For example, let m = -2, and n = 2, then \dfrac{1}{-2} + \dfrac{1}{2} = 0, and 0 is an integer.

7. There are real numbers a and b such that

 \sqrt{a + b} = \sqrt{a} + \sqrt{b} 

For example, let a = 0 and b = 9, then \sqrt{0 + 9} = \sqrt{9} = 3 = 0 + 3 = \sqrt{0} + \sqrt{9}.

8. There is an integer n > 5 such that 2^n - 1 is prime.

For example, let n = 7, then 2^7 - 1 = 127, and 127 is prime.

9. There is a real number x such that x > 1 and 2^x > x^{10}.

For example, let x = \dfrac{1}{2}, then $2^{\frac{1}{2}} \approx 1.414213562 > 0.0009765625 = \left(\frac{1}{2}\right)^{10}$

Definition: An integer n is called a perfect square if, and only if, n = k^2 for some integer k.

10. There is a perfect square that can be written as a sum of two other perfect squares.

Let n = 4 and m = 3, and let l = k^2 be the sum of their squares:

 l = k^2 = n^2 + m^2 = (4)^2 + (3)^2 = 16 + 9 = 25 

 l = k^2 = 25 

So l = 25 can be written as n^2 + m^2 where n = 4 and m = 3, and since both n and m are integers, we can say that l is a perfect square by definition of a perfect square and l can be written as the sum of two other perfect squares.

11. There is an integer n such that 2n^2 - 5n + 2 is prime.

For example let n = 3, then 2n^2 - 5n + 2 = 2(3)^2 - 5(3) + 2 = 2(9) - 15 + 2 = 18 - 15 + 2 = 3 + 2 = 5, and 5 is prime.

In 12-13, (a) write a negation for the given statement, and (b) use a counterexample to disprove the given statement. Explain how the counterexample actually shows that the given statement is false.

12. For all real numbers a and b, if a < b the a^2 < b^2.

(a)

Original:

 \forall a \in \mathbb{R} \forall b \in \mathbb{R}((a < b) \to (a^2 < b^2)) 

Negation:

 \exists a \in \mathbb{R} \exists b \in \mathbb{R}((a < b) \wedge (a^2 \geq b^2)) 

There exist real numbers a and b such that a < b and a^2 \geq b^2.

(b)

Counterexample:

Let a = -2 and let b = -1. The hypothesis a < b holds as -2 < -1 is true, but the conclusion of the original statement a^2 < b^2 is false as (-2)^2 = 4 \cancel{<} 1 = (-1)^2.

Since the original statement claims that the implication holds true for all real numbers a and b, a single counterexample is sufficient to show that the statement is false.

13. For every integer n, if n is odd then \dfrac{n - 1}{2} is odd.

(a)

Original:

Let P(n) = n \text{ is odd}

Let Q(m) = m \text{ is odd}

 \forall n \in \mathbb{Z}(P(n) \to Q\left(\frac{n - 1}{2}\right)) 

Negation:

 \exists n \in \mathbb{Z}(P(n) \wedge \neg Q\left(\frac{n - 1}{2}\right)) 

There exists some integer n such that n is odd and \dfrac{n - 1}{2} is not odd.

(b)

Counterexample:

Let n = 1. n is odd as 1 can be expressed as n = 1 = 2(k) + 1, where k = 0. This means that 1 is odd by the definition of an odd integer, and the hypothesis of the original statement is true. The conclusion of the original statement, however, is false, as \dfrac{n - 1}{2} = \dfrac{1 - 1}{2} = \dfrac{0}{2} = 0, and 0 is not odd.

Since the original statement claims that the implication holds true for all integers n, a single counterexample is sufficient to show that the statement is false.

Disprove each of the statements in 14-16 by giving a counterexample. In each case explain how the counterexample actually disproves the statement.

14. For all integers m and n, if 2m + n is odd then m and n are both odd.

Let m = 2 and let n = 1, the hypothesis 2m + n is odd is true as 2(2) + 1 = 5, and 5 is odd, but the conclusion that both m and n are odd is false, as m is even.

15. For every integer p, if p is prime then p^2 - 1 is even.

Let p = 2. The hypothesis holds true as 2 is prime, but the conclusion "p^2 - 1 is even" is false for this p as (2)^2 - 1 = 4 - 1 = 3, and 3 is not even.

16. For every integer n, if n is even then n^2 + 1 is prime.

Let n = 0, the hypothesis "n is even" holds true for this n as 0 is even. The conclusion "n^2 + 1 is prime" fails for this n as 0^2 + 1 = 0 + 1 = 1, and 1 is not prime.

In 17-20, determine whether the property is true for all integers, true for no integers, or true for some integers and false for other integers. Justify your answers.

17. (a + b)^2 = a^2 + b^2

This property is true for some integers and not others.

For example where it is true, consider a = 0 and b = 1, then (0 + 1)^2 = 1^2 = 1 = 0 + 1 = (0)^2 + (1)^2 holds true for at least two integers.

For example where it is false, consider a = 1 and b = 1, then (1 + 1)^2 = 2^2 = 4 \neq 2 = 1 + 2 = (1)^2 + (1)^2. Since this provides a counterexample, this property cannot hold true for all integers.

Therefore, this property holds true for some integers and not others.

18. \dfrac{a}{b} + \dfrac{c}{d} = \dfrac{a + c}{b + d}

This is true for a = c = 0 and $b = d = 1$as:

 \frac{0}{1} + \frac{0}{1} = 0 + 0 = 0 = \frac{0}{2} = \frac{0 + 0}{1 + 1} 

This is false for a = b = c = d = 1, as:

 \frac{1}{1} + \frac{1}{1} = 1 + 1 =  2 \neq 1 = \frac{2}{2} = \frac{1 + 1}{1 + 1} 

Therefore, this property holds true for some integers and not others.

19. -a^n = (-a)^n

This is true for a = -1 and n = 1.

 -(-1)^1 = (-(-1))^1 

 -(-1) = (-(-1)) 

 1 = 1 

This is false for a = -1 and n = 2.

 -(-1)^2 = (-(-1))^2 

 -(1) = (1)^2 

 -1 \neq 1 

Therefore, this property holds true for some integers and not others.

20. The average of any two odd integers is odd.

Let m and n be odd integers. Let m = 2k + 1 and n = 2p + 1 where k and p are any integers.

We are asserting that \dfrac{m + n}{2} is odd. By substitution, we can express this as:

 \frac{m + n}{2} = \frac{(2k + 1) + (2p + 1)}{2} = \frac{2k + 2p + 2}{2} = \frac{2(k + p + 1)}{2} = k + p + 1 

In order to prove that k + p + 1 is odd, we need to be able to express it in the form of 2(\text{some integer}) + 1 by the definition of an odd integer.

An example where this is true is if k = 2 and p = 4, then k + p + 1 = 2 + 4 + 1 = 7, and 7 is an odd integer.

A counterexample where this is false is if k = 3 and p = 4, then k + p + 1 = 3 + 4 + 1 = 8, and 8 is not an odd integer.

Therefore, this property holds true for some integers and not others.

Prove the statement in 21 and 22 by the method of exhaustion.

21. Every positive even integer less than 26 can be expressed as a sum of three or fewer perfect squares. (For instance, 10 = 1^2 + 3^2 and 16 = 4^2.)

Let's first establish all positive even integers less than 26:

 \{2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24\} 

 2 = 1^2 + 1^2 

 4 = 2^2 

 6 = 2^2 + 1^2 + 1^2 

 8 = 2^2 + 2^2 

 10 = 3^2 + 1^2 

 12 = 2^2 + 2^2 + 2^2 

 14 = 3^2 + 2^2 + 1^2 

 16 = 4^2 

 18 = 4^2 + 1^2 + 1^2 

 20 = 4^2 + 2^2 

 22 = 3^2 + 3^2 + 2^2 

 24 = 4^2 + 2^2 + 2^2 

22. For each integer n with 1 \leq n \leq 10, n^2 - n + 11 is a prime number.

Let's establish all possible values for n:

 \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\} 

n = 1:

 (1)^2 - (1) + 11 = 1 - 1 + 11 = 11 \text{ is prime} 

n = 2:

 (2)^2 - (2) + 11 = 4 - 2 + 11 = 13 \text{ is prime} 

n = 3:

 (3)^2 - (3) + 11 = 9 - 3 + 11 = 17 \text{ is prime} 

n = 4:

 (4)^2 - (4) + 11 = 16 - 4 + 11 = 23 \text{ is prime} 

n = 5:

 (5)^2 - (5) + 11 = 25 - 5 + 11 = 31 \text{ is prime} 

n = 6:

 (6)^2 - (6) + 11 = 36 - 6 + 11 = 41 \text{ is prime} 

n = 7:

 (7)^2 - (7) + 11 = 49 - 7 + 11 = 53 \text{ is prime} 

n = 8:

 (8)^2 - (8) + 11 = 64 - 8 + 11 = 67 \text{ is prime} 

n = 9:

 (9)^2 - (9) + 11 = 81 - 9 + 11 = 83 \text{ is prime} 

n = 10:

 (10)^2 - (10) + 11 = 100 - 10 + 11 = 101 \text{ is prime} 

Each of the statements in 23-26 is true. For each, (a) rewrite the statement with the quantification implicit as If _____, then _____, and (b) write the first sentence of a proof (the "starting point") and the last sentence of a proof (the "conclusion to be shown"). (Note that you do not need to understand the statements in order to be able to do these exercises.)

23. For every integer m, if m > 1 then 0 < \dfrac{1}{m} < 1.

(a) If an integer is greater than 1, then its reciprocal is between 0 and 1.

(b)

Starting Point: Suppose m is any integer such that m > 1.

To Show: 0 < \dfrac{1}{m} < 1

24. For every real number x, if x > 1 then x^2 > x.

(a) If a real number is greater than 1, then it's square is greater than itself.

(b)

Starting Point: Suppose x is any real number such that x > 1.

To Show: x^2 > x.

25. For all integers m and n, if mn = 1 then m = n = 1 or m = n = -1.

(a) If the product of any two integers is equal to 1, then both integers either equal 1 or -1.

(b)

Starting Point: Suppose m and n are any integers such that mn = 1.

To Show: m = n = 1 or m = n = -1.

26. For every real number x, if 0 < x < 1 then x^2 < x.

(a) If a real number is between 0 and 1, then its square is less than itself.

(b)

Starting Point: Suppose x is any real number such that 0 < x < 1.

To Show: x^2 < x.

27. Fill in the blanks in the following proof.

Theorem: For every odd integer n, n^2 is odd.

Proof: Suppose n is any ___ (a) ___. By definition of odd, n = 2k + 1 for some integer k. Then

 n^2 = \left(___(b)____\right)^2  \quad \text{ by substitution} 

 \quad = 4k^2 + 4k + 1 \quad \text{ by multiplying out} 

 \quad = 2(2k^2 + 2k) + 1 \quad \text{ by factoring out a 2} 

Now 2k^2 + 2k is an integer because it is a sum of products of integers. Therefore n^2 equals 2 \cdot (\text{an integer}) + 1, and so ___ (c) ___ is odd by definition of odd.

Because we have not assumed anything about n except that it is an odd integer, it follows from the principle of ___ (d) ___ that for every odd integer n, n^2 is odd.

a. odd integer.

b. 2k + 1

c. n^2

d. universal generalization

In each of 28-31:

a. Rewrite the theorem in three different ways:

as \forall _____, if _____ then _____, as \forall _____, _____ (without using the words if or then),

and as If _____, then _____ (without using an explicit universal quantifier).

b. Fill in the blanks in the proof of the theorem.

Theorem: the sum of any two odd integers is even.

Proof: Suppose m and n are any [particular but arbitrarily chosen] odd integers.

[We must show that m + n is even.]

By __ (a) __, m = 2r + 1 and n = 2s + 1 for some integers r and s.

Then

 m + n = (2r + 1) + (2s + 1) \quad \text{k by \_\_ (b) \_\_} 

 \quad = 2r + 2s + 2 

 \quad = 2(r + s + 1) \quad \text{ by algebra} 

Let u = r + s + 1. Then u is an integer because r, s, and 1 are integers and because __ c __.

Hence m + n = 2u, where u is an integer, and so, by __ (d) __, m + n is even [as was to be shown].

a.

Theorem: the sum of any two odd integers is even.

\forall integers m and n, if m and n are odd, then m + n is even.

\forall odd integers m and n, m + n is even.

If any two integers are odd, then their sum is even.

b.

(a) the definition of an odd integer

(b) substitution

(\c) any sum of integers is an integer

(d)$ the definition of an even integer

Theorem: The negative of any integer is even.

Proof: Suppose n is any [particular but arbitrarily chosen] even integer.

[We must show that -n is even.]

By __ (a) __, n = 2k for some integer k.

Then

 -n = -(2k)  \quad \text{ by \_\_ (b) \_\_} 

 \quad = 2(-k) \quad \text{ by algebra} 

Let r = -k. Then r is an integer because (-1) and k are integers and __ c __.

Hence -n = 2r, where r is an integer, and so -n is even by __ (d) __ [as was to be shown].

a.

Theorem: The negative of any integer is even.

\forall integers n, if n is negative, then n is even.

\forall negative integers n, n is even.

If an integer is negative, then it is even.

b.

(a) the definition of an even integer

(b) substitution

c the product of any two integers is an integer

(d) the definition of an even integer

Theorem 4.1.2: The sum of any even integer and any odd integer is odd.

Proof: Suppose m 8s any even integer and n is __ (a) __. By definition of even, m = 2 for some __ (b) __, and by definition of odd, n = 2s + 1 for some integer s. By substitution and algebra,

 m + n = \text{\_\_ (c) \_\_} = 2(r + s) + 1 

Since r and s are both integers, so is their sum r + s. Hence m + n has the form twice some integer plus one, and so __ (d) __ by definition of odd.

a.

Theorem 4.1.2: The sum of any even integer and any odd integer is odd.

\forall integers m and n, if m is an even integer and n is an odd integer, then m + n is odd.

\forall even integers m and odd integers n, m + n is odd.

If m is an even integer and n is any odd integer, then m + n is odd.

b.

(a) any odd integer

(b) integer r

c 2r + (2s + 1)

(d) m + n is odd

Theorem: Whenever n is an odd integer, 5n^2 + 7 is even.

Proof: Suppose n is any [particular but arbitrarily chosen] odd integer.

[We must show that 5n^2 + 7 is even.]

By definition of odd, n = __ (a) __ for some integer k.

Then

 5n^2 + 7 = \text{\_\_ (b) \_\_}  \quad \text{ by substitution} 

 \quad = 5(4k^2 + 4k + 1) + 7 

 \quad = 20k^2 + 20k + 12 

 \quad = 2(10k^2 + 10k + 6) \quad \text{ by algebra} 

Let t = __ c __. Then t is an integer because products and sums of integers are integers.

Hence 5n^2 + 7 = 2t, where t is an integer, and thus __ (d) __ by definition of even [as was to be shown].

a.

Theorem: Whenever n is an odd integer, 5n^2 + 7 is even.

\forall integers n, if n is an odd integer, then 5n^2 + 7 is even.

\forall odd integers n, 5n^2 + 7 is even.

If n is an odd integer, then 5n^2 + 7 is even.

b.

(a) 2k + 1

(b) 5(2k + 1)^2 + 7

c 10k^2 + 10k + 6

(d) 5n^2 + 7 is even

---

Exercise Set 4.2

Page 204

Prove the statements in 1-11. In each case use only the definitions of the terms and the Assumptions listed on page 161, not any previously established properties of odd and even integers. Follow the directions given in this section for writing proofs of universal statements.

1. For every integer n, if n is odd then 3n + 5 is even.

Theorem: Suppose n is any odd integer.

Proof:

Since n is odd, n = 2k + 1 for some integer k.

Then

 3n + 5 = 3(2k + 1) + 5 \quad \text{ by substitution} 

 \quad = 6k + 3 + 5 

 \quad = 6k + 8 

 \quad = 2(3k + 4)  \quad \text{ by algebra} 

Let t = 3k + 4.

Then 3n + 5 = 2(3k + 4) = 2t, where t is an integer because products and sums of integers are integers.

Therefore 3n + 5 is even by the definition of even integers.

Q.E.D.

2. For ever integer m, if m is even then 3m + 5 is odd.

Theorem: Suppose m is any even integer.

Proof:

Since m is even, m = 2k for some integer k.

Then:

 3m + 5 = 3(2k) + 5 \quad \text{ by substitution} 

 \quad = 6k + 5 

 \quad = 6k + 4 + 1 

 \quad = 2(3k + 2) + 1 \quad \text{ by algebra} 

Let t = 3k + 2.

Then 3m + 5 = 2(3k + 2) + 1 = 2t + 1 where t is an integer because the product and sum of integers are integers.

Therefore 3m + 5 is odd by the definition of odd integers.

Q.E.D.

3. For every integer n, 2n - 1 is odd.

Theorem:

Suppose n is any integer.

Proof:

Then:

 2n - 1 = 2n - 2 + 1 \quad \text{ by algebra} 

 \quad = 2(n - 1) + 1 \quad \text{ by factoring} 

Let t = n - 1.

Then 2n - 1 = 2(n - 1) + 1 = 2t + 1 where t is an integer because the difference of integers is an integer.

Therefore 2n - 1 is odd by the definition of an odd integer.

Q.E.D.

4. Theorem 4.2.2: The difference of any even integer minus any odd integer is odd.

Theorem: Suppose m is any even integer and n is any odd integer.

Proof:

Since m is even and n is odd, m = 2k and n = 2s + 1 where k is some integer and s is some integer.

Then

 m - n = 2k - (2s + 1)  \quad \text{ by substitution} 

 \quad = 2k - 2s - 1 

 \quad = 2k - 2s - 2 + 1 

 \quad = 2(k - s - 1) + 1 

Let t = k - s - 1.

Then m - n = 2(k - s - 1) + 1 = 2t + 1 where t is an integer because the difference of integers is an integer.

Therefore m - n is odd by the definition of odd integers.

Q.E.D.

5. If a and b are any odd integers, then a^2 + b^2 is even.

Theorem: Suppose a is any odd integer and b is any odd integer.

Proof:

Since a is an odd integer and b is an odd integer, a = 2k + 1 and b = 2s + 1 where k is some integer and s is some integer.

Then:

 a^2 + b^2 = (2k + 1)^2 + (2s + 1)^2 \quad \text{ by substitution} 

 \quad = (2k + 1)(2k + 1) + (2s + 1)(2s + 1) \quad \text{ by exponentiation} 

 \quad = (4k^2 + 4k + 1) + (4s^2 + 4s + 1) 

 \quad = 4k^2 + 4k + 1 + 4s^2 + 4s + 1 

 \quad = 4k^2 + 4k + 4s^2 + 4s + 2 

 \quad = 2(2k^2 + 2k + 2s^2 + 2s + 1) 

Let t = 2k^2 + 2k + 2s^2 + 2s + 1.

Then a^2 + b^2 = 2(2k^2 + 2k + 2s^2 + 2s + 1) = 2t where t is an integer because the product and sum of integers is an integer.

Therefore a^2 + b^2 is even by the definition of even integers.

Q.E.D.

6. If k is any odd integer and m is any even integer, then k^2 + m^2 is odd.

Theorem:

Suppose k is any odd integer and m is any even integer.

Proof:

Since k is an odd integer and m is an even integer, k = 2a + 1 and m = 2b where a is some integer and b is some integer.

Then:

 k^2 + m^2 = (2a + 1)^2 + (2b)^2 \quad \text{ by substitution} 

 \quad = (2a + 1)(2a + 1) + (2b)(2b) \quad \text{ by exponentiation} 

 \quad = (4a^2 + 4a + 1) + (4b^2) 

 \quad = 4a^2 + 4a + 4b^2 + 1 

 \quad = 2(2a^2 + 2a + 2b^2) + 1 

Let t = 2a^2 + 2a + 2b^2.

Then k^2 + m^2 = 2(2a^2 + 2a + 2b^2) + 1 = 2t + 1 where t is an integer because the product and sum of integers is an integer.

Therefore k^2 + m^2 is odd by the definition of an odd integer.

Q.E.D.

7. The difference between the squares of any two consecutive integers is odd.

Theorem:

Suppose n is any integer.

Proof:

Since n is an integer, n + 1 is a consecutive integer of n.

Then:

 n^2 - (n + 1)^2 = n^2 - (n + 1)(n + 1) \quad \text{ by exponentiation} 

 \quad = n^2 - (n^2 + 2n + 1) 

 \quad = n^2 - n^2 - 2n - 1 \quad \text{ by distribution} 

 \quad = -2n - 1 \quad \text{ by distribution} 

 \quad = -2n - 2 + 1 

 \quad = 2(-n - 1) + 1 

Let t = -n - 1.

Then n^2 - (n + 1)^2 = 2(-n - 1) + 1 = 2t + 1 where t is an integer because the product and difference of integers is an integer.

Therefore n^2 - (n + 1)^2 is odd by the definition of an odd integer.

Q.E.D.

8. For any integers m and n, if m is even and n is odd then 5m + 3n is odd.

Theorem:

Suppose m is any even integer and n is any odd integer.

Proof:

Since m is an even integer and n is an odd integer, m = 2k and n = 2s + 1 where k is some integer and s is some integer.

Then:

 5m + 3n = 5(2k) + 3(2s + 1) \quad \text{ by substitution} 

 \quad = 10k + 6s + 3 

 \quad = 10k + 6s + 2 + 1 

 \quad = 2(5k + 3s + 1) + 1 

Let t = 5k + 3s + 1.

Then 5m + 3n = 2(5k + 3s + 1) + 1 = 2t + 1 where t is an integer because the products and sums of integers is an integer.

Therefore 5m + 3n is odd by the definition of an odd integer.

Q.E.D.

9. If an integer greater than 4 is a perfect square, then the immediately preceding integer is not prime.

Theorem:

Suppose n is any integer where n > 4 and n is a perfect square.

Proof:

Since n is a perfect square and n > 4, then n = k^2 for some integer k where k > 2 or k < -2.

Then:

 n - 1 = k^2 - 1 \quad \text{ by substitution} 

 \quad = (k + 1)(k - 1) \quad \text{ by algebra} 

In order for n - 1 to be prime, either k + 1 or k - 1 must be equal to 1.

If k > 2, then both k + 1 > 1 and k - 1 > 1 are true.

If k < -2, then both k + 1 < 1 and k - 1 < 1 are true.

Therefore neither k + 1 nor k - 1 can ever be equal to 1.

Therefore n - 1 is not prime by the definition of a prime number.

Q.E.D.

10. If n is any even integer, then (-1)^n = 1.

Theorem:

Suppose n is any even integer.

Proof:

Since n is an even integer, then n = 2k where k is some integer.

Then:

 (-1)^n = (-1)^{2k} \quad \text{ by substitution} 

 \quad = (-1)^{2 \cdot k} 

 \quad = ((-1)^2)^k 

 \quad = 1^k 

 \quad = 1 \quad \text{ by the laws of exponents} 

Therefore (-1)^n = 1.

Q.E.D.

11. If n is any odd integer, then (-1)^n = -1.

Theorem:

Suppose n is any odd integer.

Proof:

Since n is an odd integer, then n = 2k + 1 where k is some integer.

Then:

 (-1)^n = (-1)^{2k + 1} \quad \text{ by substitution} 

 (-1)^n = (-1)^{2 \cdot k} \cdot (-1)^1 

 (-1)^n = ((-1)^2)^k \cdot (-1)^1 

 (-1)^n = 1^k \cdot -1 

 (-1)^n = 1 \cdot -1 

 (-1)^n = -1 \quad \text{ by the laws of exponents} 

Therefore (-1)^n = -1.

Q.E.D.

Prove that the statements in 12-14 are false.

12. There exists an integer m \geq 3 such that m^2 - 1 is prime.

Take the negation first:

For all integers m \geq 3, m^2 - 1 is not prime.

Theorem:

There is no integer m \geq 3 such that m^2 - 1 is prime.

Proof:

By algebra, we know that:

 m^2 - 1 = (m + 1)(m - 1) 

We also know that for m^2 - 1 to be prime, either m + 1 or m - 1 must be equal to 1.

Since m \geq 3, we know that both m + 1 \geq 4 and m - 1 \geq 2 are both true. Thus both factors are greater than 1.

Therefore m^2 - 1 is a product of two integers greater than 1, so it is not prime.

Therefore m^2 - 1 is not prime by the definition of prime numbers.

Q.E.D.

13. There exists an integer n such that 6n^2 + 27 is prime.

Take the negation first:

For all integers n, 6n^2 + 27 is not prime.

Theorem:

There is no integer n such that 6n^2 + 27 is prime.

Proof:

By algebra we know that:

 6n^2 + 27 = 3(2n^2 + 9) 

Since n^2 is always positive or 0, by the laws of exponentiation and by algebra, we can conclude that 2n^2 + 9 \geq 9 is true.

Since 3 > 1 and 2n^2 + 9 > 1, we then know that 6n^2 + 27 is a product of two integers greater than 1, so it is not prime.

6n^2 + 27 is not prime by the definition of prime numbers.

Q.E.D.

14. There exists an integer k \geq 4 such that 2k^2 - 5k + 2 is prime.

Take the negation first:

For all integers k \geq 4, 2k^2 - 5k + 2 is not prime.

Theorem:

There is no integer k \geq 4 such that 2k^2 - 5k + 2 is prime.

Proof:

By algebra we know:

 2k^2 - 5k + 2 = (k - 2)(2k - 1) 

Since we know that k \geq 4, we know that k - 2 \geq 2 and 2k - 1 \geq 7.

Since k - 2 > 1 and 2k - 1 > 1, we then know that 2k^2 - 5k + 2 is a product of two integers greater than 1, so it is not prime.

Therefore 2k^2 - 5k + 2 is not prime by definition of prime numbers.

Q.E.D.

Find the mistakes in the "proofs" shown in 15-19.

Theorem: For every integer k, if k > 0 then k^2 + 2k + 1 is composite.

"Proof: For k = 2, k > 0 and k^2 + 2k + 1 = 2^2 + 2 \cdot 2 + 1 = 9. And since 9 = 3 \cdot 3, then 9 is composite. Hence the theorem is true."

Answer: This proof just shows that the theorem is true for a single case, k = 2, in order to prove a universal claim as the theorem presents, the proof must prove the conclusion true for every integer k where k > 0.

Theorem: The difference between any odd integer and any even integer is odd.

"Proof: Suppose n is any odd integer, and m is any even integer. By definition of odd, n = 2k + 1 where k is an integer, and by definition of even, m = 2k where k is an integer. Then

 n - m = (2k + 1) - 2k = 1 

Answer: This proof makes the mistake of using k to represent two different quantities. By setting n = 2k + 1 and m = 2k, the proof implies that n = m + 1, and thus deduces the conclusion for only this situation. This proof falsely then "proves" that the difference between any even and odd integer will always equal 1, but taking most examples of even and odd integers as cases for this would show that this is false. In essence, this proof makes the mistake of assigning the same variable name to represent two different integers, and then by algebra comes to a false conclusion.

Theorem: For every integer k, if k > 0, then k^2 + 2k + 1 is composite.

"Proof: Suppose k is any integer such that k > 0. If k^2 + 2k + 1 is composite, then k^2 + 2k + 1 = rs for some integers r and s such that

 1 < r < k^2 + 2k + 1 

and

 1 < s < k^2 + 2k + 1 

Since

 k^2 + 2k + 1 = rs 

and both r and s are strictly between 1 and k^2 + 2k + 1, then k^2 + 2k + 1 is not prime. Hence k^2 + 2k + 1 is composite as was to be shown."

Answer: This proof makes the mistake of assuming what is to be proved. Instead of proving that k^2 + 2k + 1 is composite, it assumes the definition of composite numbers applies to the expression and then extrapolates logic about r and s that cannot be known because it has not yet been proven that k^2 + 2k +1 is composite. This starts at the line starting with "Since", which cannot be asserted as that is an assertion of the conclusion, not the hypothesis.

Teacher's answer: This incorrect proof assumes what is to be proved. The word since in the third sentence is completely unjustified. The second sentence tells only what happens if k^2 + 2k + 1 is composite. But at that point in the proof, it has not been established that k^2 + 2k + 1 is composite. In fact, that is exactly what is to be proved.

Theorem: The product of any even integer and any odd integer is even.

"Proof: Suppose m is any even integer and n is any odd integer. If m \cdot n is even, then by definition of even there exists an integer r such that m \cdot n = 2r. Also since m is even, there exists an integer p such that m = 2p, and since n is odd there exists an integer q such that n = 2q + 1. Thus

 mn = (2p)(2q + 1) = 2r 

where r is an integer. By definition of even, then, m \cdot n is even, as was to be shown."

Answer: This incorrect proof exhibits confusion between what is known and what is still to be shown. The writer correctly uses the definitions of even and odd integers to express m and n as 2p and 2q + 1, but assumes the conclusion that mn must be an expression of 2r, which is exactly what is to be shown, but has not yet been proven. In essence, they have jumped to the conclusion.

Theorem: The sum of any two even integers equals 4k for some integer k.

"Proof: Suppose m and n are any two even integers. By definition of even, m = 2k for some integer k and n = 2k for some integer k. By substitution,

 m + n = 2k + 2k = 4k 

That is what was to be shown."

Answer: This incorrect proof suffers from multiple problems. One is that it uses the same variable name k to represent two potentially different integers when expressing both m and n as even integers. The writer then incorrectly sums them to 4k and concludes they have proven the conclusion, but the form of 4k does not explicitly show that m + n is even by the definition of even integers.

In 20-38 determine whether the statement is true or false. Justify your answer with a proof or a counterexample, as appropriate. In each case use only the definitions of the terms and the Assumptions listed on page 161, not any previously established properties.

20. The product of any two odd integers is odd.

Theorem:

Suppose n is any odd integer and m is any odd integer.

Proof:

Since n and m are odd integers, n = 2k + 1 and m = 2s + 1 where k is some integer and s is some integer.

Then:

 n \cdot m = (2k + 1)(2s + 1) \quad \text{ by substitution} 

 \quad = 4ks + 2s + 2k + 1 

 \quad = 2(2ks + s + k) + 1  \quad \text{ by algebra} 

Let t = 2ks + s + k.

Then n \cdot m = 2(2ks + s + k) + 1 = 2t + 1 where t is an integer because the products and sums of integers is an integer.

Therefore n \cdot m is odd by the definition of odd integers.

Q.E.D.

21. The negative of any odd integer is odd.

Theorem:

Suppose n is any odd integer.

Proof:

Since n is odd, n = 2k + 1 where k is some integer.

Then:

 -n = -(2k + 1) \quad \text{ by substitution} 

 \quad = -2k - 1 

 \quad = -2k - 2 + 1 

 \quad = 2(-k - 1) + 1 

Let t = -k - 1.

Then -n = 2(-k - 1) + 1 = 2t + 1 where t is an integer because the products and differences of integers is an integer.

Therefore -n is odd by definition of an odd integer.

Q.E.D.

22. For all integers a and b, 4a + 5b + 3 is even.

False. Intuition says if a = b = 0 then 4a + 5b + 3 = 3 which is not even. Let's prove this more formally.

Take the negation:

There exists some integer a and some integer b such that 4a + 5b + 3 is not even.

Theorem: There is some integer a and some integer b such that 4a + 5b + 3 is not even.

Let a = 0 and let b = 0

Then:

 4a + 5b + 3 = 4(0) + 5(0) + 3 \quad \text{ by substitution} 

 \quad = 0 + 0 + 3 

 \quad = 3 

Since 3 is not even, 4a + 5b + 3 is not even for the given a and b.

Therefore there exists integers a and b such that 4a + 5b + 3 is not even and the original given statement is false.

Q.E.D.

23. The product of any even integer and any integer is even.

Theorem:

Suppose n is any even integer and m is any integer.

Proof:

Since n is even, n = 2k for some integer k.

Then:

 n \cdot m = (2k)(m) \quad \text{ by substitution} 

 \quad = 2km 

 \quad = 2(km) 

Let t = km.

Then n \cdot m = 2(km) = 2t where t is an integer because the product of integers is an integer.

Therefore n \cdot m is even by definition of even integers.

Q.E.D.

24. If a sum of two integers is even, then one of the summands is even. (In the expression a + b, a and b are called summands.)

This is false, quickly consider 1 + 3 = 4 where both the summands are odd, but the sum is even.

Take the negation first:

There exists two integers whose sum is even but neither integer is even.

Claim:

There is some integer a and there is some integer b such that a + b is even and neither a nor b is even.

Proof:

Let a = 1 and b = 3.

Then:

 a + b = 4 

 \quad = 2(2) 

Then a + b is even by the definition of even integers.

Then:

 a = 1 

 \quad = 2(0) + 1 

And:

 b = 3 

 \quad = 2(1) + 1 

Then both a and b are odd by the definition of odd integers.

Therefore a + b is even, but a and b are not even for the given a and b, therefore the statement is false.

Q.E.D.

25. The difference of any two even integers is even.

Theorem:

Suppose m is an even integer and n is an even integer.

Proof:

Since m and n are even integers, m = 2k and n = 2s where k is some integer and s is some integer.

Then:

 n - m = (2s) - (2k) \quad \text{ by substitution} 

 \quad = 2s - 2k 

 \quad = 2(s - k) \quad \text{ by algebra} 

Let t = s - k.

Then n -m = 2(s - k) = 2t where t is an integer because the difference of integers is an integer.

Therefore n - m is even by the definition of even integers.

Q.E.D.

26. For all integers a, b, and c, if a, b, and c are consecutive, then a + b + c is even.

This is false. Take the negation for the claim.

Claim:

There exists some integer a, some integer b, and some integer c such that a, b, and c are consecutive and a + b + c is not even.

Proof:

Let a = 2, b = 3, c = 4.

Then:

 a + b + c = 2 + 3 + 4 \quad \text{ by substitution} 

 \quad = 9 

 \quad = 8 + 1 

 \quad = 2(4) + 1 

Therefore for the given a, b, and c, a + b + c is not even, by the definition of an odd number.

Therefore the given a, b, and c are consecutive numbers, but their sum is not even. The statement is false.

Q.E.D.

27. The difference of any two odd integers is even.

Theorem:

Suppose n is any odd integer and m is any odd integer.

Proof:

Since n and m are odd integers, n = 2k + 1 and m = 2s + 1 where k is some integer and s is some integer.

Then:

 n - m = (2k + 1) - (2s + 1) \quad \text{ by substitution} 

 \quad = 2k + 1 - 2s - 1 

 \quad = 2k - 2s 

 \quad = 2(k - s) 

Let t = k - s.

Then n - m = 2(k - s) = 2t where t is an integer because the difference of integers is an integer.

Therefore n - m is even by definition of an even integer.

Q.E.D.

28. For all integers n and m, if n - m is even then n^3 - m^3 is even.

Theorem:

Suppose n is any integer and m is any integer and n - m is even.

Proof:

Since we know that n - m is even, n - m = 2k where k is some integer.

Then:

 n^3 - m^3 = (n - m)(n^2 + nm + m^2) \quad \text{ by factoring} 

 \quad = 2k(n^2 + nm + m^2) \quad \text{ by substitution} 

 \quad = 2[k(n^2 + nm + m^2)] 

Let t = k(n^2 + nm + m^2).

Then n^3 - m^3 = 2t where t is an integer because products and sums of integers is an integer.

Therefore n^3 - m^3 is even by the definition of even integers.

Q.E.D.

29. For every integer n, if n is prime then (-1)^n = -1.

This is false when n = 2. Let's prove our claim.

Claim:

There exists some integer n such that n is prime and (-1)^n \neq -1.

Proof:

Let n = 2.

Then:

 (-1)^n = (-1)^2 \quad \text{ by substitution} 

 \quad = 1 

 1 \neq -1 

Therefore since there is a prime number for n such that (-1)^n \neq -1, the given statement is false.

Q.E.D.

30. For every integer m, if m > 2 then m^2 - 4 is composite.

This is false. If m = 3, then m^2 - 4 = 9 - 4 = 5 which is not composite. Let's prove our claim.

Claim:

There exists some integer m such that m > 2 and m^2 - 4 is not composite.

Proof:

Let m = 3.

Then:

 m^2 - 4 = (3)^2 - 4 \quad \text{ by substitution} 

 \quad = 9 - 4 

 \quad = 5 

 \quad = (1)(5) 

Since m^2 - 4 cannot be written as the product of 2 factors where both factors are greater than 1, m^2 - 4 is not composite.

Therefore since there is some integer m such that m > 2 and m^2 - 4 is not composite, this statement is false.

Q.E.D.

31. For every integer n, n^2 - n + 11 is a prime number.

This is false for when n = 11, let's formalize our claim.

Claim:

There exists some integer n such that n^2 - n + 11 is not a prime number.

Proof:

Let n = 11.

Then:

 n^2 - n + 11 = (11)^2 - (11) + 11 \quad \text{ by substitution} 

 \quad = 121 - 11 + 11 

 \quad = 121 

 \quad = (11)(11) 

Therefore n^2 - n + 11 is not a prime number since it is divisible by a number other than 1 and itself for this given n.

Thus there exists some integer n such that n^2 - n + 11 is not a prime number, and therefore the given statement is false.

Q.E.D.

32. For every integer n, 4(n^2 + n + 1) - 3n^2 is a perfect square.

Theorem:

Suppose n is any integer.

Proof:

Then:

 4(n^2 + n + 1) - 3n^2 = 4n^2 + 4n + 4 - 3n^2 \quad \text{ by distribution} 

 \quad = n^2 + 4n + 4 

 \quad = (n + 2)(n + 2) 

 \quad = (n + 2)^2 

Let t = n + 2.

Then 4(n^2 + n + 1) - 3n^2 = t^2 where t is an integer because the sum of integers is an integer.

Therefore 4(n^2 + n + 1) - 3n^2 is a perfect square by the definition of perfect squares.

Q.E.D.

33. Every positive integer can be expressed as a sum of three or fewer perfect squares.

This is false.

Claim:

There exists some positive integer x such that x cannot be expressed as the sum of three or fewer perfect squares.

Proof:

Let x = 7. We check all sums of three nonnegative perfect squares a^2 + b^2 + c^2, where a, b, c \in \{0, 1, 2\} because 3^2 = 9 > 7.

Possible squares: 0^2 = 0, 1^2 = 1, 2^2 = 4.

Now we check all sums

1. Using only 0 and 1:

• 0 + 0 + 1 = 1, 0 + 1 + 1 = 2, 1 + 1 + 1 = 3

All of these are too small and do not add up to 7.

2. Using a 4 (2^2) with 0 and 1:

• 4 + 0 + 0 = 4, 4 + 0 + 1 = 5, 4 + 1 + 1 = 6, 4 + 4 + 0 = 8

All of these do not equal 7.

No combination sums to 7.

Therefore, since all possible combinations from the given set of numbers that could potentially sum to 7 when each individual number is squared have been exhausted, it can be concluded that x = 7 cannot be expressed as the sum of three or fewer perfect squares.

Therefore there exists at least one integer x such that x cannot be expressed as a sum of three or fewer perfect squares, and this statement is false.

Q.E.D.

34. (Two integers are consecutive if, and only if, one is one more than the other.) Any product of four consecutive integers is one less than a perfect square.

Theorem:

Suppose n is any integer.

Proof:

Then:

 (n)(n + 1)(n + 2)(n + 3) = (n(n + 3))(n + 1)(n + 2) 

 \quad = (n^2 + 3n)(n^2 + 3n + 2)

 \quad = (n^2 + 3n)((n^2 + 3n) + 2)

Let x = n^2 + 3n.

Then:

 \quad = (x)((x) + 2) 

 \quad = x^2 + 2x 

 \quad = x^2 + 2x + 1 - 1 

 \quad = (x^2 + 2x + 1) - 1 

 \quad = (x + 1)(x + 1) - 1 

 \quad = (x + 1)^2 - 1 

Then remove the substitution:

 \quad = ((n^2 + 3n) + 1)^2 - 1 

 \quad = (n^2 + 3n + 1)^2 - 1 

Since n^2 + 3n + 1 is an integer because the products and sum of integers is an integer, this means that (n^2 + 3n + 1)^2 is a perfect square and (n^2 + 3n + 1)^2 - 1 is one less than a perfect square.

Therefore the product of any four consecutive integers is one less than a perfect square.

Q.E.D.

35. If m and n are any positive integers and mn is a perfect square, then m and n are perfect squares.

This is false.

Claim:

There is a positive integer m and there is a positive integer n such that mn is a perfect square and m and n are not perfect squares.

Proof:

Let m = 2 and n = 8.

Then:

 mn = (2)(8) \quad \text{ by substitution} 

 \quad = 16 

 \quad = 4^2 

Then mn is a perfect square, but m and n are not perfect squares.

Therefore there exists some m and there exists some n such that mn is a perfect square and m and n are not perfect squares, proving the statement false.

Q.E.D.

36. The difference of the squares of any two consecutive integers is odd.

Theorem:

Suppose n is any integer.

Proof:

Then:

 (n + 1)^2 - n^2 = (n + 1)(n + 1) - n^2 \quad \text{ by substitution} 

 \quad = n^2 + 2n + 1 - n^2 

 \quad = 2n + 1 

Therefore (n + 1)^2 - n^2 is odd by the definition of an odd integer.

Q.E.D.

37. For all nonnegative real numbers a and b, \sqrt{ab} = \sqrt{a}\sqrt{b}. (Note that if x is a nonnegative real number, then there is a unique nonnegative real number y, denoted \sqrt{x}, such that y^2 = x.)

Theorem:

Suppose a is any nonnegative real number and b is any nonnegative real number.

Proof:

Since a \geq 0 and b \geq 0, we know that \sqrt{a} and \sqrt{b} are defined nonnegative real numbers such that:

 (\sqrt{a})^2 = a 

and

 (\sqrt{b})^2 = b 

Then:

 (\sqrt{a}\sqrt{b})^2 = (\sqrt{a})^2(\sqrt{b})^2 = ab \quad \text{ by the product of powers property} 

We then know that \sqrt{a}\sqrt{b} \geq 0 because both factors are nonnegative.

So \sqrt{a}\sqrt{b} is a nonnegative real number whose square is ab.

Therefore \sqrt{ab} = \sqrt{a}\sqrt{b} by the definition of square root (uniqueness of the nonnegative number whose square is ab).

Q.E.D.

38. For all nonnegative real numbers a and b,

 \sqrt{a + b} = \sqrt{a} + \sqrt{b} 

This is false.

Claim:

There is some nonnegative real number a and some nonnegative real number b such that \sqrt{a + b} \neq \sqrt{a} + \sqrt{b}.

Proof:

Let a = 9 and b = 16.

Then:

 \sqrt{a + b} = \sqrt{9 + 16} \quad \text{ by substitution} 

 \quad = \sqrt{25} 

 \quad = 5 

Then:

 5 \stackrel{?}{=} \sqrt{a} + \sqrt{b} 

 5 \stackrel{?}{=} \sqrt{9} + \sqrt{16} \quad \text{ by substitution} 

 5 \stackrel{?}{=} 3 + 4 

 5 \neq 7 

Therefore for the given a and b, we have shown that \sqrt{a + b} \neq \sqrt{a} + \sqrt{b}, thus proving the statement false.

Q.E.D.

39. Suppose that integers m and n are perfect squares. Then m + n + 2\sqrt{mn} is also a perfect square. Why?

Theorem:

Suppose m is any perfect square and n is any perfect square.

Proof:

Since m and n are perfect squares, m = k^2 and n = s^2 for some integer k and some integer s.

Then:

 m + n + 2\sqrt{mn} = (k^2) + (s^2) + 2\sqrt{(k^2)(s^2)} \quad \text{ by substitution} 

 \quad = k^2 + s^2 + 2\sqrt{k^2}\sqrt{s^2} \quad \text{ by the product of powers property} 

 \quad = k^2 + s^2 + 2ks 

 \quad = k^2 + 2ks + s^2 \quad \text{ by the commutative property} 

 \quad = (k + s)(k + s) 

 \quad = (k + s)^2 

Therefore m + n + 2\sqrt{mn} is a perfect square by the definition of a perfect square.

Q.E.D.

40. If p is a prime number, must 2^p - 1 also be prime? Prove or give a counterexample.

False.

Claim:

There is some prime number p such that 2^p - 1 is not prime.

Let p = 11.

Then:

 2^p - 1 = 2^{11} - 1 \quad \text{ by substitution} 

 \quad = 2048 - 1 

 \quad = 2047 

 \quad = (23)(89) 

Thus there is a case where p is a prime number and 2^p - 1 is not prime, and therefore the given statement is false.

Q.E.D.

41. If n is a nonnegative integer, must 2^{2n} + 1 be prime? Prove or give a counterexample.

False.

Claim:

There exists a nonnegative integer n such that 2^{2n} + 1 is not prime.

Proof:

Let n = 5.

Then:

 2^{2n} + 1 = 2^{2 \cdot 5} + 1 \quad \text{ by substitution} 

 \quad = 2^{10} + 1 

 \quad = 1024 + 1 

 \quad = 1025 

 \quad = (25)(41) 

Thus there exists an nonnegative integer n such that 2^{2n} + 1 is not prime, and therefore the given statement is false.

Q.E.D.

---

Exercise Set 4.3

Page 210

The numbers in 1-7 are all rational. Write each number as a ratio of two integers.

1. -\dfrac{35}{6}

 -\frac{35}{6} = -\frac{35}{6} 

2. 4.6037

 4.6037 = \frac{46037}{10000} 

3. \dfrac{4}{5} + \dfrac{2}{9}

 \frac{4}{5} + \frac{2}{9} = \frac{9(4) + 5(2)}{45} = \frac{46}{45} 

4. 0.37373737\dots

Let x = 0.37373737\dots, then 100x = 37.373737\dots, so 100x - x = 99x = 37. Therefore:

 x = 0.37373737\dots = \frac{37}{99} 

5. 0.56565656\dots

Let x = 0.56565656\dots, then 100x = 56.565656\dots, so 100x - x = 99x = 56. Therefore:

 x = 0.56565656\dots = \frac{56}{99} 

6. 320.5492492492\dots

 x = 320.5492492492\dots 

 10000x = 3205492.492492492\dots 

 10x = 3205.492492492\dots 

 10000x - 10x = 9990x = 3202287 

 x = \frac{3202287}{9990} 

7. 52.4672167216721\dots

 x = 52.4672167216721\dots 

 100000x = 5246721.672167216721\dots 

 10x = 524.672167216721\dots

 100000x - 10x = 99990x  = 5246197 

 x = 52.4672167216721\dots = \frac{5246197}{99990} 

8. The zero product property, says that if a product of two real numbers is 0, then one of the numbers must be 0.

a. Write this property formally using quantifiers and variables.

Let P(x) be "x = 0."

Let Q(y) be "y = 0."

Let R(x, y) be "(x)(y) = 0."

 \forall x \in \mathbb{R} \forall y \in \mathbb{R} (R(x, y) \to (P(x) \vee Q(y))) 

b. Write the contrapositive of your answer to part (a).

 \forall x \in \mathbb{R} \forall y \in \mathbb{R} ((\neg P(x) \wedge \neg Q(y)) \to \neg R(x, y)) 

c. Write an informal version (without quantifier symbols or variables) for your part to part (b).

If any two real numbers do not equal zero, then their product does not equal zero.

9. Assume that a and b are both integers and that a \neq 0 and b \neq 0. Explain why \dfrac{(b - a)}{(ab^2)} must be a rational number.

A rational number is a ratio of integers with a nonzero denominator. The given fraction

 \frac{(b - q)}{(ab^2)} 

is rational, the numerator is an integer as the difference of integers are integers, and the denominator is an integer because the product of integers are integers, also the assumption states that both a and b are not 0, so the denominator cannot be 0 by the zero product property. Hence the given fraction is a rational number.

10. Assume that m and n are both integers and that n \neq 0. Explain why \dfrac{(5m - 12n)}{(4n)} must be a rational number.

Given that m and n are both integers, in the given fraction

 \frac{(5m -12n)}{4n} 

The numerator 5m - 12n is an integer because the difference of integers are integers. The denominator 4n is an integer because the product of integers are integers. Also, the since n \neq 0, 4n \neq 0 by the zero product property. Hence the given fraction is a rational number.

11. Prove that every integer is a rational number.

Theorem:

Suppose x is any integer.

Proof:

Then:

 x = x \cdot 1  

 \dfrac{x}{1} = x 

Then x is an integer and 1 is an integer where 1 \neq 0. Hence x can be expressed as a quotient of integers with a nonzero denominator and therefore x is a rational number by definition of a rational number.

Q.E.D.

12. Let S be the statement "The square of any rational number is rational." A formal version of S is "For every rational number r, r^2 is rational." Fill in the blanks in the proof for S.

Proof:

Suppose that r is __ (a) __. By definition of rational, r = \dfrac{a}{b} for some __ (b) __ with b \neq 0. By substitution,

 r^2 = \text{\_\_ (c) \_\_} = \frac{a^2}{b^2} 

Since a and b are both integers, so are the products a^2 and __ (d) __. Also b^2 \neq 0 by the __ (e) __. Hence r^2 is a ratio of two integers with a non-zero denominator,n and so __ (f) __ by definition of rational.

a. a rational number

b. integers a and b

c. \left(\frac{a}{b}\right)^2

d. b^2

e. zero product property

f. r^2 is a rational number

13. Consider the following statement: The negative of any rational number is rational.

a. Write the statement formally using a quantifier and a variable.

 \forall q \in \mathbb{Q} (-q \in \mathbb{Q}) 

Alternatively:

 \forall q ((q \in \mathbb{Q}) \in (-q \in \mathbb{Q})) 

b. Determine whether the statement is true or false and justify your answer.

Theorem:

Suppose q is any rational number.

Proof:

Since q is a rational number, q can be expressed as \dfrac{a}{b} where a and b are integers and b \neq 0.

Then:

 -q = -\left(\frac{a}{b}\right) \quad \text{ by substitution} 

 -q = \frac{-a}{b} 

Then the numerator -a is an integer because the product of integers are integers. The denominator b is an integer and b \neq 0 by assumption of q as a rational number. Hence -q can be expressed as the ratio of two integers with a nonzero denominator, and therefore -q is a rational number by definition of rational numbers.

Q.E.D.

14. Consider the statement: The cube of any rational number is a rational number.

a. Write the statement formally using a quantifier and a variable.

 \forall q ((q \in \mathbb{Q}) \to (q^3 \in \mathbb{Q})) 

b. Determine whether the statement is true or false and justify your answer.

Theorem:

Suppose q is any rational number.

Proof:

Since q is a rational number, q = \dfrac{a}{b} where a and b are integers and b \neq 0.

Then:

 q^3 = \left(\frac{a}{b}\right)^3 \quad \text{ by substitution} 

 q^3 = \frac{a^3}{b^3} \quad \text{ by power of a quotient} 

Then the numerator a^3 is an integer because the products of integers are integers. Also the denominator b^3 is an integer because the product of integers are integers and b^3 \neq 0 by the zero product property.

Thus q^3 can be expressed as a ratio of two integers with a nonzero denominator and therefore q^3 is a rational number by definition of a rational number.

Q.E.D.

Determine which of the statements in 15-19 are true and which are false. Prove each true statement directly from the definitions, and give a counterexample for each false statement. For a statement that is false, determine whether a small change would make it true. If so, make the change and prove the new statement. Follow the directions for writing proofs on page 173.

15. The product of any two rational numbers is a rational number.

Theorem:

Suppose q and r are rational numbers.

Proof:

Since q and r are rational numbers, then q = \dfrac{a}{b} and r = \dfrac{c}{d} where a, b, c, and d are some integers and b \neq 0 and d \neq 0.

Then:

 qr = \left(\frac{a}{b}\right)\left(\frac{c}{d}\right) \quad \text{ by substitution} 

 qr = \frac{ac}{bd} 

Then the numerator ac is an integer because the product of integers are integers. The denominator bd is an integer because the product of integers are integers, and bd \neq 0 by the of the zero product property.

Thus qr can be expressed as a ratio of two integers with a nonzero denominator and therefore qr is a rational number by the definition of a rational number.

Q.E.D.

16. The quotient of any two rational numbers is a rational number.

This is false.

Claim:

There exists some rational number q and some rational number r such that \dfrac{q}{r} is not a rational number.

Proof:

Let q = \dfrac{1}{2} and r = \dfrac{0}{1}.

Then:

 \frac{q}{r} = \frac{\dfrac{1}{2}}{\dfrac{0}{1}} \quad \text{ by substitution} 

 \quad = \frac{1}{2 \cdot 0} 

 \quad = \text{ undefined} 

So the numerator of the given \dfrac{q}{r} is 1 which is an integer, but the denominator is 0, which means \dfrac{q}{r} is not any number, and therefore not a rational number.

Thus there exists two rational numbers whose quotients are not a rational number, therefore the statement is false.

Q.E.D.

A small change that would make this true were if the statement were reworded as:

For any two rational numbers, the quotient of those two numbers is a rational number as long as the rational number in the divisor doesn't equal 0.

17. The difference of any two rational numbers is a rational number.

Theorem:

Suppose that q and r are any rational numbers.

Proof:

Since q and r are rational numbers, q = \dfrac{a}{b} and r = \dfrac{c}{d} where a, b, c, and d are some integers and b \neq 0 and d \neq 0.

Then:

 q - r = \frac{a}{b} - \frac{c}{d} \text{ by substitution} 

 \quad = \frac{ad - cb}{bd} 

Then the numerator ad - cb is an integer because the difference and products of integers are integers. The denominator bd is an nonzero integer because the products of integers are integers and because of the zero product property.

Thus q - r can be expressed as a ratio of two integers with a nonzero denominator, and therefore q - r is a rational number by the definition of a rational number.

Q.E.D.

18. If r and s are any two rational numbers, then \dfrac{r + s}{2} is rational.

Theorem:

Suppose r and s are any two rational numbers.

Proof:

Since r and s are rational numbers, then r = \dfrac{a}{b} and s = \dfrac{c}{d} where a, b, c, and d are integers and b \neq 0 and d \neq 0.

Then:

By substitution:

 \frac{r + s}{2} = \frac{\dfrac{a}{b} + \dfrac{c}{d}}{2} 

 \quad = \frac{1}{2}\left(\frac{a}{b} + \frac{c}{d}\right) 

 \quad = \frac{a}{2b} + \frac{c}{2d} 

 \quad = \frac{ad + bc}{2bd} 

Then the numerator ad + bc is an integer because the products and sums of integers are integers. The denominator 2bd is a nonzero integer because the products of integers are integers and because of the zero product property.

Thus \dfrac{r + s}{2} can be expressed as the ratio of two integers with a nonzero denominator, and therefore \dfrac{r + s}{2} is a rational number by the definition of a rational number.

Q.E.D.

19. For all real numbers a and b, if a < b then a < \dfrac{a + b}{2} < b.

    (You may use the properties of inequalities in T17-T27 of Appendix A.)

Theorem:

Suppose a and b are any real numbers and that a < b.

Proof:

Then:

By T19:

 a + a < a + b 

 2a < a + b 

By T20:

 a < \frac{a + b}{2} 

And:

By T19:

 a + b < b + b 

 a + b < 2b 

By T20:

 \frac{a + b}{2} < b 

Therefore a < \dfrac{a + b}{2} < b.

Q.E.D.

20. Use the results of exercises 18 and 19 to prove that given any two rational numbers r and s with r < s, there is another rational number between r and s. An important consequence is that there are infinitely many rational numbers in between any two distinct rational numbers. See Section 7.4.

Theorem:

Suppose r is any rational number and s is any rational number where r < s.

Proof:

By 18, we know that \dfrac{r + s}{2} is a rational number.

By 19, we know that if r < s, then r < \dfrac{r + s}{2} < s.

Therefore there exists some rational number \dfrac{r + s}{2} that is between r and s, [as was to be shown].

Q.E.D.

Use the properties of even and odd integers that are listed in Example 4.3.3 to do exercises 21-23. Indicate which properties you use to justify your reasoning.

21. True or false? If m is any even integer and n is any odd integer, then m^2 + 3n is odd. Explain.

Theorem:

Suppose m is any even integer and n is any odd integer.

Proof:

By 3, the product of any two odd integers is odd, then:

 3n \text{ is odd} 

Since m is even, m = 2k for some integer k.

Then:

By substitution:

 m^2 = (2k)^2 

 \quad = 4k^2 

 \quad = 2(2k^2) 

Then m^2 is even by the definition of an even integer.

 m^2 \text{ is even} 

By 5, the sum of any odd integer and any even integer is odd.

Thus m^2 + 3n is odd, therefore the statement is true.

Q.E.D.

22. True or false? If a is any odd integer, then a^2 + a is even. Explain.

Theorem:

Suppose a is any odd integer.

Proof:

Then:

 a^2 = a \cdot a 

By 3, the product of any two odd integers is odd, then:

 a^2 \text{ is odd} 

By 2, the sum and difference of any two odd integers are even, then:

 a^2 + a \text{ is even} 

Therefore the statement is true.

Q.E.D.

23. True or false? If k is any even integer and m is any odd integer, then (k + 2)^2 - (m - 1)^2 is even. Explain.

Theorem:

Suppose k is any even integer and m is any odd integer.

Proof:

By 1, the sum of any two even integers is even, then:

 k + 2 \text{ is even} 

By 1, the product of any two even integers is even, then:

 (k + 2)^2 = (k + 2)(k + 2) 

 (k + 2)^2 \text{ is even} 

By 2 the difference of any two odd integers is even, then:

 m - 1 \text{ is even} 

By 1 the product of any two even integers is even, then:

 (m - 1)^2 = (m - 1)(m - 1) 

 (m - 1)^2 \text{ is even} 

By 1 the difference of any two even integers is even, then:

 (k + 2)^2 - (m - 1)^2 \text{ is even} 

Therefore the statement is true.

Q.E.D.

Derive the statements in 24-26 as corollaries of Theorems 4.3.1, 4.3.2, and the results of exercises 12, 13, 14, 15, and 17.

24. For any rational numbers r and s, 2r + 3s is rational.

Theorem:

By 15, the product of any two rational numbers is a rational number, then:

 2r \text{ is rational} 

and

 3s \text{ is rational} 

By Theorem 4.3.2, the sum of any two rational numbers is rational, then:

 2r + 3s \text{ is rational} 

Therefore the statement is true.

Q.E.D.

Proof:

25. If r is any rational number, then 3r^2 - 2r + 4 is rational.

By 15, the product of any two rational numbers is a rational number, then:

 r^2 = r \cdot r 

 r^2 \text{ is rational} 

 3r^2 = 3 \cdot r^2 

 3r^2 \text{ is rational} 

and

 2r = 2 \cdot r 

 2r \text{ is rational} 

By 17, the difference of any two rational numbers is a rational number, then:

 3r^2 - 2r \text{ is rational} 

By Theorem 4.3.2, the sum of any two rational numbers is rational, then:

 (3r^2 - 2r) + 4 \text{ is rational} 

Therefore the statement is true.

Q.E.D.

26. For any rational number s, 5s^3 + 8s^2 - 7 is rational.

Theorem:

Suppose s is any rational number.

Proof:

By 15, the product of any two rational numbers is a rational number, then:

 s^2 = s \cdot s 

 s^2 \text{ is rational} 

 s^3 = s^2 \cdot s 

 s^3 \text{ is rational} 

 5s^3 = 5 \cdot s^3 

 5s^3 \text{ is rational} 

and

 8s^2 = 8 \cdot s^2 

 8s^2 \text{ is rational} 

By 17, the difference of any two rational numbers is a rational number, then:

 8s^2 - 7 \text{ is rational} 

By Theorem 4.3.2, the sum of any two rational numbers is rational, then:

 5s^3 + (8s^2 - 7) \text{ is rational} 

Therefore the statement is true.

Q.E.D.

27. It is a fact that if n is any nonnegative integer, then

 1 + \frac{1}{2} + \frac{1}{2^2} + \frac{1}{2^3} + \dots + \frac{1}{2^n} = \frac{1 - \left(\dfrac{1}{2^{n + 1}}\right)}{1 - \left(\dfrac{1}{2}\right)}  

(A more general form of this statement is proved in Section 5.2.) Is the right-hand side of this equation rational? If so, express it as a ratio of two integers.

Theorem:

Suppose n is any nonnegative integer.

Proof:

Consider:

 \frac{1 - \left(\dfrac{1}{2^{n + 1}}\right)}{1 - \left(\dfrac{1}{2}\right)} 

The denominator can be simpilifed as:

 1 - \frac{1}{2} = \frac{1}{2}  

Then:

 \frac{1 - \left(\dfrac{1}{2^{n + 1}}\right)}{\frac{1}{2}} 

 \quad = 2\left(1 - \frac{1}{2^{n + 1}}\right)

 \quad = 2 - \frac{2}{2^{n + 1}} 

 \quad = 2 - \frac{1}{2^n} 

 \quad = \frac{2 \cdot 2^n - 1}{2^n}

 \quad = \frac{2^{n + 1} - 1}{2^n}

Since n is a nonnegative integer, the numerator 2^{n + 1} - 1 is an integer because the products and differences of integers are integers. And the denominator 2^n is a positive integer because of the products of integers and because n is a nonnegative integer.

Therefore right-hand side of the given equation is a rational number by the definition of rational numbers.

Q.E.D.

28. Suppose a, b, c, and d are integers and a \neq c. Suppose also that x is a real number that satisfies the equation

 \frac{ax + b}{cx + d} = 1 

Must x be rational? If so, express x as a ratio of two integers.

Theorem:

Suppose a, b, c, and d are any integers and suppose x is a real number that satisfies the equation:

 \frac{ax + b}{cx + d} = 1 

Proof:*

Consider:

 \frac{ax + b}{cx + d} = 1 

 ax + b = cx + d 

 ax - cx = d - b 

 x(a - c) = d - b 

 x = \frac{d - b}{a - c} 

Then the numerator d - b is an integer because the difference of integers are integers. The denominator a - c must be a nonzero integer because the difference of integers are integers and because a \neq c.

Therefore x must be a rational number by the definition of rational numbers.

Q.E.D.

29. Suppose a, b, and c are integers and x, y, and z are nonzero real numbers that satisfy the following equations:

 \frac{xy}{x + y} = a \quad \text{ and } \quad \frac{xz}{x + z} = b \quad \text{ and } \quad \frac{yz}{y + z} = c 

Is x rational? If so, express it as ratio of two integers.

Omitted.

30. Prove that if one solution for a quadratic equation of the form x^2 + bx + c = 0 is rational (where b and c are rational), then the other solution is also rational. (Use the fact that if the solutions of the equation are r and s, then x^2 + bx + c = (x - r)(x - s).)

Theorem:

Suppose there is any rational number r that is a solution to a quadratic equation of the form:

 x^2 + bx + c = 0 

Where b and c are rational.

And suppose s is the other solution to the given equation.

Proof:

Given that both r and s are solutions to the given equation, then:

 x^2 + bx + c = (x - r)(x - s) = x^2 - rx - sx + rs 

This means that:

 bx = (-r - s)x 

 b = -1(r + s) 

And:

 c = rs 

Let's analyze b and isolate s.

 b = -1(r + s) 

 -b = r + s 

 -b - r = s 

Since both b and r are rational numbers, then b = \dfrac{g}{h} and r = \dfrac{i}{j} where g, h, i, and j are some integers and h \neq 0 and j \neq 0.

Then:

 s = -b - r = -\left(\frac{g}{h}\right) - \left(\frac{i}{j}\right) \text{ by substitution} 

 \quad = \frac{-1(gj + hi)}{hj} 

The numerator -1(gj + hi) is an integer because the sum and products of integers are integers. The denominator is a nonzero integer because the products of integers are integers and because of the zero product property.

Therefore s can be expressed as a ratio of two integers where the denominator is nonzero. Thus s is a rational number by the definition of rational numbers, therefore the other solution is rational.

Q.E.D.

31. Prove that if a real number c satisfies a polynomial equation of the form

 r_3x^3 + r_2x^2 + r_1x + r_0 = 0 

where r_0, r_1, r_2, and r_3 are rational numbers, then c satisfies an equation of the form

 n_3x^3 + n_2x^2 + n_1x + n_0 = 0 

where n_0, n_1, n_2, and n_3 are integers.

Definition: A number c is called a root of a polynomial p(x) if, and only if, p(c) = 0.

Theorem:

Suppose c is any real number that satisfies a polynomial equation of the form

 r_3x^3 + r_2x^2 + r_1x + r_0 = 0 

where r_0, r_1, r_2, and r_3 are rational numbers.

Proof:

Since c is a real number that satisfies the given equation, then:

 r_3c^3 + r_2c^2 + r_1c + r_0 = 0 

Since r_3, r_2, r_1, and r_0 are rational numbers, then r_3 = \dfrac{a_3}{b_3}, r_2 = \dfrac{a_2}{b_2}, r_1 = \dfrac{a_1}{b_1}, and r_0 = \dfrac{a_0}{b_0} where a_3, a_2, a_1, a_0 are some integers and b_3, b_2, b_1, b_0 are some nonzero integers.

Then, by substitution:

 r_3c^3 + r_2c^2 + r_1c + r_0 = \left(\frac{a_3}{b_3}\right)c^3 + \left(\frac{a_2}{b_2}\right)c^2 + \left(\frac{a_1}{b_1}\right)c + \frac{a_0}{b_0} = 0 

 \quad = \frac{a_3b_2b_1b_0c^3 + a_2b_3b_1b_0c^2 + a_1b_3b_2b_0c + a_0b_3b_2b_1}{b_3b_2b_1b_0} = 0 

 \quad = a_3b_2b_1b_0c^3 + a_2b_3b_1b_0c^2 + a_1b_3b_2b_0c + a_0b_3b_2b_1 = 0 

Let n_3 = a_3b_2b_1b_0, and n_2 = a_2b_3b_1b_0, and n_1 = a_1b_3b_2b_0, and n_0 = a_0b_3b_2b_1.

Then n_3, n_2, n_1, and n_0 are integers because of the product of integers.

Thus we can write the given equation as:

 n_3c^3 + n_2c^2 + n_1c + n_0 = 0 

Where c is a real number that satisfies the equation:

 n_3x^3 + n_2x^2 + n_1x + n_0 = 0 

Q.E.D.

32. Prove that for every real number c, if c is a root of a polynomial with rational coefficients, then c is a root of a polynomial with integer coefficients.

Theorem:

Suppose c is a root of a polynomial with rational coefficients.

Proof:

Then

 r_nx^n + r_{n - 1}x^{n - 1} + \dots + r_1x + r_0 = 0 

where each r_i is rational.

Then each r_i can be written as a ratio of integers with nonzero denominators. Let D be a common multiple of all denominators of the r_i. Multiplying the equation by D gives

 s_nx^n + s_{n - 1}x^{n - 1} + \dots + s_1x + s_0 = 0 

where each s_i is an integer.

Thus c is a root of a polynomial with integer coefficients.

Q.E.D.

Use the properties of even and odd integers that are listed in Example 4.3.3 to do exercises 33 and 34.

33. When expressions of the form (x - r)(x - s) are multiplied out, a quadratic polynomial is obtained. For instance, (x - 2)(x - (-7)) = (x - 2)(x + 7) = x^2 + 5x - 14.

a. What can be said about the coefficients of the polynomial obtained by multiplying out (x - r)(x - s) when both r and s are odd integers? When both r and s are even integers? When one of r and s is even and the other odd?

Case when both r and s are odd integers:

Theorem:

Suppose r and s are odd integers.

Conclusion:

Let x be some real number.

Then:

 (x - r)(x - s) = x^2 - rx - sx - rs = x^2 + (-1)(r + s)x + (-1)rs 

We know the coefficient of x^2 is 1.

By 2, we know the sum of any two odd integers are even, then:

We know the coefficient of -1(r + s) is even.

By 3, we know the product of any two odd integers is odd, then:

We know the coefficient of rs is odd.

Case when both r and s are even integers:

Theorem:

Suppose r and s are even integers.

Conclusion:

Let x be some real number.

Then:

 (x - r)(x - s) = x^2 - rx - sx - rs = x^2 + (-1)(r + s)x + (-1)rs 

We know the coefficient of x^2 is 1.

By 1 we know the sum of any two even integers is even, then:

We know the coefficient of (-1)(r + s)x is even.

By 1 we know the product of any two even integers is even, then:

We know the coefficient of (-1)rs is even.

Case where r and s is even and the other odd:

Theorem:

Suppose r and s are any integers where one is even and the other is odd.

Conclusion:

Let x be some real number.

Then:

 (x - r)(x - s) = x^2 - rx - sx - rs = x^2 + (-1)(r + s)x + (-1)rs 

We know the coefficient of x^2 is 1.

By 5, we know the sum of any odd integer and any even integer is odd, then:

We know the coefficient of (-1)(r +s)x is odd.

By 4, we know the product of any even integer and any odd integer is even, then:

We know the coefficient of (-1)rs is even.

b. It follows from part (a) that x^2 - 1253x + 255 cannot be written as a product of two polynomials with integer coefficients. Explain why this is so.

Because in all cases from part (a), the middle coefficient and the third coefficient were always either even and odd or odd and even. Since both 1253 and 255 are odd, this expression cannot be expressed as the product of two polynomials with integer coefficients.

34. Observe that

 (x - r)(x -s)(x - t) = x^3 - (r + s + t)x^2 + (rs + rs + st)x - rst 

a. Derive a result for cubic polynomials similar to the result in part (a) of exercise 33 for quadratic polynomials.

Case where r and s and t are all even:

The coefficient of x^3 is 1.

By 1, the sum of any two even integers is even, then:

 r + s \text{ is even} 

 (r + s) + t \text{ is even} 

The coefficient of (r + s + t)x^2 is even.

By 1, the sum and product of any two even integers is even, then:

 rs \text{ is even} 

 st \text{ is even} 

 (rs + rs + rt) \text{ is even} 

The coefficient of (rs + rs + st)x is even.

By 1, the product of any two even integers is even, then:

 rs \text{ is even} 

 rst \text{ is even} 

The coefficient of rst is even.

Case where r is odd and s and t are even:

The coefficient of x^3 is 1.

By 1 the sum of any two even integers is even, then:

 s + t \text{ is even} 

By 5 the sum of any odd integer and any even integer is odd.

 r + (s + t) \text{ is odd} 

The coefficient of (r + s + t)x^2 is odd.

By 4, the product of any even integer and any odd integer is even, then:

 rs \text{ is even} 

By 1, the sum and product of any two even integers is even.

 st \text{ is even} 

 rs + st \text{ is even} 

 rs + (rs + st) \text{ is even} 

The coefficient of (rs + rs + st)x is even.

 (rs)t \text{ is even} 

The coefficient of rst is even.

Case where r and s are odd and t is even:

The coefficient of x^3 is 1.

By 2, the sum of any two odd integers is even.

 r + s \text{ is even} 

By 1, the sum of any two even integers is even.

 (r + s) + t \text{ is even} 

The coefficient of (r + s + t)x^2 is even.

By 3, the product of any two odd integers is odd.

 rs \text{ is odd} 

By 4, the product of any even integer and any odd integer is even.

 st \text{ is even} 

By 2, the sum of any two odd integers is even.

 rs + rs \text{ is even} 

By 1, the sum of any two even integers is even.

 (rs + rs) + st \text{ is even} 

The coefficient of (rs + rs + st)x is even

By 4, the product of any even integer and any odd integer is even.

 (rs)t \text{ is even} 

The coefficient of rst is even.

Case where r and s and t are all odd:

The coefficient of x^3 is 1.

By 2, the sum of any two odd integers is even.

 r + s \text{ even} 

By 5, the sum of any odd integer and any even integer is odd.

 (r + s) + t \text{ is odd} 

The coefficient of (r + s + t)x^2 is odd.

By 3, The product of any two odd integers is odd.

 rs \text{ is odd} 

 st \text{ is odd} 

By 2, the sum of any two odd integers is even.

 rs + rs \text{ is even} 

By 5, the sum of any odd integer and any even integer is odd.

 (rs + rs) + st \text{ is odd} 

The coefficient of (rs + rs + st)x is odd.

 (x - r)(x -s)(x - t) = x^3 - (r + s + t)x^2 + (rs + rs + st)x - rst 

By 3, The product of any two odd integers is odd.

 (rs)t \text{ is odd.} 

The coefficient of rst is odd.

b. Can x^3 + 7x^2 - 8x - 27 be written as a product of three polynomials with integer coefficients? Explain.

In all cases, the order of the second through fourth terms are never: "odd, even, odd". Therefore the given polynomial x^3 + 7x^2 - 8x - 27 can be written as a product of three polynomials with integer coefficients.

In 35-39 find the mistakes in the "proofs" that the sum of any two rational numbers is a rational number.

"Proof: Any two rational numbers produce a rational number when added together. So if r and s are particular but arbitrarily chosen rational numbers, then r + s is rational."

This proof assumes what is to be proved.

"Proof: Let rational numbers r = \dfrac{1}{4} and s = \dfrac{1}{2} be given. Then r + s = \dfrac{1}{4} + \dfrac{1}{2} = \dfrac{3}{4}, which is a rational number. This is what was to be shown."

This proof is arguing from examples.

"Proof: Suppose r and s are rational numbers. By definition of rational, r = \dfrac{a}{b} for some integers a and b with b \neq 0, and s = \dfrac{a}{b} for some integers a and b with b \neq 0. Then

 r + s = \frac{a}{b} + \frac{a}{b} = \frac{2a}{b} 

Let p = 2a. Then p is an integer since it is a product of integers. Hence r + s = \dfrac{p}{b}, where p and b are integers and b \neq 0. Thus r + s is a rational number by definition of rational. This is what was to be shown."

This incorrect proof uses the same letter to mean two different things.

"Proof: Suppose r and s are rational numbers. Then r = \dfrac{a}{b} and s = \dfrac{c}{d} for some integers a, b, c, and d with b \neq 0 and d \neq 0 (by definition of rational.) Then

 r + s = \frac{a}{b} + \frac{c}{d} 

But this is a sum of two fractions, which is a fraction. So r - s is a rational number since a rational number is a fraction."

This incorrect proof exhibits confusion between what is known and what is still to be shown. Additionally, they simply abandon what is to be shown since what is to be shown is r + s is rational, not r - s is rational.

"Proof: Suppose r and s are rational numbers. If r + s is rational, then by definition of rational r + s = \dfrac{a}{b} for some integers a and b with b \neq 0. Also since r and s are rational, r = \dfrac{i}{j} and s = \dfrac{m}{n} for some integers i, j, m, and n with j \neq 0 and n \neq 0. It follows that

 r + s = \frac{i}{j} + \frac{m}{n} = \frac{a}{b} 

which is a quotient of two integers with a nonzero denominator. Hence it is a rational number. This is what is to be shown.

This incorrect prove is assuming what is to be proved.

---

Exercise Set 4.4

Page 220

Give a reason for your answer in each of 1-13. Assume that all variables represent integers.

1. Is 52 divisible by 13?

Yes 52 = 13 \cdot 4

2. Does 7 \mid 56?

Yes 56 = 7 \cdot 8

3. Does 5 \mid 0?

Yes, 0 = 5 \cdot 0

4. Does 3 divide (3k + 1)(3k + 2)(3k + 3)?

Yes 3 | 3(3k + 1)(3k + 2)(k + 1)

5. Is 6m(2m + 10) divisible by 4?

Yes 6m(2m + 10) = 12m^2 + 60m = 4 \cdot (3m^2 + 15m)

6. Is 29 a multiple of 3?

No, \dfrac{29}{3} \approx 9.666666\dots which is not an integer.

7. Is -3 a factor of 66?

Yes, 66 = -3(-22)

8. Is 6a(a + b) a multiple of 3a?

Yes, 6a(a + b) = 3a(2)(a + b)

9. Is 4 a factor of 2a \cdot 34b?

Yes. 2a \cdot 34b = 68ab = 4(17ab)

10. Does 7 \mid 34?

No \dfrac{34}{7} = 4 + \dfrac{6}{7} which is not an integer.

11. Does 13 \mid 73?

No \dfrac{73}{13} = 5 + \dfrac{8}{13} which is not an integer.

12. If n = 4k + 1, does 8 divide n^2 - 1?

Yes.

 n^2 - 1 = (4k + 1)^2 - 1 = 16k^2 + 8k + 1 - 1 = 16k^2 + 8k = 8(2k^2 + k) 

13. If n = 4k + 3, does 8 divide n^2 - 1?

Yes.

 n^2 - 1 = (4k + 3)^2 - 1 = 16k^2 + 24k + 9 - 1 = 16k^2 + 24k + 8 = 8(2k^2 + 3k + 1) 

14. Fill in the blanks in the following proof that for all integers a and b, if a \mid b then a \mid (-b).

Proof:

Suppose a and b are integers such that __ (a) __. By definition of divisibility, there exists an integer r such that __ (b) __. By substitution,

 -b = -(ar) = a(-r) 

Let t = __ (c) __. Then t is an integer because t = (-1) \cdot r, and both -1 and r are integers. Thus, by substitution, -b = at, where t is an integer, and by the definition of divisibility, __ (d) __, as was to be shown.

a. a \mid b

b. b = a \cdot r

c. -r

d. a | (-b)

Prove statements 15 and 16 directly from the definition of divisibility.

15. For all integers a, b, and c, if a \mid b and a \mid c then a \mid (b + c).

Proof:

Suppose a, b, and c are any integers such that a \mid b and a \mid c

By definition of divisibility, b = ar and c = as for some integers r and s.

Then:

 b + c = ar + as = a(r + s) 

Let t = r + s, where t is an integer because the sum of integers are integers. And thus b + c = a \cdot t. By the definition of divisibility then a \mid (b + c).

Q.E.D.

16. For all integers a, b, and c, if a \mid b then a \mid c then a \mid (b - c).

Proof:

Suppose a, b, and c are any integers such that a \mid b and a \mid c

By definition of divisibility, b = ar and c = as for some integers r and s.

Then:

 b - c = ar - as = a(r - s) 

Let t = r - s, where t is an integer because the difference of integers are integers. And thus b - c = a \cdot t. By the definition of divisibility then a \mid (b - c).

Q.E.D.

17. For all integers a, b, c, and d, if a \mid c and b \mid d then ab \mid cd.

Proof:

Suppose a, b, c, and d are any integers such that a \mid c and b \mid d.

By definition of divisibility, c = ar and d = bs for some integers r and s.

Then:

 cd = (ar)(bs) = ab(rs) 

Let t = rs, where t is an integer because the product of integers are integers. Then cd = ab \cdot t. By the definition of divisibility then ab \mid cd.

Q.E.D.

18. Consider the following statement: The negative of any multiple of 3 is a multiple of 3.

a. Write the statement formally using a quantifier and a variable.

 \forall x \in \mathbb{Z}((3 \mid x) \to (3 \mid -x)) 

b. Determine whether the statement is true or false and justify your answer.

Proof:

Suppose x is any integer such that 3 \mid x.

By definition of a multiple, x = 3k for some integer k.

Then:

 -x = -(3k) = 3(-k) 

Then -k is an integer because the product of integers are integers. Therefore, by the definition of divisibility, 3 \mid -x.

Q.E.D.

19. Show that the following statement is false: For all integers a and b, if 3 \mid (a + b) then 3 \mid (a - b).

Proof by Counterexample:

Let a = 1 and b = 2.

Then:

 a + b = 1 + 2 = 3 

So 3 \mid 3 is true. But, then:

 a - b = 1 - 2 = -1 

 3 \nmid -1 

Thus, for the given a and b, 3 \mid (a + b), but 3 \nmid (a - b). Therefore the statement is false.

Q.E.D.

For each statement in 20-32, determine whether the statement is true or false. Prove the statement directly from the definitions if it is true, and give a counterexample if it is false.

20. The sum of any three consecutive integers is divisible by 3.

Proof:

Suppose n is any integer.

Then:

 n + (n + 1) + (n + 2) = 3n + 3 = 3(n + 1) 

Let t = n + 1, where t is an integer because the sum of integers are integers. Then n + (n + 1) + (n + 2) = 3t. Therefore, by the definition of divisibility, 3 \mid n + (n + 1) + (n + 2).

Q.E.D.

21. The product of any two even integers is a multiple of 4.

Proof:

Suppose x and y are any two even integers.

Since x and y are even integers, x = 2k and y = 2m where k and m are some integers.

Then:

 xy = (2k)(2m) = 4km 

Let t = km, where t is an integer because the product of integers are integers. Then xy = 4t. Therefore, by the definition of divsibility, 4 \mid xy.

Q.E.D.

22. A necessary condition for an integer to be divisible by 6 is that it be divisible by 2.

Quick Note:

Recall that "R ... necessary condition for $S$" means S \to R. Thus this is saying:

If an integer is divisible by 6, then it is divisible by 2.

Proof:

Suppose x is any integer and 6 \mid x.

Then x = 6k where k is some integer.

Then:

 x = 6k = 2(3k) 

Let t = 3k where t is an integer because the product of integers is integers. Then x = 2t. Therefore by the definition of divisibility, 2 \mid x.

Q.E.D.

23. A sufficient condition for an integer to be divisible by 8 is that it be divisible by 16.

Quick Note:

"R is a sufficient condition for $S$" means "if R then S."

This reads then as:

If an integer is divisible by 16, then it is divisible by 8.

Proof:

Let x be any integer and 16 \mid x.

Since 16 \mid x, x = 16k where k is some integer.

Then:

 x = 16k = 8(2k) 

Let t = 2k where t is an integer by the product of integers. Then x = 8t, and thus 8 \mid x by the definition of divisibility.

Q.E.D.

24. For all integers a, b, and c, if a \mid b and a \mid c then a \mid (2b - 3c).

Proof:

Suppose a, b, and c are any integers where a \mid b and a \mid c.

Since a \mid b and a \mid c, b = ak and c = am where k and m are some integers.

Then:

 2b - 3c = 2(ak) - 3(am) 

 \quad = a(2k - 3m) 

Let t = 2k - 3m, where t is an integer by the difference and product of integers. Then 2b - 3c = at. Thus a \mid 2b - 3c by the definition of divisibility.

Q.E.D.

25. For all integers a, b, and c, if a is a factor of c and b is a factor of c then ab is a factor of c.

Proof by Counterexample:

Let a = 4, b = 8, and c = 8.

Then a \mid c is 4 \mid 8 and b \mid c is 8 \mid 8, but ab \mid c is 32 \mid 8, which is false since 32 \nmid 8. Therefore this statement is false.

Q.E.D.

26. For all integers a, b, and c, if ab \mid c then a \mid c and b \mid c.

Proof:

Suppose a, b, and c are integers and ab \mid c.

Since ab \mid c, c = abk where k is some integer.

Then:

 c = abk = a(bk) 

And:

 c = abk = b(ak) 

Let t = bk and u = ak where t and u are integers by the product of integers. Then c = at and c = bu. Therefore, by the definition of divisibility, a \mid c and b \mid c.

Q.E.D.

27. For all integers a, b, and c, if a \mid (b + c) then a \mid b or a \mid c.

Proof by Counterexample:

Let a = 3, b = 4, and c = 5.

Then a \mid (b + c) is 3 \mid 9, which is true. Then, however, a \mid b is 3 \mid 4, which is false since 3 \nmid 4 and a \mid c becomes 3 \mid 5, which is also false since 3 \nmid 5.

Thus for the given a, b, and c, a \mid (b + c), but a \nmid b and a \nmid c. Therefore the statement is false.

Q.E.D.

28. For all integers a, b, and c, if a \mid bc then a \mid b or a \mid c.

Proof by Counterexample:

Let a = 6, b = 2, c = 3.

Then a \mid bc is 6 \mid 6, which is true. Then, however, a \mid b is 6 \mid 2, which is false since 6 \nmid 2 and a \mid c is 6 \mid 3 which also false since 6 \nmid 3.

Thus for the given a, b, and c, a \mid bc is true, but then a \nmid b and a \nmid c. Therefore the statement is false.

Q.E.D.

29. For all integers a and b, if a \mid b then a^2 \mid b^2.

Proof:

Suppose a and b are any integers where a \mid b.

Since a \mid b, then b = ak for some integer k.

Then:

 b^2 = (ak)^2 

 b^2 = a^2k^2 

Let t = k^2 where t is an integer by the product of integers. Then b^2 = a^2t. Therefore, by the definition of divisibility, a^2 \mid b^2.

Q.E.D.

30. For all integers a and n, if a \mid n^2 and a \leq n then a \mid n.

Proof by Counterexample:

Let a = -36 and n = 6.

Then a \mid n^2 is -36 \mid 36, which is true and a \leq n is -36 \leq 6, which is also true. Then, however, a \mid n is -36 \mid 6, which is false since -36 \nmid 6.

Thus for the given a and n, a \mid n^2 and a \leq n, but a \nmid n. Therefore this statement is false.

Q.E.D.

31. For all integers a and b, if a \mid 10b then a \mid 10 or a \mid b.

Proof:

Let a = 4, b = 2.

Then a \mid 10b is 4 \mid 20 is true, but then a \mid 10 is 4 \mid 10 is false and a \mid b is 4 \mid 2 is false.

Thus for the given a and b, a \mid 10b, but then a \nmid 10 and a \nmid b. Therefore the statement is false.

Q.E.D.

32. A fast-food chain has a contest in which a card with numbers on it is given to each customer who makes a purchase. If some of the numbers on the card add up to 100, then the customer wins $100. A certain customer receives a card containing the numbers

72, 21, 15, 36, 69, 81, 9, 27, 42, and 63.

Will the customer win $100? Why or why not?

No, each of the given numbers is divisible by 3, but 3 \nmid 100, therefore the sum of any of the given numbers can never equal $100.

33. Is it possible to have a combination of nickels, dimes, and quarters that add up to $4.72? Explain.

No, nickels, dimes and quarters represent 5¢, 10¢, and 25¢ respectively. They have a common divisor of 5, but $4.72 or 472¢, is not divisible by 5, and so it is not possible to have a combination of nickels, dimes and quarters that will add up to $4.72.

34. Consider a string consisting of a's, b's, and c's where the number of b's is three times the number of a's and the number of c's is five times the number of a's. Prove that the length of the string is divisible by 3.

Proof:

Suppose n is any integer that represents the number of a characters in a string.

Suppose also that 3n is the number of b characters in the string and 5n represents the number of c characters in the string.

Let L be the length of the string.

Then the length of the string is:

 L = n + 3n + 5n = 9n = 3(3n) 

Let t = 3n where t is an integer by the product of integers. Then L = 3t. Thus, by the definition of divisibility, 3 \mid L.

Q.E.D.

35. Two athletes run a circular track at a steady pace so that the first completes one round in 8 minutes and the second in 10 minutes. If they both start from the same spot at 4 P.M., when will be the first time they return to the start?

We are looking at the LCM (least common multiple) of both 8 and 10 in this case, which is 40. Then the two athletes will return to the start for the first time at 4:40 P.M.

36. It can be shown (see exercises 44-48) that an integer is divisible by 3 if, and only if, the sum of its digits is divisible by 3; an integer is divisible by 9 if, and only if, the sum of its digits is divisible by 9; an integer is divisible by 5 if, and only if, its right-most digit is a 5 or a 0; and an integer is divisible by 4 if, and only if, the number formed by its right-most two digits is divisible by 4. Check the following integers for divisibility by 3, 4, 5, and 9.

a. 637,425,403,705,125

Divisible by 3?

 3 \stackrel{?}{\mid} (6 + 3 + 7 + 4 + 2 + 5 + 4 + 0 + 3 + 7 + 0 + 5 + 1 + 2 + 5) 

 3 \stackrel{?}{\mid} 54 

Yes, \dfrac{54}{3} = 18

Divisible by 4?

 4 \stackrel{?}{\mid} 25 

No, \dfrac{25}{4} = 6 + \dfrac{1}{4}

Divisible by 5?

Last digit a 5 or 0?

Yes, last digit is 5.

Divisible by 9?

 9 \stackrel{?}{\mid} (6 + 3 + 7 + 4 + 2 + 5 + 4 + 0 + 3 + 7 + 0 + 5 + 1 + 2 + 5) 

 9 \stackrel{?}{\mid} 54 

Yes, \dfrac{54}{9} = 6

b. 12,858,306,120,312

Divisible by 3?

 3 \stackrel{?}{\mid} (1 + 2 + 8 + 5 + 8 + 3 + 0 + 6 + 1 + 2 + 0 + 3 + 1 + 2) 

 3 \stackrel{?}{\mid} 42 

Yes \dfrac{42}{3} = 14

Divisible by 4?

 4 \stackrel{?}{\mid} 12 

Yes \dfrac{12}{4} = 3

Divisible by 5?

Last digit a 5 or 0?

No.

Divisible by 9?

 9 \stackrel{?}{\mid} (1 + 2 + 8 + 5 + 8 + 3 + 0 + 6 + 1 + 2 + 0 + 3 + 1 + 2) 

 9 \stackrel{?}{\mid} 42 

No, \dfrac{42}{9} = 4 + \dfrac{2}{3}.

c. 517,924,440,926,512

Divisible by 3?

 3 \stackrel{?}{\mid} (5 + 1 + 7 + 9 + 2 + 4 + 4 + 4 + 0 + 9 + 2 + 6 + 5 + 1 + 2) 

 3 \stackrel{?}{\mid} 61 

No, \dfrac{61}{3} = 20 + \dfrac{1}{3}

Divisible by 4?

 4 \stackrel{?}{\mid} 12 

Yes \dfrac{12}{4} = 3

Divisible by 5?

Last digit a 5 or 0?

No.

Divisible by 9?

 9 \stackrel{?}{\mid} (5 + 1 + 7 + 9 + 2 + 4 + 4 + 4 + 0 + 9 + 2 + 6 + 5 + 1 + 2) 

 9 \stackrel{?}{\mid} 61 

No, \dfrac{61}{9} = 6 + \dfrac{7}{9}

d. 14,328,083,360,232

Divisible by 3?

 3 \stackrel{?}{\mid} (1 + 4 + 3 + 2 + 8 + 0 + 8 + 3 + 3 + 6 + 0 + 2 + 3 + 2) 

 3 \stackrel{?}{\mid} 45 

Yes \dfrac{45}{3} = 15

Divisible by 4?

 4 \stackrel{?}{\mid} 32 

Yes \dfrac{32}{4} = 8

Divisible by 5?

Last digit a 5 or 0?

No.

Divisible by 9?

 9 \stackrel{?}{\mid} (1 + 4 + 3 + 2 + 8 + 0 + 8 + 3 + 3 + 6 + 0 + 2 + 3 + 2) 

 9 \stackrel{?}{\mid} 45 

Yes, \dfrac{45}{9} = 5

37. Use the unique factorization theorem to write the following integers in standard factored form.

a. 1,176

 1176 = 8 \cdot 147 = 8 \cdot 7 \cdot 21 = 2 \cdot 2 \cdot 2 \cdot 7 \cdot 7 \cdot 3 

 \quad = 2^3 \cdot 7^2 \cdot 3 

b. 5,733

 5733 = 49 \cdot 117 = 7 \cdot 7 \cdot 9 \cdot 13 = 7^2 \cdot 3^2 \cdot 13 

 \quad = 7^2 \cdot 3^2 \cdot 13 

c. 3,675

 3675 = 25 \cdot 147 = 5 \cdot 5 \cdot 7 \cdot 21 = 5^2 \cdot 7 \cdot 7 \cdot 3 

 \quad = 5^2 \cdot 7^2 \cdot 3 

38. Let n = 8,424.

a. Write the prime factorization for n.

 8,424 = 24 \cdot 351 = 6 \cdot 4 \cdot 3 \cdot 117 

 \quad = 3 \cdot 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3 \cdot 39 

 \quad = 3^3 \cdot 2^3 \cdot 39 

 \quad = 3^3 \cdot 2^3 \cdot 3 \cdot 13 

 \quad = 3^4 \cdot 2^3 \cdot 13 

b. Write the prime factorization for n^5.

 n = 3^4 \cdot 2^3 \cdot 13 

 n^5 = (3^4 \cdot 2^3 \cdot 13)^5 

0$ n^5 = 3^{20} \cdot 2^{15} \cdot 13^5

c. Is n^5 divisible by 20? Explain.

 20 = 2^2 \cdot 5 

So in order for 20 \mod n^5, then 2^2 \mid n^5 and 5 \mid n^5, 2^2 \mid n^5 is possible since one of the prime factorizations of n^5 is 2^{15} but none of the prime factorizations of n^5 is 5. Therefore 20 \nmid n^5.

d. What is the least positive integer m so that 8,424 \cdot m is a perfect square?

To make 8424 \cdot m square, all prime exponents must be even. Let's examine our prime factorization form of n:

 n = 3^4 \cdot 2^3 \cdot 13 

Only our last two terms need an additional factor each to make their exponents even, so to make 8424m a perfect square, m = 2 \cdot 13 = 26, this will make:

 8424m = 3^4 \cdot 2^4 \cdot 13^2 

39. Suppose that in standard factored form a = p_1^{e_1}p_2^{e_2} \dots p_k^{e_k}, where k is a positive integer; p_1, p_2, \dots, p_k are prime numbers; and e_1, e_2, \dots, e_k are positive integers.

a. What is the standard factored form for a^3?

 a^3 = p_1^{3e_1}p_2^{3e_2} \dots p_k^{3e_k} 

b. Find the least positive integer k such that 2^4 \cdot 3^5 \cdot 7 \cdot 11^2 \cdot k is a perfect cube (that is, it equals an integer to the third power). Write the resulting product as a perfect cube.

 k = 2^2 \cdot 3 \cdot 7^2 \cdot 11 

a. If a and b are integers and 12a = 25b, does 12 \mid b? does 25 \mid a? Explain.

Because 12a = 25b, the unique factorization theorem guarantees that the standard factored forms of 12a and 25b must be the same. Thus 25b contains the factors 2^2 \cdot 3 (= 12). But since neither 2 nor 3$ divides 25, the factors 2^2 \cdot 3 must all occur in b, and hence 12 \mid b. Similarly, 12a contains the factors 5^2 = 25, and since 5 is not a factor of $124, the factors 5^2 must occur in a. So 25 \mid a.

b. If x and y are integers and 10x = 9y, does 10 \mid y? does 9 \mid x? Explain.

Because 10x = 9y, the unique factorization theorem guarantees that the standard factored forms of 10x and 9y must be the same. Thus 10x contains the factors 3^2. But since 3 does not divide 10, the factor 3^2 must all occur in x, and hence 9 \mid x. Similary 10x contains factors 2 \cdot 5, and since neither 5 nor 2 are factors of 9, the factors 2 \cdot 5 must occur in y. So 10 \mid y.

41. How many zeros are at the end of 45^8 \cdot 88^5? Explain how you can answer this question without actually computing the number. (Hint: 10 = 2 \cdot 5.)

If we find the standard factored form of 45^8 \cdot 88^5 and then find the total amount of $10$'s, this should tell us how many zeros are at the end of 45^8 \cdot 88^5.

 45^8 \cdot 88^5 = (9 \cdot 5)^8 \cdot (4 \cdot 22)^5 

 \quad = (3^2 \cdot 5)^8 \cdot (2^2 \cdot 2 \cdot 11)^5 

 \quad = (3^2 \cdot 5)^8 \cdot (2^3 \cdot 11)^5 

 \quad = 3^{16} \cdot 5^8 \cdot 2^{15} \cdot 11^5 

The total amount of $10$'s we can find is the maximum amount of $5 \cdot 2$'s we can factor from this expression, which is 8 (while we have 15 $2$'s, we only have 8 $5$'s).

Therefore there are 8 zeros in 45^8 \cdot 88^5.

42. If n is an integer and n > 1, then n! is the product of n and every other positive integer that is less than n. For example, 5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1.

a. Write 6! in standard factored form.

 6! = 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 

 6! = 3 \cdot 2 \cdot 5 \cdot 2 \cdot 2 \cdot 3 \cdot 2 

 6! = 2^4 \cdot 3^2 \cdot 5 

b. Write 20! in standard factored form.

Writing this out would be exhaustive, instead let's use Legendre's formula.

 20! = 2^a \cdot 3^b \cdot 5^c \cdot 7^d \cdot 11^e \cdot 13^f \cdot 17^g \cdot 19^h 

Take the floor of every possible prime factor, and those are the exponents of each.

 \left\lfloor \frac{20}{2} \right\rfloor + \left\lfloor \frac{20}{4} \right\rfloor + \left\lfloor \frac{20}{8} \right\rfloor + \left\lfloor \frac{20}{16} \right\rfloor 

 \quad = 10 + 5 + 2 + 1 = 18 

 2^{18} 

 \left\lfloor \frac{20}{3} \right\rfloor + \left\lfloor \frac{20}{9} \right\rfloor 

 6 + 2 = 8 

 3^8 

 \left\lfloor \frac{20}{5} \right\rfloor 

 5^4 

 \left\lfloor \frac{20}{7} \right\rfloor 

 7^2 

 \boxed{20! = 2^{18} \cdot 3^8 \cdot 5^4 \cdot 7^2 \cdot 11 \cdot 13 \cdot 17 \cdot 19} 

c. Without computing the value of (20!)^2 determine how many zeros are at the end of this number when it is written in decimal form. Justify your answer.

We can square the answer for 20! from part b:

 (20!)^2 = (2^{18} \cdot 3^8 \cdot 5^4 \cdot 7^2 \cdot 11 \cdot 13 \cdot 17 \cdot 19)^2 

 \quad = 2^{36} \cdot 3^{16} \cdot 5^8 \cdot 7^4 \cdot 11^2 \cdot 13^2 \cdot 17^2 \cdot 19^2 

Then take all combinations of 2 and 5, and take the minimum exponent between them as this will tell us how many zeros are at the end of this number when it is written in decimal form.

 \min(36, 8) = 8 

So there are 8 zeros at the end of (20!)^2.

43. At a certain university 2/3 of the mathematics students and 3/5 of the computer science students have taken a discrete mathematics course. The number of mathematics students who have taken the course equals the number of computer science students who have taken the course. If there are at least 100 mathematics students at the university, what are the least possible number of mathematics students and the least possible number of computer science students at the university?

Let M be the number of mathematics students and C be the number of computer science students.

Given:

 \frac{2}{3}M = \frac{3}{5}C 

Set them equal:

 \frac{2}{3}M = \frac{3}{5}C = x 

So:

 M = \frac{3}{2}x 

 C = \frac{5}{3}x 

To make both integers, x must be a multiple of 6:

 x = 6k 

Then:

 M = 9k 

 C = 10k 

Now use the given condition:

 M \geq 100 

 9k \geq 100 \Rightarrow k \geq 12 

Smallest k = 12:

 M = 9 \cdot 12 = 108 

 C = 10 \cdot 12 = 120 

Math Students: 108

Computer Science Students: 120

Definition: Given any nonnegative integer n, the decimal representation of n is an expression of the form

 d_kd_{k + 1} \dots d_2d_1d_0 

where $kr is a nonnegative integer, d_0, d_1, d_2, \dots, d_k (called the decimal digits of n) are integers from 0 to 9 inclusive, dk \neq 0 unless n = 0 and k = 0, and

 n = d_k \cdot 10^k + d_{k + 1} \cdot 10^{k + 1} + \dots + d_2 \cdot 10^2 + d_1 \cdot 10 + d_0 

(For example, 2,503 = 2 \cdot 10^3 + 5 \cdot 10^2 + 0 \cdot 10 + 3.)

44. Prove that if n is any nonnegative integer whose decimal representation ends in 0, then 5 \mid n. (Hint: If the decimal representation of a nonnegative integer n ends in d_0, then n = 10m + d_0 for some integer m.)

Proof:

Suppose n is any nonnegative integer whose decimal representation ends in 0.

Because n is a nonnegative integer, it can be shown in decimal representation as:

 n = 10m + d_0 

Where m is some integer.

Since we know that $n$'s decimal representation ends in 0, that means that d_0 = 0. So n is:

 n = 10m 

Then:

 n = 5(2m) 

Then 2m is an integer by the product of integers. By the definition of divisibility, 5 \mid n.

Q.E.D.

45. Prove that if n is any nonnegative integer whose decimal representation ends in 5, then 5 \mid n.

Proof:

Suppose n is any nonnegative integer whose decimal representation ends in 5.

Because n is a nonnegative integer, it can be shown in decimal representation as:

 n = 10m + d_0 

Where m is some integer.

Since we know that $n$'s decimal representation ends in 5, that means that d_0 = 5. So n is:

 n = 10m + 5 

Then:

 n = 5(2m + 1) 

Then 2m + 1 is an integer by the product and sum of integers. By the definition of divisibility, 5 \mid n.

Q.E.D.

46. Prove that if the decimal representation of a nonnegative integer n ends in d_1d_0 and if 4 \mid (10d_1 + d_0), then 4 \mid n. (Hint: If the decimal representation of a nonnegative integer n ends in d_1d_0, then there is an integer s such that n = 100s + 10d_1 + d_0.)

Proof:

Suppose n is any nonnegative integer whose decimal representation ends in d_1d_0 and 4 \mid (10d_1 + d_0).

Since 4 \mid (10d_1 + d_0), then 10d_1 + d_0 = 4k for some integer k.

And since the decimal representation of n ends in d_1d_0, then there is an integer s such that n = 100s + 10d_1 + d_0.

 n = 100s + 10d_1 + d_0 

Then, by substitution:

 n = 100s + 4k 

 n = 4(25s + k) 

Where 25s + k is an integer by the product and sum of integers. Thus 4 \mid n.

Q.E.D.

47. Observe that

7,524 = 7 \cdot 1,000 + 5 \cdot 100 + 2 \cdot 10 + 4 \ \quad = 7(999 + 1) + 5(99 + 1) + 2(9 + 1) + 4 \ \quad = (7 \cdot 99 + 7) + (5 \cdot 99 + 5) + (2 \cdot 9 + 2) + 4 \ \quad = (7 \cdot 999 + 5 \cdot 99 2 \cdot 9) + (7 + 5 + 2 + 4) \ \quad = (7 \cdot 111 \cdot 9 + 5 \cdot 11 \cdot 9 + 2 \cdot 9) + (7 + 5 + 2 + 4) \ \quad = (7 \cdot 111 + 5 \cdot 11 + 2) \cdot 9 + (7 + 5 + 2 + 4) \ \quad = (\text{an integer divisible by 9})i + (\text{the sum of the digits of } 7,524)

Since the sum of the digits of 7,524 is divisible by 9, 7,524 can be written as a sum of two integers each of which is divisible by 9. It follows from exercise 15 that 7,524 is divisible by 9.

Generalize the argument given in this example to any nonnegative integer n. In other words, prove that for any nonnegative integer n, if the sum of the digits of n is divisible by $9r, then n is divisible by 9.

Omitted.

48. Prove that for any nonnegative integer n, if the sum of the digits of n is divisible by 3, then n is divisible by 3.

Omitted.

49. Given a positive integer n written in decimal form, the alternating sum of the digits of n is obtained by starting with the right-most digit, subtracting the digit immediately to its left, adding the next digit to the left, subtracting the next digit, and so forth. For example, the alternating sum of the digits of 180,928 is 8 - 2 + 9 - 0 + 8 - 1 = 22. Justify the fact that for any nonnegative integer n, if the alternating sum of the digits of n is divisible by 11, then n is divisible by 11.

Omitted.

50. The integer 123,123 has the form abc,abc, where a, b, and c are integers from 0 through 9. Consider all six-digit integers of this form. Which prime numbers divide every one of these integers? Prove your answer.

Omitted.

---

Exercise Set 4.5

Page 232

For each of the values of n and d given in 1-6, find integers q and r such that n = dq + r and 0 \leq r < d.

1. n = 70, d = 9

 d \mid n 

 d \mod r 

 d \mid n = 7 

 n = dq + r 

 n = 9(7) + 7 

 q = 7, r = 7 

2. n = 62, d = 7

 n = dq + r 

 62 = (7)(8) + (6) 

 q = 8, r = 6 

3. n =36, d = 40

 36 = (40)(0) + (36) 

 q = 0, r = 36 

4. n = 3, d = 11

 3 = (11)(0) + (3) 

 q = 0, r = 3 

5. n = -45, d = 11

 -45 = (11)(-5) + 10 

Note that r must be nonnegative, hence why negatives look different here.

 q = -5, r = 10 

6. n = -27, d = 8

 -27 = (8)(-4) + 5 

 q = -4, r = 5 

Evaluate the expressions in 7-10.

a. 43\ div\ 9

 43\ div\ 9 = 4 

b. 43 \mod 9

 43 \mod 9 = 7 

a. 50\ div\ 7

 50\ \div\ 7 = 7 

b. 50 \mod 7

 50 \mod 7 = 1 

a. 28\ div\ 5

 28\ div\ 5 = 5 

b. 28 \mod 5

 28 \mod 5 = 3 

a. 30\ div\ 2

 30\ div\ 2 = 15 

b. 30 \mod 2

 30 \mod 2 = 0 

11. Check the correctness of formula (4.5.1) given in Example 4.5.3 for the following values of \text{Day}T and N.

4.5.1

 n = dq + r \text{ and } 0 \leq r < d 

a. \text{Day}T = 6(\text{Saturday}) \text{ and } N = 15

 \text{Day}N = (\text{Day}T + N) \mod 7 

 \quad = (6 + 15) \mod 7 

 \quad = 21 \mod 7 = 0 

b. \text{Day}T = 0(\text{Sunday}) \text{ and } N = 7

 \text{Day}N = (\text{Day}T + N) \mod 7 

 \quad = (0 + 7) \mod 7 

 \quad = 7 \mod 7 = 0 

c. \text{Day}T = 4(\text{Thursday}) \text{ and } N = 12

 \text{Day}N = (\text{Day}T + N) \mod 7 

 \quad = (4 + 12) \mod 7 

 \quad = 16 \mod 7 = 2 

12. Justify formula (4.5.1) for general values of \text{Day}T and N.

Omitted

13. On a Monday a friend says he will meet you again in 30 days. What day of the week will that be?

 \text{Day}N = (\text{Day}T + N) \mod 7 

 \quad = (1 + 30) \mod 7 

 \quad = 31 \mod 7 = 3  

0 + 3 days = Wednesday

14. If today is Tuesday, what day of the week will it be 1,000 days from today?

 \text{Day}N = (\text{Day}T + N) \mod 7 

 \text{Day}N = (2 + 1000) \mod 7 

 \text{Day}N = 1002 \mod 7 = 1 

Monday.

15. January 1, 2000, was a Saturday, and 2000 was a leap year. What day of the week will January 1, 2050, be?

Leap years occur roughly every 4 years. In the 50 year time span that means 50 \div 4 = 12.5. Taking the ceiling of this we have 13 additional days.

The amount of days for 50 years is 50 \cdot 365 = 18250, so N = 18250 + 13 = 18263.

Now we can plug this in:

 \text{Day}N = (\text{Day}T + N) \mod 7 

 \quad = (6 + 18263) \mod 7 

 \quad = 18269 \mod 7 = 6 

So January 1, 2050 will be a Saturday.

16. Suppose d is a positive and n is any integer. If d \mid n, what is the remainder obtained when the quotient remainder theorem is applied to n with divisor d?

r = 0

Because d \mid n, n = dq + 0 for some integer q. Thus the remainder r, is 0.

17. Prove directly from the definitions that for every integer n, n^2 - n + 3 is odd. Use division into two cases: n is even and n is odd.

Proof:

Suppose n is any integer.

Case n is even:

Since n is even, n = 2k for some integer k.

Then by substitution:

 n^2 - n + 3 = (2k)^2 - (2k) + 3 

 \quad = 4k^2 - 2k + 3 

 \quad = 4k^2 - 2k + 2 + 1 

 \quad = 2(2k^2 - k + 1) + 1 

Let m = 2k^2 - k + 1, where m is an integer by the product and sum of integers. Therefore n^2 - n + 3 is odd by the definition of odd integers.

Case n is odd:

Since n is odd, n = 2s + 1 for some integer s.

Then by substitution:

 n^2 - n + 3 = (2s + 1)^2 - (2s + 1) + 3 

 n^2 - n + 3 = (2s + 1)(2s + 1) - 2s - 1 + 3 

 n^2 - n + 3 = (4s^2 + 4s + 1) - 2s - 1 + 3 

 n^2 - n + 3 = 4s^2 + 2s + 3 

 n^2 - n + 3 = 4s^2 + 2s + 2 + 1 

 n^2 - n + 3 = 2(2s^2 + s + 1) + 1 

Let p = 2s^2 + s + 1 where p is an integer by the product and sum of integers. Therefore n^2 - n + 3 is odd by the definition of odd integers.

In both cases n^2 - n + 3 is odd.

Q.E.D.

a. Prove that the product of any two consecutive integers is even.

Proof:

Suppose n is any integer.

Then the product of n and its consecutive integer is:

 n(n + 1) = n^2 + n 

Case where n is even:

Since n is even, n = 2k for some integer k.

Then by substitution:

 n^2 + n = (2k)^2 + (2k) 

 \quad = 4k^2 + 2k 

 \quad = 2(2k^2 + k) 

Let m = 2k^2 + k where m is an integer by the product and sum of integers. Therefore n^2 + n is even by the definition of even integers.

Case where n is odd:

Since n is odd, n = 2s + 1, for some integer s.

Then by substitution:

 n^2 + n = (2s + 1)^2 + (2s + 1) 

 n^2 + n = (2s + 1)(2s + 1) + 2s + 1 

 n^2 + n = 4s^2 + 4s + 1 + 2s + 1 

 n^2 + n = 4s^2 + 6s + 2 

 n^2 + n = 2(2s^2 + 3s + 1) 

Let p = 2s^2 + 3s + 1, where p is an integer by the product and sum of integers. Therefore n^2 + n is even by the definition of even integers.

In both cases n^2 + n is even, therefore the product of any two consecutive integers is even.

Q.E.D.

b. The result of part (a) suggests that the second approach in the discussion of Example 4.5.7 might be possible after all. Write a new proof of Theorem 4.5.3 based on this observation.

4.5.3 Demonstrates this proof:

Prove: The square of any odd integer has the form 8m + 1 for some integer m.

But suggests another approach might be possible.

"You could try another approach by arguing that since n is odd, you can represent it as 2q + 1 for some integer q. Then $n^2 = (2q + 1)^2 = 4q^2 + 4q + 1 = 4(q^2 + q) + 1$". It is clear from this analysis that n^2 can be rewritten in the form 4m + 1, but it may not be clear that it can be written as 8m + 1.

Given part a, we can now prove this. Let's do that now:

Proof:

Suppose n is any odd integer.

Since n is odd, n = 2q + 1 for some integer q.

Then:

 n^2 = (2q + 1)^2 

 n^2 = (2q + 1)(2q + 1) 

 n^2 = 4q^2 + 4q + 1 

 n^2 = 4(q^2 + q) + 1 

By part a, we know that q^2 + q is even. So q^2 + q = 2m, for some integer m.

 n^2 = 4(2m) + 1 

 n^2 = 8m + 1 

Therefore n^2 has the form 8m + 1 for some integer m.

Q.E.D.

19. Prove directly from the definitions that for all integers m and n, if m and n have the same parity, then 5m + 7n is even. Divide into two cases: m and n are both even and m and n are both odd.

Proof:

Suppose m and n are any two integers with the same parity.

Case m and n are even:

Since m and n are even, m = 2k and n = 2p for some integers k and p.

Then:

 5m + 7n = 5(2k) + 7(2p) 

 \quad = 10k + 14p 

 \quad = 2(5k + 7p) 

Let s = 5k + 7p where s is an integer by the product and sum of integers.

Therefore 5m + 7n is even by the definition of even integers.

Case m and n are odd:

Since m and n are odd, m = 2t + 1 and n = 2v + 1 for some integers t and v.

Then:

 5m + 7n = 5(2t + 1) + 7(2v + 1) 

 5m + 7n = 10t + 5 + 14v + 7 

 5m + 7n = 10t + 14v + 12 

 5m + 7n = 2(5t + 7v + 6) 

Let w = 5t + 7v + 6 where w is an integer by the product and sum of integers.

Therefore 5m + 7n is even by the definition of even integers.

In both cases, 5m + 7n is even. Therefore for all integers m and n, if m and n have the same parity, then 5m + 7n is even.

Q.E.D.

20. Suppose a is any integer. If a \mod 7 = 4, what is 5a \mod 7? In other words, if division of a by 7 gives a remainder of 4, what is the remainder when 5a is divided by 7? Your solution should show that you obtain the same answer no matter what integer you start with.

 a \mod 7 = 4 

 5a \mod 7 = ? 

Since a \mod 7 = 4, this means that the remainder obtained when a is divided by 7 is 4. This means there is some integer q so that

 a = 7q + 4 

Thus

 5a = 5(7q + 4) = 35q + 20 

And when put into the form defined by the quotient-remainder theorem:

n = dq + r, recall our original divisor was 7, so:

 \quad = 7(5q + 2) + 6 

So,

 5a \mod 7 = 6 

21. Suppose b is any integer. If b \mod 12 = 5, what is 8b \mod 12? In other words, if division of b by 12 gives a remainder of 5, what is the remainder when 8b is divided by 12? Your solution should show that you obtain the same answer no matter what integer you start with.

 b \mod 12 = 5 

 8b \mod 12 = ? 

 b = 12d + 5 

 8b = 8(12d + 5) 

 \quad = 96d + 40 

 \quad = 12(8d + 3) + 4 

 8b \mod 12 = 4 

22. Suppose c is any integer. If c \mod 15 = 3, what is 10c \mod 15? In other words, if division of c by 15 gives a remainder of 3, what is the remainder when 10c is divided by 15? Your solution should show that you obtain the same answer no matter what integer you start with.

 c \mod 15 = 3 

 10c \mod 15 = ? 

 c = 15d + 3 

 10c = 10(15d + 3) 

 10c = 150d + 30 

 10c = 15(10d + 2) + 0 

 10c \mod 15 = 0 

23. Prove that for every integer n, if n \mod 5 = 3 then n^2 \mod 5 = 4.

Proof:

Suppose n is any integer where n \mod 5 = 3.

Since n \mod 5 = 3, n = 5d + 3 for some integer d.

Then:

 n^2 = (5d + 3)^2 

 n^2 = (5d + 3)(5d + 3) 

 n^2 = 25d^2 + 30d + 9 

 n^2 = 5(5d^2 + 6d + 1) + 4 

Let s = 5d^2 + 6d + 1 where s is an integer by the product and sum of integers. Then the remainder is 4 by the quotient remainder theorem.

Therefore n^2 \mod 5 = 4.

Q.E.D.

24. Prove that for all integers m and n, if m \mod 5 = 2 and n \mod 5 = 1 then mn \mod 5 = 2.

Proof:

Suppose m and n are any integers where m \mod 5 = 2 and n \mod 5 = 1.

Since m \mod 5 = 2 and n \mod 5 = 1, m = 5d + 2 and n = 5q + 1 for some integers d and q.

Then:

 mn = (5d + 2)(5q + 1) 

 mn = 25dq + 5d + 10q + 2 

 mn = 5(5dq + d + 2q + 0) + 2 

 mn = 5(5dq + d + 2q) + 2 

Let u = 5dq + d + 2q where u is an integer by the product and sum of integers. Then mn has a remainder of 2 when divided by 5 by the quotient-remainder theorem.

Therefore mn \mod 5 = 2.

Q.E.D.

25. Prove that for all integers a and b, if a \mod 7 = 5 and b \mod 7 = 6 then ab \mod 7 = 2.

Proof:

Suppose a and b are any integers where a \mod 7 = 5 and b \mod 7 = 6.

Since a \mod 7 = 5 and b \mod 7 = 6, a = 7d + 5 and b = 7q + 6 for some integers d and q.

Then:

 ab = (7d + 5)(7q + 6) 

 \quad = 49dq + 35q + 42d + 30 

 \quad = 7(7dq + 5q + 6d + 4) + 2 

Let u = 7dq + 5q + 6d + 4 where u is an integer by the product and sum of integers. Then by the quotient-remainder theorem, ab when divided by 7 has a remainder of 2.

Therefore ab \mod 7 = 2.

Q.E.D.

26. Prove that a necessary and sufficient condition for an integer n to be divisible by a positive integer d is that n \mod d = 0.

Proof:

Suppose n is any integer and d is a positive integer where d \mid n.

Since d \mid n and d \neq 0, n = dq for some integer q by the definition of divisibility.

Then:

 n = dq 

 \quad = dq + 0 

Then, n when divided by d has a remainder of 0 by the quotient-remainder theorem.

Thus n \mod d = 0.

Suppose then that n \mod d = 0 where n is any integer and d is a positive integer.

Since n \mod d = 0 and d \neq 0, then n = dq + 0 for some integer q by the quotient-remainder theorem.

Then:

 n = dq + 0 

 n = dq 

Thus d \mid n by the definition of divisibility.

Therefore it has been shown that a necessary and sufficient condition for an integer n to be divisible by a positive integer d is that n \mod d = 0.

Q.E.D.

27. Use the quotient-remainder theorem with divisor equal to 2 to prove that the square of any integer can be written in one of the two forms 4k or 4k + 1 for some integer k.

Proof:

Suppose n is any integer.

Case 1: n is even:

Since n is even, n = 2q for some integer q.

Then:

 n^2 = (2q)^2 

 \quad = 4q^2 

Let k = 2q^2 where k is an integer by the product of integers.

Then n^2 can be written in the form of 4k.

Case 2: n is odd:

Since n is odd, n = 2q + 1 for some integer q.

Then:

 n^2 = (2q + 1)^2 

 \quad = (2q + 1)(2q + 1) 

 \quad = 4q^2 + 4q + 1 

 \quad = 4(q^2 + q) + 1 

Let k = q^2 + q where k is an integer by the product and sum of integers.

Then n^2 can be written in the form of 4k + 1.

Therefore by Case 1, n^2 can be written in the form 4k, and by Case 2 n^2 can be written in the form 4k + 1.

Q.E.D.

a. Prove: Given any set of three consecutive integers, one of the integers is a multiple of 3.

Proof:

Suppose n is any integer.

Case 1: n is a multiple of 3:

Since n is a multiple of 3, n = 3d where d is some integer.

Then n + 1 = 3d + 1 and (n + 1) \mod 3 = 1 by the quotient-remainder theorem.

Then n + 2 = 3d + 2 and $(n + 2) \mod 3 = 2$A by the quotient -remainder theorem.

Therefore n is a multiple of 3 but n + 1 and n + 2 are not.

Case 2: n + 1 is a multiple of 3:

Since n + 1 is a multiple of 3, n + 1 = 3d where d is an integer such that d > 0 by the definition of divisibility.

Then n = 3d - 1 = 2d + 3 - 1 = 2d + 2 and n \mod 3 = 2 by the quotient-remainder theorem.

Then $n + 2 = 3d + 1 and (n + 2) \mod 3 = 1 by the quotient-remainder theorem.

Therefore n + 1 is a multiple of 3 but n and n + 2 are not.

Case 3: n + 2 is a multiple of 3:

Since n + 2 is a multiple of 3, n + 2 = 3d where d is an integer such that d > 0 by the definition of divisibility.

Then n + 1 = 3d - 1 = 2d + 3 - 1 = 2d + 2 and (n + 1) \mod 3 = 2 by the quotient-remainder theorem.

Then n = 3d - 2 = 2d + 3 - 2 = 2d + 1 and n \mod 3 = 1 by the quotient-remainder theorem.

Therefore n + 2 is a multiple of 3 but n and n + 1 are not.

In all three cases, in any given set of three consecutive integers, one of the integers is a multiple of 3.

Q.E.D.

b. Use the result of part (a) to prove that any product of three consecutive integers is a multiple of 3.

Proof:

Suppose n is any integer.

By a., either n or n + 1 or n + 2 is a multiple of 3.

Case n is a multiple of $3$:

Since n is a multiple of 3, n = 3d for some integer d.

Then:

 n(n + 1)(n + 2) = (3d)(n + 1) (n + 2) 

 \quad = 3\left[(d)(n + 1) (n + 2)\right] 

Let m = \left[(d)(n + 1) (n + 2)\right] where m is an integer by the product and sum of integers. Then 3 \mid (n)(n + 1)(n + 2) by the definition of divisibility.

Therefore n(n + 1)(n + 2) is a multiple of 3.

Case n + 1 is a multiple of $3$:

Since n+ 1 is a multiple of 3, n + 1 = 3d for some integer d.

Then:

 n(n + 1)(n + 2) = n(3d)(n + 2) 

 \quad = 3\left[n(d)(n + 2)\right] 

Let m = \left[n(d)(n + 2)\right] where m is an integer by the product and sum of integers. Then 3 \mid (n)(n + 1)(n + 2) by the definition of divisibility.

Therefore n(n + 1)(n + 2) is a multiple of 3.

Case n + 2 is a multiple of $3$:

Since n + 2 is a multiple of 3, n + 2 = 3d for some integer d.

Then:

 n(n + 1)(n + 2) = n(n + 1)(3d) 

 \quad = 3\left[n(n + 1)(d)\right] 

Let m = \left[n(n + 1)(d)\right] where m is an integer by the product and sum of integers. Then 3 \mid (n)(n + 1)(n + 2) by the definition of divisibility.

Therefore n(n + 1)(n + 2) is a multiple of 3.

In all three cases, any product of three consecutive integers is a multiple of 3.

Q.E.D.

a. Use the quotient-remainder theorem with divisor equal to 3 to prove that the square of any integer has the form 3k or 3k + 1 for some integer k.

Proof:

Suppose n is any integer.

By the quotient-remainder theorem, n can be represented as:

n = 3q, \text{ or } n = 3q + 1 \text{ or } n = 3q + 2 for some integer q.

Case n = 3q:

Then:

 n^2 = (3q)^2 

 \quad = 9q^2 

 \quad = 3(3q^2) 

Let k = 3q^2 where k is an integer by the product of integers.

Then n^2 has the form 3k.

Case n = 3q + 1:

Then:

 n^2 = (3q + 1)^2 

 \quad = (3q + 1)(3q + 1) 

 \quad = 9q^2 + 6q + 1 

 \quad = 3(3q^2 + 2q) + 1 

Let k = 3q^2 + 2q where k is an integer by the product and sum of integers.

Then n^2 has the form 3k + 1.

Case n = 3q + 2:

Then:

 n^2 = (3q + 2)^2 

 n^2 = (3q + 2)(3q + 2) 

 n^2 = 9q^2 + 12q + 4 

 n^2 = 9q^2 + 12q + 3 + 1 

 n^2 = 3(3q^2 + 4q + 1) + 1 

Let k = 3q^2 + 4q + 1 where k is an integer by the product and sum of integers.

Then n^2 has the form of 3k + 1.

Therefore, in all cases, the square of any integer has the form 3k or 3k + 1 for some integer k.

Q.E.D.

b. Use the \mod notation to rewrite the result of part (a).

Therefore, in all cases, the square of any integer n in mod notation can be represented as n^2 \mod 3 = 0 or n^2 \mod 3 = 1.

a. Use the quotient-remainder theorem with divisor equal to 3 to prove that the product of any two consecutive integers has the form 3k or 3k + 2 for some integer k.

Proof:

Suppose n is any integer.

By the quotient-remainder theorem, n can be represented as:

 n = 3q \text{ or } n = 3q + 1 \text{ or } n = 3q + 2 

for some integer q.

Case n = 3q:

Then:

 n(n + 1) = (3q)(3q + 1) 

 \quad = 9q^2 + 3q 

 \quad = 3(q^2 + q) 

Let k = q^2 + q where k is an integer by the product and sum of integers.

Then n(n + 1) has the form 3k.

Case n = 3q + 1:

Then:

 n(n + 1) = (3q + 1)((3q + 1) + 1) 

 \quad = (3q + 1)(3q + 2) 

 \quad = 9q^2 + 9q + 2 

 \quad = 3(3q^2 + 3q) + 2 

Let k = 3q^2 + 3q where k is an integer by the product of integers.

Then n(n + 1) has the form 3k + 2.

Case n = 3q + 2:

Then:

 n(n + 1) = (3q + 2)((3q + 2) + 1) 

 \quad = (3q + 2)(3q + 3) 

 \quad = 9q^2 + 9q + 6 

 \quad = 3(3q^2 + 3q + 2) 

Let k = 3q^2 + 3q + 2 where k is an integer by the product and sum of integers.

Then n(n + 1) has the form 3k.

In all three cases, the product of any two consecutive integers has the form 3k or 3k + 2.

Q.E.D.

b. Use the \mod notation to rewrite the result of part (a).

In all three cases, the product of any two consecutive integers, n and n + 1 can be written in mod notation as n(n + 1) \mod 3 = 0 or n(n + 1) \mod 3 = 2.

In 31-33, you may use the properties listed in Example 4.3.3.

a. Prove that for all integers m and n, m + n and m - n are either both odd or both even.

Proof:

Suppose m and n are any integers.

Case both m and n are even:

Property 1: The sum and difference of any two even integers are even.

By property 1 both m + n and m - n are even.

Case both m and n are odd:

Property 2: The sum and difference of any two odd integers are even.

By property 2 both m + n and m - n are even.

Case where m is odd and n is even:

Property 5: The sum of any odd integer minus any even integer is odd.

By property 5 both m + n and m - n are odd.

Case where m is even and n is odd:

Property 5: The sum of any odd integer minus any even integer is odd.

By property 5 both m + n and m - n are odd.

In all cases m + n and m - n are both odd or are both even.

Q.E.D.

b. Find all solutions to the equation m^2 - n^2 = 56 for which both m and n are positive integers.

 m^2 - n^2 = (m + n)(m - n) = 56 

 56 = 2 * 28 = 2 * 2 * 14 = 2 * 2 * 2 * 7 = 2^3 * 7 = 8 * 7 

Therefore (m + n)(m - n) = (8)(7) or (m - n)(m + n) = (8)(7). By part a, m and n must either both be odd or both be even.

m + n = 14 and m - n = 4 where m = 9 and n = 5.

Or also:

m + n = 28 and m - n = 2 where m = 15 and n = 13.

c. Find all solutions to the equation m^2 - n^2 = 88 for which both m and n are positive integers.

 m^2 - n^2 = (m + n)(m - n) = 88 

 88 = 2 * 44 = 2^2 * 22 = 2^3 * 11 

By part a, m and n must either both be odd or both be even.

m + n = 22 and m - n = 4 where m = 13 and n = 9

m + n = 44 and m - n = 2 where m = 23 and n = 21

32. Given any integers a, b, and c, if a - b is even and b - c is even, what can you say about the parity of 2a - (b + c)? Prove your answer.

Proof:

Suppose a, b, and c are any integers where a - b is even and b - c is even.

Note that 2a - (b + c) = a + a - (b + c) \ = a + a - b - c \ = a - b + a - c \ = (a - b) + (a - c)

Since we know that (a - b) is even and b - c is even.

Property 1: The difference of any two even integers are even.

By Property 1, we then know that (a - b) + (a - c) is even.

Therefore the parity of 2a - (b + c) is even.

Q.E.D.

33. Given any integers a, b, and c, if a - b is odd and b - c is even, what can you say about the parity of a - c? Prove your answer.

Proof:

Suppose a, b and c are any integers where a - b is odd and b - c is even.

Note that a - c = (a - b) + (b - c)

By property 5, we know that the sum of any odd integer and even integer is odd.

Therefore the parity of a - c is odd.

Q.E.D.

34. Given any integer n, if n > 3, could n, n + 2, and n + 4 all be prime? Prove or give a counterexample.

Proof by Counterexample:

Case where n = 4:

Let n = 4.

n = 4 \ n + 2 = 6 \ n + 4 = 8

Thus for the given n n > 3, but n is not prime, n + 2 is not prime, and n + 4 is not prime. Therefore the statement is false.

Q.E.D.

Prove each of the statements in 35-43.

35. The fourth power of any integer has the form 8m or 8m + 1 for some integer m.

Proof:

Suppose n is any integer.

By the quotient remainder theorem, n can be written as

n = 4q \text{ or} \ n = 4q + 1 \text{ or} \ n = 4q + 2 \text{ or} \ n = 4q + 3 \text{ or} \

for some integer q.

Case n = 4q:

Then:

 n^4 = (4q)^4 

 \quad = 256q^4 

 \quad = 8(32q^4) 

Let m = 32q^4 where m is an integer by the product of integers.

Thus n^4 is in the form 8m.

Case n = 4q + 1:

Then:

 n^4 = (4q + 1)^4 

 \quad = 256q^4 + 256q^3 + 96q^2 + 16q + 1 

 \quad = 8(32q^4 + 32q^3 + 12q^2 + 2q) + 1 

Let m = 32q^4 + 32q^3 + 12q^2 + 2q where m is an integer by the product and sum of integers.

Thus n^4 is in the form 8m + 1.

Case n = 4q + 2:

Then:

 n^4 = (4q + 2)^4 

 n^4 = 256q^4 + 512q^3 + 384q^2 + 128q + 16 

 n^4 = 8(32q^4 + 64q^3 + 48q^2 + 16q + 2) 

Let m = 32q^4 + 64q^3 + 48q^2 + 16q + 2 where m is an integer by the product and sum of integers.

Thus n^4 is in the form 8m.

Case n = 4q + 3:

Then:

 n^4 = (4q + 3)^4 

 \quad = 256q^4 + 768q^3 + 864q^2 + 432q + 81 

 \quad = (256q^4 + 768q^3 + 864q^2 + 432q + 80) + 1 

 \quad = 8(32q^4 + 96q^3 + 108q^2 + 54q + 8) + 1 

Let m = 32q^4 + 96q^3 + 108q^2 + 54q + 8 where m is an integer by the product and sum of integers.

Thus n^4 is in the form 8m + 1.

In all cases, the fourth power of any integer has the form 8m or 8m + 1 for some integer m.

Q.E.D.

36. The product of any four consecutive integers is divisible by 8.

Proof:

Suppose n is any integer.

By the quotient remainder theorem, n can be represented as:

n = 4q \text{ or} \ n = 4q + 1 \text{ or} \ n = 4q + 2 \text{ or} \ n = 4q + 3 \text{ or} \

Case n = 4q:

 n(n + 1)(n + 2)(n + 3) = (4q)(4q + 1)(4q + 2)(4q + 3) 

 \quad = 256q^4 + 384q^3 + 176q^2 + 24q 

 \quad = 8(32q^4 + 48q^3 + 22q^2 + 3q) 

Let m = 32q^4 + 48q^3 + 22q^2 + 3q where m is an integer by the product and sum of integers.

Then 8 \mid n(n + 1)(n + 2)(n + 3).

Case n = 4q + 1:

 n(n + 1)(n + 2)(n + 3) = ((4q + 1))((4q + 1) + 1)((4q + 1) + 2)((4q + 1) + 3) 

 \quad = 256q^4 + 640q^3 + 560q^2 + 200q + 24 

 \quad = 8(32q^4 + 80q^3 + 70q^2 + 25q + 3) 

Let m = 32q^4 + 80q^3 + 70q^2 + 25q + 3 where m is an integer by the product and sum of integers.

Then 8 \mid n(n + 1)(n + 2)(n + 3).

Case n = 4q + 2:

 n(n + 1)(n + 2)(n + 3) = ((4q + 2))((4q + 2) + 1)((4q + 2) + 2)((4q + 2) + 3) 

 \quad = 256q^4 + 896q^3 + 1136q^2 + 616q + 120 

 \quad = 8(32q^4 + 112q^3 + 142q^2 + 77q + 15) 

Let m = 32q^4 + 112q^3 + 142q^2 + 77q + 15 where m is an integer by the product and sum of integers.

Then 8 \mid n(n + 1)(n + 2)(n + 3).

Case n = 4q + 3:

 n(n + 1)(n + 2)(n + 3) = ((4q + 3))((4q + 3) + 1)((4q + 3) + 2)((4q + 3) + 3) 

 \quad = 256q^4 + 1152q^3 + 1904q^2 + 1368q + 360 

 \quad = 8(32q^4 + 144q^3 + 238q^2 + 171q + 45) 

Let m = 32q^4 + 144q^3 + 238q^2 + 171q + 45 where m is an integer by the product and sum of integers.

Then 8 \mid n(n + 1)(n + 2)(n + 3).

In all cases 8 \mid n(n + 1)(n + 2)(n + 3). Therefore the product of any four consecutive integers is divisible by 8.

Q.E.D.

37. For any integer n, n^2 + 5 is not divisible by 4.

Proof:

Suppose n is any integer.

_Case n is even:

Since n is even, n = 2k for any integer k.

Then:

 n^2 + 5 = (2k)^2 + 5 

 \quad = 4k^2 + 4 + 1 

 \quad = 4(k^2 + 1) + 1 

Then (n^2 + 5) \mod 4 = 1 and n^2 + 5 is not divisible by 4.

_Case n is odd:

Since n is odd, n = 2k + 1 for any integer k.

Then:

 n^2 + 5 = (2k + 1)^2 + 5 

 \quad = (2k + 1)(2k + 1) + 5 

 \quad = 4k^2 + 4k + 1 + 5 

 \quad = 4k^2 + 4k + 6 

 \quad = 4k^2 + 4k + 4 + 2 

 \quad = 4(k^2 + k + 1) + 2 

Let m = k^2 + k + 1 where m is an integer by the product and sum of integers. Then (n^2 + 5) \mod 4 = 2 and n^2 + 5 is not divisible by 4.

In both cases, n^2 + 5 is not divisible by 4.

Q.E.D.

38. For every integer m, m^2 = 5k, or m^w = 5k + 1, or m^2 = 5k + 4 for some integer k.

Proof:

Suppose m is any integer.

By the quotient-remainder theorem, we can say m is:

m = 5q \ m = 5q + 1 \ m = 5q + 2 \ m = 5q + 3 \ m = 5q + 4 \

Case m = 5q:

 m^2 = (5q)^2 

 m^2 = 25q^2 

 m^2 = 5(5q^2) 

Let k = 5q^2, where k is any integer by the product of integers.

Then m^2 = 5k.

Case m = 5q + 1:

 m^2 = (5q + 1)^2 

 m^2 = (5q + 1)(5q + 1) 

 \quad = 25q^2 + 10q + 1 

 \quad = 5(5q^2 + 2q) + 1 

Let k = 5q^2 + 2q, where k is any integer by the product of integers.

Then m^2 = 5k + 1.

Case m = 5q + 2:

 m^2 = (5q + 2)^2 

 \quad = (5q + 2)(5q + 2) 

 \quad = 25q^2 + 20q + 4 

 \quad = 5(5q^2 + 4q) + 4 

Let k = 5q^2 + 4q, where k is any integer by the product of integers.

Then m^2 = 5k + 4.

Case m = 5q + 3:

 m^2 = (5q + 3)^2 

 \quad = (5q + 3)(5q + 3) 

 \quad = 25q^2 + 30q + 9 

 \quad = 25q^2 + 30q + 5 + 4 

 \quad = 5(5q^2 + 6q + 1) + 4 

Let k = 5q^2 + 6q + 1, where k is any integer by the product of integers.

Then m^2 = 5k + 4.

Case m = 5q + 4:

 m^2 = (5q + 4)^2 

 \quad = (5q + 4)(5q + 4) 

 \quad = 25q^2 + 40q + 16 

 \quad = 25q^2 + 40q + 15 + 1 

 \quad = 5(5q^2 + 8q + 3) + 1 

Let k = 5q^2 + 8q + 3, where k is any integer by the product of integers.

Then m^2 = 5k + 1.

In all cases, m^2 = 5k or m^2 = 5k + 1 or m^2 = 5k + 4. Therefore for every integer m, m^2 = 5k or m^2 = 5k + 1 or m^2 = 5k + 4 for some integer k.

Q.E.D.

39. Every prime number except 2 and 3 has the form 6q + 1 or 6q + 5 for some integer q.

Suppose p is any prime number where p \neq 2 and p \neq 3.

By the quotient-remainder theorem, if p were any integer, we could express p as:

p = 6q \ p = 6q + 1 \ p = 6q + 2 \ p = 6q + 3 \ p = 6q + 4 \ p = 6q + 5 \

But since p is a prime number that is not 2 and not 3, this narrows us down to:

p = \cancel{6q} \text{ even, not prime} \ p = 6q + 1 \ p = \cancel{6q + 2} \text{ even not prime} \ p = \cancel{6q + 3} \text{ divisible by 3, not prime} \ p = \cancel{6q + 4} \text{ even not prime} \ p = 6q + 5 \

Therefore, every prime number p except 2 and 3 has the form 6q + 1 or 6q + 5.

Q.E.D.

40. If n is any odd integer, then n^4 \mod 16 = 1.

Proof:

Suppose n is any odd integer.

Sine n is odd, n = 2k + 1 for any integer k.

Then:

 n^4 = (2k + 1)^4 

 \quad = (2k + 1)(2k + 1)(2k + 1)(2k + 1) 

 \quad = 16k^4 + 32k^3 + 24k^2 + 8k + 1 

 \quad = 16k^4 + 32k^3 + 16k^2 + 8k^2 + 8k + 1 

 \quad = 16(k^4 + 2k^3 + k^2) + 8k^2 + 8k + 1 

 n^4 \mod 16 = 8k^2 + 8k + 1 (\mod 16) 

 = 8(k^2 + k) + 1 (\mod 16) 

 = 8(k(k + 1)) + 1 (\mod 16) 

Note here that k(k + 1) is even as the product of two consecutive products is even. Therefore k(k + 1) = 2m for some integer m$.

 = 8(2m) + 1 (\mod 16) 

 = 16m + 1 (\mod 16) 

 n^4 \mod 16 = 1 

Q.E.D.

41. For all real numbers x and y, |x| \cdot |y| = |xy|.

Proof:

Suppose x and y are any real numbers.

Case x < 0 and y < 0:

 |x| = -x \text{ by the definition of absolute value} 

 |y| = -y \text{ by the definition of absolute value} 

 |x| \cdot |y| = -x \cdot -y = xy 

Then:

 |xy| = xy 

Since x and y are both negative, their product xy is positive.

Therefore:

 |x| \cdot |y| = |xy| 

Case x \geq 0 and y < 0:

 |x| = x 

 |y| = -y 

 |x| \cdot |y| = x \cdot -y = -xy 

Since x is nonnegative and y is negative, xy \leq 0.

Therefore:

 |xy| = -xy 

So,

 |x| \cdot |y| = |xy| 

Case x < 0 and y \geq 0:

 |x| = -x 

 |y| = y 

 |x| \cdot |y| = -xy 

Since x is negative and y is nonnegative, xy \leq 0.

Therefore:

 |xy| = -xy 

So,

 |x| \cdot |y| = |xy| 

Case x \geq 0 and y \geq 0:

 |x| = x 

 |y| = y 

 |x| \cdot |y| = xy 

Since x is nonnegative and y is nonnegative, xy \geq 0

 |xy| = xy 

So,

 |x| \cdot |y| = |xy| 

In all cases, |x| \cdot |y| = |xy|. Therefore for all real numbers x and y, |x| \cdot |y| = |xy|.

Q.E.D.

42. For all real numbers r and c with c \geq 0, -c \leq r \leq c if, and only if, |r| \leq c. (Hint: Proving A if, and only if, B requires proving both if A then B and if B then A.)

Suppose r and c are real numbers where c \geq 0 and -c \leq r \leq c.

Case where r < 0:

 |r| = -r 

Since we assumed that:

 -c \leq r \leq c 

Then:

 c \geq -r 

Or:

 -r \leq c 

Since:

 |r| = -r 

It follows that:

 |r| \leq c 

Case where r \geq 0:

 |r| = r 

Since we assumed that:

 -c \leq r \leq c 

Then:

 r \leq c 

Since:

 |r| = r 

It follows that:

 |r| \leq c 

Therefore |r| \leq c.

In both cases for all real numbers r and c with c \geq 0, it has been shown that if -c \leq r \leq c, then |r| \leq c.

And then suppose r and c are real numbers where c \geq 0 and |r| \leq c.

Case where r < 0:

 |r| = -r 

Since:

 |r| \leq c 

Then:

 -r \leq c 

 r \geq -c 

Or:

 -c \leq r 

Case where r \geq 0:

 |r| = r 

Since:

 |r| \leq c 

 r \leq c 

It follows from both cases then that -c \leq r \leq c.

Therefore it has been shown that for all real numbers r and c with c \geq 0, -c \leq r \leq c if, and only if, |r| \leq c.

Q.E.D.

43. For all real numbers a and b, \lvert|a| - |b|\rvert \leq |a - b|.

Omitted.

44. A matrix \mathbb{M} has 3 rows and 4 columns.

\left[\begin{array}{cccc} a_{11} & a_{12} & a_{13} & a_{14} \ a_{21} & a_{22} & a_{23} & a_{24} \ a_{31} & a_{32} & a_{33} & a_{34} \ \end{array}\right]

The 12 entries in the matrix are to be stored in row major form in locations 7,609 to 7,620 in a computer's memory. This means that the entries in the first row (reading left to right) are stored first, then the entries in the second row, and finally the entries in the third row.

a. Which location will a_{22} be stored in?

\left[\begin{array}{cccc} 7609 & 7610 & 7611 & 7612 \ 7613 & \boxed{7614} & a_{23} & a_{24} \ a_{31} & a_{32} & a_{33} & a_{34} \ \end{array}\right]

b. Write a formula (in i and j) that gives the integer n so that a_{ij} is stored in location 7,609 + n.

Row-major order means we count:

• 4 entries per row.

So before row i, there are 4(i - 1) entries.

Within row i, entry j adds j - 1.

So:

 n = 4(i - 1) + (j - 1) 

c. Find formulas (in n) for r and s so that a_{rs} is stored in location 7,609 + n.

We start from:

 n = 4(i - 1) + (j - 1) 

So:

 n + 1 = 4(i - 1) + j 

Divide:

 i = \lfloor \frac{n}{4} \rfloor + 1 

Remainder gives:

 j = (n \mod 4) + 1 

So:

 r = \lfloor \frac{n}{4} \rfloor + 1, \quad s = (n \mod 4) + 1 

45. Let \mathbb{M} be a matrix with m rows and n columns, and suppose that the entries of \mathbb{M} are stored in a computer's memory in row major form (see exercise 44) in locations N, N + 1, N + 2, \dots, N + mn - 1. Find formulas in k for r and s so that a_{rs} is stored in location N + k.

Row-major order means: Each row has n entries.

We are given location: N + k

So k counts how far into the matrix we are (starting at 0).

Row index r.

Each full row uses n positions, so

 r = \lfloor \frac{k}{n} \rfloor + 1 

Column index s.

Position inside the row is the remainder:

 s = (k \mod n) + 1 

Final answer:

 r = \lfloor \frac{k}{n} \rfloor + 1, \quad s = (k \mod n) + 1 

46. If m, n, and d are integers, d > 0 and m \mod d = n \mod d, does it necessarily follow that m = n? That m - n is divisible by d? Prove your answers.

Omitted

47. If m, n, and d are integers d > 0, and d \mid (m - n), what is the relation between m 'mod d' and n \mod d? Prove your answer.

Omitted

48. If m, n, a, b, and d are integers, d > 0 and m \mod d = a and n \mod d = b, is (m + n) \mod d = a + b? Is (m + n) \mod d = (a + b) \mod d? Prove your answers.

Omitted

49. If m, n, a, b, and d are integers, d > 0, and m \mod d = a and n \mod d = b, is (mn) \mod d = ab? Is (mn) \mod d = ab \mod d? Prove your answers.

Omitted

50. Prove that if m, d, and k are integers and d > 0, then (m + dk) \mod d = m \mod d.

Omitted

---

Exercise Set 4.6

Page 240

Compute \lfloor x \rfloor and \lceil x \rceil for each of the values of x in 1-4.

1. 37.999

\lfloor 37.999 \rfloor = 37

\lceil 37.999 \rceil = 38

2. \dfrac{17}{4}

\dfrac{17}{4} = 4 + \dfrac{1}{4} = 4.25

\lfloor \dfrac{17}{4} \rfloor = 4

\lceil \dfrac{17}{4} \rceil = 5

3. -14.00001

\lfloor -14.00001 \rfloor = -15

\lceil -14.00001 \rceil = -14

4. -\dfrac{32}{5}

-\dfrac{32}{5} = -6.4

\lfloor -\dfrac{32}{5} \rfloor = -7

\lceil -\dfrac{32}{5} \rceil = -6

5. Use the floor notation to express 259\ div\ 11 and 259 \mod 11.

 259\ div\ 11 = \lfloor \frac{259}{11} \rfloor = \lfloor 23.54545454\dots \rfloor = 23 

 259 \mod 11 = 259 - 11 \cdot \lfloor \frac{259}{11} \rfloor 

 = 259 - 11 \cdot 23 

 = 6 

6. If k is an integer, what is \lceil k \rceil? Why?

 \lceil k \rceil = k 

The ceiling of k is k. Since k is already an integer, then given the definition for ceiling:

 \lceil k \rceil = n \Leftrightarrow n - 1 < k \leq n 

We can substitute in n = k:

 k - 1 < k \leq k 

And both parts are true, so:

 \lceil k \rceil = k 

7. If k is an integer, what is \left\lceil k + \dfrac{1}{2} \right\rceil? Why?

 \left\lceil k + \frac{1}{2} \right\rceil = k + 1 

By the definition of ceiling:

 \ceil k + \dfrac{1}{2} \rceil = n \Leftrightarrow n - 1 < k + \frac{1}{2} \leq n 

Now substitute in n = k + 1:

 (k + 1) - 1 < k + \frac{1}{2} \leq k + 1 

 k < k + \frac{1}{2} \leq k + 1 

And both parts are true, so:

 \lceil k + \frac{1}{2} \rceil = k + 1 

8. Seven pounds of raw material are needed to manufacture each unit of a certain product. Express the number of units that can be produced from n pounds of raw material using either the floor or the ceiling notation. Which notation is more appropriate?

7 pounds of raw material per product is main ratio.

This means that the number of units q from n pounds can be expressed using the quotient-remainder theorem as:

 n = 7q 

Where the remainder is removed as no more units can be created from leftover raw material.

And when converted to floor notation, this is:

 q = \left\lfloor \frac{n}{7} \right\rfloor 

The reason floor is more appropriate is that leftover material would not realistically be able to be utilized to make another unit of said product.

9. Boxes, each capable of holding 36 units, are used to ship a product from the manufacturer to a wholesaler. Express the number of boxes that would be required to ship n units of the product using either the floor or the ceiling notation. Which notation is more appropriate?

Each box can hold up to 36 units of product. Shipping n units of product can be expressed using the quotient remainder theorem as:

 n = 36q + r 

Where r is the remaining products that did not fill another box.

Then we convert to ceiling notation:

 q = \left\lceil \frac{n}{36} \right\rceil 

The ceiling notation is more appropriate as even after packing all boxes full, you cannot simply not ship the remaining product, so another box filled with the remaining products is added to the shipment.

10. If 0 = Sunday, 1 = Monday, 2 = Tuesday, ..., 6 = Saturday, then January 1 of year n occurs on the day of the week given by the following formula:

 \left(n + \left\lfloor \frac{n - 1}{4} \right\rfloor - \left\lfloor \frac{n - 1}{100} \right\rfloor + \left\lfloor \frac{n - 1}{400} \right\rfloor\right) \mod 7 

a. Use this formula to find January 1 of

i. 2050

6 = Saturday

ii. 2100

5 = Friday

iii. the year of your birth.

Omitted

b. Interpret the different components of this formula.

11. State a necessary and sufficient condition for the floor of a real number to equal that number.

It is a necessary and sufficient condition for any real number, x to to satisfy \lfloor x \rfloor = x that x be an integer.

12. Let S be the statement: For any odd integer n, \left\lfloor \dfrac{n}{2} \right\rfloor = \dfrac{(n - 1)}{2}. Then S is true, but the following "proof" is incorrect. Find the mistake.

"Proof:

Suppose n is any odd integer. Then n = 2k + 1 for some integer k. Consequently,

 \left\lfloor \frac{2k + 1}{2} \right\rfloor = \frac{(2k + 1) - 1}{2} = \frac{2k}{2} = k 

But n = 2k + 1. Solving for k gives k = \dfrac{(n - 1)}{2}. Hence, by substitution, \left\lfloor \dfrac{n}{2} \right\rfloor = \dfrac{(n - 1)}{2}."

The mistake is in the initial substitution, by setting:

 \left\lfloor \frac{2k + 1}{2} \right\rfloor = \frac{(2k + 1) - 1}{2} 

The author of this proof assumes the what is to be proved.

13. Prove that if n is any even integer, then \left\lfloor \dfrac{n}{2} \right\rfloor = \dfrac{n}{2}.

Proof: Suppose n is any even integer.

Since n is an even integer, n = 2k for some integer k.

Then, by substitution:

 \left\lfloor \frac{n}{2} \right\rfloor = \left\lfloor \frac{2k}{2} \right\rfloor 

 = \left\lfloor k \right\rfloor 

Because k is an integer, and by the definition of floor, k \leq k < k + 1. We then know that:

 \lfloor k \rfloor = k 

It follows then that:

 \left \lfloor \frac{2k}{2} \right\rfloor = \frac{2k}{2} 

 \left \lfloor \frac{n}{2} \right\rfloor = \frac{n}{2} 

Q.E.D.

14. Show that the following statement is false.

For all real numbers x and y, \lfloor x - y \rfloor = \lfloor x \rfloor - \lfloor y \rfloor.

Proof by Counterexample:

Let x = \dfrac{1}{2} and y = \dfrac{3}{4}

Then:

 \lfloor x - y \rfloor = \left\lfloor \frac{1}{2} - \frac{3}{4} \right\rfloor 

 = -1 

Then consider:

 \lfloor x \rfloor - \lfloor y - \rfloor = \left\lfloor \frac{1}{2} \right\rfloor - \left\lfloor \frac{3}{4} \right\rfloor  

 = 0 - 0 

 = 0 

Thus:

 -1 \neq 0 

\lfloor x - y \rfloor \neq \lfloor x \rfloor - \lfloor y \rfloor$ $.

Therefore for the given x and y, this statement is false.

Q.E.D.

Some of the statements in 15-22 are true and some are false. Prove each true statement and find a counterexample for each false statement, but do not use Theorem 4.6.1 in your proofs.

15. For every real number x, \lfloor x - 1 \rfloor = \lfloor x \rfloor - 1.

Proof:

Suppose x is any real number.

By the definition of floor, x can then be expressed as:

 \lfloor x \rfloor \Leftrightarrow n \leq x < n + 1 

for some integer n.

Subtracting 1 from all sides of the inequality is:

 n - 1 \leq x - 1 < n 

Since n - 1 is an integer by the difference of integers, by the definition of floor:

 \lfloor x - 1 \rfloor = n - 1 

It follows by substitution then that:

 \lfloor x - 1 \rfloor = \lfloor x \rfloor - 1 

Q.E.D.

16. For every real number x, \left\lfloor x^2 \right\rfloor = \lfloor x \rfloor^2

Proof by Counterexample:

Let x = -\dfrac{1}{2}

 x^2 = \frac{1}{4} 

 \lfloor x^2 \rfloor = \lfloor \frac{1}{4} \rfloor = 0 

Now consider:

 \lfloor x \rfloor^2 = \lfloor -\frac{1}{2} \rfloor^2 = (-1)^2 = 1 

And then:

 0 \neq 1 

 \lfloor x^2 \rfloor \neq \lfloor x \rfloor^2 

Then for the given x, \lfloor x^2 \rfloor \neq \lfloor x \rfloor^2. Therefore the statement is false.

Q.E.D.

17. For every integer n,

\left\lfloor \dfrac{n}{3} \right\rfloor = \begin{cases} \dfrac{n}{3} & \text{if } n \mod 3 = 0 \ \dfrac{(n - 1)}{3} & \text{if } n \mod 3 = 1 \ \dfrac{(n - 2)}{3} & \text{if } n \mod 3 = 2 \ \end{cases}

Proof:

Suppose n is any integer.

Case where n \mod 3 = 0:

Since n \mod 3 = 0, then by the definition of mod:

Since n \mod 3 = 0, n can be written as:

 n = 3q + 0 

for some integer q by the definition of mod.

By substitution:

 \left\lfloor \frac{n}{3} \right\rfloor = \left\lfloor \frac{3q}{3} \right\rfloor 

 = \lfloor q \rfloor 

 = q \quad \text{ by the definition of floor} 

Since q = \dfrac{n}{3}:

 \left\lfloor \frac{n}{3} \right\rfloor = \frac{n}{3} 

Case where n \mod 3 = 1:

Since n \mod 3 = 1, then by the definition of mod:

Since n \mod 3 = 1, n can be written as:

 n = 3q + 1 

for some integer q by the definition of mod.

By substitution:

 \left\lfloor \frac{n}{3} \right\rfloor = \left\lfloor \frac{3q + 1}{3} \right\rfloor 

 = \left\lfloor \frac{3q}{3} + \frac{1}{3} \right\rfloor 

 = \left\lfloor q + \frac{1}{3} \right\rfloor 

 = q \quad \text{ by the definition of floor} 

Since q = \dfrac{n - 1}{3}:

 \left\lfloor \frac{n}{3} \right\rfloor = \frac{n - 1}{3} 

Case where n \mod 3 = 2:

Since n \mod 3 = 2, n can be written as:

 n = 3q + 2 

for some integer q by the definition of mod.

By substitution:

 \left\lfloor \frac{n}{3} \right\rfloor = \left\lfloor \frac{3q + 2}{3} \right\rfloor 

 = \left\lfloor \frac{3q}{3} + \frac{2}{3} \right\rfloor 

 = \left\lfloor q + \frac{2}{3} \right\rfloor 

 = q \quad \text{ by the definition of floor} 

Since q = \dfrac{n - 2}{3}:

 \left\lfloor \frac{n}{3} \right\rfloor = \frac{n - 2}{3} 

Q.E.D.

18. For all real numbers x and y, \lceil x + y \rceil = \lceil x \rceil + \lceil y \rceil.

Proof by Counterexample:

Let x = -\dfrac{1}{2} and y = -\dfrac{3}{4}.

Consider:

 \lceil x + y \rceil = \left\lceil -\frac{1}{2} + \left(-\frac{3}{4}\right) \right\rceil 

 = -1 

Then:

 \lceil x \rceil + \lceil y \rceil = \left\lceil -\frac{1}{2} \right\rceil + \left\lceil -\frac{3}{4} \right\rceil 

 = 0 + 0 

 = 0 

Then:

 -1 \neq 0 

 \lceil x + y \rceil \neq \lceil x \rceil + \lceil y \rceil 

Therefore, for the given x and y, the statement is false.

Q.E.D.

19. For every real number x, \lceil x - 1 \rceil = \lceil x \rceil - 1.

Proof:

Suppose x is any real number.

By the definition of ceiling, x can be expressed as:

 \lceil x \rceil = n \Leftrightarrow n - 1 < x \leq n 

for some integer n.

If we then subtract 1 from the inequality, we get:

 n - 2 < x - 1 \leq n - 1 

Since n - 1 is an integer by the difference of integers, by the definition of ceiling:

 \lceil x - 1 \rceil = n - 1 

It follows by substitution then that:

 \lceil x - 1 \rceil = \lceil x \rceil - 1 

Q.E.D.

20. For all real numbers x and y, \lceil xy \rceil = \lceil x \rceil \cdot \lceil y \rceil.

Proof by Counterexample:

Let x = 2 and y = \dfrac{1}{2}.

Then:

 \lceil xy \rceil = \left\lceil 2\left(\frac{1}{2}\right) \right\rceil = \lceil 1 \rceil = 1 

Then consider:

 \lceil x \rceil \cdot \lceil y \rceil = \lceil 2 \rceil \cdot \left\lceil \frac{1}{2} \right\rceil 

 = 2 \cdot 1 

 = 2 

Since:

 1 \neq 2 

Then:

 \lceil xy \rceil \neq \lceil x \rceil \cdot \lceil y \rceil 

Thus it has been shown that for at least one given x and one given y,

 \lceil xy \rceil \neq \lceil x \rceil \cdot \lceil y \rceil 

Therefore the statement is false.

Q.E.D.

21. For every odd integer n, \lceil \dfrac{n}{2} \rceil = \dfrac{(n - 1)}{2}.

Proof by Counterexample:

Let n = 1.

Consider:

 \left\lceil \dfrac{n}{2} \right\rceil = \left\lceil \dfrac{1}{2} \right\rceil 

 = 1 

Then:

 \frac{n - 1}{2} = \frac{1 - 1}{2} = \frac{0}{2} = 0 

Since 1 \neq 0:

 \left\lceil \dfrac{n}{2} \right\rceil \neq \frac{n - 1}{2} 

Thus it has been shown that there exists some value for n such that:

 \left\lceil \dfrac{n}{2} \right\rceil \neq \frac{n - 1}{2} 

Therefore the statement is false.

Q.E.D.

22. For all real numbers x and y, \lceil xy \rceil = \lceil x \rceil \cdot \lfloor y \rfloor.

Proof by Counterexample:

Let x = \dfrac{5}{4} and y = \dfrac{1}{2}.

Then:

 \lceil xy \rceil = \left\lceil \left(\frac{5}{4}\right)\left(\frac{1}{2}\right) \right\rceil 

 = 1 

Then:

 \lceil x \rceil \cdot \lfloor y \rfloor = \left\lceil \frac{5}{4} \right\rceil \cdot \left\lfloor \frac{1}{2} \right\rfloor 

 = 2 \cdot 0 = 0 

So:

 1 \neq 0 

 \lceil xy \rceil \neq \lceil x \rceil \cdot \lfloor y \rfloor 

So, it has been shown that there exists a value for x and a value for y such that:

 \lceil xy \rceil \neq \lceil x \rceil \cdot \lfloor y \rfloor 

Therefore the statement is false.

Q.E.D.

Prove each of the following statements in 23-33.

23. For any real number x, if x is not an integer, then \lfloor x \rfloor + \lfloor -x \rfloor = -1.

Suppose x is any real number where x is not an integer.

By the definition of floor, since x is not an integer, x can be expressed as:

 \lfloor x \rfloor = n \Leftrightarrow n < x < n + 1 

for n is some integer.

Note that since x is not an integer there is no "or equal to" here.

We can then multiply the inequality by -1:

 -n > -x > -n - 1 

Where -n - 1 is an integer by the product and difference of integers. Since -n - 1 is an integer, it then follows:

 \lfloor -x \rfloor = -n - 1 

 \lfloor x \rfloor + \lfloor -x \rfloor = n + (-n - 1) = -1 

Therefore:

 \lfloor x \rfloor + \lfloor -x \rfloor = -1 

Q.E.D.

24. For any integer m and any real number x, if x is not an integer, then \lfloor x \rfloor + \lfloor m - x \rfloor = m - 1.

Proof:

Suppose x is any real number where x is not an integer, and suppose m is any an integer.

Since m is an integer and x is not an integer, then m - x is not an integer by the difference of integers.

It follows then that:

 \lfloor m - x \rfloor = n \Leftrightarrow n < m - x < n + 1 

for some integer n.

Let's then subtract m from the inequality:

 n - m < -x < n + 1 - m 

And multiply the inequality by -1:

 m - n > x > m - n - 1 

Rewritten:

 m - n - 1 < x < m - n 

Since m - n - 1 is an integer, this means that:

 \lfloor x \rfloor = m - n - 1 

By substitution then:

 \lfloor x \rfloor + \lfloor m - x \rfloor = (m - n - 1) + (n) 

 \lfloor x \rfloor + \lfloor m - x \rfloor = m - 1 

Q.E.D.

25. For every real number x, \left\lfloor \dfrac{\left\lfloor \dfrac{x}{2}\right\rfloor}{2} \right\rfloor = \left\lfloor \dfrac{x}{4} \right\rfloor.

Proof:

Suppose x is any real number.

Let n = \left\lfloor \dfrac{x}{2} \right\rfloor.

Note that n is automatically an integer due to floor always outputting an integer.

By the definition of floor, since n is an integer:

 \left\lfloor \frac{x}{2} \right\rfloor = n \Leftrightarrow n \leq \frac{x}{2} < n + 1 

_Case where n is even:

Since n is even, n = 2k for some integer k.

By substitution:

 \left\lfloor \frac{x}{2} \right\rfloor = 2k \Leftrightarrow 2k \leq \frac{x}{2} < 2k + 1 

We can then multiply out our inequality:

 2(2k) \leq x < 2(2k) + 2 

 4k \leq x < 4k + 2 

We then divide by 4:

 k \leq \frac{x}{4} < k + \frac{1}{2} 

By substitution then:

 \left\lfloor \frac{x}{4} \right\rfloor = k 

_Case where n is odd:

Since n is odd, n = 2k + 1 for some integer k.

By substitution:

 \left\lfloor \frac{x}{2} \right\rfloor = 2k + 1 \Leftrightarrow 2k + 1 \leq \frac{x}{2} < (2k + 1) + 1 

We can then multiply out our inequality:

 2(2k + 1) \leq x < 2(2k + 1) + 2 

 4k + 2 \leq x < 4k + 4 

We then divide by 4:

 k + \frac{1}{2} \leq \frac{x}{4} < k + 1 

By substitution then:

 \left\lfloor \frac{x}{4} \right\rfloor = k 

Thus in both cases we have shown the given statement to be true for all real numbers x.

Q.E.D.

26. For every real number x, if x - \lfloor x \rfloor < \dfrac{1}{2} then \lfloor 2x \rfloor = 2\lfloor x \rfloor.

Suppose x is any real number where x - \lfloor x \rfloor < \dfrac{1}{2}.

 x - \lfloor x \rfloor < \frac{1}{2} 

Multiplying by 2 gets us:

 2x - 2\lfloor x \rfloor < 1 

Now add 2\lfoor x \rfloor to both sides:

 2x < 2\lfloor x \rfloor + 1 

By definition of floor \lfoor x \rfloor \leq x. Thus:

 2\lfloor x \rfloor \leq 2x 

Putting these two inequalities together shows:

 2\lfloor x \rfloor \leq 2x < 2\lfloor x \rfloor + 1 

By definition of floor, this means then that:

 \lfloor 2x \rfloor = 2\lfloor x \rfloor 

Which is what was to be shown.

Q.E.D.

27. For every real number x, if x - \lfloor x \rfloor \geq \dfrac{1}{2} then \lfloor 2x \rfloor = 2\lfloor x \rfloor + 1.

Proof:

Suppose x is any real number where x - \lfloor x \rfloor \geq \dfrac{1}{2}.

By the definition of floor, one can express some integer n such that:

 \lfloor x \rfloor = n \Leftrightarrow n \leq x < n + 1 

Then subtract n from the inequality:

 0 \leq x - n < 1 

We know that x - \lfloor x \rfloor \geq \dfrac{1}{2}.

 \frac{1}{2} \leq x - n < 1 

Multiply all sides by 2:

 1 \leq 2(x - n) < 2 

By substitution:

 \lfloor 2(x - n) \rfloor = 1 

[To get to the form we want, we have to express x as a further expression of $n$]

We can rewrite x as x = x + n - n:

Since n = \lfloor x \rfloor:

 2x = 2(n + (x - n)) 

 2x = 2n + 2(x - n) 

Then take the floor:

 \lfloor 2x \rfloor = \lfloor 2n + 2(x - n) \rfloor 

Since 2n is an integer:

 = 2n + \lfloor 2(x - n) \rfloor 

And we know that \lfloor 2(x - n) \rfloor = 1, so substitute:

 = 2n + 1 

And we know n = \lfoor x \rfloor, so substitute again:

 = 2\lfoor x \rfloor + 1 

Therefore \lfloor 2x \rfloor = 2\lfloor x \rfloor + 1.

Q.E.D.

28. For any odd integer n,

 \left\lfloor \frac{n^2}{4} \right\rfloor = \left(\frac{n - 1}{2}\right)\left(\frac{n + 1}{2}\right) 

Proof:

Suppose n is any odd integer.

Since n is odd, n = 2k + 1 for some integer k.

Then, by substitution:

 \left\lfloor \frac{n^2}{4} \right\rfloor = \left\lfloor \frac{(2k + 1)^2}{4} \right\rfloor  

 = \left\lfloor \frac{(2k + 1)(2k + 1)}{4} \right\rfloor  

 = \left\lfloor \frac{4k^2 + 4k + 1}{4} \right\rfloor  

 = \left\lfloor \frac{4k^2 + 4k}{4} + \frac{1}{4} \right\rfloor  

 = \left\lfloor k^2 + k + \frac{1}{4} \right\rfloor  

By the definition of floor, since k^2 + k is an integer:

 k^2 + k \leq k^2 + k + \frac{1}{4} < k^2 + k + 1 

It then follows that:

 = \left\lfloor k^2 + k + \frac{1}{4} \right\rfloor = k^2 + k  

Now, also by substitution:

 \left(\frac{n - 1}{2}\right)\left(\frac{n + 1}{2}\right) = \left(\frac{(2k + 1) - 1}{2}\right)\left(\frac{(2k + 1) + 1}{2}\right)  

 = \left(\frac{2k}{2}\right)\left(\frac{2k + 2}{2}\right)  

 = k(k + 1)  

 k^2 + k 

We have thus shown that the two expressions are equal:

 \left\lfloor \frac{n^2}{4} \right\rfloor = \left(\frac{n - 1}{2}\right)\left(\frac{n + 1}{2}\right) 

Q.E.D.

29. For any odd integer n,

 \left\lceil \frac{n^2}{4} \right\rceil = \frac{n^2 + 3}{4} 

Proof:

Suppose n is any odd integer.

Since n is an odd integer, n = 2k + 1 for some integer k.

Then by substitution:

 \left\lceil \frac{n^2}{4} \right\rceil = \left\lceil \frac{(2k + 1)^2}{4} \right\rceil  

 = \left\lceil \frac{(2k + 1)(2k + 1)}{4} \right\rceil  

 = \left\lceil \frac{4k^2 + 4k + 1}{4} \right\rceil  

 = \left\lceil k^2 + k + \frac{1}{4} \right\rceil  

By the definition of ceiling:

 k^2 + k < k^2 + k + \frac{1}{4} \leq k^2 + k + 1 

It then follows that

 \lceil k^2 + k + \frac{1}{4} \rceil = k^2 + k + 1 

Then by substitution:

 \frac{n^2 + 3}{4} = \frac{(2k + 1)^2 + 3}{4} 

 = \frac{(2k + 1)(2k + 1) + 3}{4} 

 = \frac{4k^2 + 4k + 1 + 3}{4} 

 = \frac{4k^2 + 4k + 4}{4} 

 = k^2 + k + 1 

Thus we have shown that these two expressions are equal.

 \left\lceil \frac{n^2}{4} \right\rceil = \frac{n^2 + 3}{4} 

Q.E.D.

30. For every integer n, \left\lfloor \dfrac{n}{2} \right\rfloor + \left\lceil \frac{n}{2} \right\rceil = n.

Proof:

Suppose n is any integer.

Case where n is even:

Since n is even, n = 2k for some integer k.

By substitution:

 \left\lfloor \frac{n}{2} \right\rfloor + \left\lceil \frac{n}{2} \right\rceil = \left\lfloor \frac{2k}{2} \right\rfloor + \left\lceil \frac{2k}{2} \right\rceil  

 = \lfloor k \rfloor + \lceil k \rceil  

Since k is an integer, then we know that:

 \lfloor k \rfloor = k \quad \text{ and } \lceil k \rceil = k 

So:

 = \lfloor k \rfloor + \lceil k \rceil = k + k = 2k = n 

Case where n is odd:

Since n is odd, n = 2k + 1 for some integer k.

By substitution:

 \left\lfloor \frac{n}{2} \right\rfloor + \left\lceil \frac{n}{2} \right\rceil = \left\lfloor \frac{2k + 1}{2} \right\rfloor + \left\lceil \frac{2k + 1}{2} \right\rceil  

 = \left\lfloor \frac{2k}{2} + \frac{1}{2} \right\rfloor + \left\lceil \frac{2k}{2} + \frac{1}{2} \right\rceil  

 = \left\lfloor k + \frac{1}{2} \right\rfloor + \left\lceil k + \frac{1}{2} \right\rceil  

By the definition of floor:

 k \leq k + \frac{1}{2} < k + 1 

So:

 \left\lfloor k + \frac{1}{2} \right\rfloor = k 

By the definition of ceiling:

 k < k + \frac{1}{2} \leq k + 1 

So:

 \left\lceil k + \frac{1}{2} \right\rceil = k + 1 

Then:

 = \left\lfloor k + \frac{1}{2} \right\rfloor + \left\lceil k + \frac{1}{2} \right\rceil = k + k + 1 

 = 2k + 1 = n 

In both cases we have shown that the given equation is true. Therefore we have shown that the given equation is true for every integer n.

Q.E.D.

31. For every integer n, \left\lfloor \dfrac{\left\lceil \dfrac{n}{2} \right\rceil}{3} \right\rfloor = \left\lfloor \dfrac{n}{6} \right\rfloor.

Omitted.

32. For every integer n, \left\lceil \dfrac{\left\lceil \frac{n}{2} \right\rceil}{3} \right\rceil = \left\lceil \dfrac{n}{6} \right\rceil

Omitted.

33. A necessary and sufficient condition for an integer n to be divisible by a nonzero integer d is that n = \left\lfloor \dfrac{n}{d} \right\rfloor \cdot d. In other words, for every integer n and nonzero integer d,

a. if d \mid n, then n = \left\lfloor \dfrac{n}{d} \right\rfloor \cdot d.

b. if n = \left\lfloor \dfrac{n}{d} \right\rfloor \cdot d then d \mid n.

Omitted.

---

Exercise Set 4.7

Page 248

1. Fill in the blanks in the following proof by contradiction that there is no least positive real number.

Proof: Suppose not. That is, suppose that there is a least positive real number x. [We must deduce (a)]. Consider the number \dfrac{x}{2}. Since x is a positive real number, \dfrac{x}{2} is also (b). In addition, we can deduce that \dfrac{x}{2} < x by multiplying both sides of the inequality 1 < 2 by c and dividing (d). Hence \dfrac{x}{2} is a positive real number that is less than the least positive real number. This is a (e). [Thus the supposition is false, and so there is no least positive real number.]

a. a contradiction

b. a positive real number.

c. x

d. both sides by 2.

e. contradiction

2. Is \dfrac{1}{0} an irrational number? Explain.

No. Since \dfrac{1}{0} is undefined, it is not a number at all.

3. Use proof by contradiction to show that for every integer n, 3n + 2 is not divisible by 3.

Proof by contradiction:

Suppose not. That is, suppose that there is an integer n, such that 3n + 2 is divisible by 3.

By definition of divisibility:

 3n + 2 = 3k 

for some integer k.

 3n + 2 = 3k 

 2 = 3k - 3n 

 3k - 3n = 2 

 3(k - n) = 2 

 k - n = \frac{2}{3} 

Now, k - n is an integer by the difference of integers, but \dfrac{2}{3} is not an integer. So k - n is an integer and is not an integer.

This is a contradiction.

Q.E.D.

4. Use proof by contradiction to show that for every integer m, 7m + 4 is not divisible by 7.

Proof by contradiction:

Suppose not. That is, suppose that there is an integer m such that 7m + 4 is divisible by 7.

By the definition of divisibility:

 7m + 4 = 7k 

for some integer k.

By the laws of algebra, this can be rewritten as:

 7m + 4 = 7k 

 7m - 7k = -4 

 7k - 7m = 4 

 7(k - m) = 4 

 k - m = \frac{4}{7} 

Now, k - m is an integer by the difference of integers, but \dfrac{4}{7} is not an integer. Therefore k - m is an integer and not an integer.

This is a contradiction.

Q.E.D.

Carefully formulate the negations of each of the statements in 5-7. Then prove each statement by contradiction.

5. There is no greatest even integer.

Negation: There is some greatest even integer.

Proof by contradiction:

Suppose not. That is, suppose there is some greatest even integer x.

Since x is an even integer, x = 2k for some integer k. Then suppose there is number y, such that y = x + 2.

By substitution:

 y = 2k + 2 

 y = 2(k + 1) 

Now, k + 1 is an integer by the sum of integers. Since y is expressed in the form of 2 \cdot (\text{an integer}), y is an integer by the product of integers and an even integer by the definition of even. Since y = x + 2, x is not the greatest even integer, since y > x and y is even. So, x is not the greatest even integer and x is the greatest even integer.

This is a contradiction.

Q.E.D.

6. There is no greatest negative real number.

Negation: There is some greatest negative real number.

Proof by contradiction:

Suppose not. That is, suppose that there is some greatest negative real number y. In other words, there exists some negative real number y such that for all negative real numbers x, y \geq x.

Let Y = \dfrac{y}{2}.

\dfrac{y}{2} > y since y is negative, Y is a negative number that is greater than y. So, y is not the greatest negative real number and y is the greatest negative real number.

This is a contradiction.

Q.E.D.

7. There is no least positive rational number.

Negation: There is some least positive rational number.

Proof by contradiction:

Suppose not. That 8s, suppose that there is some least positive rational number, y.

Since y is a rational number, y = \dfrac{a}{b} where both a and b are integers and b \neq 0.

Let Y = \dfrac{y}{2}.

By substitution:

 Y = \frac{\dfrac{a}{b}}{2} 

 Y = \frac{a}{2b} 

Now, 2b is an integer by the product of integers and 2b \neq 0 by the zero product property. Thus, Y is a rational number since both a and 2b are integers and Y has a nonzero denominator. Y < y as \dfrac{a}{2b} < \dfrac{a}{b}. Therefore y is not the least positive rational number and y is the least positive rational number.

This is a contradiction.

Q.E.D.

8. Fill in the blanks for the following proof that the difference of any rational number and any irrational number is irrational.

Proof (by contradiction):

Suppose not. That is, suppose that there exist (a) x and (b) y such that x - y is rational. By definition of rational, there exist integers a, b, c, and d with b \neq 0 and d \neq 0 so that x = c and x - y = (d). By substitution,

 \frac{a}{b} - y = \frac{c}{d} 

Adding y and subtracting \dfrac{c}{d} on both sides gives

 y = \text{(e)} \quad \text{ by substitution} 

 = \frac{ad}{bd} - \frac{bc}{bd} 

 = \frac{ad - bc}{bd} \quad \text{ by algebra} 

a. some rational number

b. some irrational number

c. \dfrac{a}{b}

d. \dfrac{c}{d}

e. \dfrac{a}{b} - \dfrac{c}{d}

f. integers

g. integers

h. zero product property

i. rational

Now both ad - bc and bd are integers and products and differences of (f) are (g). And bd \neq 0 by the (h). Hence y is a ratio of integers with a nonzero denominator, and thus y is (i) by definition of rational. We therefore have both that y is irrational and that y is rational, which is a contradiction. [Thus the supposition is false and the statement to be proved is true.]

a. When asked to prove that the difference of any irrational number and any rational number is irrational, a student began, "Suppose not. That is, suppose the difference of any irrational number and any rational number is rational." What is wrong with beginning the proof in this way? (Hint: If needed, review the answer to exercise 11 in Section 3.2.)

The problem is that the negation of a universal is an existential, and the student did not apply that. Instead the statement should be:

"Suppose not. That is, suppose the difference of some irrational number and some rational number is rational."

b. Prove that the difference of any irrational number and any rational number is irrational.

Proof by contradiction:

Suppose not. That is, suppose there is some irrational number x and some rational number y such that x - y is rational.

Since y is rational and x - y is rational, y = \dfrac{a}{b} and x - y = \dfrac{c}{d} where a b, c, and d are integers and b \neq 0 and d \neq 0.

Then by substitution:

 x - \dfrac{a}{b} = \dfrac{c}{d} 

 x = \dfrac{c}{d} - \dfrac{a}{b} 

 x = \dfrac{cb}{bd} - \dfrac{ad}{bd} 

 x = \dfrac{cb - ad}{bd} 

Now, cb - ad is an integer by the difference and product of integers. bd is an integer by the product of integers and bd \neq 0 by the zero product property. By the definition of rational numbers then, x is a rational number. Therefore, x is a rational number and an irrational number.

This is a contradiction.

Q.E.D.

10. Let S be the statement: For all positive real numbers r and s, \sqrt{r + s} \neq \sqrt{r} + \sqrt{s}. Statement S is true, but the following "proof" is incorrect. Find the mistake.

"Proof by contradiction: Suppose not, that is, suppose that for all positive real numbers r and s, \sqrt{r + s} = \sqrt{r} + \sqrt{s}. This means that the equation will be true no matter what positive real numbers are substituted for r and s. So let r = 9 and s = 16. Then r and s are positive real numbers and

 \sqrt{r + s} = \sqrt{9 + 16} = \sqrt{25} = 5 

whereas

 \sqrt{r} + \sqrt{s} = \sqrt{9} + \sqrt{16} = 3 + 4 k 7 

Since 5 \neq 7, we have that \sqrt{r + s} \neq \sqrt{r} + \sqrt{s}, which contradicts the supposition that \sqrt{r + s} = \sqrt{r} + \sqrt{s}. This contradiction shows that the supposition is false, and hence statement S is true."

The mistake the student makes is in that they do not take the proper negation of the universal statement. Instead of supposing the negation of the statement for all r and s, the student should have started with an existential quantifier of the negating statement. It should have started with:

"Suppose not. That is, suppose that there exists some positive real numbers r and s such that \sqrt{r + s} = \sqrt{r} + \sqrt{s}."

The student also then goes to provide specific number examples for r and s, which is a technique generally reserved for proof by counterexample, not contradiction. By providing a specific example for their (incorrect) universal statement, they are not even proving for all, nor are they proving there exists some. They are just proving that the negation is a contradiction for a singular example.

Let T be the statement: The sum of any two rational numbers is rational. Then T is true, but the following "proof" is incorrect. Find the mistake.

"Proof by contradiction: Suppose not. That is, suppose that the sum of any two rational numbers is not rational. This means that no matter what two rational numbers are chosen their sum is not rational. Now both 1 and 3 are rational because 1 = \dfrac{1}{1} and 3 = \dfrac{3}{1}, and so both are ratios of integers with a nonzero denominator. Hence, by supposition, the sum of 1 and 3, which is 4, is not rational. But 4 is rational because 4 = \dfrac{4}{1}, which is a ratio of integers with a nonzero denominator. Hence 4 is both rational and not rational, which is a contradiction. This contradiction shows that the supposition is false, and hence statement T is true.

The mistake the student makes is in that they do not take the proper negation of the universal statement. Instead of supposing that the sum of any two rational numbers is not rational, the student should have started with an existential quantifier of the negating statement. It should have started with:

"Suppose not. That is, suppose that there are some rational numbers x and y such that x + y is not rational."

12. Let R be the statement: The square root of any irrational number is irrational.

a. Write the negation for R.

Negation: The square root of some irrational number is rational.

b. Prove R by contradiction.

Proof by contradiction:

Suppose not. That is, suppose there is some irrational number x such that \sqrt{x} is rational.

Since \sqrt{x} is rational, \sqrt{x} = \dfrac{a}{b} where a and b are integers and b \neq 0.

Then by substitution:

 \sqrt{x} = \frac{a}{b} 

 (\sqrt{x})^2 = \left(\frac{a}{b}\right)^2 

 x = \frac{a^2}{b^2} 

Now, a^2 is an integer by the product of integers. Additionally, b^2 is an integer by the product of integers and b^2 \neq 0 by the zero product property. Thus x is a rational number. Therefore x is a rational number and x is an irrational number.

This is a contradiction.

Q.E.D.

13. Let S be the statement: The product of any irrational number and any nonzero rational number is irrational.

a. Write the negation for S.

The product of some irrational number and some nonzero rational number is rational.

b. Prove S by contradiction.

Proof by contradiction:

Suppose not. That is, suppose that there exists some irrational number x and some nonzero rational number y such that xy is rational.

Since y is a nonzero rational number, y = \dfrac{a}{b} where a and b are integers and a \neq 0 and b \neq 0. Since xy is rational, xy = \dfrac{c}{d} where c and d are integers and d \neq 0.

Then, by susbstitution:

 xy = x\left(\frac{a}{b}\right) = \frac{c}{d} 

 x\left(\frac{a}{b}\right) = \frac{c}{d} 

 x = \frac{c}{d}\left(\frac{b}{a}\right) 

 x = \frac{cb}{ad} 

Now, cd is an integer by the product of integers. Additionally, ad is an integer by the product of integers and ad \neq 0 by the zero product property. Thus, x is a rational number. Therefore x is a rational number and x is an irrational number.

This is a contradiction.

Q.E.D.

14. Let T be the statement: For every integer a, if a \mod 6 = 3 , then a \mod 3 \neq 2.

a. Write a negation for T.

Negation: For some integer a, a \mod 6 = 3 and a \mod 3 = 2.

b. Prove T by contradiction.

Proof by contradiction:

Suppose not. That is, suppose for some integer a, a \mod 6 = 3 and a \mod 3 = 2.

Since a \mod 6 = 3, then by the quotient remainder theorem:

 a = 6q + 3 

for some integer q.

 a = 6q + 3 

Then, since a \mod 3 = 2, then by the quotient remainder theorem:

 a = 3s + 2 

for some integer s.

  6q + 3 = 3s + 2 

  6q - 3s = 2 - 3 

  3(2q - s) = -1 

  (2q - s) = -\frac{1}{3} 

Now, 2q - s is an integer by the product and difference of integers, but -\dfrac{1}{3} is not an integer. So 2q - s is an integer and 2q - s is not an integer.

This is a contradiction.

Q.E.D.

15. Do there exists integers a, b, and c such that a, b, and c are all odd and a^2 + b^2 = c^2? Prove your answer.

Proof by contradiction:

Suppose not. That is, suppose that there exist odd integers a, b, and c such that a^2 + b^2 = c^2.

Since a and b are odd, a = 2m + 1, b = 2n + 1 for some integers m and n.

By substitution:

 a^2 = (2m + 1)^2 = 4m^2 + 4m + 1 = 4m(m + 1) + 1 

 b^2 = (2n + 1)^2 = 4n^2 + 4n + 1 = 4n(n + 1) + 1 

Therefore:

 a^2 \equiv 1 (\mod 4), b^2 \equiv 1 (\mod 4) 

Adding these congruences leaves:

 a^2 + b^2 \equiv 1 + 1 \equiv 2 (\mod 4) 

So the left hand satisfies:

 a^2 + b^2 \equiv 2 (\mod 4) 

Now, consider c. Since c is odd, c = 2k + 1 for some integer k.

Then by substitution:

 c^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 4k(k + 1) + 1 

So:

 c^2 \equiv 1 (\mod 4) 

But we were given a^2 + b^2 = c^2, so this implies:

 a^2 + b^2 = c^2 (\mod 4) 

This is,

 2 \equiv 1 (\mod 4) 

This is impossible.

This is a contradiction.

Q.E.D.

Prove each statement in 16-19 by contradiction.

16. For all odd integers a and b, b^2 - a^2 \neq 4. (Hint: b^2 - a^2 = (b + a)(b - a) and the only way to factor 4 is either 4 = 2 \cdot 2 or 4 = 4 \cdot 1.)

Proof by contradiction:

Suppose not. That is, suppose that there exists some odd integers a and b such that b^2 - a^2 = 4.

Consider:

 b^2 - a^2 = (b + a)(b - a) = 4 

By the sum and difference of integers, both b + a and b - a are integers. The only integers where 4 is factored by are 2 \cdot 2 and 1 \cdot 4.

Thus there are only some cases to consider:

Case (b + a) = 2 and (b - a) = 2:

 b + a = b - a 

 b = b - 2a 

 b - b = -2a 

 0 = -2a 

 a = 0 

Since a = 0, a is an even integer. Therefore a is an even integer and a is an odd integer. This is a contradiction.

Case (b + a) = 4 and (b - a) = 1:

 b + a = 4 

 b = 4 - a 

 b - a = 1 

By substitution:

 b - (4 - a) = 1 

 b - 4 + a = 1 

 b + a = 5 

So, b + a = 5 and b + a = 4. This is a contradiction.

Case (b + a) = 1 and (b - a) = 4:

 b + a = 1 

 b = 1 - a 

By substitution:

 b - a = 4 

 b - (1 - a) = 4 

 b - 1 + a = 4 

 b + a = 5 

So b + a = 1 and b + a = 5. This is a contradiction.

In all cases, this is a contradiction.

Q.E.D.

17. For all prime numbers a, b, and c, a^2 + b^2 \neq c^2.

Proof by contradiction:

Suppose not. That is, suppose that for some prime numbers a, b, and c, a^2 + b^2 = c^2.

Consider that:

 a^2 + b^2 = c^2 

 a^2 = c^2 - b^2 

 a^2 = (c - b)(c + b) 

Since a, b, and c, are prime. By the unique prime factorization of integers theorem, the only possible values for c - b and c + b are:

 a^2 = (a^2)(1) = (c - b)(c + b) 

 a^2 = (1)(a^2) = (c - b)(c + b) 

 a^2 = (a)(a) = (c - b)(c + b) 

Let's check these cases:

_Case c - b = a^2 and c + b = 1:

Add:

 (c - b) + (c + b) = a^2 + 1 

 2c = a^2 + 1 

 c = \frac{a^2 + 1}2 

Subtract:

 (c - b) - (c + b) = a^2 - 1 

 -2b = a^2 - 1 

 b = -\frac{a^2 - 1}{2} 

 b = \frac{1 - a^2}{2} 

Now, a, b, and c are prime number, but checking for small prime(s) shows:

 a = 2 

 c = \frac{(2)^2 + 1}2 

 c = \frac{5}2 

 b = \frac{1 - a^2}{2} 

 b = \frac{1 - (2)^2}{2} 

 b = -\frac{3}{2} 

So b and c are not prime numbers and b and c are not prime numbers. This is a contradiction.

_Case c - b = a and c + b = a:

Add:

 (c - b) + (c + b) = a + a 

 2c = 2a 

 c = a 

Subtract:

 (c - b) - (c - b) = a - a 

 -2b = 0 

 b = 0 

So, b is a prime number and b is not a prime number. This is a contradiction.

_Case c - b = 1 and c + b = a^2:

Add:

 (c - b) + (c + b) = 1 + a^2 

 2c = 1 + a^2 

 c = \frac{1 + a^2}{2} 

Subtract:

 (c + b) - (c - b) = 1 - a^2 

 c - b - c - b = 1 - a^2 

 -2b = 1 + a^2 

 b = -\frac{1 - a^2}{2} 

 b = \frac{a^2 + 1}{2} 

Now, a, b, and c are prime number, but checking for small prime(s) shows:

 a = 2 

 b = \frac{(2)^2 + 1}{2} 

 b = \frac{5}{2} 

 c = \frac{1 + (2)^2}{2} 

 c = \frac{5}{2} 

So b and c are not prime numbers and b and c are prime numbers. This is a contradiction.

In all cases, this is a contradiction.

Q.E.D.

18. If a and b are rational numbers, b \neq 0, and r is an irrational number, then a + br is irrational.

Proof by contradiction:

Suppose not. That is, suppose that a and b are rational numbers, b \neq 0, and r is an irrational number and a + br is rational.

Since a, b and a + br are rational numbers, a = \dfrac{u}{t}, b = \dfrac{v}{w}, a + br = \dfrac{x}{y} where u, t, v, w, x and y are integers and t \neq 0, v \neq 0, w \neq 0, and y \neq 0.

Then by substitution:

 a + br = \frac{x}{y} = \left(\frac{u}{t}\right) + \left(\frac{v}{w}\right)r 

 \frac{x}{y} = \left(\frac{u}{t}\right) + \left(\frac{v}{w}\right)r 

 \frac{x}{y} - \left(\frac{u}{t}\right) = \left(\frac{v}{w}\right)r 

 \frac{xt}{ty} - \left(\frac{uy}{ty}\right) = \left(\frac{v}{w}\right)r 

 \frac{xt - uv}{ty} = \left(\frac{v}{w}\right)r 

 \left(\frac{xt - uv}{ty}\right)\left(\frac{w}{v}\right) = r 

 \frac{w(xt - uv)}{tyv} = r 

Now w(xt - uv) is an integer by the product and difference of integers. Additionally, tyv is an integer by the product of integers and tyv \neq 0 by the zero product property. Thus, by the definition of rational numbers, r is rational. Therefore r is rational and r is irrational.

This is a contradiction.

Q.E.D.

19. For any integer n, n^2 - 2 is not divisible by 4.

Proof by contradiction:

Suppose not. That is, suppose there exists an integer n, such that n^2 - 2 is divisible by 4.

Since n^2 - 2 is divisible by 4, then (n^2 - 2) \equiv 0 (\mod 4).

Case n is odd:

Since n is odd, n = 2k + 1 for some integer k.

Then:

 n^2 - 2 = (2k + 1)^2 - 2 

 = 4k^2 + 4k + 1 - 2 

 = 4k^2 + 4k - 1 

 = 4(k^2 + k) - 1 

 4(k^2 + k) - 1 \equiv -1 (\mod 4) 

So (n^2 - 2) \equiv -1 (\mod 4) and (n^2 - 2) \equiv 0 (\mod 4). This is a contradiction.

Case n is even:

Since n is even, n = 2k for some integer k.

Then:

 n^2 - 2 = (2k)^2 - 2 

 = 4k^2 - 2 

 = 4(k^2) - 2 

 4(k^2) - 2 \equiv -2 (\mod 4) 

So (n^2 - 2) \equiv -2 (\mod 4) and (n^2 - 2) \equiv 0 (\mod 4). This is a contradiction.

In all cases, this is a contradiction.

Q.E.D.

By definition of divisibility, there exists an integer k so that b = ak.

20. Fill in the blanks in the following proof by contraposition that for every integer n, if 5 \cancel{\mid} n^2 then 5 \cancel{\mid} n.

Proof (by contraposition): [The contrapositive is: For every integer n, if 5 \mid n then 5 \mid n^2.] Suppose n is any integer such that (a). [We must show that (b).] By definition of divisibility, n = c for some integer k. By substitution, n^2 = (d) = 5(5k^2). But 5k^2 is an integer because it is a product of integers. Hence n^2 = 5 \cdot (\text{an integer}), and so (e) [as was to be shown].

a. 5 \mid n

b. 5 \mid n^2

c. 5k

d. (5k)^2

e. 5 \mid n^2

21. Consider the statement "For every integer n, if n^2 is odd then n is odd."

a. Write what you would suppose and what you would need to show to prove this statement by contradiction.

Supposition: Suppose that for some integer n, n^2 is odd and n is even.

Consequent: Show that n^2 is even, a contradiction.

b. Write what you would suppose and what you would need to show to prove this statement by contraposition.

Supposition: Suppose that n is any even integer.

Consequent: Show that n^2 is even.

22. Consider the statement "For every real number r, if r^2 is irrational then r is irrational."

a. Write what you would suppose and what you would need to show to prove this statement by contradiction.

Supposition: Suppose there is some real number r such that r^2 is irrational and r is rational.

Consequent: Show that r^2 is rational, a contradiction.

b. Write what you would suppose and what you would need to show to prove this statement by contraposition.

Supposition: Suppose r is any real number such that r is rational.

Consequent: Show that r^2 is rational.

Prove each of the statements in 23-25 in two ways: (a) by contraposition and (b) by contradiction.

23. The negative of any irrational number is irrational.

a.

Proof by contraposition:

Suppose x is any number such that -x is rational.

Since -x is rational, -x = \dfrac{a}{b} where a and b are some integers and b \neq 0.

Then by substitution:

 -x = \dfrac{a}{b} 

 x = -\dfrac{a}{b} 

 x = \dfrac{-a}{b} 

Now, -a is an integer by the product of integers.

Therefore x is a rational number.

Q.E.D.

b.

Proof by contradiction:

Suppose not, That is, suppose x is some irrational number and -x is rational.

Since -x is rational, -x = \dfrac{a}{b} where a and b are some integers and b \neq 0.

Then, by algebra:

 -x = \dfrac{a}{b} 

 x = -\dfrac{a}{b} 

 x = \dfrac{-a}{b} 

Now, -a is an integer by the product of integers. Therefore x is a rational number and x is an irrational number.

This is a contradiction.

Q.E.D.

24. The reciprocal of any irrational number is irrational. (The reciprocal of a nonzero real number x is \dfrac{1}{x}.)

a.

Proof by contraposition:

Suppose x is any number such that \dfrac{1}{x} is rational.

Since \dfrac{1}{x} is a rational number, \dfrac{1}{x} = \dfrac{a}{b} where a and b are some integers and b \neq 0.

Then by substitution:

 \frac{1}{x} = \frac{a}{b} 

 x = \frac{b}{a} 

It has been established that b is an integer. It has also been established that a is an integer, and since \dfrac{1}{x} is rational, it follows that a \neq 0.

Therefore x is a rational number.

Q.E.D.

b.

Proof by contradiction:

Suppose not. That is suppose there is an irrational number x such that \dfrac{1}{x} is rational.

Since \dfrac{1}{x} is a rational number, \dfrac{1}{x} = \dfrac{a}{b} where a and b are some integers and b \neq 0.

Then by substitution:

 \frac{1}{x} = \frac{a}{b} 

 x = \frac{b}{a} 

It has been established that b is an integer. It has also been established that a is an integer, and since \dfrac{1}{x} is rational, it follows that a \neq 0.

Therefore x is a rational number and x is an irrational number.

This is a contradiction.

Q.E.D.

25. For every integer n, if n^2 is odd then n is odd.

a.

Proof by contraposition:

Suppose n is any integer such that n is even.

Since n is even, n = 2k for some integer k.

Then by substitution:

 n^2 = (2k)^2 

 = 4k^2 

 = 2(2k^2) 

Now, 2k^2 is an integer by the product of integers.

Therefore n^2 is even by the definition of even.

b.

Proof by contradiction:

Suppose not. That is, suppose that n is some integer such that n^2 is odd and n is even.

Since n is even, n = 2k for some integer k.

Then by substitution:

 n^2 = (2k)^2 

 = 4k^2 

 = 2(2k^2) 

Now, 2k^2 is an integer by the product of integers. Therefore n^2 is even and n^2 is odd.

This is a contradiction.

Q.E.D.

Use any method to prove the statements in 26-29.

26. For all integers a, b, and c, if a \cancel{\mid} bc then a \cancel{\mid} b.

Proof by contraposition:

Suppose a, b, and c are any integers such that a \mid b.

Since a \mid b, by the definition of divisiblity, b = ak for some integer k.

Then by substitution:

 bc = (ak)c 

 = a(kc) 

Now, kc is an integer by the product of integers. Since bc = a(kc), it follows that a \mid a(kc).

Therefore a \mid bc by definition of divisibility.

27. For all positive real numbers r and s, \sqrt{r + s} \neq \sqrt{r} + \sqrt{s}.

Proof by contradiction:

Suppose not. That is, suppose that for some positive real numbers r and s, \sqrt{r + s} = \sqrt{r} + \sqrt{s}.

 \sqrt{r + s} = \sqrt{r} + \sqrt{s} 

 (\sqrt{r + s})^2 = (\sqrt{r} + \sqrt{s})^2 

 r + s = (\sqrt{r} + \sqrt{s})(\sqrt{r} + \sqrt{s}) 

 r + s = (\sqrt{r})^2 + 2(\sqrt{r})(\sqrt{s}) + (\sqrt{s})^2 

 r + s = r + 2\sqrt{r}\sqrt{s} + s 

 0 = 2\sqrt{r}\sqrt{s} 

 0 = \sqrt{r}\sqrt{s} 

By the zero product property, either \sqrt{r} or \sqrt{s} must be 0, which means that either r = 0 or s = 0.

Case where r = 0:

If r = 0, then r is both 0 and a positive real number. This is a contradiction.

Case where s = 0:

If s = 0, then s is both 0 and a positive real number. This is a contradiction.

In both cases, this is a contradiction.

Q.E.D.

28. For all integers a, b, and c, if a \mid b and a \cancel{\mid} c, then a \cancel{\mid} (b + c).

Proof by contradiction:

Suppose not. That is, suppose that a, b, and c are some integers such that a \mid b, a \cancel{\mid} c and a \mid (b + c).

Since a \mid (b + c) and a \mid b, then b + c = ak and b = am for some integers k and m.

Then by substitution:

 (am) + c = ak 

 am + c = ak 

 c = ak - am 

 c = a(k - m) 

Now, k - m is an integer by the difference of integers. Thus by the definition of divisibility, a \mid c. Therefore a \mid c and a \cancel{\mid} c.

This is a contradiction.

Q.E.D.

29. For all integers m and n, if m + n is even then m and n are both even or m and n are both odd.

Proof by contradiction:

Suppose not. That is, suppose that m and n are some integers such that m + n is even and either m is even and n is odd or m is odd and n is even.

Case where m is even and n is odd:

Since m is even and n is odd, then m = 2k and n = 2p + 1 for some integers k and p.

Then by substitution:

 m + n = (2k) + (2p + 1) 

 = 2k + 2p + 1 

 = 2(k + p) + 1 

Now, k + p is an integer by the sum of integers. Thus m + n is odd by the definition of odd integers. Therefore m + n is odd and m + n is even.

This is a contradiction.

Case where m is odd and n is even:

Since m is odd and n is even, then m = 2k + 1 and n = 2p for some integers k and p.

Then by substitution:

 m + n = (2k + 1) + (2p) 

 = 2k + 2p + 1 

 = 2(k + p) + 1 

Now, k + p is an integer by the sum of integers. Thus m + n is odd by the definition of odd integers. Therefore m + n is odd and m + n is even.

This is a contradiction.

In both cases, this is a contradiction.

Q.E.D.

a. Let n = 53. Find an approximate value for \sqrt{n} and write a list of all the prime numbers less than or equal to \sqrt{n}. Is the following statement true or false? When n = 53, n is not divisible by any prime number less than or equal to \sqrt{n}.

 \sqrt{53} \approx 7.280109889 

All prime numbers \leq \sqrt{n}:

 \{2, 3, 5, 7\} 

Yes this is true, as when 53 is divided by any of these prime numbers in this set, the result does not equal an integer.

b. Suppose n is a fixed integer. Let S be the statement, "n is not divisible by any prime number less than or equal to \sqrt{n}." The following statement is equivalent to S:

\forall prime number p, if p is less than or equal to \sqrt{n} then n is not divisible by p.

Which of the following are negations for S?

(i) \exists a prime number p such that p \leq \sqrt{n} and n is divisible by p.

Yes, this is a negation for S.

(ii) n is divisible by every prime number less than or equal to \sqrt{n}.

No, this is not a negation for S.

(iii) \exists a prime number p such that p is a multiple of n and p is less than or equal to \sqrt{n}.

No, this is not a negation for S.

(iv) n is divisible by some prime number that is less than or equal to \sqrt{n}.

Yes, this is a negation for S.

(v) \forall prime number p, if p is less than or equal to \sqrt{n}, then n is divisible by p.

No, this is not a negation for S.

a. Prove by contraposition: For all positive integers n, r, and s, if rs \leq n, then r \leq \sqrt{n} or s \leq \sqrt{n}. (Hint: Use Theorem T27 in Appendix A.)

Proof by contraposition:

Suppose n, r, and s are some positive integers such that r > \sqrt{n} and s > \sqrt{n}.

Theorem T27 States:

If 0 < a < c and 0 < b < d, then 0 < ab < cd.

With a = \sqrt{n}, b = \sqrt{n}, c = r, and d = s, it follows that:

If 0 < \sqrt{n} < r and 0 < \sqrt{n} < s, then 0 < \sqrt{n}\sqrt{n} < rs.

Therefore rs > n.

Q.E.D.

b. Prove: For each integer n > 1, if n is not prime then there exists a prime number p such that p \leq \sqrt{n} and n is divisible by p. (Hint: Use the results of part (a), Theorems 4.4.1, 4.4.3, and 4.4.4, and the transitive property of order.)

Omitted.

c. State the contrapositive of the result of part (b). The results of exercise 31 provide a way to test whether an integer is prime.

Omitted.

Test for Primality

Given an integer n > 1, to test whether n is prime check to see if it is divisible by a prime number less than or equal to its square root. If it is not divisible by any of these numbers, then it is prime.

32. Use the test for primality to determine whether the following numbers are prime or not.

a. 667

b. 557

c. 527

d. 613

33. The sieve of Eratosthenes, named after its inventor, the Greek scholar Eratosthenes (276-194 B.C.E.), provides a way to find all prime numbers less than or equal to some fixed number n. To construct it, write out all the integers from 2 to n. Cross out all multiples of 2 except 2 itself, then all multiples of 3 except 3 itself, then all multiples of 5 except 5 itself, and so forth. Continue crossing out the multiples of each successive prime number up to \sqrt{n}. The numbers that are not crossed out are all the prime numbers from 2 to n. Here is a sieve of Eratosthenes that includes the numbers from 2 to 27. The multiples of 2 are crossed out with a /, the multiples of 3 with a , and the multiples of 5 with a -.

See image on Page 250.

Use the sieve of Eratosthenes to find all prime numbers less than 100.

34. Use the test for primality and the result of exercise 33 to determine whether the following numbers are prime.

a. 9,269

b. 9,103

c. 8,623

d. 7,917

35. Use proof by contradiction to show that every integer greater than 11 is a sum of two composite numbers.

36. For all odd integers a, b, and c, if z is a solution of ax^2 + bx + c = 0 then z is irrational. (In the proof, use the properties of even and odd integers that are listed in Example 4.3.3.)

---

Page 256

Exercise Set 4.8

1. A calculator display shows that \sqrt{2} = 1.414213562. Because 1.414213562 = \dfrac{1414213562}{1000000000}, this suggests that \sqrt{2} is a rational number, which contradicts Theorem 4.8.1. Explain the discrepancy.

The reason for this discrepancy is due to mistaking \sqrt{2} \approx 1.41.4213562 for \sqrt{2} = 1.414213562. The calculator cannot display \sqrt{2} finitely as it is an irrational number and its non-repeating decimal goes on forever. Therefore, you cannot find equivalencies for 1.414213562 and express \sqrt{2} as a rational number as it is "demonstrated" here.

2. Example 4.3.1(h) illustrates a technique for showing that any repeating decimal number is rational. A calculator display shows the result of a certain calculation as 40.72727272727. Can you be sure that the result of the calculation is a rational number? Explain.

Yes. The reason you can be sure that the result of the calculation is a rational number is because repeating decimal places can always be expressed as a rational number usually by subtracting the repeating decimal places from a larger number with the same repeating decimal places. For the given example:

Let x = 40.72727272727 \dots, so 100x = 4072.727272727 \dots. Then:

 100x - x = 99x = 4072.727272727\dots - 40.72727272727\dots = 4032 

 99x = 4032  

 x = \frac{4032}{99} 

Which is an expression for 40.72727272727 in rational form.

3. Could there be a rational number whose first trillion digits are the same as the first trillion digits of \sqrt{2}? Explain.

Yes, because the first trillion digits of \sqrt{2} is potentially finite. In that case it is rational. In another case where the first trillion digits are then repeated, then we know by 4.3.1(h) that this form of a decimal is also rational. Similarly, if even smaller portions of those first trillion digits are then repeated, this same principle applies.

4. A calculator display shows that the result of a certain calculation is 0.2. Can you be sure that the result of the calculation is a rational number?

Yes. Since the decimal 0.2 has a finite amount of decimal places, we can simply express it as a fraction:

Let x = 0.2 and 10x = 2.

Then:

 10x = 2 

 x = \frac{2}{10} 

 x = \frac{1}{5} 

Where 1 and 5 are integers and 5 \neq 0. This is a rational number.

5. Let s be the statement: The cube root of every irrational number is irrational. This statement is true, but the following "proof" is incorrect. Explain the mistake.

"Proof (by contradiction):

Suppose not. Suppose the cube root of every irrational number is rational. But 2\sqrt{2} is irrational because it is a product of a rational and an irrational number, and the cube root of 2\sqrt{2} is \sqrt{2}, which is irrational. This is a contradiction, and hence it is not true that the cube root of every irrational number is rational. Thus the statement to be proved is true."

This incorrect proof has two problems. One is that in its supposition, the wording suggests that the cube root of every irrational number is rational, when the negation of the given statement would be that "Suppose the cube root of some irrational number is rational."

The author of this incorrect proof then goes onto use a specific example of 2\sqrt{2} for their proof. While this is fine for a disproof by counterexample, a proof by contradiction should be more general. It should instead read as:

Proof by contradiction:

Suppose not. Suppose the cube root of some irrational number x, is rational.

Since the cube root of x is rational, this means that \sqrt[3]{x} = \dfrac{a}{b} for some integers a and b where b \neq 0.

Then, by laws of algebra:

 \sqrt[3]{x} = \frac{a}{b} 

 x = \left(\frac{a}{b}\right)^3 

 x = \frac{a^3}{b^3} 

Now, a^3 and b^3 are integers by the product of integers, where b^3 \neq 0 by the zero product property. Thus x is a rational number and an irrational number.

This is a contradiction.

Q.E.D.

Determine which statements in 6-16 are true and which are false. Prove those that are true and disprove those that are false.

6. 6 - 7\sqrt{2} is irrational.

Proof by contradiction:

Suppose not. Suppose 6 - 7\sqrt{2} is rational. Then by definition of rational,

 6 - 7\sqrt{2} = \frac{a}{b} 

For some integers a and b where b \neq 0.

It follows that:

 6 - 7\sqrt{2} = \frac{a}{b} 

 -7\sqrt{2} = \frac{a}{b} - 6 

 \sqrt{2} = \frac{6 - \dfrac{a}{b}}{7} 

 \sqrt{2} = \frac{6b - a}{7b} 

Now, since 6b - a and 7b are integers by the product and difference of integers and 7b \neq 0 by the zero product property. This means that \sqrt{2} is rational. The \sqrt{2}, however, is known to not be rational by Theorem 4.8.1.

This is a contradiction.

Q.E.D.

7. 3\sqrt{2} - 7 is irrational.

Proof by contradiction:

Suppose not. Suppose \sqrt{2} - 7 is rational.

Since \sqrt{2} - 7 is rational, \sqrt{2} - 7 = \dfrac{a}{b} for some integers a and b where b \neq 0.

Then, by laws of algebra:

 \sqrt{2} - 7 = \frac{a}{b} 

 \sqrt{2} = \frac{a}{b} + 7 

 \sqrt{2} = \frac{a + 7b}{b} 

Now, a + 7b is an integer by the product and sum of integers. Thus \sqrt{2} is rational. We know, however, by Theorem 4.8.1 that \sqrt{2} is irrational.

This is a contradiction.

Q.E.D.

8. \sqrt{4} is irrational.

This is false. \sqrt{4} = 2 = \dfrac{2}{1}, which is rational.

9. \dfrac{\sqrt{2}}{6} is irrational.

Proof by contradiction:

Suppose not. Suppose \dfrac{\sqrt{2}}{6} is rational. Then by the definition of rational:

 \frac{\sqrt{2}}{6} = \frac{a}{b} 

for some integers a and b where b \neq 0.

Then, by laws of algebra:

 \sqrt{2} = \frac{6a}{b} 

Now, 6a is an integer by the product of integers. Thus \sqrt{2} is a rational number. We know by Theorem 4.8.1 that \sqrt{2} is irrational.

This is a contradiction.

Q.E.D.

10. The sum of any two irrational numbers is irrational.

Proof by counterexample:

Let a = \sqrt{2}, and let b = -\sqrt{2}. Then, their sum is:

 a + b = \sqrt{2} + (-\sqrt{2}) = 0 = \frac{0}{1} 

Which is rational. This statement is false.

Q.E.D.

11. The difference of any two irrational numbers is irrational.

Proof by counterexample:

Let a = \sqrt{2}, and let b = \sqrt{2}. Then, their sum is:

 a + b = \sqrt{2} - \sqrt{2}) = 0 = \frac{0}{1} 

Which is rational. This statement is false.

Q.E.D.

12. The positive square root of a positive irrational number is irrational.

 \forall x \in \mathbb{R} (I(x) \to I(\sqrt{x})) 

Contrapositive:

 \forall x \in \mathbb{R} (\neg I(\sqrt{x}) \to \neg I(x)) 

 \forall x \in \mathbb{R} (R(\sqrt{x}) \to R(x)) 

Proof by contraposition:

Suppose r is any positive real number such that \sqrt{r} is rational.

Since \sqrt{r} is rational, \sqrt{r} = \dfrac{a}{b} where a and b are integers and b \neq 0.

Then:

 \sqrt{r} = \frac{a}{b} 

 r = \left(\frac{a}{b}\right)^2 

 r = \frac{a^2}{b^2} 

Now, a^2 and b^2 are both integers by the product of integers and b^2 \neq 0 by the zero product property.

Therefore r is a rational number.

Q.E.D.

13. If r is any rational number and s is any irrational number, then \dfrac{r}{s} is irrational.

Proof by counterexample:

Let r = 0 and s = \sqrt{2}, then \dfrac{r}{s} = \dfrac{0}{\sqrt{2}} = 0 = \dfrac{0}{1} which is rational.

Therefore, this statement is false.

Q.E.D.

14. The sum of any two positive irrational numbers is irrational.

Proof by counterexample:

Let x = \sqrt{2} and y = 2 - \sqrt{2}, then:

 x + y = \sqrt{2} + (2 - \sqrt{2}) = 2 = \dfrac{2}{1} 

Thus, x + y is a rational number.

Therefore, this statement is false.

Q.E.D.

15. The product of two irrational numbers is irrational.

Proof by counterexample:

 \sqrt{2} \cdot \sqrt{2} = (\sqrt{2})^2 = 2 = \frac{2}{1} 

Which is a rational number.

This statement is false.

Q.E.D.

16. If an integer greater than 1 is a perfect square, then its cube root is irrational.

Proof by counterexample:

Consider 64 = 8^2, then 64 > 1 and 64 is a perfect square. Then consider \sqrt[3]{64} = 4 = \dfrac{4}{1}. Thus \sqrt[3]{64} is rational.

Thus there is at least one integer greater than 1 that is a perfect square and its cube root is rational.

This statement is false.

Q.E.D.

17. Consider the following sentence: If x is rational then \sqrt{x} is irrational. Is this sentence always true, sometimes true and sometimes false, or always false? Justify your answer.

This statement is sometimes true and sometimes false. Consider when x = 2, then \sqrt{2} is irrational. This is the case when the statement is true. Then consider when x = 9 then \sqrt{9} = 3 = \dfrac{3}{1} is rational.. This is a case when the statement is false. Therefore this statement is sometimes true and sometimes false.

a. Prove that for every integer a, if a^3 is even then a is even.

Proof by contrapositive:

Suppose a is any integer such that a is odd.

Since a is odd, a = 2k + 1 for some integer k.

Then:

 a^3 = (2k + 1)^3 

 a^3 = 8k^3 + 12k^2 + 6k + 1 

 a^3 = 2(4k^3 + 6k^2 + 3k) + 1 

Now, 4k^3 + 6k^2 + 3k is an integer by the product and sum of integers. Therefore a^3 is odd by definition of odd integers.

Q.E.D.

b. Prove that \sqrt[3]{2} is irrational.

Proof by contradiction:

Suppose not. That is, suppose \sqrt[3]{2} is rational. Then, by definition of rational:

 \sqrt[3]{2} = \frac{a}{b} 

for some integers a and b where b \neq 0 and \dfrac{a}{b} is written in lowest terms.

Then:

 \sqrt[3]{2} = \frac{a}{b} 

 2 = \left(\frac{a}{b}\right)^3 

 2 = \frac{a^3}{b^3} 

 2b^3 = a^3 

Now, by the definition of even integers, we know that a^3 is even. We also know by part (a), that if a^3 is even, then a is even.

Since a is even, a = 2k for some integer k. Then:

 2b^3 = (2k)^3 

 2b^3 = 8k^3 

 2b^3 = 8k^3 

 b^3 = 4k^3 

 b^3 = 2(2k^3) 

Now, 2k^3 is an integer by the product of integers. Additionally, b^3 is even by the definition of even integers. Additionally, by part (a) b is even since b^3 is even.

Since both a and b and even, \sqrt[3]{2} is not in lowest terms, so \sqrt[3]{2} is not rational, which contradicts the supposition.

Q.E.D.

a. Use proof by contradiction to show that for any integer n, it is impossible for n to equal both 3q_1 + r_1 and 3q_2 + r_2, where q_1, q_2, r_1, and r_2 are integers, 0 \leq r_1 < 3, 0 \leq r_2 < 3, and r_1 \neq r_2.

Proof by contradiction:

Suppose not. That is, suppose n is some integer such n = 3q_1 + r_1 = 3q_2 + r_2, where q_1, q_2, r_1, and r_2 are some integers such that 0 \leq r_1 < 3 and 0 \leq r_2 < 3 and r_1 \neq r_2.

Then:

 3q_1 + r_1 = 3q_2 + r_2 

 3q_1 - 3q_2 = r_2 - r_1 

 3(q_1 - q_2) = r_2 - r_1 

This means that 3 \mid (r_2 - r_1).

Since 0 \leq r_1,r_2 < 3, it follows that:

 -2 \leq r_2 - r_1 \leq 2 

This means that 3 \cancel{\mid} (r_2 - r_1), which contradicts the earlier finding that 3 \mid (r_2 - r_1).

Q.E.D.

b. Use proof by contradiction, the quotient-remainder theorem, division into cases, and the result of part (a) to prove that for every integer n, if n^2 is divisible by 3 then n is divisible by 3.

Proof by contradiction:

Suppose not. That is, suppose n is some integer such that n^2 is divisible by 3 and n is not divisible by 3.

Since n is not divisible by 3, then n = 3k + 1 or n = 3k + 2 for some integer k.

Case where n = 3k + 1:

 n^2 = (3k + 1)^2 

 n^2 = 9k^2 + 6k + 1 

 n^2 = 3(3k^2 + 2k) + 1 

By the quotient-remainder theorem, this means that 3 \cancel{\mid} n^2. This contradicts the supposition.

Case where n = 3k + 2:

 n^2 = (3k + 2)^2 

 n^2 = 9k^2 + 12k + 4 

 n^2 = 9k^2 + 12k + 3 + 1 

 n^2 = 3(3k^2 + 4k + 1) + 1 

By the quotient-remainder theorem, this means that 3 \cancel{\mid} n^2. This contradicts the supposition.

In both cases, the supposition is contradicted.

Q.E.D.

c. Prove that \sqrt{3} is irrational.

Proof by contradiction:

Suppose not. Suppose that \sqrt{3} is rational.

Since \sqrt{3} is rational, \sqrt{3} = \dfrac{a}{b} for some integers a and b where b \neq 0 and \dfrac{a}{b} is in lowest terms.

Then:

 \sqrt{3} = \frac{a}{b} 

 3 = \left(\frac{a}{b}\right)^2 

 3 = \frac{a^2}{b^2} 

 3b^2 = a^2 

This means that 3 \mid a^2. By part (b), we then know that 3 \mid a. This means that a = 3k for some integer k. Then:

 3b^2 = (3k)^2 

 3b^2 = 9k^2 

 b^2 = 3k^2 

This means that 3 \mid b^2. Then, however, \dfrac{a}{b} is not in lowest terms since 3 \mid a and 3 \mid b. This is a contradiction.

Q.E.D.

20. Give an example to show that if d is not prime and n^2 is divisible by d, then n need not be divisible by d.

We need to find a non prime number d and a real number n such that:

 d \mid n^2 

 d \cancel{\mid} n 

Let d = 4 and n = 2.

Then:

 4 \mid 4 

 4 \cancel{\mid} 2 

21. The quotient-remainder theorem says not only that there exist quotients and remainders but also that the quotient and remainder of a division are unique. Prove the uniqueness. That is, prove that if a and d are integers with d > 0 and if q_1, r_1, q_2, and r_2 are integers such that

 a = dq_1 + r_1 \quad \text{ where } 0 \leq r_1 < d 

and

 a = dq_2 + r_2 \quad \text{ where } 0 \leq r_2 < d 

then

 q_1 = q_2 \quad \text{ and } r_1 = r_2 

Proof:

Suppose a, d are any integers and q_1, q_2, r_1, and r_2 are some integers such that a = dq_1 + r_1 where 0 \leq r_1 < d and a = dq_2 + r_2 where 0 \leq r_2 < d.

Then:

 dq_1 + r_1 = dq_2 + r_2 

 dq_1 - dq_2 = r_2 - r_1 

 d(q_1 - q_2) = r_2 - r_1 

Since 0 \leq r_1,r_2 < d, this means that:

 -(d - 1) \leq r_2 - r_1 \leq d - 1 

And this means:

 |r_2 - r_1| < d 

Since d(q_1 - q_2) = r_2 - r_1 means d \mid (r_2 - r_1), but we also know that |r_2 - r_1| < d, then it follows that r_2 - r_1 = 0. Thus, it then follows that r_1 = r_2

Then by substitution:

 d(q_1 - q_2) = r_2 - r_1 

 q_1 - q_2 = 0 

Thus it follows that q_1 = q_2.

Therefore, it has been shown that q_1 = q_2 and r_1 = r_2.

Q.E.D.

22. Prove that \sqrt{5} is irrational.

Lemma 22:

If 5 divides a^2, then 5 divides a.

Proof by contradiction:

Suppose not, that is suppose a is some integer such that 5 \mid a^2 and 5 \cancel{\mid} a.

Since 5 \cancel{\mid} a, this means that a = 5q + r for some unique integers q and r, such that 1 \leq r < 5.

Then, by substitution:

 a^2 = (5q + r)^2 

 a^2 = 25q^2 + 10qr + r^2 

 a^2 = 5(5q^2 + 2qr) + r^2 

So:

 a^2 \equiv r^2 (\mod 5) 

Then by cases:

 r = 1 \to r^2 (\mod 5) = 1 

 r = 2 \to r^2 (\mod 5) = 4 

 r = 3 \to r^2 (\mod 5) = 4 

 r = 4 \to r^2 (\mod 5) = 1 

So in all cases r^2 \cancel{\equiv} 0 (\mod 5)

Therefore 5 \cancel{\mid} a^2, which contradicts the supposition.$

Q.E.D.

Proof by contradiction:

Suppose not. Suppose that \sqrt{5} is rational.

Since \sqrt{5} is rational, \sqrt{5} = \dfrac{a}{b} for some integers a and b where b \neq 0 and \dfrac{a}{b} is in lowest terms.

Then:

 \sqrt{5} = \frac{a}{b} 

 5 = \left(\frac{a}{b}\right)^2 

 5 = \frac{a^2}{b^2} 

 5b^2 = a^2 

Thus we know that 5 \mid a^2, and by Lemma 22, we then know that 5 \mid a.

So, since 5 \mid a, a = 5k for some integer k.

Then by substitution:

 5b^2 = (5k)^2 

 5b^2 = 25k^2 

 b^2 = 5k^2 

So then we know that 5 \mid b^2, and by Lemma 22, we then know that 5 \mid b. Then, however, \dfrac{a}{b} is not in lowest terms. Therefore \sqrt{5} is irrational, which contradicts the supposition.

Q.E.D.

23. Prove that for any integer a, 9 \cancel{\mid} (a^2 - 3).

Hint: This statement is true. If a^2 - 3 = 9b, then a^2 = 9b + 3 = 3(3b + 1), and so a^2 is divisible by 3. Hence, by exercise 19(b), a is divisible by 3. Thus a^2 =(3c)^2 for some integer c.

Proof by contradiction:

Suppose not. That is, suppose that for some integer a, 9 \mid (a^2 - 3).

Since 9 \mid (a^2 - 3), then a^2 - 3 = 9b for some integer b. This then becomes:

 a^2 - 3 = 9b 

 a^2 = 9b + 3 

 a^2 = 3(3b + 1) 

So 3 \mid a^2, by 9(b), we then know that 3 \mid a. Since 3 \mid a, a = 3c for some integer c. By substitution:

 (3c)^2 = 3(3b + 1) 

 9c^2 = 3(3b + 1) 

 3c^2 = 3b + 1 

 3c^2 - 1 = 3b 

But since 3 \cancel{\mid} 3c^2 - 1 and 3 \mid 3b, this statement can never hold for b and c. This is a contradiction.

Q.E.D.

24. An alternative proof of the irrationality of \sqrt{2} counts the number of $2$'s on the two sides of the equation 2n^2 = m^2 and uses the unique factorization of integers theorem to deduce a contradiction. Write a proof that uses this approach.

Statement: \sqrt{2} is irrational.

Proof by contradiction:

Suppose not. That is, suppose \sqrt{2} is rational. Then there are some integers m and n where n \neq 0 such that:

 \sqrt{2} = \frac{m}{n} 

where \dfrac{m}{n} have no common factors. Then:

 \sqrt{2} = \frac{m}{n} 

 2 = \frac{m^2}{n^2} 

 2n^2 = m^2 

By the unique factorization theorem, we can express n as the product of prime numbers as:

 n = 2^a \cdot p_1^{e_1} \dots \cdot p_k^{e_k} 

Then, we can express n^2 as:

 n^2 = 2^{2a} 

Since the exponent is even, we know the number of 2s in n^2 is even. It then follows that 2n^2 adds one more 2:

 2n^2 = 2^{2a + 1} 

So 2n^2 has an odd number of $2$s.

We can then apply the same logic to m^2.

 m = 2^b \cdot p_1^{e_1} \dots \cdot p_q^{e_q} 

 m^2 = 2^{2b} 

So m^2 has an even number of $2$s. Thus 2n^2 has an odd number of $2$s and m^2 has an even number of $2$s, which contradicts the statement 2n^2 = m^2.

Q.E.D.

25. Use the proof technique illustrated in exercise 24 to prove that if n is any positive integer that is not a perfect square, then \sqrt{n} is irrational.

Proof by contradiction:

Suppose not. That is, suppose n is some positive integer such that n is not a perfect square and \sqrt{n} is rational.

Since \sqrt{n} is rational, \sqrt{n} = \dfrac{a}{b} for some integers a and b, where b \neq 0 and where \dfrac{a}{b} is in lowest terms.

Then:

 \sqrt{n} = \frac{a}{b} 

 n = \left(\frac{a}{b}\right)^2 

 n = \frac{a^2}{b^2} 

 nb^2 = a^2 

By the unique factorization theorem, a can be written as a product of prime numbers:

 a = p_1^{e_1}p_2^{e_2} \cdot \dots \cdot p_k^{e_k} 

And:

 a^2 = p_1^{2e_1}p_2^{2e_2} \cdot \dots \cdot p_k^{2e_k} 

This means that all prime exponents in a^2 are even.

Similarly:

 b = q_1^{f_1}q_2^{f_2} \cdot \dots \cdot q_m^{f_m} 

And:

 b^2 = q_1^{2e_1}q_2^{2e_2} \cdot \dots \cdot q_k^{2e_m} 

This means that all prime exponents in b^2 are even.

Since nb^2 = a^2, all prime exponents in nb^2 are even since all the prime exponents in a^2 are even. Therefore n is a perfect square

This contradicts the supposition that n is not a perfect square.

Q.E.D.

26. Prove that \sqrt{2} + \sqrt{3} is irrational.

Proof by contradiction:

Suppose not. That is suppose that \sqrt{2} + \sqrt{3} is rational.

Since \sqrt{2} + \sqrt{3} is rational, then \sqrt{2} + \sqrt{3} = \dfrac{a}{b} where a and b are some integers and b \neq 0 and \dfrac{a}{b} has no common factors.

Then, by substitution:

 \sqrt{2} + \sqrt{3} = \frac{a}{b} 

 \left(\sqrt{2} + \sqrt{3}\right)^2 = \left(\frac{a}{b}\right)^2 

 \left(\sqrt{2} + \sqrt{3}\right)\left(\sqrt{2} + \sqrt{3}\right) = \frac{a^2}{b^2} 

 2 + 2\sqrt{2}\sqrt{3} + 3 = \frac{a^2}{b^2} 

 2\sqrt{6} + 5 = \frac{a^2}{b^2} 

 2\sqrt{6} = \frac{a^2}{b^2} - 5 

 \sqrt{6} = \frac{\dfrac{a^2}{b^2} - 5}{2} 

 \sqrt{6} = \frac{a^2 - 5b^2}{2b^2} 

By the proof given in exercise 25, we know that \sqrt{6} is irrational.

Now, a^2 - 5b^2 is an integer by the product and difference of integers. Also 2b^2 is an integer by the product of integers and 2b^2 \neq 0 by the zero product property.

Therefore \sqrt{6} is a rational number which contradicts what we derived from the proof given in exercise 25 that \sqrt{6} is irrational.

Q.E.D.

27. Prove that \log_5(2) is irrational. (Hint: Use the unique factorization of integers theorem.)

Omitted.

28. Let N = 2 \cdot 3 \cdot 5 \cdot 7 + 1. What remainder is obtained when N is divided by 2?$3$?$5$?$7$? Justify your answer.

 N = 2(3 \cdot 5 \cdot 7) + 1 

 N \mod 2 = 1 

 N = 3(2 \cdot 5 \cdot 7) + 1 

 N \mod 3 = 1 

 N = 5(2 \cdot 3 \cdot 7) + 1 

 N \mod 5 = 1 

 N = 7(2 \cdot 3 \cdot 5) + 1 

 N \mod 7 = 1 

29. Suppose a is an integer and p is a prime number such that p \mid a and p \mid (a + 3). What can you deduce about p? Why?

Since p \mid a and p \mid (a + 3), then p \mid ((a + 3) - a). It follows then that p \mid 3, and the only prime number that divides 3 is 3 itself.

 p = 3 

30. Let p_1, p_2, p_3, \dots be a list of all prime numbers in ascending order. Here is a table of the first six:

p_1	p_2	p_3	p_4	p_5	p_6
2	3	5	7	11	13

a. Let N_1 = p_1, N_2 = p_1 \cdot p_2, N_3 = p_1 \cdot p_2 \cdot p_3, \dots N_6 = p_1 \cdot p_2 \cdot p_3 \cdot p_4 \cdot p_5 \cdot p_6. Calculate N_1, N_2, N_3, N_4, N_5, and N_6.

N_1	N_2	N_3	N_4	N_5	N_6
2	6	30	210	2310	30030

b. For each i = 1, 2, 3, 4, 5, 6, find whether N_i is itself prime or just has a prime factor less than itself. (Hint: Use the test for primality from exercise 31 in Section 4.7 to determine your answers.)

Test for Primality

Given an integer n > 1, to test whether n is prime check to see if it is divisible by a prime number less than or equal to its square root. If it is not divisible by any of these numbers, then it is prime.

N_1 is prime.

N_2 is not prime.

N_3 is not prime.

N_4 is not prime.

N_5 is not prime.

N_6 is not prime.

For exercises 31 and 32, use the fact that for ever integer n,

 n! = n(n - 1) \dots 3 \cdot 2 \cdot 1 

31. An alternative proof of the infinitude of the prime numbers begins as follows:

Proof: Suppose there are only finitely many prime numbers. Then one is the largest. Call it p. Let M = p! + 1. We will show that there is a prime number q such that q > p. Complete this proof.

Proof by contradiction:

Suppose not. That is suppose there are only finitely many prime numbers. Then one is the largest. Call it p. Let M = p! + 1.

Let q be a prime number such that q \leq p.

Since q \leq p, q \mid p!. This means that:

 p! \equiv 0 (\mod q) 

It then follows that:

 M = p! + 1 \equiv 1 (\mod q) 

So, q \cancel{\mid} M.

Since q is a prime number that cannot divide M, either M is prime itself or M has a prime factor greater than p, which contradicts the supposition.

Q.E.D.

We will show that there is a prime number q such that q > p.

32. Prove that for every integer n, if n > 2 then there is a prime number p such that n < p < n!.

Omitted.

33. Prove that if p_1, p_2, \dots, and p_n are distinct prime numbers with p_1 = 2 and n > 1, then p_1, p_2, \dots, p_n + 1 can be written in the form 4k + 3 for some integer k.

Omitted.

a. Fermat's last theorem says that for every integer n > 2, the equation x^n + y^n = z^n has no positive integer solution (solution for which x, y, and z are positive integers). Prove the following: If for every prime number p > 2, x^p + y^p = z^p has no positive integer solution, then for any integer n > 2 that is not a power of 2, x^n + y^n = z^n has no positive integer solution.

Omitted.

b. Fermat proved that there are no integers x, y, and z such that x^4 + y^4 = z^4. Use this result to remove the restriction in part (a) that n not be a power of 2. That is, prove that if n is a power of 2 and n > 4, then x^n + y^n = z^n has no positive integer solution.

Omitted.

For exercises 35-38 note that to show there is a unique object with a certain property, show that (1) there is an object with the property and (2) if objects A and B have the property, then A = B.

35. Prove that there exists a unique prime number of the form n^2 - 1, where n is an integer that is greater than or equal to 2.

Omitted.

36. Prove that there exists a unique prime number of the form n^2 + 2n - 3, where n is a positive integer.

Omitted.

37. Prove that there is at most one real number a with the property that a + r = r for every real number r. (Such a number is called an additive identity.)

Omitted.

38. Prove that there is at most one real number b with the property that br = r for every real number r. (Such a number is called a multiplicative identity.)

Omitted.

---

Exercise Set 4.9

Page 265

In 1 and 2 find the degree of each vertex and the total degree of the graph. Check that the number of edges equals one-half of the total degree.

1. See page 265.

\text{deg(v_1)} = 3

\text{deg(v_2)} = 2

\text{deg(v_3)} = 4

\text{deg(v_4)} = 2

\text{deg(v_5)} = 1

\text{deg(v_6)} = 0

\text{deg}(\text{total}) = 12

\text{total edges} = 6

2. See page 265.

\text{deg(v_1)} = 1

\text{deg(v_2)} = 5

\text{deg(v_3)} = 4

\text{deg(v_4)} = 4

\text{deg(v_5)} = 1

\text{deg(v_6)} = 3

\text{deg}(\text{total}) = 18

\text{total edges} = 9

3. A graph has vertices of degrees 0, 2, 2, 3, and 9. How many edges does the graph have?

 \frac{1}{2}(0 + 2 + 2 + 3 + 9) = 8 \text{ edges} 

4. A graph has vertices of degrees 1, 1, 4, 4, and 6. How many edges does the graph have?

 \frac{1}{2}(1 + 1 + 4 + 4 + 6) = 8 \text{ edges} 

In each of 5-13 either draw a graph with the specified properties or explain why no such graph exists.

5. Graph with five vertices of degrees 1, 2, 3, 3, and 5.

6. Graph of four vertices of degrees 1, 2, 3, and 3.

Not possible. It has an odd number of total degrees, 9. By 4.9.2, the total degree of a graph must be even.

7. Graph with four vertices of degrees 1, 1, 1, and 4.

Not possible. It has an odd number of total degrees, 7. By 4.9.2, the total degree of a graph must be even.

8. Graph with four vertices of degrees 1, 2, 3, and 4.

9. Simple graph with four vertices of degrees 1, 2, 3, and 4.

No such graph. The vertex of degree 4 would have to be connected by edges to 4 distinct vertices other than itself. This is not possible in a simple graph since it cannot loop back on itself.

10. Simple graph with five vertices of degrees 2, 3, 3, 3, and 5.

Not possible, as the vertex of degree 5 would have to loop back on itself in a graph of 5 vertices, which contradicts the definition of a simple graph.

11. Simple graph with five vertices of degrees 1, 1, 1, 2, and 3.

12. Simple graph with six edges and all vertices of degree 3.

13. Simple graph with nine edges and all vertices of degree 3.

14. At a party attended by a group of people, two people knew one other person before the party, and five people knew two other people before the party. The rest of the people knew three other people before the party. A total of 15 pairs of people knew each other before the party.

a. How many people attending the party knew three other people before the party?

 (2 \cdot 1) + (5 \cdot 2) + 3x = 2 + 10 + 3x = 12 + 3x 

 12 + 3x = 2(15) 

 12 + 3x = 30 

 3x = 18 

 \boxed{x = 6} 

b. How many people attended the party?

 2 + 5 + 6 = \boxed{13} 

15. A small social network contains three people who are network friends with six other people in the network, one person who is network friend with five other people in the network, and five people who are network friends with four other people in the network. The rest are network friends with three other people in the network. The network contains 41 pairs of network friends.

a. How many people are network friends with three other people in the network?

 (3 \cdot 6) + (1 \cdot 5) + (5 \cdot 4) + 3x = 41(2) 

 43 + 3x = 82 

 3x = 39 

 \boxed{x = 13} 

b. How many people are in the network?

 3 + 1 + 5 + 13 = \boxed{22} 

a. In a group of 15 people, is it possible for each person to have exactly 3 friends? Justify your answer. (Assume that friendship is a symmetric relationship: If x is a friend of y, then y is a friend of x.)

Proof by contradiction:

Suppose that, in a group of 15 people, each person had exactly three friends. Then you could draw a graph representing each person by a vertex and connecting two vertices by an edge if the corresponding people were friends. But such a graph would have 15 vertices, each of degree 3, for a total of 45. This would contradict the fact that the total degree of any graph is even. Hence the supposition must be false, and in a group of 15 people it is not possible for each to have exactly three friends.

b. In a group of 4 people, is it possible for each person to have exactly 3 friends? Justify your answer.

Proof:

Suppose that, in a group of 4 people, each person has exactly 3 friends. Then you could draw a graph representing each person by a vertex and connecting two vertices by an edge if the corresponding people were friends. Such a graph would have 4 vertices, each of degree 3, for a total of 12. The total degree is even, and therefore it is possible for each person to have exactly 3 friends.

17. In a group of 25 people, is it possible for each to shake hands with exactly 3 other people? Justify your answer.

No 25 \cdot 3 = 75 is odd number of total degrees.

18. Is there a simple graph, each of whose vertices has even degree? Justify your answer.

Yes, a minimum number of vertices would be 3. Each vertex would have a degree of 2 that would reach out to the other two vertices.

19. Suppose that G is a graph with v vertices and e edges and that the degree of each vertex is at least d_{\text{min}} and at most d_{\text{max}}. Show that

 \frac{1}{2}d_{\text{min}} \cdot v \leq e \leq \frac{1}{2}d_{\text{max}} \cdot v 

Proof:

Let e be the total number of edges, let t be the total degree of the graph, let d_{\text{min}} be the minimum degree of any vertex in G, and let d_{\text{max}} be the maximum degree of any vertex in G.

The total degree of G is greater than or equal to the minimum degree times the total amount of vertices.

 d_{\text{min}} \cdot v \leq t  

Also the total degree of G is less than or equal to the maximum degree times the total amount of vertices.

 d_{\text{min}} \cdot v \leq t \leq d_{\text{max}} \cdot v 

The total degree of G is 2e.

 d_{\text{min}} \cdot v \leq 2e \leq d_{\text{max}} \cdot v 

 \frac{1}{2}d_{\text{min}} \cdot v \leq e \leq \frac{1}{2}d_{\text{max}} \cdot v 

a. Draw K_6, a complete graph on six vertices.

b. Use the result of Example 4.9.9 to show that the number of edges of a simple graph with n vertices is less than or equal to \dfrac{n(n - 1)}{2}.

Prove that for any positive integer n, the number of edges of a simple graph with n vertices is less than or equal to \dfrac{n(n - 1)}{2}.

Proof:

Suppose n and e are any positive integers such that a simple graph K_n has n vertices and e edges.

By Example 4.9.9, we know the number of edges of a complete graph, K_m is:

 \text{the number of edges of } K_m = \frac{m(m - 1)}{2} 

A simple graph is a graph that does not have any loops or parallel edges, while a complete graph is a simple graph with m vertices and exactly one edge connecting each pair of distinct vertices.

It follows then that the total number of edges for the simple graph K_n could only have at most the total number of edges for a complete graph of n vertices.

Therefore we have proven that:

 e \text{ for } K_n \leq \frac{n(n - 1)}{2} 

Q.E.D.

a. In a simple graph, must every vertex have degree that is less than the number of vertices in the graph? Why?

Yes. Let G be a simple graph with n vertices and let v be a vertex of G. Since G has no parallel edges, v can be joined by at most a single edge to each of the n - 1 other vertices of G, and since G has no loops, v cannot be joined to itself. Therefore, the maximum degree of v is n - 1.

b. Can there be a simple graph that has four vertices all of different degrees? Why?

No. Suppose there is a simple graph with four vertices, all of which have different degrees. By part (a), no vertex can have a degree greater than three, and of course, no vertex can have a degree less than 0. Therefore, the only possible degrees of the vertices are 0, 1, 2, and 3. Since all four vertices have different degrees, there is one vertex with each degree. But then the vertex of degree 3 is connected to all other vertices, which contradicts the fact that one of the vertices has degree 0. Hence the supposition is false, and there is no simple graph with four vertices each of which has a different degree.

c. For any integer n \geq 5, can there be a simple graph that has n vertices all of different degrees? Why?

No, let n be an integer such that n \geq 5, and let G be a simple graph with n vertices. By part (a) no vertex can have a degree greater than n - 1. Since n \geq 5, then n - 1 \geq 4. Therefore the only possible degrees of the vertices are 0, 1, \dots, n - 1.

Since there are n vertices and n possible degree values, each degree must occur exactly once. In particular there must be a vertex of degree 0 and a vertex of degree n - 1.

However, a vertex of degree n - 1 is adjacent to every other vertex in the graph, including the vertex of degree 0. This contradicts the fact that a vertex of degree 0 is adjacent to no vertices.

22. In a group of two or more people, must there always be at least two people who are acquainted with the same number of people within the group? Why?

Yes.

Let the group contain n \geq 2 people. Model the situation with a simple graph G where each person is represented by a vertex. Two vertices are connected by an edge if the corresponding people are acquainted.

Then the degree of a vertex is the number of people in the group that person is acquainted with.

By Exercise 21, a simple graph with n vertices cannot have all n vertices of different degrees. Equivalently, there must be at least two vertices with the same degree.

Therefore, there must be at least two people who are acquainted with the same number of people within the group.

23. Recall that K_{m, n} denotes a complete bipartite graph on (m, n) vertices.

a. Draw K_{4, 2}.

b. Draw K_{1, 3}.

c. Draw K_{3, 4}.

d. How many vertices of K_{m, n} have degree m? degree n?

Vertices that have degree m are all vertices in \{n\}.

Vertices that have degree n are all vertices in \{m\}.

e. What is the total degree of K_{m, n}?

 (m \cdot n) + (n \cdot m) = 2mn 

f. Find a formula in terms of m and n for the number of edges of K_{m, n}. Justify your answer.

 e = mn 

Justification omitted.

24. A (general) bipartite graph G is a simple graph whose vertex set can be partitioned into two disjoint nonempty subsets V_1 and V_2 such that vertices in V_1 may be connected to vertices in V_2, but no vertices in V_1 and no vertices in V_2 are connected to other vertices in V_2. For example, the bipartite graph G illustrated in (i) can be redrawn as shown in (ii). From the drawing in (ii), you can see that G is bipartite with mutually disjoint vertex sets V_w = \{v_1, v_3, v_5\} and V_2 = \{v_2, v_4, v_6\}.

(i) See Page 266

(ii) See Page 266

Find which of the following graphs are bipartite. Redraw the bipartite graphs so that their bipartite nature is evident.

See Page 266.

25. Suppose r and s are any positive integers. Does there exist a graph G with the property that G has vertices of degrees r and s and no other degrees? Explain.

Omitted.

---

Exercise Set 4.10

Page 278

Find the value of z when each of the algorithm segments in 1 and 2 is executed.

i := 2\\ \text{\textbf{if }} (i > 3 \text{ or } i \leq 0)\\ \ \ \ \ \text{\textbf{then }} z := 1\\ \ \ \ \ \text{\textbf{else }} z := 0

z = 0

i := 3\\ \text{\textbf{if }} (i \leq 3 \text{ or } i > 6)\\ \ \ \ \ \text{\textbf{then }} z := 2\\ \ \ \ \ \text{\textbf{else }} z := 0

z = 2

3. Consider the following algorithm segment:

\text{\textbf{if }} x \cdot y > 0 \text{\textbf{ then do }} y := 3 \cdot x\\ \ \ \ \ x := x + 1 \text{\textbf{end do}}\\ \ \ \ \ z := x \cdot y

Find the value of z if prior to execution x and y have the values given below.

a. x = 2, y = 3

y = 3 \cdot 3 = 9, and x = 2 + 1 = 3, and z = 9 \cdot 3 \cdot = 27

b. x = 1, y = 1

y = 3 \cdot 1 = 3, and x = 1 + 1 = 2, and z = 3 \cdot 2 = 6

Find the values of a and e after execution of the loops in 4 and 5 by first making trace tables for them.

a := 2\\ \text{\textbf{for }} i := 1 \text{\textbf{ to }} 3\\ \ \ \ \ a:= 3a + 1\\ \text{\textbf{next }} i

	0	1	2	3
a	2	7	22	67
i	1	2	3	4

After execution, a = 67.

e := 2, f := 0\\ \text{\textbf{for }} k := 1 \text{\textbf{ to }} 3\\ \ \ \ \ e := e \cdot k\\ \ \ \ \ f := e + f\\ \text{\textbf{next }} k

	0	1	2	3
e	2	2	4	12
f	0	2	6	18
k	1	2	3	4

After execution, e = 12, f = 18.

Make a trace table to trace the action of Algorithm 4.10.1 for the input variables given in 6 and 7.

6. a = 26, d = 7

	0	1	2	3
a	26	26	26	26
d	7	7	7	7
r	26	19	12	5
q	0	1	2	3

After execution, q = 3, and r = 5.

7. a = 59, d = 13

	0	1	2	3	4
a	59	59	59	59	59
d	13	13	13	13	13
r	59	46	33	20	7
q	0	1	2	3	4

After execution, q = 4, r = 7.

8. The following algorithm segment makes change; given an amount of money A between 1¢ and 99¢, it determines a breakdown of A into quarters (q), dimes (d), nickels (n), and pennies (p).

q := A \text{div } 25 \ A := A \mod 25 \ d := A \text{div } 10 \ A := A \mod 10 \ n := A \text{div } 5 \ p := A \mod 5

a. Trace this algorithm segment for A = 69.

A	69	19	9
q	2
d		1
n			1
p				4

b. Trace this algorithm segment for A = 87.

A	87	12	2
q	3
d		1
n			0
p				0

Find the greatest common divisor of each of the pairs of integers in 9-12. (Use any method you wish.)

9. 27 and 72

 \text{gcd}(27, 72) = 9 

10. 5 and 9

 \text{gcd}(5, 9) = 1 

11. 7 and 21

 \text{gcd}(7, 21) = 7 

12. 48 and 54

 \text{gcd}(54, 48) = \text{gcd}(48, 6) = \text{gcd}(6, 0) = 6 

Use the Euclidean algorithm to hand-calculate the greatest common divisors of each of the pairs of itnegers in 13-16.

13. 1,188 and 385

 \text{gcd}(1188, 385) = \text{gcd}(385, 33) = \text{gcd}(33, 22) = \text{gcd}(22, 11) = \text{gcd}(11, 0) = 11 

14. 509 and 1,177

 \text{gcd}(1177, 509) = \text{gcd}(509, 159) = \text{gcd}(159, 32) = \text{gcd}(32, 31) = \text{gcd}(31, 1) = \text{gcd}(1, 0) = 1 

15. 832 and 10,933

 \text{gcd}(10933, 832) = \text{gcd}(832, 117) = \text{gcd}(117, 13) = \text{gcd}(13, 0) = 13 

16. 4,131 and 2,431

 \text{gcd}(4131, 2431) = \text{gcd}(2431, 1700) = \text{gcd}(1700, 731) = \text{gcd}(731, 238) = \text{gcd}(238, 17) = \text{gcd}(17, 0) = 17 

Make a trace table to trace the action of Algorithm 4.10.2 for the input variables given in 17-19.

17. 1,001 and 871

A	1001
B	871
a	1001	871	130	91	39	13
b	871	130	91	39	13	0
r	871	130	91	39	13	0
\text{gcd}							13

After execution, \text{gcd} = 13.

18. 5,859 and 1,232

A	5859
B	1232
a	5859	1232	931	301	28	21	7
b	1232	931	301	28	21	7	0
r	1232	931	301	28	21	7	0
\text{gcd}								7

After execution, \text{gcd} = 7.

19. 1,570 and 488

A	1570
B	488
a	1570	488	106	64	42	22	20	2
b	488	106	64	42	22	20	2	0
r	488	106	64	42	22	20	2	0
\text{gcd}									2

After execution, \text{gcd} = 2.

**Definition: Integers a and b are said to be relatively prime if, and only if, their greatest common divisor is 1.

In 20 and 21 trace the action of Algorithm 4.10.2 to determine whether the integers are relatively prime.

20. 4,167 and 2,563

A	4167
B	2563
a	4167	2563	1604	959	645	314	17	8	1
b	2563	1604	959	645	314	17	8	1	0
r	2563	1604	959	645	314	17	8	1	0
\text{gcd}										1

After execution, \text{gcd} = 1, and because of this, 4,167 and 2,563 are relatively prime.

21. 34,391 and 6,728

A	34391
B	6728
a	34391	6728	751	720	31	7	3	1
b	6728	751	720	31	7	3	1	0
r	6728	751	720	31	7	3	1	0
\text{gcd}									1

After execution, \text{gcd} = 1, and because of this, 34,391 and 6,728 are relatively prime.

22. Prove that for all positive integers a and b, a \mid b if, and only if, \text{gcd}(a, b) = a. (Note that to prove "A if, and only if, B," you need to prove "if A then $B$" and "if B then A.")

Proof:

Suppose a and b are any positive integers such that a \mid b.

By the definition of divisibility, any number is divisible by at least 1 and itself. It follows then that a \mid a. This makes a a common divisor of a and b. Thus, by definition of the common divisor, a is less than or equal to the greatest common divisor of a and b, a \leq \text{gcd}(a, b).

Similarly, since \text{gcd}(a, b) is the greatest common divisor of a and b, it must also divide a, \text{gcd}(a, b) \mid a. Thus, by Theorem 4.4.1, \text{gcd}(a, b) \leq a.

We know that when a \leq \text{gcd}(a, b) and \text{gcd}(a, b) \leq a are both true, this means that \text{gcd}(a, b) = a.

Therefore \text{gcd}(a, b) = a. [as was to be shown.]

Then, suppose a and b are any positive integers such that their greatest common divisor is \text{gcd}(a, b) = a.

By definition of a common divisor, a \mid \text{gcd}(a, b) and \text{gcd}(a, b) \mid b.

Therefore a \mid b. [as was to be shown.]

Q.E.D.

a. Prove that if a and b are integers, not both zero, and d = \text{gcd}(a, b), then \dfrac{a}{d} and \dfrac{b}{d} are integers with no common divisor that is greater than 1.

Proof by contradiction:

Suppose not. That is, suppose that a and b are any nonzero integers and there is some positive integer d, where d = \text{gcd}(a, b) and \dfrac{a}{d} and \dfrac{b}{d} are integers with a common divisor that is greater than 1.

Since d = \text{gcd}(a, b). By the definition of a common divisor, d \mid a and d \mid b.

Since d \mid a and d \mid b, by the definition of divisibility, a = dk and b = dm for some integers k and m. By algebra:

 a = dk \to \frac{a}{d} = k 

 b = dm \to \frac{b}{d} = m 

Since \dfrac{a}{d} and \dfrac{b}{d} are integers with a common divisor that is greater than 1. This means that k and m have some common divisor, c such that c > 1. Because c > 1, this means that dc > d. It follows that dc would then be a common divisor of a and b where dc > d, which means that d is not the greatest common divisor of a and b, d \neq \text{gcd}(a, b).

This is a contradiction.

Q.E.D.

b. Write an algorithm that accepts the numerator and denominator of a fraction as input and produces as output the numerator and denominator of that fraction written in lowest terms. (The algorithm may call upon the Euclidean algorithm as needed.)

Algorithm

[Given a rational number \dfrac{N}{D}, output both N and D in lowest terms.]

[Note that EA() here represents calling the Euclidean Algorithm]

Input: \dfrac{N}{D} [a rational number.]

Algorithm Body:

d := EA(N, D)\\ n := \dfrac{N}{d}\\ m := \dfrac{D}{d}

Output: n and m.

24. Complete the proof of Lemma 4.10.2 by proving the following: If a and b are any integers with b \neq 0 and q and r are any integers such that

 a = bq + r 

then

 \text{gcd}(b, r) \leq \text{gcd}(a, b) 

Continuation of Lemma 4.10.2:

2. \text{\textbf{gcd}}(b, r) \leq \text{\textbf{gcd}}(a, b):

a. [We will first show that any common divisor of b and r is also a common divisor of a and b.]

Let b and r be integers where b \neq 0, and let c be a common divisor of b and r. Then c \mid b and c \mid r and so, by definition of divisibility, b = nc and r = mc, for some integers n and m. Substitute into the equation

 a = bq + r 

to obtain

 a = (nc)q + mc 

 a = (nq + m)c 

Now, nq + m is an integer, and so, by definition of divisibility, c \mid a. Because we already know that c \mid b, we can conclude that c is a common divisor of a and b [as was to be shown].

b. [Next, we show that \text{gcd}(b, r) \leq \text{gcd}(a, b).]

Now the greatest common divisor of b and r is defined because b and r are not both zero. Also, by part (a), every common divisor of b and r is a common divisor of a and b, and so the greatest common divisor of b and r is a common divisor of a and b. But then \text{gcd}(b, r) (being one of the common divisors of a and b) is less than or equal to the greatest common divisor of a and b:

 \text{gcd}(b, r) \leq \text{gcd}(a, b) 

a. Prove: If a and d are positive integers and q and r are integers such that a = dq + r and 0 \leq r < d, then

 -a = d(-(q + 1)) + (d - r) 

and

 0 < d - r \leq d 

Proof:

Suppose a and d are positive integers, and that q and r are integers such that a = dq + r and 0 \leq r < d.

By algebra:

 a = dq + r 

 -a = -(dq + r) 

 -a = -(dq + d - d +  r) 

 -a = -(d(q + 1) - d + r) 

 -a = -d(q + 1) + d - r 

 -a = d(-(q + 1)) + (d - r) 

Then, also by algebra:

 0 \leq r < d 

 0 \geq -r > -d 

Then add d to all sides:

 0 + d \geq -r + d > -d + d 

 d \geq -r + d > 0 

Rearranged:

 0 < d - r \leq d 

Therefore -a = d(-(q + 1)) + (d - r) and 0 < d - r \leq d.

Q.E.D.

b. Indicate how to modify Algorithm 4.10.1 to allow for the input a to be negative.

Algorithm 4.10.1 Division Algorithm

[Given an integer a and a positive integer d, the aim of the algorithm is to find integers q and r that satisfy the conditions a = dq + r and 0 \leq r < d. This is done by subtracting d repeatedly from a until the result is less than d but is nonnegative.

 0 \leq a - d - d - d - \dots - d = a - dq < d

The total number of $d$'s that are subtracted is the quotient q. The quantity a - dq equals the remainder r.]

Input: a [an integer], d [a positive integer]

Algorithm Body:

\text{\textbf{if }}(a \geq 0) \text{\textbf{then}}\\ \ \ r := a, q := 0\\ \ \ \text{\textbf{while }}(r \geq d)\\ \ \ \ \ r := r - d\\ \ \ \ \ q := q + 1\\ \ \ \text{\textbf{end while}}\\ \text{\textbf{else}}\\ \ \ r := -a, q := 0\\ \ \ \text{\textbf{while }}(r \geq d)\\ \ \ \ \ r := r - d\\ \ \ \ \ q := q + 1\\ \ \ \text{\textbf{end while}}\\ \ \ \text{\textbf{if }}(r == 0) \text{\textbf{ then}}\\ \ \ \ \ q := -q\\ \ \ \text{\textbf{else}}\\ \ \ \ \ q := -(q + 1)\\ \ \ \ \ r := d - r\\ \ \ \text{\textbf{end if}}\\ \text{\textbf{end if}}

Output: q, r

a. Prove that if a, d, q, and r are integers such that a = dq + r and 0 \leq r < d, then

 q = \left\lfloor \frac{a}{d} \right\rfloor \quad \text{ and } r = a - \left\lfloor \frac{a}{d} \right\rfloor \cdot d

Proof:

Suppose a, d, q, and r are any integers such that a = dq + r and 0 \leq r < d.

By algebra:

 a = dq + r 

 r = a - dq 

Then by substitution:

 0 \leq r < d 

 0 \leq a - dq < d 

 dq \leq a < dq + d 

 dq \leq a < d(q + 1) 

 q \leq \frac{a}{d} < q + 1 

Thus, by the definition of floor, q = \left\lfloor \dfrac{a}{d} \right\rfloor.

Then, by substitution:

 a = dq + r 

 a = d\left\lfloor \frac{a}{d} \right\rfloor + r 

 r = a - d\left\lfloor \frac{a}{d} \right\rfloor 

 r = a - \left\lfloor \frac{a}{d} \right\rfloor \cdot d 

Therefore q = \left\lfloor \dfrac{a}{d} \right\rfloor and r = a - \left\lfloor \dfrac{a}{d} \right\rfloor \cdot d.

Q.E.D.

b. In a computer language with a built-in floor function, \text{div} and \text{mod} can be calculated as follows:

 a \text{ div } d = \left\lfloor \frac{a}{d} \right\rfloor \quad \text{ and } \quad a \mod d = a - \left\lfloor \frac{a}{d} \right\rfloor \cdot d 

Rewrite the steps of Algorithm 4.10.2 for a computer language with a built-in floor function but without \text{div} and \text{mod}.

Algorithm Body:

a := A, b := B, r:= B

[If b \neq 0, compute a \mod b, the remainder of the integer division of a by b, and set r equal to this value. Then repeat the process using b in place of a and r in place of b.]

\text{\textbf{while }} (b \neq 0)\\ \ \ \ \ r := a - \left\lfloor \dfrac{a}{b} \right\rfloor \cdot b

[The value of a \mod b can be obtained by calling the division algorithm.]

\ \ \ \ a := b\\ \ \ \ \ b := r\\ \text{\textbf{end while}}

[After execution of the \text{\textbf{while}} loop, \text{gcd}(A, B) = a.]

\text{gcd} := a

27. An alternative to the Euclidean algorithm uses subtraction rather than division to compute greatest common divisors. (After all, division is repeated subtraction.) It is based on the following lemma.

Lemma 4.10.3

Algorithm 4.10.3 Computing gcd's by Subtraction

[Given two positive integers A and B, variables a and b are set equal to A and B. Then a repetitive process begins. If a \neq 0, and b \neq 0, then the larger of a and b is set equal to a - b (\text{if } a \geq b) \text{ or to } b - a(\text{if } a < b), and the smaller of a and b is left unchanged. This process is repeated over and over until eventually a or b becomes 0. By Lemma 4.10.3, after each repetition of the process,

 \text{gcd}(A, B) = \text{gcd}(a, b) 

After the last repetition,

 \text{gcd}(A, B) = \text{gcd}(a, 0) \quad \text{ or } \quad \text{gcd}(A, B) = \text{gcd}(0, b) 

depending on whether a or b is nonzero. But by Lemma 4.10.1,

 \text{gcd}(a, 0) = a \quad \text{ and } \quad \text{gcd}(0, b) = b 

Hence, after the last repetition,

 \text{gcd}(A, B) = a \text{ if } a \neq 0 \quad \text{ or } \quad \text{gcd}(A, B) = b \text{ if } b \neq 0 

Input: A, B [positive integers]

Algorithm Body:

a := A, b := B\\ \text{\textbf{while }} (a \neq 0 \text{ and } b \neq 0)\\ \ \ \ \ \text{\textbf{if }} a \geq b \text{\textbf{ then }} a := a - b\\ \ \ \ \ \ \ \ \ \text{\textbf{else }} b := b - a\\ \text{\textbf{end while}}\\ \ \ \ \ \text{\textbf{if }} a = 0 \text{\textbf{ then }} gcd := b\\ \ \ \ \ \text{\textbf{else }} gcd := a

[After execution of the if-then-else statement, \text{gcd} = \text{gcd}(A, B).]

Output: \text{gcd} [a positive integer]

a. Prove Lemma 4.10.3.

Proof:

Suppose a and b are any integers such that a \geq b > 0.

Let c be some integer such that c is common divisor of both a and b such that c \mid a and c \mid b.

Since c \mid a and c \mid b, a = nc and b = mc for some integers n and m.

By substitution:

 a - b = nc - mc 

 a - b = c(n - m) 

Now, n - m is an integer by the difference of integers, and so by the definition of divisibility, c \mid (a - b).

Thus, it follows that \text{gcd}(a, b) \leq \text{gcd}(b, a - b).

Let k be some integer such that k is common divisor of both a - b and b such that k \mid (a - b) and k \mid b.

Since k \mid (a - b) and k \mid b, a - b = nk and b = mk for some integers n and m.

By substitution:

 a - b = nk 

 a = nk + b 

 a = nk + mk 

 a = k(n + m) 

Since m + n is an integer by the sum of integers, the definition of divisibility tells us that k \mid a.

Since we already know that k \mid b, it follows that k is a common divisor of both a and b.

Thus it follows that \text{gcd}(a, b) \geq \text{gcd}(b, a - b).

It has now been established that \text{gcd}(a, b) \leq \text{gcd}(b, a - b) and also that \text{gcd}(a, b) \geq \text{gcd}(b, a- b).

Therefore \text{gcd}(a, b) = \text{gcd}(b, a - b)

Q.E.D.

b. Trace the execution of Algorithm 4.10.3 for A = 630 and B = 336.

A	630
B	336
a	630	294	294	252	210	168	126	84	42	0
b	336	336	42	42	42	42	42	42	42	42
\text{gcd}										42

c. Trace the execution of Algorithm 4.10.3 for A = 768 and B = 348.

A	768
B	348
a	768	420	72	72	72	72	72	12	12	12	12	12	0
b	348	348	348	276	204	132	60	60	48	36	24	12	12
\text{gcd}													12

Exercises 28-32 refer to the following definition.

Definition: The least common multiple of two nonzero integers a and b, denoted \text{\textbf{lcm}}(a, b), is the positive integer c such that

a. a \mid c and b \mid c

b. for all positive integers m, if a \mid m and b \mid m, then c \leq m.

28. Find

a. \text{lcm}(12, 18)

\text{lcm}(12, 18) = 36

b. \text{lcm}(2^2 \cdot 3 \cdot 5, 2^3 \cdot 3^2)

 \text{lcm}(12, 18) = 2^3 \cdot 3^2 \cdot 5 = 360 

c. \text{lcm}(2800, 6125)

 2800 = 100 \cdot 28 = 10^2 \cdot 7 \cdot 4 = 2^2 \cdot 5^2 \cdot 7 \cdot 2^2 = 2^4 \cdot 5^2 \cdot 7 

 6125 = 25 \cdot 245 = 5^2 \cdot 5 \cdot 49 = 5^3 \cdot 7^2 

 2800 = 2^4 \cdot 5^2 \cdot 7 

 6125 = 5^3 \cdot 7^2 

 \text{lcm}(2800, 6125) = 2^4 \cdot 5^3 \cdot 7^2 = 98000 

29. Prove that for all positive integers a and b, \text{gcd}(a, b) = \text{lcm}(a, b) if, and only if, a = b.

Proof:

Suppose a and b are any positive integers such that \text{gcd}(a, b) = \text{lcm}(a, b).

Let k be some integer such that k = \text{gcd}(a, b) = \text{lcm}(a, b).

Since k = \text{gcd}(a, b), k \mid \text{gcd}(a, b), and thus k \leq a and k \leq b.

And since k = \text{lcm}(a, b), \text{lcm}(a, b) \mid k and thus a \leq k and b \leq k.

Since k \leq a and a \leq k, this means that k = a.

And since k \leq b and b \leq k, this means that k = b.

By the law of transitivity, a = k = b.

Thus a = b.

Now, suppose a and b are any positive integers such that a = b.

By the definition of greatest common divisor, \text{gcd}(a, a) = a.

By the definition of least common multiple, \text{lcm}(a, a) = a.

This means that \text{gcd}(a, a) = \text{lcm}(a, a).

Since a = b, b can be substituted for a:

 \text{gcd}(a, b) = \text{lcm}(a, b) 

Thus \text{gcd}(a, b) = \text{lcm}(a, b)

Therefore it has been shown that if \text{gcd}(a, b) = \text{lcm}(a, b), then a = b, and it has also been shown that if a = b, then \text{gcd}(a, b) = \text{lcm}(a, b).

Q.E.D.

30. Prove that for all positive integers a and b, a \mid b if, and only if, \text{lcm}(a, b) = b.

Proof:

Suppose a and b are any positive integers such that a \mid b.

By the definition of a multiple, b \mid b means that b is a multiple of b.

This means that since a \mid b and b \mid b, that b is a common multiple of both a and b.

Let m be some positive integer such that b \mid m and a \mid m. Since b and m are positive integers, and since b \mid m, this means that b \leq m.

Thus \text{lcm}(a, b) = b.

Then suppose a and b are any positive integers such that \text{lcm}(a, b) = b.

By the definition of a common multiple, we know that a \mid \text{lcm}(a, b). Since we also know that \text{lcm}(a, b) = b, by substitution:

 a \mid b 

Thus a \mid b.

Therefore it has been shown that if a \mid b, then \text{lcm}(a, b) = b and it has also been shown that if \text{lcm}(a, b) = b, then a \mid b.

Q.E.D.

31. Prove that for all integers a and b, \text{gcd}(a, b) \mid \text{lcm}(a, b).

Proof:

Suppose a and b are any integers.

Since a is an integer, this means that \text{gcd}(a, b) \mid a and a \mid \text{lcm}(a, b).

By the transitive property of divisibility, this means that:

 \text{gcd}(a, b) \mid \text{lcm}(a, b) 

Therefore \text{gcd}(a, b) \mid \text{lcm}(a, b).

Q.E.D.

32. Prove that for all positive integers a and b, \text{gcd}(a, b) \cdot \text{lcm}(a, b) = ab.

Omitted.