Transcript Using the Euclidean Algorithm

MAT 320 Spring 2011
Section 1.2
320 = 276 ·1 + 44
276 = 44 ·6 + 12
44
= 12 ·3 +
8
12
=
8
·1 +
4
8
=
4
·2 +
0
Start by dividing the smaller number into
the larger number. Write the result in the
form a = bq + r.
The divisor (b) from the previous step
becomes the dividend (a) in the next step.
The remainder (r) from the previous step
becomes the divisor (b) in the next step.
Keep going until you get a remainder of
zero. The last non-zero remainder is the
greatest common divisor of the original a
and b you started with.
In this case, (320, 296) = 4.
592 = 346 ·1 + 246
346 = 246 ·1 + 100
246 = 100 ·2 + 46
Start by dividing the smaller number into
the larger number. Write the result in the
form a = bq + r.
The divisor (b) from the previous step
becomes the dividend (a) in the next step.
The remainder (r) from the previous step
becomes the divisor (b) in the next step.
100 = 46 ·2 +
8
46
=
8
·5 +
6
8
=
6
·1 +
2
Keep going until you get a remainder of
zero. The last non-zero remainder is the
greatest common divisor of the original a
and b you started with.
6
=
2
·3 +
0
In this case, (346, 592) = 2.
Find (54, 240).
1.

The GCD is 6.
Find (674, 308).
2.

The GCD is 2.

Given positive integers a and b with
d = (a, b), there exist integers U and V
such that aU + bV = d.

For example, (324, 148) = 4, and it turns
out that 324 · 16 + 148 · (-35) = 4.

How do we find the values of U and V?

We will use the Euclidean algorithm to find the values of U
and V.

Use the Euclidean algorithm, and then solve all of the
equations (except for the last one) for the remainder.
324 = 148 ·2 + 28
28
= 324 +(-2)· 148
148 = 28 ·5 +
8
8
= 148 +(-5)· 28
28
=
8
·3 +
4
4
= 28 +(-3)· 8
8
=
4
·2 +
0

We want to find values of U and V such that
4 = U · 148 + V · 324.

In the language of linear algebra, we want to express
4 as a “linear combination” of 148 and 324.

Notice that the last equation we wrote down has 4
as a linear combination of 28 and 8, which is not
quite what we want.
4
= 28 +(-3)· 8

So what do we do now? Use the previous equation
to substitute into your linear combination.

Simplify your equation, but leave the boxed numbers
alone!
4
= 28 +(-3)· 8
4
= 28 +(-3)· ( 148 +(-5)· 28 )
4
= 16 · 28 +(-3)· 148

Now we have
4
= 16 · 28 +(-3)· 148

which expresses 4 as a linear combination of
28 and 148. We’re getting closer to what we
want.

Continue substituting, at each step using the
previous equation

4
= 16 · 28 +(-3)· 148
4
= 16 · ( 324 +(-2)· 148 ) +(-3)· 148
4
= 16 · 324 +(-35)· 148
We finally have our values of U and V
guaranteed by Bézout’s Theorem.

Use the Euclidean Algorithm to show that
(15, 36) = 3.

Use back-substitution to find integers U and V
so that 3 = 15U + 36V.
 3 = 15 · 5 + 36 · (-2)

Earlier we found out that (54, 240) = 6.

Bézout’s Theorem tells us that we can write 6 as a
linear combination of 54 and 240.

Since 6 divides 54 and 6 divides 240, every linear
combination of 54 and 240 is divisible by 6. (WHY?)

Therefore, 6 is the smallest positive integer that can be
written as a linear combination of 54 and 240.

In fact, the “span” of 54 and 240 is exactly the set of
multiples of 6!