Greatest Common Divisors; Euclidean Algorithm.

January 5, 2013

Recently, I’ve been learning to program in a new language and have been doing Project Euler problems for practice — of course, as the name suggests, most of these problems deal explicitly with problems which must be solved (efficiently) with mathematical techniques.  Two of the most common algorithms I’ve used are: Prime Testing, GCD Finder.  I’ll post about the former later, but the latter is an interesting problem in its own right:

Initial Problem.  Given two natural (positive whole) numbers called $m, n$, can we find some other natural number that divides both of them?

This problem is a first step.  It’s nice to be able to write numbers as a multiple of some other number; for example, if we have 16 and 18, we may write them as $8\times 2$ and $9\times 2$, thus giving us some insight as to the relationship between these two numbers. In that case it may be easy to see, but perhaps if you’re given the numbers 46629 and 47100, you may not realize right away that these numbers are $99\times 471$ and $100\times 471$ respectively.  This kind of factorization will reveal "hidden" relationships between numbers.

So, given two numbers, how do we find if something divides both of them — in other words, how do we find the common divisors of two numbers?  If we think back to when we first began working with numbers (in elementary school, perhaps) the first thing to do would be to note that 1 divides every number.  But that doesn’t help us all that much, as it turns out, so we go to the next number: if both numbers are even, then they have 2 as a common factor.  Then we "factor" both numbers by writing them as $2\times\mbox{ something}$ and then attempt to keep dividing things out of the something.  We then move onto 3, skip 4 (since this would just be divisible by 2 twice), go onto 5, then 7, then…and continue for the primes.  This gives a prime factorization, but we have to note that if, say, 2 and 5 divide some number, then so does 10.  These latter divisors are the composite factors.

This seems excessive, but it is sometimes the only way one can do it.

Anecdote!: On my algebra qualifying exam, there was a question regarding a group of order 289 which required us to see if 289 was prime or not; if not, we were to factor it.  We were not allowed calculators, so what could we do?  Try everything.  Note that we only need to try up to the square root of the number (which we could estimate in other ways), but it’s still a number of cases.  If you check, none of the following numbers divide into 289: 2, 3, 5, 7, 11, 13.  At this point, I was about to give up and call it a prime, but, for whatever reason, I decided to try 17.  Of course, as the clever reader will have pointed out, $289 = 17\times 17$.  It is not prime.  There was, luckily, only one student who thought it was prime, but it points out how the algorithm above is not entirely trivial if one does not have access to a computer or calculator.

Once we have a common divisor, or a set of common divisors, a natural thing to want to do is to find the biggest (we already have the smallest, 1) since in this way we can write our numbers with the largest common factor multiplied by some other number.  It will, in effect, make things prettier.

Real Problem.  Find the greatest divisor which is common to two natural numbers, $m, n$.

If you were just learning about this kind of thing, you may spout out the following solution: find all of the common divisors, then pick the greatest.  While this is not especially efficient, it is a solution.  Unfortunately, even for small numbers, this gets out of hand quickly.  For example, 60 and  420 have the following common divisors: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60.  This takes a while to compute by hand.

Even if we were to find prime factors, this would be $60 = 2^2 \times 3\times 5$ and $420 = 2^2 \times 3 \times 5\times 7$, which gives us that they share a number of prime factors.  A bit of thinking gives us that we take all of the prime factors they "share" and multiply them together to get the greatest common divisor.  This is another potential solution which is much faster than simply listing out all of the common divisors.  Unfortunately, this falls prey to the same kind of trap that other prime-related problems do: it is, at times, especially difficult to factor large composite numbers.  For example, the "reasonably small" number 49740376105597 has a prime factorization of $2741 \times 37813 \times 479909$; this is not at all efficient to factor if one does not have a computer or a specialized calculator with a factoring algorithm on it.  As a mean joke, you may ask your friend to factor something like 1689259081189, which is actually the product of the 100,000th and 100,001st prime — that is, they would need to test 99,999 primes before getting to the one which divides the number.  If they divided by one prime per second (which is quite fast!) this would take them 1 day, 3 hours, and 46 minutes.  Not especially effective, but it will eventually get the job done.

Real Problem, With Efficiency: Find the greatest divisor which is common to two natural numbers, $m,n$, but do so in an efficient manner (we’ve all got deadlines!).

We need to sit down and think about this now.  We need an entirely new idea.  We note, at least, that for the two numbers $m,n$ that one of them must be larger than the other (or else the problem is trivial).  One thing to try would be to see if the smaller one goes into the larger one (for example, above we had 60 going into 420, which gave us the easy solution that 60 must be the greatest common divisor).  If not, maybe we can see how much is left over.  That is, if $m$ is the larger number,

$m = a_{1}n + r_{1}$

where here $a_{1}$ is the number of times $n$ goes into $m$ without exceeding it, and $r_{1}$ is the "remainder"; if it’s equal to 0, then $n$ evenly divides into $m$, and otherwise it is less than $n$ (or else we could divide an additional $n$ into $m$).

Using this, if $r_{1}\neq 0$, we may write $m - a_{1}n = r_{1}$; this means that, in particular, $r_{1}$ divides $m$ and $a_{1}n$, so it is a factor of $m$ and of $a_{1}n$.  But it may not actually be a factor of $n$; so let’s see how many times it goes into $n$.  Using the same process…

$n = a_{2}r_{1} + r_{2}$

and by rearranging, we have that $n - a_{2}r_{1}$ is divisible by $r_{2}$.  So, $n$ is divisible by $r_{2}$, but we aren’t sure if $r_{1}$ is divisible by $r_{2}$…if it were, we would be able to say that $r_{2}$ was a common divisor of $m$ and $n$ (why?).  That’s something at least.

The cool thing about our algorithm here is that, because $a_{1}n + r_{1} = m$ we have that either $r_{1} = 0$ and we’re done with the algorithm, or $r_{1} > 0$ and we may form a new equation $n = a_{2}r_{1} + r_{2}$; this equation has, on the left-hand side, the number $n$ which is less than the previous equation’s left-hand side, which was $m$.  Continuing this process, we will have $r_{1}, r_{2}, \dots$ on the left-hand side, each of which is less than the one which came before it.  Because $r_{i} \geq 0$ for any of the remainders, eventually it will become 0 (why?) and this algorithm will terminate.  That is, we will have found some $r_{i}$ which is a common divisor for both $n, m$; specifically, it will be the $r_{i}\neq 0$ such that $r_{i+1} = 0$ (or, it may simply be $n$ if $n$ divides $m$).

This algorithm, called the Euclidean Algorithm, actually does more "automatically": it not only finds a common divisor, but actually finds the greatest common divisor of $m,n$, which, from now on, we will denote $\gcd(m,n)$.  The "proof" of this is simply noting that $\gcd(m,n) = \gcd(n,r_{1}) = \gcd(r_{1},r_{2}) = \cdots = \gcd(r_{i-1},r_{i}) = r_{i}$ (we noted this above without making reference to the gcd, but the reader should attempt to go through all the same steps using the idea of the gcd).

So.  If you have two natural numbers, $n,m$, you divide them, find the remainder, write the equation, then continue as above until you get a 0 remainder.  Then you pick the remainder directly before you got 0 as your gcd (or, you pick the smaller number if one number divides the other).  Pretty simple algorithm, but is it efficient?

Without going into formal "efficiency" definitions, "yes", it is quite efficient.  To prove it, let’s take an "average" example using the "large" numbers 1337944608 and 4216212.  We note that (by pen and paper, or by using a standard calculator) that

1337944608 = 317(4216212) + 1405404.

Next, we note that

4216212 = 3(1405404) + 0

which instantly gives us the solution $\gcd(4216212, 1337944608) = 1405404$.  That’s pretty awesome.  Note that this was an especially quick trial, but even the "worst" ones are relatively quick.

Unexpected Corollary!:  For $n,m$ natural numbers, if $\gcd(n,m) = k$ then there exists integers $a,b$ such that $an + bm = k$.

This is more useful than you might think at first glance, and we’ll get into why in a later post, but what’s nice about this corollary is that it comes "for free" from the Euclidean algorithm.  Note that, since $k$ divides $n, m$, it suffices to prove this corollary for $an + bm = 1$ where $n, m$ have $\gcd(n,m) = 1$.  The proof uses induction on the number of steps of the Euclidean algorithm for those numbers, but for those of you who are more experienced and know modular arithmetic, you may enjoy the following simple proof:

"Clever" Proof of the Corollary: Let $m > n$ (for equality, the proof is easy).  We will only care about remainders in this proof, so we will look at some numbers modulo $m$.  Consider

