So we've computed the GCD, the greatest common divisor, of two whole
numbers by invoking the Euclidean algorithm.
But one of the themes of mathematics is generalization.
We can often take something
that originally was designed to work in a more specific context and then
generalize, apply it to that broader context.
And even when the results don't quite make
sense, there still might be some interesting consequences.
So let's apply this kind of thinking to the greatest common divisor situation.
Let's act as if we were going to compute
the GCD of the square root of two and the square root of three.
And let's just see what happens.
So I want to give some geometric
perspective on the Euclidean algorithm as well.
So we'll draw a rectangle of a width root three and height root two.
Now, if we're thinking about the Euclidean
algorithm geometrically, I would be asking us to think about how
many times root 2 fits inside root 3 and where we can fit one copy
of the square root of 2 inside the square root of 3.
So now let's write this down.
Algebraically we'd write down
the square root of three and we want to write down our division problem
the square root of three is equal to how many copies of the square root of two.
So can fit one copy of the square root of two into the square root of three.
But there's some remainder and that remainder is root three minus root two.
Now we're doing the Euclidean algorithm,
so we iterate and we ask ourselves how
many times does the previous stage's remainder divide the square root of two?
So we can represent that geometrically
by drawing squares of side length root three minus root two.
And we see that there are four of those
squares that would fit into that length of the square root of two.
And we've got a remainder left over.
The remainder is 5√2 − 4√3.
Now we're onto the next stage in the Euclidean algorithm.
We've got √3 − √2.
And I want to know how many times the previous stage's remainder fits into that.
We can think about that geometrically by drawing a couple squares.
Those squares have side length, 5√2 − 4√3.
And we can see that there's two of them.
So the quotient there is two,
but we've got that very narrow piece remaining and that very narrow piece
corresponds to the remainder of 9√3 − 11√2.
And because that piece was so narrow, that remainder is very small.
9√3 − 11√2 is so small that you might say it's
approximately zero and consequently 9√3 is approximately 11√2.
Now, doing just a little bit of algebra
reveals that the square root of three halves is approximately 11/9.
11/9 squares to 121/81
and three halves is exactly 120/80.
So what we found here is an exceptionally
good, rational approximation to the square root of three halves.
I'm not sure what I expected to have happen when we applied the Euclidean
algorithm to two real numbers like this, but this is a really neat consequence.
We were able to get this exceptionally
good rational approximation to the square root of one point five.
So I'm selling this as if this is some
sort of generalization of the Euclidean algorithm to arbitrary real numbers.
But that's kind of a lie!
I mean, we're really getting back to our "roots."
You know, what we're really doing here it is geometry.
And after all, why was someone like Euclid,
clearly a geometer, interested in something
like GCD, which maybe seems like the purview of number theory.
Well one key reason is a search for commensurability, a search
for a common unit that could measure two different lengths.
And it's exactly what we're seeing, uh uh, here when we draw these kind of geometric
pictures and we're trying to compute the GCD.
Well, in any case, let's try to do the same kind of game
but, instead of trying to compute, compute the GCD of root two and root three,
let's try to do the same kind of game
but for log 2 and log 3.
So I'll again start by drawing a rectangle this time of width log 3 and height
log 2.
Then the Euclidean logarithm asks us to think
about how many times log 2 fits inside log 3.
And we can fit log 2 inside log 3 once.
That's the big square there.
And there's some remainder.
The remainder is log 3 − log 2.
So the first step in the Euclidean algorithm summarized as follows: log 3
is one copy of log 2 plus this remainder of log 3 minus log 2.
Now, I want to know how many times
that remainder of log 3 − log 2 fits into log 2.
I can only fit the one square in there,
so log 2 is one copy of that previous remainder,
log 3 − log 2,
plus this new remainder of
2 log 2 − log 3.
Now, this next stage, I can only fit one square in there,
so I'll record this in the next step of the Euclidean algorithm.
Now in this next stage, the quotient is 2. Right
which I can visibly see because I can fit two squares in there,
and then I'll record that in the next step of the Euclidean algorithm.
So now I'll divide 2 log 3 − 3 log 2
by 8 log 2 − 5 log 3.
I'll get a quotient of 2
and I'll record that in this next stage of the Euclidean algorithm.
Now, if I'd been doing this with whole
numbers, I, I'd eventually get a remainder of zero.
I mean, log 3 and log 2 are not commensurable.
So this process will never actually end.
But this remainder that I've got at this
stage, 12 log 3 − 19 log 2, that remainder is quite small.
And consequently, 12 log 3 is approximately
19 log 2.
Now, that coincidence of logarithms tells us that 3¹² is very
close to 2¹⁹. Dividing both sides by
2¹² reveals that 3/2 raised to the twelfth
power is very close to 2⁷.
This approximate equality has a certain musical interpretation.
We say the two notes are separated by an "octave"
if one note is twice the frequency
of the other. And we say that two notes are separated by a "fifth"
if one note is 3/2 the frequency of the other.
So this is saying, musically, that 12 "fifths" is about seven "octaves."
And because this is a musical fact, it's something that we can try to hear.
So let's listen to seven octaves. [Eight notes]
So now I'll start at that same low note [Music] and I'll move up 12 "fifths." [13 notes]
Now it's an approximate equality,
so those two notes aren't exactly the same.
Let's listen to the result of going up twelfths again [High note] and going up seven octaves [High note]
Twelve fifths. [High note]
Seven octaves. [High notes]
And to be precise, twelve fifths is a bit more than seven octaves.
So that note, after moving up 12 fifths,
is a bit higher than what we got when we moved up seven octaves.
This is a neat example in part because it
shows just how connected mathematics is to everything else.
Some of you've already seen the "circle of fifths," maybe in a music theory
context, and it's cool how that's connected to things like log 2, log 3,
and also this sort of interesting take on the Euclidean algorithm.
And there's a historical footnote here as well.
So what we're calling the Euclidean algorithm,
Euclid's algorithm, it's probably not actually due to Euclid.
It actually has its roots in older mathematics
due to the Pythagoreans
and the Pythagoreans were interested in things like special ratios and music!
So maybe this musical connection that we're seeing is maybe not so surprising.