Finding Integer Solutions Worksheet With Answer Key - 7th Grade, Serin Hong

Math 7 Spring 2016

Instructor: Serin Hong

PROBLEM SET 1 SOLUTIONS

1. (a) (5 pts) Use the Euclidean algorithm to ﬁnd gcd(1287, 403).

Solution. The Euclidean algorithm is performed as follows:

1287 = 403 3 + 78,

403 = 78 5 + 13,

78 = 13 6.

Hence we have gcd(1287, 403) = 13.

(b) (10 pts) Find all the integer solutions of 1287x + 403y = 104.

Solution. Since 104 = 13 8 is divisible by 13 = gcd(1287, 403), the equation 1287x + 403y = 104

has integer solutions.

We can rewrite the ﬁrst two equations in part (a) as 78 = 1287

403 3 and 13 = 403

78 5.

Substituiting the former to the latter yields 13 = 403

(1287

403 3) 5 = 403 16

1287 5. Then

104 = 13 8 = (403 16

1287 5) 8 = 403 128

1287 40,

1287

403

so x =

40, y = 128 is a solution. From

= 99 and

= 31, we can parametrize all the integer

solutions by

x =

31t,

y = 128 + 99t where t

0 votes

Parent category: Education