University of WaterlooMATH 135 SAMPLE Final ExaminationAlgebra for Honours Mathematics Fall 2016Instructors: M. Akash, S. Bauman, C. Bruni, B. Charbonneau, A. Gamache, R. Garbary,G. Gauthier-Shalom, I. Goulden, J. Koeller, W. Kuo, Y. Liu, A. Menezes, R. Moosa, P. Nelson,J. Pretti, R Trelford, D. Wagner, R. WillardInstructions1. Fill in your ID number and User ID above.2. Write your answers in the
...[Show More]

**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-Shalom, 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.

1

**For 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]**

2

3. Give all the solutions to *z*3 + 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]**

3

5. Determine all integers *x *and *y *such that **[3 marks]**

*• *6*x *+ 10*y *= 14, and

*• x ≡ *3 (mod 7), and

*• *20 *< y < *40.

6. Consider the polynomial *p*(*x*) = *x*5 + 2*x*4 + 6*x*3 + 12*x*2 *- *27*x - *54. One root of this polynomial is 3*i*.

Express *p*(*x*) as a product of five linear polynomials in C[*x*]. **[3 marks]**

4

**For 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 *= *-*18*i *is 18(cos (32*π *) + *i *sin (32*π *)).

(g) gcd(29931005101*; *29831005102) = 29831005101

5

**The 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 *+ 18*y *= 6 has an integer solution. **[4 marks]**

6

9. Prove that if *w *is an *nth *root of unity, then *w*1 is also an *nth *root of unity.

(Recall: The *nth *roots of unity are the *nth *roots of 1.) **[4 marks]**

7

10. Let *a 2 *Z. Prove that if *a*221 *≡ *20 (mod 23) and 100 *< a < *125, then *a *= 112. **[3 marks]**

8

11. 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.

9

12. 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]**

10

13. Let *f*(*x*) =

*n*X *k*

=0

*xk *be a polynomial in Z2[*x*]. **[5 marks]**

Prove by mathematical induction that for all *n 2 *N, [*f*(*x*)]2 =

*n*X *k*

=0

*x*2*k*.

11

14. Let *a *and *b *be coprime positive integers.

Prove that *f*(*s; t*) *2 *N *× *N : *as *+ *bt *= *abg *= *;*. **[3 marks]**

12

**This 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.

13

**This 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.

14

**MATH 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*,

6*n ≡ *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 *z*3 + 27 = 0 in standard form.

**Answer: ***p*3 27 cos *π*+2 3*kπ* + *ip*3 27 sin *π*+2 3*kπ*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

[Show Less]