Let $a,b \in \mathbb{Z}$. We say that $a$ divides $b$, written $a \given b$, if there’s an integer $n$ such that $b = na$. If $a$ divides $b$, then $b$ is divisible by $a$, and $a$ is a divisor or factor of $b$. Also, $b$ is called a multiple of $a$.

This article covers the greatest common divisor and how to find it using the Euclidean Algorithm, the Extended Euclidean Algorithm to find solutions to the equation $ax + by = gcd(a, b)$ where $x, y$ are unknowns.

The Extended Euclidean Algorithm finds solutions to the equation $ax + by = gcd(a, b)$ where $x, y$ are unknowns. This article covers a few applications of the Extended Euclidean Algorithm like finding the modular multiplicative inverse of a number and finding solutions for linear congruence equations.