Basics for GCD Using Euclidean Algorithm || Lesson 121 || Discrete Math & Graph Theory ||

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 lt= 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 lt= d1
When this happens d1 lt= d2 and d2 lt= d1? when d1 = d2
We showed d1 = d2.

Link for playlists: