Finding Integer Solutions Worksheet With Answer Key - 7th Grade, Serin Hong (Page 2 of 6) in pdf

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

Math 7 Spring 2016

Instructor: Serin Hong

2. (a) (5 pts) Give a deﬁnition of the greatest common divisor of three integers a, b, c.

Solution. The greatest common divisor of a, b, c is the largest integer d such that d a, d b, d c.

(b) (15 pts) Prove that gcd(a, b, c) = gcd(gcd(a, b), c) for any integers a, b, c.

Solution. Let g

= gcd(a, b), g

= gcd(g

, c) and g = gcd(a, b, c). We want to show g

= g.

Note that g

, as the greatest common divisor of g

and c, divides g

= gcd(a, b), which divides

both a and b. Therefore g

also divides both a and b. On the other hand, g

divides c as the

greatest common divisor of g

and c. Hence g

is indeed a common divisor of a, b, c, and we have

gcd(a, b, c) = g.

Now we note that g = gcd(a, b, c) divides a, b, c. Since g

= gcd(a, b), there exist integers x, y such

that ax + by = g

. As g divides both a and b, it must divide ax + by = g

. Then g is a common

divisor of g

and c, implying that g

= gcd(g

, c).

Thus we have both g

g and g

, thereby concluding that g

= g as desired.

Remark. You can also prove this using prime factorizations of a, b, c.

Solution. By part (b), we have gcd(408, 884, 1071) = gcd(gcd(408, 884), 1071).

We ﬁrst ﬁnd gcd(408, 884) by the Euclidean algorithm as follows:

884 = 408 2 + 68,

408 = 68 6.

Here we ﬁnd gcd(408, 884) = 68.

Then we perform the Euclidean algorithm to ﬁnd gcd(68, 1071):

1071 = 68 15 + 51,

68 = 51 1 + 17,

51 = 17 3.

The algorithm gives us gcd(68, 1071) = 17.

(d) (10 pts) Do there exist integers x, y, z such that 408x + 884y + 1071z = 123?

(Hint: You don’t have to solve the equation.)

Solution. By part (b), we know that 17 divides 408, 884 and 1071. Therefore 17 must divide

408x + 884y + 1071z if x, y, z are integers. However, 123 = 17 7 + 4 is not divisible by 17. Hence

there do not exist integers x, y, z satisfying 408x + 884y + 1071z = 123.

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

Related Articles

Related forms

Related Categories