I Need Someone To Take My First Year Algebra Exam At 9 Am (Lasts 2.5 Hours)

Reference for MATH 135 Final Exam, F21 Notation In MATH 135, we define the natural numbers N = {1, 2, 3, · · · , } to be the set of positive integers. List of Propositions You may use any of the results below without proof. When you do, make sure to clearly state the name (e.g. Transitivity of Divisibility) or the acronym (e.g. TD) associated with the result that you are using. Transitivity of Divisibility (TD) For all integers a, b and c, if a | b and b | c, then a | c. Divisibility of Integer Combinations (DIC) For all integers a, b and c, if a | b and a | c, then for all integers x and y, a | (bx+ cy). Pascal’s Identity (PI) For all positive integers n and m with m ≤ n, we have ( n m ) = ( n− 1 m− 1 ) + ( n− 1 m ) . Binomial Theorem (BT) For all integers n ≥ 0 and for all complex numbers a and b, (a+ b)n = n∑ m=0 ( n m ) an−mbm. Bounds By Divisibility (BBD) For all integers a and b, if b | a and a 6= 0 then b ≤ |a|. Division Algorithm (DA) For all integers a and positive integers b, there exist unique integers q and r such that a = qb+r, 0 ≤ r < b. GCD With Remainders (GCD WR) For all integers a, b, q and r, if a = qb+ r, then gcd(a, b) = gcd(b, r). GCD Characterization Theorem (GCD CT) For all integers a and b, and non-negative integers d, if d is a common divisor of a and b, and there exist integers s and t such that as+ bt = d, then d = gcd(a, b). Bézout’s Lemma (BL) For all integers a and b, there exist integers s and t such that as+ bt = d, where d = gcd(a, b). Common Divisor Divides GCD (CDD GCD) For all integers a, b and c, if c | a and c | b then c | gcd(a, b). Coprimeness Characterization Theorem (CCT) For all integers a and b, gcd(a, b) = 1 if and only if there exist integers s and t such that as+bt = 1. Division by the GCD (DB GCD) For all integers a and b, not both zero, gcd ( a d , b d ) = 1, where d = gcd(a, b). Coprimeness and Divisibility (CAD) For all integers a, b and c, if c | ab and gcd(a, c) = 1, then c | b. Euclid’s Lemma (EL) For all integers a and b, and prime numbers p, if p | ab, then p | a or p | b. Unique Factorization Theorem (UFT) Every natural number n > 1 can be written as a product of prime factors uniquely, apart from the order of factors. 1 Divisors From Prime Factorization (DFPF) Let n ≥ 2 and c ≥ 1 be positive integers, and let n = pα11 p α2 2 · · · p αk k be the unique represen- tation of n as a product of distinct primes p1, p2, . . . , pk, where α1, α2, . . . , αk are positive inte- gers. The integer c is a positive divisor of n if and only if c can be represented as a product c = pβ11 p β2 2 · · · p βk k , where 0 ≤ βi ≤ αi for i = 1, 2, . . . , k. GCD From Prime Factorization (GCD PF) Let a and b be positive integers, and let a = pα11 p α2 2 · · · p αk k , and b = p β1 1 p β2 2 · · · p βk k , be ways to express a and b as products of the distinct primes p1, p2, . . . , pk, where some or all of the exponents may be zero. We have gcd(a, b) = pγ11 p γ2 2 · · · p γk k where γi = min{αi, βi} for i = 1, 2, . . . , k. Linear Diophantine Equation Theorem, Part 1 (LDET 1) For all integers a, b and c, with a and b not both zero, the linear Diophantine equation ax+ by = c (in variables x and y) has an integer solution if and only if d | c, where d = gcd(a, b). Linear Diophantine Equation Theorem, Part 2, (LDET 2) Let a, b and c be integers with a and b not both zero, and define d = gcd(a, b). If x = x0 and y = y0 is one particular integer solution to the linear Diophantine equation ax+ by = c, then the set of all solutions is given by {(x, y) : x = x0 + bdn, y = y0 − a dn, n ∈ Z}. Congruence Add and Multiply (CAM) For all positive integers n, if ai ≡ bi (mod m) for all 1 ≤ i ≤ n, then a1 + a2 + · · · + an ≡ b1 + b2 + · · ·+ bn (mod m), and a1a2 · · · an ≡ b1b2 · · · bn (mod m). Congruence Power (CP) For all positive integers n and integers a and b, if a ≡ b (mod m), then an ≡ bn (mod m). Congruence Divide (CD) For all integers a, b and c, if ac ≡ bc (mod m) and gcd(c,m) = 1, then a ≡ b (mod m). Congruent Iff Same Remainder (CISR)) For all integers a and b, a ≡ b (mod m) if and only if a and b have the same remainder when divided by m. Congruent To Remainder (CTR) For all integers a and b with 0 ≤ b < m, a ≡ b (mod m) if and only if a has remainder b when divided by m. Linear Congruence Theorem (LCT) For all integers a and c, with a non-zero, the linear congruence ax ≡ c (mod m) has a solution if and only if d | c, where d = gcd(a,m). Moreover, if x = x0 is one particular solution to this congruence, then the set of all solutions is given by {x ∈ Z : x ≡ x0 (mod md )}, or, equivalently, {x ∈ Z : x ≡ x0, x0 + md , x0 + 2 m d , . . . , x0 + (d− 1) m d (mod m)}. Modular Arithmetic Theorem (MAT) For all integers a and c, with a non-zero, the equation [a][x] = [c] in Zm has a solution if and only if d | c, where d = gcd(a,m). Moreover, when d | c, there are d solutions, given by [x0] , [ x0 + m d ] , [ x0 + 2 m d ] , . . . , [ x0 + (d− 1)md ] , where [x] = [x0] is one particular solution. Inverses in Zm (INV Zm) Let a be an integer with 1 ≤ a ≤ m− 1. The element [a] in Zm has a multiplicative inverse if and only if gcd(a,m) = 1. Moreover, when gcd(a,m) = 1, the multiplicative inverse is unique. Inverses in Zp (INV Zp) For all prime numbers p and non-zero elements [a] in Zp, the multiplicative inverse [a]−1 exists and is unique. 2 Fermat’s Little Theorem (F`T) For all prime numbers p and integers a not divisible by p, we have ap−1 ≡ 1 (mod p). Corollary of Fermat’s Little Theorem (Corollary of FlT) For all prime numbers p and integers a, we have ap ≡ a (mod p). Chinese Remainder Theorem (CRT) For all integers a1 and a2, and positive integers m1 and m2, if gcd(m1,m2) = 1, then the simulta- neous linear congruences n ≡ a1 (mod m1) n ≡ a2 (mod m2) have a unique solution modulo m1m2. Thus, if n = n0 is one particular solution, then the solutions are given by the set of all integers n such that n ≡ n0 (mod m1m2). Splitting Modulus Theorem (SMT) For all integers a and positive integers m1 and m2, if gcd(m1,m2) = 1, then the simultaneous congruences n ≡ a (mod m1) n ≡ a (mod m2) have exactly the same solutions as the single congruence n ≡ a (mod m1m2). Properties of Conjugate (PCJ) For the complex conjugate, the following properties hold for all z, w ∈ C: 1. (z) = z 2. z + w = z + w 3. z + z = 2 Re(z) and z − z = 2 Im(z) i 4. z w = z w 5. If z 6= 0, then (z−1) = (z)−1. Triangle Inequality (TIQ) For all z, w ∈ C, we have |z + w| ≤ |z|+ |w|. Properties of Modulus (PM) For the modulus, the following properties hold for all z, w ∈ C: 1. |z| = 0 if and only if z = 0 2. |z| = |z| 3. z z = |z|2 4. |z w| = |z| |w| 5. If z 6= 0, then |z−1| = |z|−1. Polar Multiplication in C (PMC) For all complex numbers z1 = r1(cos θ1 + i sin θ1) and z2 = r2(cos θ2 + i sin θ2), we have z1z2 = r1r2 ( cos(θ1 + θ2) + i sin(θ1 + θ2) ) . De Moivre’s Theorem (DMT) For all real numbers θ and integers n, we have (cos θ + i sin θ)n = cosnθ + i sinnθ. 3 Complex n-th Roots Theorem (CNRT) For all complex numbers a = r(cos θ+ i sin θ) and natural numbers n, the complex n-th roots of a are given by n √ r ( cos ( θ+2kπ n ) + i sin ( θ+2kπ n )) , k = 0, 1, 2, . . . , n− 1. Quadratic Formula (QF) For all complex numbers a, b and c, with a 6= 0, the solutions to az2 + bz + c = 0 are given by z = −b±w2a , where w is a solution to w 2 = b2 − 4ac. Degree of a Product (DP) For all fields F, and all non-zero polynomials f(x) and g(x) in F[x], we have deg f(x)g(x) = deg f(x) + deg g(x) . Division Algorithm for Polynomials (DAP) For all fields F, and all polynomials f(x) and g(x) in F[x] with g(x) not the zero polynomial, there exist unique polynomials q(x) and r(x) in F[x] such that f(x) = q(x)g(x) + r(x), where r(x) is the zero polynomial, or deg r(x) < deg g(x). Remainder Theorem (RT) For all fields F, all polynomials f(x) ∈ F[x], and all c ∈ F, the remainder polynomial when f(x) is divided by x− c is the constant polynomial f(c). Factor Theorem (FT) For all fields F, all polynomials f(x) ∈ F[x], and all c ∈ F, the linear polynomial x − c is a factor of the polynomial f(x) if and only if f(c) = 0 (equivalently, c is a root of the polynomial f(x)). Fundamental Theorem of Algebra (FTA) For all complex polynomials f(z) with deg f(z) ≥ 1, there exists a z0 ∈ C such that f(z0) = 0. Complex Polynomials of Degree n Have n Roots (CPN) For all integers n ≥ 1, and all complex polynomials f(z) of degree n ≥ 1, there exist complex numbers c 6= 0 and c1, c2, . . . , cn such that f(z) = c(z− c1)(z− c2) · · · (z− cn). Moreover, the roots of f(z) are c1, c2, . . . , cn. Conjugate Roots Theorem (CJRT) For all polynomials f(x) with real coefficients, if c ∈ C is a root of f(x), then c ∈ C is a root of f(x). Real Quadratic Factors (RQF) For all polynomials f(x) with real coefficients, if c ∈ C is a root of f(x), and Im(c) 6= 0, then there exists a real quadratic polynomial g(x) and a real polynomial q(x) such that f(x) = g(x)q(x). Moreover, the quadratic factor g(x) is irreducible in R[x]. Real Factors of Real Polynomials (RFRP) For all real polynomials f(x) of positive degree, f(x) can be written as a product of real linear and real quadratic factors. Rational Roots Theorem (RRT) For all polynomials f(x) = anx n + an−1x n−1 + · · ·+ a2x2 + a1x+ a0 with integer coefficients and n ≥ 1, if pq is a rational root of f(x) with gcd(p, q) = 1, then p | a0 and q | an. 4 . University of Waterloo MATH 135 Final Assessment Algebra for Honours Mathematics Winter 2020 Instructors: Z. Cramer, B. Ferguson, R. Garbary, J.P. Pretti Submission deadline: Tuesday, April 21 at 4:00pm EDT (Waterloo time) Instructions 1. This assessment consists of 14 questions worth 60 marks total. 2. Unless indicated otherwise, thoroughly justify all of your answers. 3. Prior to the submission deadline, you may not communicate with any person in any form about the final assessment. 4. As an exception to point #3, you may email your instructor in the unlikely event that you believe there is an error on the assessment. Beyond this, instructors will not provide any help with the questions on this assessment. 5. When completing the final assessment, you are permitted to (a) use the internet with the exception of point #3 above; (b) consult any course materials, your own notes, and the final assessment reference sheet posted to LEARN; (c) use any type of calculator to check your answers. However, you must convince a marker (who is not using a calculator) that your work is correct. 6. Submit this assessment to Crowdmark by the deadline above. You may either print the assessment and complete your work in the space provided, or complete the assessment on separate paper. Late submissions will not be accepted. Statement of Academic Integrity By submitting this assessment, I acknowledge the following statements to be true: - The work I submit here is entirely my own. - I have not used any unauthorized aids. - I have not discussed and will not discuss the contents of this assessment with anyone until after the submission deadline. - I am aware that misconduct can result in significant penalties, including failing the course and suspension (covered in Policy 71: https://uwaterloo.ca/secretariat/policies-procedures- guidelines/policy-71). 1 https://uwaterloo.ca/secretariat/policies-procedures-guidelines/policy-71 https://uwaterloo.ca/secretariat/policies-procedures-guidelines/policy-71 . 1. Let p, q, r be distinct primes. Determine gcd(p10q20r30, (p2qr2)10) in terms of p, q, r.[2] 2. Given that [x0] = [6] is a solution to [12][x] = [8] in Z64, write down the complete solution.[2] Express your answer(s) in the form [a], where a is an integer and 0 ≤ a < 64. 3. Determine the units digit (i.e., the ones digit) of 7202.[3] 2 4. Write (2− 2i)6 in standard form.[4] 5. Find all z ∈ C that satisfy the equation z6 = 32z. You may express your solution(s) in polar[4] form. 3 6. Determine all integer solutions (x, y) to the linear Diophantine equation 21x+ 15y = 72 such[4] that x ≥ 0 and y ≥ 0. 4 7. Let z, w ∈ C be such that |z| = |w| = 2 and zw = 1 + i. Determine |z − w|2.[4] 8. You are an eavesdropper who has intercepted the ciphertext C = 9 sent using RSA. You have[5] obtained the public key (29, 91) and have managed to factor n = 91 as 7 · 13. Determine the original message M . 5 9. It is known that 3i is a root of the polynomial f(x) = 2x5 − 5x4 + 18x3 − 44x2 + 9.[6] (a) Write f(x) as a product of irreducible polynomials in C[x].[4] (b) Write f(x) as a product of irreducible polynomials in R[x].[1] (c) Write f(x) as a product of irreducible polynomials in Q[x].[1] 6 10. True or False. Indicate whether each statement is true or false. No justification is required.[8] (a) For all f(x) ∈ R[x], if f(x) has no real roots, then f(x) is irreducible in R[x].[1] True False (b) {x ∈ Z : gcd(x, 20) = 1} = {y ∈ Z : gcd(2y, 40) = 2}.[1] True False (c) There are infinitely many integers x satisfying the simultaneous congruence[1] { 2x ≡ 4 (mod 8) x+ 1 ≡ 5 (mod 7). True False (d) For every a ∈ Z, the LDE (2a+ 1)x+ ay = 1 has a solution.[1] True False (e) In Z48, the equation [9][x] = [4] has exactly 3 solutions.[1] True False (f) For all d ∈ Z, if d | 10 and d | 15 and d = 10s+ 15t for some s, t ∈ Z, then d = 5.[1] True False (g) For all polynomials f(x) with integer coefficients, if f ( √ 2 1 + i ) = 0, then f ( 1 + i√ 2 ) = 0.[1] True False (h) For all x ∈ Z, if 2x 6≡ 1 (mod 6), then 4x 6≡ 2 (mod 6).[1] True False 7 11. Prove that there does not exist an integer x such that x2 ≡ 5 (mod 6).[4] 8 12. Let p be an odd prime, and let a be an odd integer such that p - a. Prove that[4] ap−1 ≡ 1 (mod 2p). 9 13. Prove that for all a, b, c ∈ Z, c | gcd(a, c) · gcd(b, c) if and only if c | ab.[6] 10 14. Let θ ∈ R be such that 2 sin(θ) cos(θ) = 1√ 2 . Prove that sin(θ) + cos(θ) is irrational.[4] Hint: Use the Rational Roots Theorem. 11 . University of Waterloo MATH 135 Final Assessment Algebra for Honours Mathematics Winter 2020 Instructors: Z. Cramer, B. Ferguson, R. Garbary, J.P. Pretti Submission deadline: Tuesday, April 21 at 4:00pm EDT (Waterloo time) Instructions 1. This assessment consists of 14 questions worth 60 marks total. 2. Unless indicated otherwise, thoroughly justify all of your answers. 3. Prior to the submission deadline, you may not communicate with any person in any form about the final assessment. 4. As an exception to point #3, you may email your instructor in the unlikely event that you believe there is an error on the assessment. Beyond this, instructors will not provide any help with the questions on this assessment. 5. When completing the final assessment, you are permitted to (a) use the internet with the exception of point #3 above; (b) consult any course materials, your own notes, and the final assessment reference sheet posted to LEARN; (c) use any type of calculator to check your answers. However, you must convince a marker (who is not using a calculator) that your work is correct. 6. Submit this assessment to Crowdmark by the deadline above. You may either print the assessment and complete your work in the space provided, or complete the assessment on separate paper. Late submissions will not be accepted. Statement of Academic Integrity By submitting this assessment, I acknowledge the following statements to be true: - The work I submit here is entirely my own. - I have not used any unauthorized aids. - I have not discussed and will not discuss the contents of this assessment with anyone until after the submission deadline. - I am aware that misconduct can result in significant penalties, including failing the course and suspension (covered in Policy 71: https://uwaterloo.ca/secretariat/policies-procedures- guidelines/policy-71). 1 https://uwaterloo.ca/secretariat/policies-procedures-guidelines/policy-71 https://uwaterloo.ca/secretariat/policies-procedures-guidelines/policy-71 1. Let p, q, r be distinct primes. Determine gcd(p10q20r30, (p2qr2)10) in terms of p, q, r.[2] Solution: By GCD from Prime Factorization (GCD PF) gcd(p10q20r30, (p2qr2)10) = gcd(p10q20r30, p20q10r20) = p10q10r20. 2. Given that [x0] = [6] is a solution to [12][x] = [8] in Z64, write down the complete solution.[2] Express your answer(s) in the form [a], where a is an integer and 0 ≤ a < 64. Solution: Since gcd(12, 64) = 4, there are 4 solutions by the Modular Arithmetic Theorem (MAT). These solutions are given by [x0], [ x0 + 64 4 ] , [ x0 + 2 · 64 4 ] , [ x0 + 3 · 64 4 ] . The complete solution is [6], [22], [38], [54]. 3. Determine the units digit (i.e., the ones digit) of 7202.[3] Solution: The units digit is given by the remainder of 7202 after division by 10. Thus, we compute 7202 (mod 10). We obtain 7202 ≡ (72)101 ≡ 49101 ≡ (−1)101 ≡ −1 ≡ 9 (mod 10). Therefore, the units digit of 7202 is 9. 2 4. Write (2− 2i)6 in standard form.[4] Solution: We begin by writing 2− 2i in polar form. Note that |2− 2i| = √ 22 + (−2)2 = √ 4 + 4 = √ 8 = 2 √ 2. As a result, 2− 2i = 2 √ 2 ( 1√ 2 − 1√ 2 i ) = 2 √ 2 ( cos 7π 4 + i sin 7π 4 ) . Thus, by DMT, we have (2− 2i)6 = (2 √ 2)6 ( cos ( 6 · 7π 4 ) + i sin ( 6 · 7π 4 )) = 29 ( cos 21π 2 + i sin 21π 2 ) = 29 ( cos π 2 + i sin π 2 ) (since sine and cosine are 2π-periodic) = 512i 5. Find all z ∈ C that satisfy the equation z6 = 32z. You may express your solution(s) in polar[4] form. Solution: Note that z6 = 32z if and only if z(z5−32) = 0. Thus, either z = 0 or z5 = 32. To solve the second equation, we use the Complex nth Roots Theorem (CNRT). In polar form, 32 = 32(cos 0 + i sin 0), hence the solutions to z5 = 32 are given by z = 5 √ 32 ( cos ( 0 + 2kπ 5 ) + i sin ( 0 + 2kπ 5 )) = 2 ( cos ( 2kπ 5 ) + i sin ( 2kπ 5 )) . (k = 0, 1, 2, 3, 4) Thus, the solutions to z6 = 32z are z = 0 z = 2 (cos 0 + i sin 0) = 2 z = 2 ( cos 2π 5 + i sin 2π 5 ) z = 2 ( cos 4π 5 + i sin 4π 5 ) z = 2 ( cos 6π 5 + i sin 6π 5 ) z = 2 ( cos 8π 5 + i sin 8π 5 ) 3 6. Determine all ineger solutions (x, y) to the linear Diophantine equation 21x+ 15y = 72 such[4] that x ≥ 0 and y ≥ 0. Solution: Using the Extended Euclidean Algorithm, we obtain xi yi ri qi 1 0 21 0 0 1 15 0 1 −1 6 1 −2 3 3 2 − − 0 2 so 21(−2) + 15(3) = gcd(21, 15) = 3. Multiplying by 72/3 = 24, we obtain 21(−48) + 15(72) = 72, so (x, y) = (−48, 72) is a particular solution. By LDET2, the complete solution is {(x, y) : x = −48 + 5n, y = 72− 7n, n ∈ Z} . Note that in order to satisfy the condition x ≥ 0, we need −48 + 5n ≥ 0, and therefore n > 48/5 = 9.4. Since n is an integer, n ≥ 10. Additionally, to satisfy the condition y ≥ 0, we need 72 − 7n ≥ 0, and hence n ≥ 72/7 ≈ 10.286. Since n is an integer, we have n ≤ 10. Thus n = 10 is the only value of n corresponding to a solution in the correct range. Our only solution is (x, y) = (−48 + 5(10), 72− 7(10)) = (2, 2). 4 7. Let z, w ∈ C be such that |z| = |w| = 2 and zw = 1 + i. Determine |z − w|2.[4] Solution: By PM and PCJ, we have that |z − w|2 = (z − w)(z − w) = (z − w)(z − w) = zz − zw − zw + ww. Since |z| = |w| = 2, we have that zz = |z|2 = 22 = 4 and ww = |w|2 = 22 = 4. Additionally, zw = 1 + i and zw = (zw) = 1 + i = 1− i. Consequently, |z − w|2 = zz − zw − zw + ww = 4− (1 + i)− (1− i) + 4 = 6. 8. You are an eavesdropper who has intercepted the ciphertext C = 9 sent using RSA. You have[5] obtained the public key (29, 91) and have managed to factor n = 91 as 7 · 13. Determine the original message M . Solution: We have that e = 29 and n = pq, where p = 7 and q = 13. Since the private key d satisfies the congruence ed ≡ 1 (mod (p− 1)(q − 1)), we have 29d ≡ 1 (mod 6 · 12). That is, 29d ≡ 1 (mod 72). It suffices to solve 29d+ 72y = 1. By the Extended Euclidean Algorithm, we obtain xi yi ri qi 1 0 72 0 0 1 29 0 1 −2 14 2 −2 5 1 2 − − 0 14 We therefore have that 72(−2) + 29(5) = 1, hence 29(5) ≡ 1 (mod 72). It follows that d = 5. We will now use d to decrypt the ciphertext C. We have M ≡ Cd (mod 91), hence M ≡ 95 ≡ (92)2 · 9 ≡ (−10)2 · 9 ≡ 9 · 9 ≡ 81 (mod 91). Since 0 ≤ 81 < n, it follows that M = 81. 5 9. It is known that 3i is a root of the polynomial f(x) = 2x5 − 5x4 + 18x3 − 44x2 + 9.[6] (a) Write f(x) as a product of irreducible polynomials in C[x].[4] Solution: Since f(x) is a polynomial with real coefficients, the Conjugate Roots Theo- rem (CJRT) implies that 3i = −3i is also a root of f(x). Thus, by the Factor Theorem (FT), x− 3i and x+ 3i are factors of f(x). Using long division, f(x) = (x2 + 9)(2x3 − 5x2 + 1) = (x− 3i)(x+ 3i)(2x3 − 5x2 + 1). By the Rational Roots Theorem, if p q is a rational root of 2x3 − 5x2 + 1, then p | 1 and q | 2. In this case we have p q = ±1 or ±1 2 . By trial and error we find that 1 2 is a root of 2x3 − 5x2 + 1, and hence x− 1 2 is a factor. By long division, 2x3 − 5x2 + 1 = ( x− 1 2 ) (2x2 − 4x− 2) = (2x− 1) (x2 − 2x− 1). Finally, we obtain the roots 1 ± √ 2 of x2 − 2x − 1 using the quadratic formula. Thus, x2 − 2x− 1 = (x− (1 + √ 2))(x− (1 + √ 2)). Putting everything together we conclude that f(x) = (2x− 1) (x− 3i)(x+ 3i)(x− (1− √ 2))(x− (1 + √ 2)). Since each of these factors is a linear polynomial, it is irreducible in C[x]. (b) Write f(x) as a product of irreducible polynomials in R[x].[1] Solution: Since x − 3i and x + 3i are not polynomials in R[x], we have that x2 + 9 is irreducible in R[x]. Thus, f(x) = (2x− 1) (x2 + 9)(x− (1− √ 2))(x− (1 + √ 2)) is a product of irreducible polynomials in R[x]. (c) Write f(x) as a product of irreducible polynomials in Q[x].[1] Solution: Since x − (1 − √ 2) and x − (1 + √ 2) are not polynomials in Q[x], we have that x2 − 2x− 1 is irreducible in Q[x]. Thus, f(x) = (2x− 1) (x2 + 9)(x2 − 2x− 1) is a product of irreducible polynomials in Q[x]. 6 10. True or False. Indicate whether each statement is true or false. No justification is required.[8] (a) For all f(x) ∈ R[x], if f(x) has no real roots, then f(x) is irreducible in R[x].[1] True False (b) {x ∈ Z : gcd(x, 20) = 1} = {y ∈ Z : gcd(2y, 40) = 2}.[1] True False (c) There are infinitely many integers x satisfying the simultaneous congruence[1] { 2x ≡ 4 (mod 8) x+ 1 ≡ 5 (mod 7). True False (d) For every a ∈ Z, the LDE (2a+ 1)x+ ay = 1 has a solution.[1] True False (e) In Z48, the equation [9][x] = [4] has exactly 3 solutions.[1] True False (f) For all d ∈ Z, if d | 10 and d | 15 and d = 10s+ 15t for some s, t ∈ Z, then d = 5.[1] True False (g) For all polynomials f(x) with integer coefficients, if f ( √ 2 1 + i ) = 0, then f ( 1 + i√ 2 ) = 0.[1] True False (h) For all x ∈ Z, if 2x 6≡ 1 (mod 6), then 4x 6≡ 2 (mod 6).[1] True False 7 11. Prove that there does not exist an integer x such that x2 ≡ 5 (mod 6).[4] Proof. Every integer x is congruent to its remainder modulo 6 by Congruent Iff Same Re- mainder (CISR). Thus, each x ∈ Z is congruent to exactly one of the integers 0, 1, 2, 3, 4, 5. Furthermore, if x ≡ a (mod 6), then x2 ≡ a2 (mod 6) by Congruence Power (CP). We com- pute these congruences in the following table: x (mod 6) 0 1 2 3 4 5 x2 (mod 6) 0 1 4 3 4 1 From the table we can see that for all integers x ∈ Z, x2 is congruent to 0, 1, 3 or 4 modulo 6. Thus, there does not exist an integer x such that x2 ≡ 5 (mod 6). 8 12. Let p be an odd prime, and let a be an odd integer such that p - a. Prove that[4] ap−1 ≡ 1 (mod 2p). Proof. Observe that since p is an odd prime, gcd(2, p) = 1. Thus, by the Splitting Modulus Theorem (SMT), ap−1 ≡ 1 (mod 2p)⇐⇒ { ap−1 ≡ 1 (mod 2) ap−1 ≡ 1 (mod p) Since a is odd, a ≡ 1 (mod 2) and hence ap−1 ≡ 1p−1 ≡ 1 (mod 2) by Congruence Power. Furthermore, since p - a, Fermat’s Little Theorem implies that ap−1 ≡ 1 (mod p). By the equivalence above, we conclude that ap−1 ≡ 1 (mod 2p). 9 13. Prove that for all a, b, c ∈ Z, c | gcd(a, c) · gcd(b, c) if and only if c | ab.[6] Proof. Let a, b, c ∈ Z, and suppose that c | gcd(a, c) · gcd(b, c). Since gcd(a, c) | a and gcd(b, c) | b, it follows that gcd(a, c) · gcd(b, c) | ab. Thus, by TD, c | ab. Conversely, assume that c | ab. There then exists an integer k such that ab = ck. By Bezout’s Lemma (BL), there exist integers s, t, p, q such that gcd(a, c) = as+ ct and gcd(b, c) = bp+ cq. We then have that gcd(a, c) · gcd(b, c) = (as+ ct)(bp+ cq) = ab(sp) + c(asq + tbp+ tcq) = ck(sp) + c(asq + tbp+ tcq) = c(ksp+ asq + tbp+ tcq). Since kbp+ asq + tbp+ tcq is an integer, we conclude that c | gcd(a, c) · gcd(b, c). 10 14. Let θ ∈ R be such that 2 sin(θ) cos(θ) = 1√ 2 . Prove that sin(θ) + cos(θ) is irrational.[4] Hint: Use the Rational Roots Theorem. Proof. Let a = sin(θ) + cos(θ). Note that a2 = sin2(θ) + 2 sin(θ) cos(θ) + cos2(θ) = 1 + 2 sin(θ) cos(θ) = 1 + 1√ 2 . As a result, a2 − 1 = 1√ 2 . Squaring both sides, we have that a4 − 2a2 + 1 = 1 2 , and therefore 2a4 − 4a2 + 1 = 0. This shows that a = sin(θ) + cos(θ) is a root of the polynomial f(x) = 2x4 − 4x2 + 1. By the Rational Roots Theorem, if p q is a rational root of f(x), then p | 1 and q | 2, hence p q = ±1 or ±1 2 . For every such number, we compute the value of the function f(x): x 1 −1 1/2 −1/2 f(x) −1 −1 1/8 1/8 Since none of these candidates are roots of f(x), we conclude that f(x) has no rational roots. Therefore, sin(θ) + cos(θ) is irrational. 11