Blogs, Proofs

The Division Algorithm

In Comparing fractions with Pythagoras we explored the Pythagorean belief that all numbers are commensurate.  That is, given two numbers, we can find a smaller number that divides both of these numbers.  The reason for this belief was that fact that this is indeed true for all natural numbers (note each natural number is divisible by one, so any pair has a common divisor).  Later the followers of Pythagoras (to their dismay) actually found numbers that do not have a common divisor, thus invalidating their original belief. However, the idea of finding common divisors is still a topic of interest to this day.  In particular, if we can find a greatest such common divisor, this is extremely helpful when working with many number theoretic results.  We will therefore, for any two given natural numbers, determine how to find the greatest common divisor.

Division Algorithm

In order to find a common divisor in Comparing fractions with Pythagoras we found a common divisor by taking the smaller number and subtracting from the larger.  We then looked at the remaining pieces and continued this process until we were left with numbers that all had the same value.  While this process will provide us with a common divisor, we can improve upon the time it takes by changing the algorithm slightly.

By the time Euclid had written the Elements, it was known that instead of subtracting one piece at a time, we could instead subtract as many pieces as possible without making a negative number.  For example, if we work with the numbers

  • Choose two numbers 37 and 7.
  • We can write \(37=7*5+2\).
    • When writing the numbers this way, we notice that a number \(d\) will divide 37 and 7 if and only if it divides 7 and 2.
    • To see this, note that if \(d\) divides 37 and 7, then \(d\) divides 35 since it divides 7.  Therefore, it must also divide 2 in order to be able to get to 37.
    • Now, if \(d\) divides 7 and 2, then it divides both terms in the right hand side of \(37=7*5+2\), so it divides the whole term, which is 37.
  • Now, we write \(7=3*2+1\).
    • Again, a number divides 2 and 7, and therefore 7 and 37, if and only if it divides 2 and 1.
  • We can now write \(2=2*1+0\).
    • Again, a number divides 2 and 1, and therefore 2 and 7, and therefore 7 and 37 if and only if it divides 1 and 0.
  • Since 1 divides 1 and 0, and 1 is the largest divisor of itself, 1 is the greatest common divisor of 7 and 37.

In general, this process will look like

\[ \begin{align*} a&=qb+r_{1} \text{ } 0 \leq r_{1} < b \\ b&=q_{1}r_{1}+r_{2} \text{ } 0 \leq r_{2} < r_{1} \\ r_{i-1}&=q_{i}r_{i}+r_{i+1} \\ \ldots \end{align*} \]

Eventually, the \(r_{n+1}\) must be 0 since each \(r_{i}\) gets strictly smaller after each step until it reaches 0.  When we reach the point where \(r_{n+1}=0\), we can no longer divide, so we stop.  Then \(r_{n}\) is the greatest common divisor of \(a\) and \(b\).

To recap, notice that we have just proven that not only do any two natural numbers have a common divisor, but they also have a unique greatest common divisor.  While the proofs by contradiction have been fun, it is still nice to occasionally show how to find the object that you are looking for.  Here, we have done just that and given a constructive proof.

A helpful equation

With the equations we used to find the greatest common divisor,

\[ \begin{align*} a&=qb+r_{1} \text{ } 0 \leq r_{1} < b \\ b&=q_{1}r_{1}+r_{2} \text{ } 0 \leq r_{2} < r_{1} \\ r_{i-1}&=q_{i}r_{i}+r_{i+1} \\ \end{align*} \]

we note that, if \(r_{n+1}=0\), then

\[ \begin{align*} a-bq&=r_{1} \text{ } 0 \leq r_{1} < b \\ b-q_{1}(a-bq)&=r_{2} \text{ } 0 \leq r_{2} < r_{1} \\ ka+lb&=r_{n} \text{ for some } k,l \in \mathbb{Z} \\  \end{align*} \]

Therefore, if \(d=gcd(a,b)\), there exist integers \(k\) and \(l\) such that \(ka+lb=d\).  Furthermore, if \(ma+nb=c\) for any integers \(m,n\) and \(c\), then \(d\) divides both terms of \(ma\) and \(nb\), so \(d\) divides \(c\).  Hence we have that \(ma+nb=c\) if and only if the greatest common divisor of \(a\) and \(b\) divides \(c\).

I mention this, because we will be using this in the next post when we talk about the difference between irreducibles and primes.  I defined irreducibles and mentioned primes in All those primes, but I didn’t define what a prime number is.  Therefore, we will look at this in more detail.

Conclusion

Here, we have taken the technique used in Comparing fractions with Pythagoras and improved upon it in order to find the greatest common divisor of two natural numbers quicker than we were previously able to.  Furthermore, the technique we used allowed us to find a formula that will be extremely helpful in the next post.  In the process, we were able to some constructive proofs.  While this one was more involved than the previous proofs we did by contradiction, it made up for this fact by constructing the answer we were looking for.

Thanks for visiting the blog and reading the post.  If you liked it, make sure to follow the blog here on FacebookTwitter or Instagram and be sure to share it so that others can also enjoy it.  I hope you’ll join us again when we talk about irreducible and prime numbers.

1 thought on “The Division Algorithm”

We'd love to hear your thoughts!

This site uses Akismet to reduce spam. Learn how your comment data is processed.