Mid-term Exam 2015, Questions and answers PDF

Preview

Summary

Mid-term...

Description

MATH 210

Midterm Examination

February 26, 2015

Instructions: The exam has six questions labelled 1 through 6. Each question has subquestions. The total mark is 70. The exam paper has seven pages. The exam is two hours in length. To receive full credit you must explain your answers. Write all answers in the space provided. You may use the backs of the pages if necessary. Approved calculator (Casio fx-991) is permitted. NO data sheet is allowed.

Name: Student Number:

1

2

3

Page 1 of 7

4

5

6

Total

Page 2 of 7

MATH 210 March 2014

1. [5pts each] (a) Find all solutions of 98x + 35y = 14. Solution: Step 1. We determine gcd(98, 35) by the Euclidean algorithm. 98 = 2 · 35 + 28 35 = 1 · 28 + 7 28 = 4 · 7 + 0 Therefore gcd(98, 35) = 7. Since 7|14, we know that there are infinitely many solutions to our equation. Step 2. By the reverse Euclidean algorithm, we find that 7 = 35 − 28 = 35 − (98 − 2 · 35) = 98(−1) + 35(3). Multiplying 2 to both sides of this equation, we get 14 = 98(−2) + 35(6). Thus we have a special solution: x0 = −2 and y0 = 6. Step 3. Therefore, the general solution is given by x = −2 + t(35/7) = −2 + 5t, y = 6 − t(98/7) = 6 − 14t with t ∈ Z.

Alternative Solution: Using unimodular row reduction, we get         98 1 0 −7 1 −3 7 −1 3 14 −2 6 −→ −→ −→ 35 0 1 35 0 1 0 5 −14 0 5 −14 Hence x = −2 + 6t, y = 6 − 14t with t ∈ Z. (b) Calculate gcd(n2 − 1, n3 + n + 2) for any integer n ∈ Z. Solution 1: We can factor n2 − 1 as n2 − 1 = (n − 1)(n + 1). By long division, we get n3 + n + 2 = (n + 1)(n2 − n + 2)

Page 3 of 7

MATH 210 March 2014

and n2 − n + 2 is not divisible by n + 1 nor by n − 1. Therefore, gcd(n2 − 1, n3 + n + 2) = n + 1.

Solution 2: Regard n2 − 1 and n3 + n + 2 as polynomials of n over Z. By The Eulidean algorithm, we have n3 + n + 2 = n(n2 − 1) + 2n + 2 1 n2 − 1 = (2n + 2) (n − 1) 2 so gcd(n2 − 1, n3 + n + 2) = n + 1, as gcd is a moinc polynomial.

Page 4 of 7

MATH 210 March 2014

2. [5pts each] (a) [5 pts] Find polynomials q(x) and r(x) such that f (x) = q(x)g (x) + r(x) where f (x) = x4 + 3x3 + 2x + 4 and g(x) = x2 + 3x + 1 in Z5 [x]. Solution: We do the long division x4 + 3x3 + 2x2 + 4 = (x2 + 3x + 1)(x2 − 1) + (5x + 5) Then q(x) = x2 − 1 = x2 + 4, r(x) = 5x + 5 = 0.

(b) Find all solutions to [25][x] = [10] in Z65 . Solution: Step 1: The equation [25][x] = [10] in Z65 is equivalent to the linear congruence 25x ≡ 10 (mod 65)

(1)

Now the congruence equation (1) has a solution as gcd(25, 65) = 5 and 5|10. Indeed, there are gcd = 5 incongruent solutions to the congruence. Step 2: The congruence equation (1) is equivalent to the linear Diophantine equation of the form 25x − 65y = 10 (2) This Diophantine equation has a special solution (x0 , y0 ). We want to find it. First we divide (2) by 5 to get another Diophantine equation 5x − 13y = 2

(3)

and find a solution to (3). By inspection, or by applying the Euclidean algorithm, 13 = 5 × 2 + 3, 5 = 3 × 1 + 2 so that 2 = 5 − 3 = 5 − (13 − 5 × 2) = 5(3) − 13 · 1. Therefore, x = 3, y = 1 is a special solution to (3). Step 3: The general solution to (2) is of the form x= 3+

−65 25 t = 3 − 13t, y = 1 − t = 1 − 5t 5 5

with t ∈ Z.

Page 5 of 7

MATH 210 March 2014

