Challenge: Trace GCD

Before moving on, trace GCD($48$, $18$) by hand. Write down each recursive call and the values of $a$ and $b$. Start: GCD($48$, $18$). What is $48 \mod 18$? That becomes the new $b$.

What is the new $a$? Keep going until you hit the base case. Check your answer: the sequence should be GCD($48$, $18$) → GCD($18$, $12$) → GCD($12$, $6$) → GCD($6$, $0$). The answer is $6$. If you got this right, you understand how GCD shrinks toward the base case. If not, re-read the GCD units.