## 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 , 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 and , 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 and 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 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, . 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, .

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 and , 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 ; 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, , 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 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 is the larger number,

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

Using this, if , we may write ; this means that, in particular, divides and , so it is a factor of and of . But it may not actually be a factor of ; so let’s see how many times it goes into . Using the same process…

and by rearranging, we have that is divisible by . So, is divisible by , but we aren’t sure if is divisible by …if it were, we would be able to say that was a common divisor of and (why?). That’s *something* at least.

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

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 , which, from now on, we will denote . The "proof" of this is simply noting that (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, , 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 . That’s pretty awesome. Note that this was an especially quick trial, but even the "worst" ones are relatively quick.

**Unexpected Corollary!: **For natural numbers, if then there exists integers such that .

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 divides , it suffices to prove this corollary for where have . 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 (for equality, the proof is easy). We will only care about remainders in this proof, so we will look at some numbers modulo . Consider

Note there are exactly remainders here and that the remainder never occurs (since are relatively prime). Suppose that for each of the ; that is, the remainder 1 does not ever show up in this list. By the pigeon-hole principle (as there are remainders but only possible values for the remainders) we must have that for some . That is, we have

which implies

but this is impossible, since it implies that either or is some integer multiple of , but and we have assumes are relatively prime. Hence, the remainder must occur. That is, for some and

But what does this mean? It means that there is some integer such that . To make this prettier, let and we find that there exists integers such that , as required. .

Pretty slick, no?

## Algorithms: Plus One Game Ideas and the Graphed Plus One Game.

### November 13, 2010

Here is what I came up with for the last post on the Plus One game, and a new game on graphs.

## Algorithms: Plus One Game.

### November 12, 2010

I woke up today with a game stuck in my head.

**The Game: **Player A picks a number from 1 to 10. Player B guesses a number. If Player B’s guess matches Player A’s number, then Player B wins. If not, then Player A adds 1 to his number and the game continues.

This is not a difficult game to play. The interesting thing here is that even though there is a winning strategy (Player B simply guesses “10” every time; eventually he will win.) the game could theoretically go on forever — say Player A picked “2” but Player B always guesses “1.”

The question is, *how quick can we guarantee a win for Player B?*

The first solution I thought of was the following: have Player B guess “5” for five turns. If he doesn’t get it after five turns, then have him guess “15” for the next five turns. After a bit of thinking, though, this is not actually any better than Player B just guessing “10” every time.

**First Question: Is this the best we can do?**

** **

Now let’s make the game a bit more interesting, because (at this point) the game has a max value and a winning strategy for player B which is obvious.

**The (Harder) Game: **Player A guesses any natural number. Player B guesses a natural number, and if it matches Player A’s, then player B wins. If not, Player A adds 1 to his number and the game continues.

This game has a similar feel, but an infinite twist. There is no longer a maximum value, so our original winning strategy does not work. Nonetheless, is there a finite or countably infinite “optimal” strategy for player B?

If we were able to prove that the average number of turns for each finite game (the first game, and ones with a maximum value ) is , then it would be: just take a limit. I have a feeling that this first game can be proved to have such an optimal strategy using some kind of discrete math proof, but it’s been a while. Anyone want to take a swing at this?

(**Note: **Brooke came up with a winning strategy for player B for the infinite case, and the solution is posted on the next post. It turns out that even in the infinite case this is not a very interesting game and there is actually a *finite* winning strategy for player B. It’s probably exactly what you think it is: go up in multiples of 2’s starting at the beginning.)

## QR-Factorization.

### October 28, 2010

While I was studying for a linear algebra exam, I discovered a deep-seeded love for QR-Factorization. I’m not going to explain why this is important, or why we should care about such a factorization; in fact, I have no idea why this is important or why I should care about this. I was directed to this, so I’ll direct you there too.

Anyhow, here’s the game. Given some square matrix (this is not necessarily, but it makes it easier) , we want to decompose into an orthogonal matrix and an upper-triangular matrix .