Exercises Week 4 - Arithmetic - Answers
(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 p2-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 p2-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 | a2, then we also have p | a (by Euclid's theorem). So, then we also have p2 | a2.
(6.) We know that m2-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.
For numbers ≤ 120, we only need to check divisibility with 2, 3, 5, and 7. If the number is not divisible by any of these, it is prime. This is because √121 = 11. In fact, it is enough to check that the number N is not divisible by 2, 3, or 5 (which is easy), and that the number is not equal to 49, 77 or 91 (the only three numbers divisible by 7 and not already by 2, 3, or 5)!
(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)).