We can think of [[Euclid's Algorithm]] geometrically. Say we want to find $gcd(a,b)$ then consider a rectangle of length $a$ and height $b$. Do: - Remove the largest possible square from this rectangle, which will be a $b\times b$ square. - Then with the rectangle that remains repeat. - Keep repeating until you only have a square left. ![[Euclid's Algorithm Pictorially.png]] **Theorem** ([[Bézout's lemma]]): Let $a,b \in \mathbb{N_{*}}$. Then $(a,b)$ is the smallest positive integer so that it can be written in the form $xa+yb$ where $x,y \in \mathbb{Z}$. **Corollary**: If $a, b$ are coprime, then any positive integer can be written as $xa+yb$ for some $x,y \in \mathbb{Z}$