greatest common denominator

1 Bezout's identity

For \(m\) and \(n\), the gcd is the smallest integer \(d\) such that there exists \(r\) and \(s\) where \(d=rm + sn\)

2 Euclid's algorithm

Start with inputs \(y_0\) and \(y_1\), \(y_0>y_1\).

Repeat until \(y_{i+1}=0\):

set \(y_{i+1} = y_{i} \mod y_{i-1}\)

The GCD is the last \(y_i > 0\).

2.1 scratch work proof

This works because, for \(a>b\), \(\gcd(a,b) = \gcd(b,a\mod b)\). Why is this true? Let \(\gcd(a,b) = d\). First, \(d \mid (a\mod b)\): note that \(d \mid a\) and \(d \mid b\), so \(a = m d\) and \(b = nd\). Note that \(a \mod b = a - kb\) for some \(k\). So \(a\mod b\) is the difference of two multiples of \(d\). So \(d \mid (a \mod b)\). Next, note that \(\gcd(a,b)\) must be the greatest common denominator between \(b\) and \(\gcd(a\mod b)\). Say there was a larger common denominator, \(d'\). Then \(d' \mid b\) and \(d' \mid a \mod b = a-kb\). Then \(d' \mid a - kb + kb = a\). But if \(d' \mid a\), then it is the gcd!

3 Comments

3.1 If \(\gcd(a,b) = d\), then for every \(k\), we can find \(s\) and \(r\) such that \(sa + rb = kd\)

This comes from Bezout's identity.

3.2 If \(\gcd(a,b) = 1\), then for every \(n>ab\), we can find \(s,r > 0\) such that \(sa + rb = n\)

3.2.1 scratch work proof

Let \(a > b\). Consider the set \(S = \{ka\mod b \mid k \in [1...b]\}\). Then:

for every \(s,s' \in S\), \(s\neq s'\). If not, then \(s\equiv s' \mod b\), so \(ka\equiv k'a \mod b\). Then, \(b \mid (k-k')(a)\). But this cannot be, because \(a\) doesn't contain any factors of \(b\), and \((k-k') < b\).

So, \(|S| = b\) and \(S = [0...b-1]\). Then, the sequences [a,a+b,a+2b,…], [2a,2a+2b,…], … [ba, ba+2b,…] together cover the number line past \(ab\) completely. To see this, note that there are \(b\) sequences which are spaced \(1\mod b\) distance from each other.

3.3 If \(\gcd(a,b) = d\), then there exists \(n_0\): for every \(n>n_0\), we can find \(s,r>0\) such that \(sa + rb = n\)

3.3.1 scratch work proo

That is, we can make every scalar multiple (above \(n_0\)) of \(d\) using \(a\) and \(b\). First, let's write \(a = md\) and \(b = nd\). Let's take a look at the form of the combination \(sa + rb\) that we will finish with. This can be written: \(d(ms+nr)\). But notice that \(gcd(m,n) = 1\). If it were not the case, then we could find a bigger divisor \(d' > d\). So, we can use the previous comment, and notice that any integer \(k>mn\) can be written using some combination: \(sm + rn\).