University of Waterloo MATH 135 Sample Final Exams ( WITH 100 % CORRECT SOLUTIONS )

University of Waterloo MATH 135 SAMPLE Final Examination Algebra for Honours Mathematics Fall 2016 Instructors: M. Akash, S. Bauman, C. Bruni, B. Charbonneau, A. Gamache, R. Garbary, G. Gauthier-S halom, I. Goulden, J. Koeller, W. Kuo, Y. Liu, A. Menezes, R. Moosa, P. Nelson, J. Pretti, R Trelford, D. Wagner, R. Willard Instructions 1. Fill in your ID number and User ID above. 2. Write your answers in the space provided. If you need more room, use the last two pages, and clearly indicate this on the question page. 3. You must justify all of your answers. Your writing needs to be legible. Your arguments must be logical, clear and easy to understand. 4. There is a reference sheet supplied separately from this exam booklet. There you will find some of the major propositions that were covered in class. You may use any result from the list without proof. Make sure to clearly state the name or the acronym of the result you are using. 5. There are 14 questions. The total marks available in this exam is 50. 1For each of Questions 1 to 6, full marks will be given for a correct answer which is placed in the box provided. Part marks will only be awarded if relevant work is shown in the space provided. 1. What is the greatest common divisor of 1239 and 735? [2 marks] 2. What is the units digit (also known as the ones digit) of 6789? [2 marks] 23. Give all the solutions to z3 + 27 = 0 in standard form. [3 marks] 4. You are eavesdropping on a conversation between Alice and Bob protected by the RSA system. Alice sends Bob a public encryption key (e; n) and receives a ciphertext C. You are able to determine that 88 < n < 92 and 26 < e < 30. What are the values of n and e? [3 marks] 35. Determine all integers x and y such that [3 marks] • 6x + 10y = 14, and • x ≡ 3 (mod 7), and • 20 < y < 40. 6. Consider the polynomial p(x) = x5 + 2x4 + 6x3 + 12x2 − 27x − 54. One root of this polynomial is 3i. Express p(x) as a product of five linear polynomials in C[x]. [3 marks] 4For each part below, in the box provided, indicate whether the given statement [1 mark each] is true (T) or false (F). No justification is required. 7. (a) :(A ) B) is logically equivalent to (:A) ) (:B). (b) :(8x 2 S; P(x)) is logically equivalent to 8x 2 S; (:P(x)). (c) If a; b; c; d 2 Z, a j b, b j c, and c j d, then a j d. (d) If a; b; c 2 Z, and a j bc, then a j b or a j c. (e) (cos π4 + i sin π4 )4 1 − i = 1 2 + i 2 (f) A polar form of the complex number z = −18i is 18(cos (32π ) + i sin (32π )). (g) gcd(01; 02) = 01 5The remaining questions require proofs. Write clearly and justify your steps. Do NOT use the amount of available space as an indication of how long your answer should be". 8. Let p be a prime. Prove that px + 18y = 6 has an integer solution. [4 marks] 69. Prove that if w is an nth root of unity, then w1 is also an nth root of unity. (Recall: The nth roots of unity are the nth roots of 1.) [4 marks] 710. Let a 2 Z. Prove that if a221 ≡ 20 (mod 23) and 100 < a < 125, then a = 112. [3 marks] 811. Let a; b; c; d 2 Z such that ad − bc = 1. Let f(z) : C ! C be given by f(z) = az cz++db. Suppose that z is a complex number such that Im(z) > 0. Prove that Im(f(z)) > 0. 912. Suppose a, b and n are integers. Prove that n j gcd(a; n) · gcd(b; n) if and only if n j ab. [4 marks] 1013. Let f(x) = nX k =0 xk be a polynomial in Z2[x]. [5 marks] Prove by mathematical induction that for all n 2 N, [f(x)]2 = nX k =0 x2k. 1114. Let a and b be coprime positive integers. Prove that f(s; t) 2 N × N : as + bt = abg = ;. [3 marks] 12This page was intentionally left blank. You may use this space if you run out of room for a particular question. If you do, be sure to indicate this clearly here on this page and also on the question page. 13This page was intentionally left blank. You may use this space if you run out of room for a particular question. If you do, be sure to indicate this clearly here on this page and also on the question page. 14MATH 135 F16 Sample Final Exam Solutions 1. What is the greatest common divisor of 1239 and 735? Answer: 21 Work: We can determine this using the EEA: 1239 = 735 + 504 735 = 504 + 231 504 = 2 · 231 + 42 231 = 5 · 42 + 21 42 = 2 · 21 + 0 2. What is the units digit (also known as the ones digit) of 6789? Answer: 6 Work: We are looking for an integer x such that x ≡ 6789 (mod 10) where 0 ≤ x < 10. Note that, for all n, 6n ≡ 6 (mod 10) (We could prove this by induction relying on 62 = 36 ≡ 6 (mod 10).) Alternatively, using CRT, 6789 ≡ 0 (mod 2) 6789 ≡ 1 (mod 5) Thus 6789 ≡ 6 (mod 10). 3. Give all the solutions to z3 + 27 = 0 in standard form. Answer: p3 27 cos π+2 3kπ
+ ip3 27 sin π+2 3kπ
for k = 0; 1; 2 Solution: We have −27 = 27(cos(π) + i sin(π)): Thus, CNRT gives us the three roots above. 4. You are eavesdropping on a conversation between Alice and Bob protected by the RSA system. Alice sends Bob a public encryption key (e; n) and receives a ciphertext C. You are able to determine that 88 < n < 92 and 26 < e < 30. What are the values of n and e? Answer: (e; n) = (29; 91) Solution: Here n must be the product of two distinct primes. The only possibility is n = 13 · 7 = 91: It follows that e must be coprime to (7 − 1)(13 − 1) = 72. The only possibility is e = 29