Compsci 225 Assignment 2 Semester 2, 2022

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Compsci 225

Assignment 2

Semester 2, 2022

Upload your completed assignment as a single PDF document on Canvas before the due date. Show all working; problems that do not show their work will typically receive reduced or zero marks. Late assignments cannot be marked under any circumstances.  (With that said: if you find yourself unable to complete this assignment due to illness, injury, or personal/familial misfortune,

please email us as soon as possible. We can come up with solutions to help you succeed in CS225!) This assignment covers chapters 2-3 in your coursebook. Have fun with it!

1.   (a) Find the gcd of 149 and 84 using Euclidean algorithm.                                        [3 marks]

(b) Use the extended Euclidean algorithm to express gcd(149 , 84) in the form 149x + 84y

where x, y e Z. Show all working.                                                                          [2 marks]

(a) The steps are routine

a

b

q

r

149

84

1

65

84

65

1

19

65

19

3

8

19

8

2

3

8

3

2

2

3

2

1

1

2

1

2

0

Hence, gcd of 149 and 84 is 1

Marking instructions: 3 points.

● 1/3 points: 1 point for good faith attempt

● 2/3 points: an attempt with few minor slips

● 3/3 points: correct solution

(b) From the table in 1(a), we have

1   =   3 . 1 · 2 (1)

2   =   8 . 2 · 3                                                      (2)

3   =   19 . 2 · 8                                                    (3)

8 =   65 . 3 · 19                                                  (4)

19   =   84 . 1 · 65 (5)

65   =   149 . 1 · 84 (6)

Working our way backwards, we have

gcd(149, 84) = 1   =   3 . 1 · 2

= 3 . 1 · (8 . 2 · 3)

= 3 · 3 . 1 · 8

= 3 · (19 . 2 · 8) . 1 · 8 =   3 · 19 . 7 · 8

= 3 · 19 . 7 · (65 . 3 · 19) = 24 · 19 . 7 · 65

= 24 · (84 . 1 · 65) . 7 · 65 =   24 · 84 . 31 · 65

= 24 · 84 . 31 · (149 . 1 · 84) = 55 · 84 . 31 · 149

using (1)

using (2)

using (3)

using (4)

using (5)

using (6)

Marking instructions: 2 points.

● 1/2 points: solution with with minor flaw

● 2/2 points: for correct solution

2.  Prove the result from the coursebook on page 30.  Let m, n, k be integers with k > 0.  Show that m 三 n  mod k if and only if [m] = [n].                                                                  [6 marks]

To show m 三 n mod k if and only if [m] = [n] we need to prove the following two claims: Claim 1: If m 三 n mod k then [m] = [n]

Assume m 三 n mod k . To show [m] = [n], we need to show that [m] C [n] and [n] C [m]. Let us first prove that [m] C [n].

Let a e [m]. Then by definition, a 三 m mod k . By the transitivity property of congruence we then have

a 三 m mod k and m 三 n mod k ÷ a 三 n mod k

So, a e [n] and hence [m] C [n]. Reversing the roles of m and n in the argument above we similarly conclude that any element of [n] is also an element of [m]. Therefore,

[m] = [n]


2022-09-13