$r_{1} = n\mod m$

$r_{2} = 2n\mod m$

$\vdots$

$r_{m-1} = (m-1)n\mod m$

Note there are exactly $m-1$ remainders here and that the remainder $0$ never occurs (since $m,n$ are relatively prime).  Suppose that $r_{i} \neq 1$ for each of the $i$; that is, the remainder 1 does not ever show up in this list.  By the pigeon-hole principle (as there are $m - 1$ remainders but only $m -2$ possible values for the remainders) we must have that $r_{i} = r_{j}$ for some $i\neq j$.  That is, we have

$in \mod m = jn \mod m$

which implies

$(i-j)n\mod m = 0$

but this is impossible, since it implies that either $m = 0$ or $n$ is some integer multiple of $m$, but $m > 0$ and we have assumes $m,n$ are relatively prime.  Hence, the remainder $1$ must occur.  That is, $r_{c} = 1$ for some $c$ and

$cn \mod m = 1.$

But what does this mean?  It means that there is some integer $a$ such that $am - cn = 1$.  To make this prettier, let $b = -c$ and we find that there exists $a,b$ integers such that $am + bn = 1$, as required.  $\Box$

Pretty slick, no?

Summing 1 + 11 + 111 + … and My Problem Solving Technique.

September 17, 2011

This post was inspired by a question on the comment second of my last post about the prime-ness of 111…111.  The question is: what’s the sum of 1 + 11 + 111 + … + 111…111?  This seemed kind of silly to me (especially if the sum has less than 10 terms) but I quickly realized that I couldn’t figure out a "closed form" without appealing to weird "carry" tricks.  So I tried to figure something else out.

Because my final solution to this question was somewhat unsatisfying, I’ve made this a special kind of post!  This post will have two main purposes: to try to answer this question and to show what kinds of things I do when I don’t know the answer to a problem.  So let’s begin.

First, I scribbled out lots of examples to see if there were patterns in the numbers.  Indeed, there are, but there was no nice way to describe them in general without creating a whole lot of variables and expanding the number of terms out into a base-ten sum.  This was frustrating.  Especially because I knew there might be an easy answer looming out there that I wasn’t clever enough to see.

Second, I noted that 11 and 111 and 1111 are kind of weird numbers; written in base 10 they look pretty, but they don’t have much else in common.  As we saw in the last post, a few are prime but many are not, and many have very strange prime factorizations — these factorizations do group together, but that seemed to be too far away from this problem to use.  So, maybe another base would make them better formed?  I plugged away in wolfram alpha.  The first two bases I tried were base 2 and base 11.  Neither one worked nicely.  When I tried base 5, I found that the numbers followed an interesting pattern:

$1, 11, 111, 1111, 11111, 111111, \dots$

were mapped to

$1, 21, 421, 13421, 323421, 12023421, \dots$

Note that the last few digital always stay the same here.  Because the decimal form of these numbers is 1 + 10 + 100 + 10000 + … this is not all that surprising.  We’re essentially adding the base-5 versions of these together.  Note that $400_{5}$ means the number 400 in base 5; in decimal this is the number 100.  So $400_{5} = 100_{10}$.  We drop the $_{10}$ in our base 10 numbers and note the following:

$1 = 1_{5}$

$10 = 20_{5}$

$100 = 400_{5}$

$1000 = 13000_{5}$

$10000 = 310000_{5}$

$100000 = 11200000_{5}$

and while this seems to have a bit of a pattern, it grows too fast to be of use for adding.  On the other hand, I found that base 5 can be fairly neat when you input numbers that have "nice forms" in base 10.  Try it out!

Third, I was a bit upset, so I went back to thinking that I could write the number of terms as $n = a_{0} + a_{1}10 + a_{2}10^{2} + \dots + a_{k}10^{k}$ and some some mods to figure out the digits.  The first digit will be easy: it’s just $a_{0}$.  But then what’s the carry?  After a bit, I worked out that it will just be $\frac{n - a_{0}}{10}$.  This did not seem to be going anywhere, since this number might be somewhat large too; we would need to add this number $n - 1$ times, and then there’s another carry that will look significantly more complex than the one I just wrote.  After trying this for five carries, I started to lose track of what I was doing; the formula was getting much more difficult than just doing "normal" addition.  This clearly wasn’t going to go anywhere.  At this point, a flash of insight hit me.  Of course.  This is just like adding 1 + 10 + 100 + 1000 + …, but only a little bit off.  But how much off?

