prime factorization approach
this method uses only division (or really, only subtraction)
Recall Example 1.2: Describe \(\{7a+3b : a,b\in\mathbb{Z}\}\). Compare with the theorem.
Look at another examples: \(a=4\) and \(b=6\)
Look at the problem as: show that, among the numbers of the form \(ax+by\), you can find the greatest common divisor of \(a\) and \(b\).
Key insight: experiment shows that the gcd is the smallest positive element of the set of numbers \(ax+by\). But how to prove this?
Let \(I(a,b)=\{ax+by:x,y\in\mathbb{Z}\}\). Notice that the sum and difference of elements of \(I(a,b)\) are also in \(I(a,b)\). So if we take two (positive) elements, we can always subtract the smaller from the larger repeatedly.