Basics for GCD Using Euclidean Algorithm

This class discusses the Basics of GCD Using the Euclidean Algorithm.

The reader should have prior knowledge of the division theorem. Click Here.

If a, b, q, and r are integers and satisfy a = bq + r, then GCD(a, b) = GCD(b, r)

Assume: d1 = GCD(a, b)

d2 = GCD(b, r)

We need to show d1 = d2

d1 = GCD(a, b)

d1 divides a

d1 divides b

d1 also divides r, because r = a – bq.

Hence, any common divisor of a and b is a common divisor of b and r.

d2 = GCD(b, r)

So d1 <= d2

Similarly, d2 = GCD(b, r)

d2 divides b

d2 divides r

d2 divides a, because a = bq + r

Hence, the common divisor of b and r is the common divisor of a and b.

d1 = GCD(a, b) we say d2 <= d1

When this happens d1 <= d2 and d2 <= d1? when d1 = d2

We showed d1 = d2.