Description

Problem 1. Prove the following statement:

For every a ∈ Z such that 5 does not divide a, there exists b ∈ Z such that ab ≡ 1 mod 5.

Problem 2. We recall that given a, b ∈ Z such that ab = 0, we define the gcd of a and b to be the greatest integer that divides both a and b. We denote it by gcd(a, b).

1. Let a, b ∈ Z such that ab = 0. We suppose that there exists u, v ∈ Z such that

1 = au + bv.

Prove that gcd(a, b) = 1.

2. Write the negation of the following statement. Then decide if it is true or false and justify your answer.

For every a ∈ Z, b ∈ Z, and d ∈ Z such that d > 0,

(if there exists u, v ∈ Z such that d = au + bv, then gcd(a, b) = d).

Problem 3. Read the Division Algorithm theorem carefully in your book (Fact 1.5 page 30 in the third edition). What is the division of

1. 167 by 8?

2. −167 by 8?

Problem 4. Prove the following statement:

for every n ∈ Z such that n ≥ 0, we have 5|3³ⁿ⁺¹ + 2ⁿ⁺¹ .

Problem 5. For each of the following statements:

• Negate the statement,

• Decide if the statement (prior to negation) is true or false and justify your answer.

1. ∀a ∈ Z, if 6|a and 8|a then 48|a.

2. ∀x ∈ R, ∀y ∈ R, if xy ≥ 0 then x + y ≥ 0.

3. For every house h in Vancouver, there is a positive integer c such that (if the number of cats in h is > c, then there is no mouse in the house).

Problem 6. Explain what is wrong in the following proof and write a correct version of it.

For any real number b such that 1 < b < 5, prove that b³ − 6b² + 5b < 0.

Proof. Suppose that 1 < b < 5.

b³ − 6b² + 5b = b(b² − 6b + 5) < 0 so, since b > 0 we have b² − 6b + 5 < 0. But we notice that b² − 6b + 5 = (b − 1)(b − 5). Since 1 < b < 5, we know that b − 1 > 0 and b − 5 < 0 so indeed b² − 6b + 5 = (b − 1)(b − 5) < 0.

Page 1