Step 4: In Z65 , there should be gcd = 5 incongruent solutions. So x = 3 − 13t, with t = 0, 1, 2, 4, 5 Thus, x = 3, 3 − 13 = −10 = 55, 3 − 13 · 2 = −23 = 42, 3 − 13 · 3 = −36 = 29, 3 − 13 · 4 = −49 = 16 are the solutions. Indeed, 25 · 3 = 75 ≡ 10 (mod 65), 25 · (−10) = −250 ≡ 10 (mod 65), 25 · (42) = 1050 ≡ 10 (mod 65), 25 · (−36) = −900 ≡ 10 (mod 65), 25 · 16 = 400 ≡ 10 (mod 65).

Page 6 of 7

MATH 210 March 2014

3. [5pts each] True or false. Justify your answer providing a short proof if true, or a counterexample if false. (a) Any integral domain is a field. Solution: False. For instance, Z is an integral domain but not a field. (b) The rings Z9 and Z3 × Z3 are isomorphic. Solution: False. We know that Z9 = { 0, 1, 2, 3, 4, 5, 6, 7, 8 } and Z3 × Z3 = { (0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2) }. Suppose that there is an isomorphism f : Z9 → Z3 × Z3 . Then f (0) = (0, 0) and f (1) = (1, 1). Then f (2) = f (1 + 1) = f (1) + f (1) = (1, 1) + (1, 1) = (2, 2). Then f (3) = f (2 + 1) = f (2) + f (1) = (2, 2) + (1, 1) = (3, 3) = (0, 0). But f is one-to-one, so f (0) 6= f (3). Contradiction. Alternative solution: The number of units in Z9 is ϕ(9) = 9(1 − 31) = 6. The units are 1, 2, 4, 5, 7, 8. The number of units in Z3 × Z3 are ϕ(3)ϕ(3) = 3(1 − 13 )3(1 − 31 ) = 4. The units are (1, 1), (1, 2), (2, 1), (2, 2). So they are not isomorphic. (c) Let R be an integral domain. Suppose that char(R) 6= 0. Then char(R) = p: prime. Solution: True: Suppose that char(R) = n 6= 0. Then n is the smallest positive integer such that n1R = 0R . Suppose that n = rs with 0 < r < n and 0 < s < n. Then 0R = n1R = (rs)1R = (r 1R )(s1R ). But R is an integral domain, so there is no non-trivial zero divisors. This implies that r1R = 0R ,

or s1R = 0R .

But this contradicts the minimality of n. Hence n cannot factor into a product of two integers r, s, 0 < r, s < n. Therefore, n is prime. (d) The set of units in a ring R with identity is a subring of R. Solution: False. To be a subring of R, the zero element must be in the set of units in R. But 0 is not a unit of R.

Page 7 of 7

MATH 210 March 2014

4. [5pts each] (a) Use Euler’s Theorem to compute 33101 (mod 40). Solution: The Euler theorem states that aϕ(m) ≡ 1 (mod m) for any a ∈ Z, m a positive integer and ϕ is the Euler function. Now for m = 40, ϕ(40) = 40(1 − 12 )(1 − 51 ) = 16. Then 3316 ≡ 1 (mod 40). Write 101 = 16 · 6 + 5, so 33101 = (3316 )6 · 335 (mod 40) ≡ 335 (mod 40) ≡ (−7)5 (mod 40) ≡ 49 · 49(−7)5 (mod 40) ≡ 81 · (−7) (mod 40) ≡ −7 (mod 40) ≡ 33 (mod 40). Thus, 33101 ≡ 33 (mod 40). (b) Use the Chinese Remainder Theorem to solve the system of linear congruences x ≡ 2 (mod 3) x ≡ 3 (mod 5) x ≡ 1 (mod 7) Solution: Step 1: Solve the system x ≡ 2 (mod 3) x ≡ 3 (mod 5) Since gcd(3, 5) = 1, there exist u, v ∈ Z such that 3u + 5v = 1. For instance, u = −3, v = 2 is a solution. Then a simultaneous solution is t = 2 + 3(−3)(3 − 2) = 2 − 9 = −7 (mod 15)

Page 8 of 7

MATH 210 March 2014

Step 2: Solve the system x ≡ −7 (mod 15) x ≡ 1 (mod 7) Since gcd(15, 7) = 1, there exist u1 , v1 ∈ Z such that 15u1 + 7v1 = 1. Take, for instance, u1 = 1, v1 = −2. Then a simultaneous solution is t = −7 + 15(1)(1 + 7) = −7 + 15 · 8 = −7 + 120 = 113 ≡ 8 (mod 105) Therefore x ≡ 8 (mod 105) is the solution.

