Problem Set Worksheet (Page 4 of 8) in pdf

Problem Set Worksheet Page 4

2. Use the Euclidean Algorithm to obtain integers x and y satisfying the following:

(a) gcd (56, 72) = 56x + 72y

We ﬁnd gcd (56, 72) by using the Division Algorithm, and then “retracing our

steps.”

72 = q

(56) + r

72 = (1) (56) + 16

(eq. 1)

Repeat using 56 and 16

56 = q

(16) + r

56 = (3) (16) + 8

(eq. 2)

Repeat using 16 and 8.

16 = q

(8) + r

16 = (2) (8) + 0

gcd (56, 72) = last non-zero remainder

gcd (56, 72) = 8

So, we want x and y such that 56x + 72y = 8

From eq. 2, 8 = 56 − (3) (16)

(eq. 3)

From eq.1, we have 16 = 72 − (1) (56)

Hence, eq. 3 becomes 8 = 56 − (3) (72 − (1) (56))

⇒ 8 = (4) (56) − (3) (72)

i.e., 56 (4) + 72 (−3) = 8

Our particular solutions is (x

, y

) = (4, −3)

All other solutions are of the form

x = x

y = y

−

for t ∈ Z

Hence, all solutions are of the form:

x = 4 +

y = −3 −

for t ∈ Z

i.e., x = 4 + 9t;

y = −3 − 7t

for t ∈ Z

Problem Set Worksheet Page 4