Pick two positive numbers $a$ and $b$. They appear as two piles of dots. Take one pile away from the other, over and over, until one pile is empty: what is left in the other pile is $\gcd(a,b)$. Along the way the usual rows $a = qb + r$ of the Euclidean algorithm fill in. Then use the recipe cards to solve $ax + by = \gcd(a,b)$ (the Extended Euclidean Algorithm).
1. Take one pile away from the other
2. The Euclidean algorithm
3. Recipe cards
Each number $d$ gets a card with a pair $(x, y)$ on top, meaning $a x + b y = d$, with $a$ = and $b$ = . Click each blank card to fill it in. Work from the top down: each card needs the ones above it.
How it works
- Subtracting one pile from the other never changes the gcd: $\gcd(x, y) = \gcd(x, y - x)$. So every pile is always a multiple of $\gcd(a,b)$ (tick the "Circle the dots" box to see the groups), and when one pile is empty, the other is the gcd, since $\gcd(g, 0) = g$.
- Taking $b$ away from $a$ as many times as you can ($q$ times) leaves a remainder $r < b$: that is one row $a = qb + r$.
- For the recipe cards, the first row's cards come for free: $a = 1\cdot a + 0\cdot b$ and $b = 0\cdot a + 1\cdot b$. Each remainder is $r = $ (left) $- \; q\,\cdot$ (middle), so its card is the left card minus $q$ times the middle card. The card above the gcd is the answer $(x, y)$. The last card (above the $0$) is a check: its $x$ and $y$ satisfy $ax + by = 0$.
- See also the textbook, Sections 3.1 (The Euclidean Algorithm), 3.2 (The Extended Euclidean Algorithm) and 3.3 (Computing modular inverses).