Page 9 of 7

MATH 210 March 2014

5. [5pts each] (a) Let f : Z → Z8 be the homomorphism defined by f (n) := n (mod 8). Determine Ker(f ) and Im(f ). Solution: We have Ker(f ) = { n ∈ Z | f (n) = n (mod 8) = 0 ∈ Z8 } = { n = 8k | k ∈ Z } = 8Z and Im(f ) = { 0, 1, 2, 3, 4, 5, 6, 7 } = Z8 .   a 0 | a, b, c ∈ Z . Then S is a ring with identity. Let f : S → Z (b) Let S := b c  a 0 be the map defined by f = a. Show that f is an onto homomorphism but b c not an isomorphism. 

Solution: S is a subring of M2 (Z). Indeed, subtraction and multiplication.





0 0 0 0



and



Now suppose that f : S → Z is defined by f    a1 0 a2 0 ∈ S and B = ∈ S we have b1 c 1 b2 c 2

1 0 0 1





a 0 b c

are in S. S is closed under 

= a. Then for A =

f (A + B) = f (A) + f (B) and f (AB) = f (A)f (B). Hence f is a homomorphism. It is clearly onto, as for any a ∈ Z, is a matrix A=   there    a 0 a 0 a 0 such that f (A) = a. However, f is not one-to-one, as 6= b c b c b1 c 1 are sent to the same element a ∈ Z.

Page 10 of 7

MATH 210 March 2014

6. [5pts each] (a) Let R and S be commutative rings with identity. Let f : R → S be a ring homomorphism. Does f map zero divisors of R to zero divisors of S ? Solution: No: If f happens to be an isomorphism, then the statement is true. But when f is merely a homomorphism, the statement is false. Here is an example. Let R = Z2 × Z2 and S = Z2 and let f : Z2 × Z2 → Z2 be given by f ((a, b)) = a. We know that (1, 0) is a zero divisor of Z2 × Z2 as (1, 0)(0, 1) = (0, 0). Now f maps a zero divisor (1, 0) to 1, which is definitely not a zero divisor of Z2 . (b) Let Φ : Z[x] → Zp [x] (p :prime) be the map Φ(a0 + a1 x + a2 x2 + · · · + an xn ) = a¯0 + a¯1 x + a¯2 x2 + · · · + a¯n xn where a¯i := ai (mod p) for every i. Show that Φ is a homomorphism, which is onto. What is the kernel Ker(Φ)? Solution: Since Zp [x] has characteristic p, we have, for any a, b ∈ Z, (a + b) (mod p) = a (mod p) + b (mod p), (ab) (mod p) = (a (mod p))(b (mod p)). Let f (x) = a0 +a1 + x+ a2 x2 +· · ·+ an xn with an 6= 0 and g(x) = b0 + b1 x+ b2 x2 + · · ·+bm xm with bm 6= 0 and m ≤ n. Then f (x) + g(x) = (a0 + b0 ) + (a1 + b1 )x + (a2 + b2 )x2 + · · · + (am + bm )xm + · · · + an xn , and f (x)g(x) = a0 b0 + (a1 b0 + a0 b1 )x + (a2 b0 + a1 b1 + a0 b2 )x2 + · · · + (am b0 + am−1 b1 + · · · + a0 bm )xm + · · · + an bm xn+m . Then Φ(f (x) + g(x)) = Φ(f (x)) + Φ(g(x)) and Φ(f (x)g (x)) = Φ(f (x))Φ(g(x)). Hence Φ is a homomorphism. Φ is obviously onto, as for any a ¯ ∈ Zp , there is an a ∈ Z such that a (mod p) = a ¯. Thus, for any f¯(x) = a¯0 + a¯1 x + · · · + a¯n xn ∈ Zp [x], there exists f (x) = a0 + a1 x + · · · + an xn ∈ Z[x] such that Φ(f (x)) = f¯(x). Φ is not 1 − 1 as f (x) = 1 + x + px2 and g(x) = 1 + x are mapped to the same element 1 + x ∈ Zp [x]. The kernel of Φ is the set of all polynomials f (x) ∈ Z[x] such that Φ(f (x) = 0 ∈ Zp [x], that is, f (x) must have all coefficients multiple of p. Hence Ker(Φ) = pZ[x]....