# Euclidean Algorithm

The Euclidean algorithm is an algorithm for finding the greatest common divisor of two numbers.

Euclidean algorithm is a college-level concept that would be first encountered in a number theory course.

### Prerequisites

Congruence: | A congruence is an equation in modular arithmetic, i.e., one in which only the remainders relative to some base, known as the "modulus," are significant. |

Greatest Common Divisor: | The greatest common divisor of a set of integers is the largest integer that divides all of them. |