Here are some answers for the exercises.

2. See answers for the mini-tenta.

3.

R1 is reflexive, because x | x for all x. R1 is not symmetric, for example we have 2 | 4 but not 4 | 2. R1 is transitive, see Sats 5.4 (b) on page 123.

R2 is not reflexive, for example we have gcd(3,3)=3. R2 is symmetric because gcd(x,y)=gcd(y,x). R2 is not transitive, for example we have gcd(2,3)=1 and gcd(3,4)=1 but gcd(2,4)=2.

R3 is reflexive, symmetric and transitive, because R(x,y) is true no matter which x and y we pick.

R4 is not reflexive, because R(x,x) is false for any x (*). R4 is symmetric and transitive! Because R4 is always false, any implication with R4 on the left-hand side will be true.

So, only R3 is an equivalence relation.

((*): R4 is actually reflexive if the universe U is empty, in this case we have that for all x in U, R4(x,x)!)

4., 5., 6. See answers in the book.

7. Since n is not prime, we have a, b > 1 such that n = a ⋅ b. We now proceed with a proof by contradiction; suppose that both a and b > √n. Then we have n = a ⋅ b > √n ⋅ √ n = n. So, n > n. This is impossible, so at least one of a, b must be ≤ √ n.

8. (a) The number of elements in S is equal to b. Every choice of k generates a unique result.

To see this, consider (k ⋅ a) ≡ (k' ⋅ a) (mod b). This means that b | (k ⋅ a) - (k' ⋅ a), which in turn means that b | (k - k') ⋅ a. Since gcd(a,b)=1, this must mean that b | (k - k'). However, we have 0 ≤ k, k' < b, so the only possibility for this to happen is when k = k'.

This is also the answer to exercise 5.22 in the book.

(b) Pick a = 2 and b = 4. Then we get the set {0, 2, 0, 2} = {0, 2}, so the set will have less elements.

9. See answer in the book.