Discrete Mathematical Structures: Lecture 3.7 - The Euclidean Algorithm

Discrete Mathematical Structures, Lecture 3.7: The Euclidean algorithm.

Around 300 BC, Euclid found an algorithm to compute the greatest common divisor of two integers, which we introduce in this lecture. We then show how d=gcd(a,b) is the smallest positive integer that can be written as d=ax+by for some integers x,y. By keeping track of some extra information while doing the Euclidean algorithm, we can explicitly determine x and y. This is called the "extended Euclidean algorithm". It helps us solve certain modular arithmetic equations which we'll need when we study cryptography later in this course.

Course webpage: http://www.math.clemson.edu/~macaule/math4190-online.html