Fourth, I thought that, okay, 1 + 11 + 111 + 1111 +… is the same sum as 1 + 10 + 100 + 1000 + … with a difference of exactly 1 + 11 + 111 + … with one less term.  If there are $n$ terms in the original, then it is equal to $1 + 10 + 100 + 1000 + \dots$ with $n$ terms plus $1 + 11 + 111 + \dots$ with $n -1$ terms.  Note, then, that if we define the term $ONE_{k}$ to be the sum of $k$ terms that look like $1 + 11 + 111 + 1111\dots$, then we have $ONE_{k} = 111\dots 111 + ONE_{k-1}$.  At this point, I began kicking myself, because this tells me nothing new about the problem; in fact, it is essentially a restatement of the problem!  But because of this, I thought about what happens when we do addition in 10’s.  I realized that it is exactly the same sort of thing we are doing when we add 11’s, but each successive digit will raise by 1.  So for example, while

1 + 10 + 100 + 1000 + 10000 = 11111

we have

1 + 11 + 111 + 1111 + 11111 = 12345

Each digit, starting at the left, is one plus the one before it.  Of course, this suggests a pattern.  But then what happens when you get far enough along?

$1 + 11 + 111 + 11111 + \dots + 111111111111 = 123456790122$

which does not look as pretty.  But look; if we add in the following way, this becomes easy!  (I’ve attempted to use a chart to display place values.)

 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 +
 1 2 3 4 5 6 7 9 0 1 1 2

Which is exactly what we got above!  Note here that I’ve made a "10" that sits inside the tenth decimal place (and so is implicitly a carry of 1 in the ninth place) and a "11" that sits in the tenth place (and so is a carry of 1 in the tenth place and 1 in the eleventh place) and so on.  I’ve found that this method of computing is slightly faster than computing the original sum by hand and much less space consuming.  Unfortunately, the clever (and even not-so-clever) reader will notice that this is still the sum of $n - 8$ terms.  Though I find it faster because you are only adding at most three things in each column (carries included).  I tried to speed-test myself by adding together 20 terms this way and by doing 1 + 11 + 111 + … etc. straight out.  My times are as follows:

Original Way (Adding 1 + 11 + 111…): 1 minute.

New Way (Described above): 40 seconds.

I also was much less confident doing this the original way (try it; you’ll have to keep track of the carry and the number of ones you need to add up and that gets confusing).  The most time consuming part about the "new way" was writing out the problem; I did not count this in the "original way" because it’s just as easy to visualize the problem as it is to write it out — it would take significantly longer.  If I were to only time the "calculation" part, the new way took me about 15 seconds.  Pretty good for a human.

But, this solution was the best I could do.  I do not have a closed form.  If anyone has a different or more interesting solution, let me know.  I didn’t want to resort to asking google, but maybe there’s a cute trick that makes this into a nice closed form.  I’m not sure.

Edit: Of course, there is an easier solution which was provided to me by Josh "The Widowmaker" Silverman over at his blog.  The key was to represent this as a geometric series (something that I seem to have completely missed out on).  It turns out that the closed form expression is

$\frac{1}{81}(10^{n+1} - 10 - 9n)$

for the sum of the first $n$ numbers of this form.  To see the derivation, go to his blog and read it over.

Divisibility Rules.

January 31, 2011

Sometimes when I’m at a restaurant with friends and the check comes, we need to evenly split the bill.  If you’re a math major, then you’re already assumed to be able to calculate this in your head; nonetheless, no one wants to hear that they owe  $3.53333333333… because very few people have fractions of pennies lying around. It suffices, sometimes, to round up or down a penny or two to make things come out nice. But this means you should have a good understanding of when numbers divide into other numbers. Here’s an example (which motivated me to post this): every month, the bill for the internet is around$65.  I have two other roommates (and a freeloading daschund) so we split it up into three even parts.  Now, I know that 3 does not divide into $65, so I just "round up" to$66 and then use the excess as credit, since that’s easy to divide by 3.  But what happens if you lived with 10 other people and you needed to divide up a $2033 bill. Does this work? What about$2035?  Did you have to use a calculator?