Here are some answers for the exercises.

1. (a) and (b) Please use the Haskell code to check your answers.

(c) We first solve x ≡ 3 (mod 5) and x ≡ 4 (mod 7). We start by checking that gcd(5,7)=1. Now we find u and v such that 5u + 7v = 1, for example u=3 and v=-2. This gives us a solution for x: 4⋅5⋅3 + 3⋅7⋅(-2) = 60-42 = 18. The general solutions for this system of equations is given by x ≡ 18 (mod 35).

Next, we solve x ≡ 18 (mod 35) and x ≡ 5 (mod 11). Indeed, gcd(35,11)=1. We have to find u and v such that 35u + 11v = 1, for example u=-5 and v=16 (use the Pulverizer to get u and v). This gives a solution for x: 5⋅35⋅(-5) + 18⋅11⋅16 = -875 + 3168 = 2293. This is a perfectly fine solution, but a smaller one that is still positive is 2293 - 5⋅5⋅7⋅11 = 368.

2. (a) There are no solutions, since the left-hand side is divisable by 7 and the right-hand side is not.

(b) We first divide everything by 3 and simplify the equation to: 3x + 5y = 7. We use the Pulverizer to find numbers u and v such that 3u + 5v = 1. We get u=2 and v=-1.

We now multiply by 7 to get the solution x=14 and y=-7. Subtracting 5 from x and adding 3 to y gives x=9 and y=-4. Doing this once more gives x=4 and y=-1.

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 Lemma 9.1.2 in the book.

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. The proof goes by case split on the remainder of p after dividing by 6.

If p ≡ 0, 2, 3, or 4 (mod 6), p is divisable by 6, 2, 3, and 2, respectively, and thus not a prime number. These are thus impossible cases.

If p ≡ 1 (mod 6), let p = 6⋅k+1. We then have that p²-1 = (p+1)(p-1) = (6k+2)6k = 12(3k+1)k. We have to show that this is a number divisable by 24. 12 is divisable by 12, and (3k+1)k is divisable by 2, because either k is even or (3k+1) is even. So, 12(3k+1)k is divisable by 12⋅2 = 24.

If p ≡ 5 (mod 6), let p = 6⋅k-1. We then have that p²-1 = (p+1)(p-1) = 6k(6k-2) = 12k(3k-1). We have to show that this is a number divisable by 24. 12 is divisable by 12, and k(3k-1) is divisable by 2, because either k is even or (3k-1) is even. So, 12k(3k-1)k is divisable by 12⋅2 = 24.

5. If p | a², then we also have p | a (by Euclid's theorem). So, then we also have p² | a².

6. We know that m²-1 = (m+1)(m-1). If both m+1 and m-1 are 2 or more, we definitely do not have a prime number. This happens when m≥3. If both m+1 and m-1 are -2 or less, we also do not have a prime number. This happens when m≤-3. So the only possibilites we have left are m=-2 (then we get 3, which is prime!), m=-1 (then we get 0; no prime), m=0 (-1; no prime), m=1 (0; no prime), and m=2 (3; prime!).

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 what happens when two choices for k (k1 and k2) generate the same result. In this case we would have k1 ⋅ a ≡ k2 ⋅ a (mod b). Since gcd(a,b)=1, a has a multiplicative inverse, and we can conclude that k1 ≡ k2 (mod b). However, we have 0 ≤ k1, k2 < b, so the only possibility for this to happen is when k1 = k2.

(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. When a ≡ b (mod mn), we have that a = b + k⋅m⋅n, for some k. This means that a = b + (k⋅m)⋅n (which means that a ≡ b (mod n)) and a = b + (k⋅n)⋅m (which means that a ≡ b (mod m)).