# split them up according to their year | My Assignment Tutor

1. If we pick 12 pennies, we may have 4 from each year. So 12 is not enough. If we pick 13 (pigeons) and splitthem up according to their year (pigeonholes), then since 13 > 3 · 4, the generalised pigeonhole principle impliesthat we must have at least 5 pennies form the same year.2. (i) There are 15 possible remainders: 0; 1; : : : ; 14. So we need to choose 16 numbers by the pigeonhole principle.(ii) Notice that 9 numbers is not enough: 111; 222; : : : ; 999 have nothing in common. So we need to choose 10numbers.3. (i) Apply the Euclidean algorithm.98 = 85 · 1 + 1385 = 13 · 6 + 713 = 7 · 1 + 67 = 6 · 1 + 16 = 1 · 6 + 0Therefore, gcd(98; 85) = 1. Now work backwards through the above equations.1 = 7 – 6 · 16 = 13 – 7 · 1 ) 1 = 7 – (13 – 7 · 1) · 1 = -13 + 7 · 27 = 85 – 13 · 6 ) 1 = -13 + (85 – 13 · 6) · 2 = 85 · 2 – 13 · 1313 = 98 – 85 · 1 ) 1 = 85 · 2 – (98 – 85 · 1) · 13 = 98(-13) + 85 · 15Therefore, m = -13; n = 15.(ii) Similar to part (i), m = 23; n = -3.4. ()) Let a and b be coprime. Then d = gcd(a; b) = 1. If there is a prime p such that pja and pjb, then bydefinition of gcd we also have pjd, so d 6= 1, a contradiction. Therefore, no such p exists.(() Let p be prime such that pjd, where d = gcd(a; b). Since dja and djb, we have pja and pjb by the transitivityof divisibility.5. The easy solution is to pick a pair of distinct primes, such as 11 and 13. But the question asks you to make surethat some of the numbers are not prime. Question 4 shows, for example, that 22 = 2·11 and 35 = 5·7 are coprime.6. We have -17 ≡ 7; 3 ≡ 3; 43 ≡ 7; 15 ≡ 3; 37 ≡ 1; -11 ≡ 1; -21 ≡ 3 modulo 12.7. We have6 ≡ m (mod 3) , 3j(6 – m), 6 – m = 3k for some k 2 Z, m = 6 – 3k for some k 2 Z, m 2 f: : : ; -6; -3; 0; 3; 6; : : :gSimilarly, m ≡ 125(mod 7) if and only if m 2 f: : : ; 111; 118; 125; 132; 139; : : :g. Putting the two together, we wantall elements of the above set that are also divisible by 3, so m 2 f: : : ; 111; 132; 153; : : :g.8. We have 24 = 16 ≡ 1(mod 5), so 2100 = (24)25 ≡ 1(mod 5). Using repeated squaring and reducing modulo 7when necessary, we have31 ≡ 332 = 9 ≡ 234 ≡ 22 = 438 ≡ 42 = 16 ≡ 2316 ≡ 22 = 4332 ≡ 42 ≡ 2364 ≡ 22 = 4:Then 3100 = 364 · 332 · 34 ≡ 4 · 2 · 4 ≡ 4(mod 7).9. ()) Let [a] = [b]. Choose any x 2 [a]. Then x ≡ a(mod n) by definition of [a]. Since [a] = [b], we havex 2 [b]. Hence, x ≡ b(mod n). By the symmetry property of congruence, a ≡ x(mod n). Then by the transitivityproperty, a ≡ x; x ≡ b ) a ≡ b(mod n).(() Let a ≡ b(mod n). If x 2 [a], then x ≡ a(mod n) by definition of congruence class. Hence, x ≡ b(mod n) bytransitivity, so x 2 [b]. Thus, [a] ⊆ [b]. Similarly, [b] ⊆ [a]. Therefore, [a] = [b].10. +                                    ·                                    Not all elements of Z6 have multiplicative inverses.gcd(1; 6) = 1gcd(2; 6) = 2gcd(3; 6) = 3gcd(4; 6) = 2gcd(5; 6) = 1From this and the multiplication table, we see that [m] 2 Z6 has an inverse under multiplication if and only ifgcd(m; 6) = 1.11. In this question, we work modulo n = 7.(i) [m] is a set of numbers, Z7 is a set of sets.(ii) You may have chosen a different 8 numbers and still be correct. = f: : : ; -26; -19; -12; -5; 2; 9; 16; 23; : : :g = f: : : ; -23; -16; -9; -2; 5; 12; 19; 26; : : :g = f: : : ; -28; -21; -14; -7; 0; 7; 14; 21; : : :gZ7 = f; ; ; ; ; ; g:(iii) (a) True, since 2 ≡ 9(mod 7).(b) False,  is a set and 5 is a number.(c) True, since 5 ≡ 19(mod 7).(d) False, Z7 is a set of sets and 3 is a number.(e) True, since all congruence classes are contained in Z7 ( = ).(f) False, since [a] is a set and [b] is a set of numbers.

QUALITY: 100% ORIGINAL PAPER – NO PLAGIARISM – CUSTOM PAPER