## Music and Euclid's algorithm

Submitted by plusadmin on September 1, 2006Gottfried von Leibniz (1646-1716)

A little while ago I was reading some letters written by the 17th century German mathematician Gottfried Leibniz to an obscure contemporary of his, Conrad Henfling. The letters were about music theory and the details of how to tune musical instruments. I was surprised to find that at one point Henfling started to use Euclid's algorithm to justify his musical reasoning.

How useful could a mathematical technique from the third century BC be to a 17th-century musician? Very useful indeed, it turns out. Euclid's algorithm provides a way of dealing with equations of musical pitch, potentially helping musicians and instrument makers to tune musical instruments.

### Why Euclid's algorithm works

Consider two numbers *a* and *b* where *a > b*. Then

*a = n×b + c*

for some whole number

*n*, where

*b > c*.

If *c* is zero, then *b* is the highest common factor of *a* and *b*, and we can write *hcf(a,b) = b*.

If *c* is not zero, then any common divisor of *a* and *b*, must also divide *c* (as *a - n×b = c*), so the highest common factor of *a* and *b* must also divide *c*.

So *hcf(a,b)* divides *b* and *c*, therefore

*hcf(b,c) ≥ hcf(a,b).*

Equally, the *hcf(b,c)* must also divide *a* (as any common divisor of *b* and *c* divides *n×b + c = a*). So

*hcf(a,b) ≥ hcf(b,c)*

Therefore *hcf(a,b) = hcf(b,c)*.

We can repeat this process of finding remainders until we finally get a remainder of zero, in which case the highest common factor of the original pair of numbers *a* and *b* (in fact the highest common factor for every pair of numbers in the process), is the last non-zero remainder in the process.

### Euclid's algorithm

Euclid's algorithm is a way of finding the highest common factor of two numbers *a* and *b* (where *a > b*). First divide *a* by *b* and take the remainder, calling it *c*. Then divide *b* by *c*, and take the remainder, calling it *d*. Keep repeating this process and eventually you'll get a remainder of zero. The last non-zero remainder will be
the highest common factor of the original two numbers. (*Plus*'s sister site NRICH has several articles on Euclid's algorithm: Euclid's algorithm I and Euclid's algorithm II, and an interactivity where you can see it in action).

The algorithm works for lengths of lines as well: given any two lines, we can find a *common measure* for them — a line which goes exactly into each of them (if one exists) — by applying the same algorithm. This is quite useful, because all of the operations involved in the algorithm correspond to geometrical constructions that you can do with a ruler and compass. (You can read more about
common measures in TheMathPage course The evolution of the real numbers, including lines for which no common measures exist (such as the diagonal of a square and its side), and how
these led to the development of irrational numbers.)

The algorithm is called Euclidean because it appears in Euclid's Elements as proposition 1 of book 7. It can be useful in all sorts of situations. But what has it got to do with music?

### Intervals — musical and mathematical

Euclid (c.325-c.265BC) - an artist's impression

Right from the time of Euclid (325-265 BC), and even before, there has been a mathematical way of talking about music. Musicians talk about pitch, that is how high or low a note is. You can visualise this as how high or low it appears on a stave, or how far to the right or left it would be on a piano. Today scientists use a sound's frequency to describe its pitch in mathematical terms: for example the middle A on a piano usually has a frequency of 440 cycles per second. This simply tells us how many individual sound waves there are each second in that sound. Because there are so many of them, they are difficult to observe or to count, and for a long time it wasn't possible to find the frequency of a given note.

Before the concept of frequency was discovered mathematicians talked instead about the length of a string that would produce a particular note. Obviously the note a string produces depends not just on its length but also on its tension and its density. (You can see this with a guitar, where the strings are all the same length: the pegs adjust the tension, but you can also see that the lower notes are generally produced by thicker, heavier strings). But if you keep the tension and density constant, changing the length changes the pitch in a predictable way.

C to C is an octave, and C to G is a fifth. Don't be put off by the name "fifth", which makes it look as if it's something to do with 1/5; it isn't. But if you play up the C major scale C is the first note and G is the fifth. The next C is the eighth or "octave", from the Latin "octo" for eight.

If I halve the length of the string, the pitch always rises by what musicians call an *octave*. That's the distance from one C to the next C above it, or from one A to the next A above it, and so on. It doesn't matter what pitch you start with: if you halve the length of the string you will always get a pitch an octave higher.

If you take two thirds of the original string you get what is called a *fifth* higher. That is the distance from C to the G above it, or from D to the A above it, and so on. Once again, it doesn't matter what pitch you start at; if you shorten the string to two thirds of its original length you always get the pitch a fifth higher.

You can see what is going on here. Musicians talk about musical intervals: an interval is a relationship between two notes. It doesn't matter how high or low both of the notes are, just what relationship there is between them. Wherever you are on the keyboard, the interval between one note and the next with the same letter name is always an octave. In the same way, the interval between C and the G above it, or D and the A above it, or anything similar (seven steps on the keyboard, including both black and white notes), is always a fifth.

And each of these intervals — the octave, the fifth, and others — corresponds to a particular ratio of string lengths. The octave corresponds to 2:1 — halving the length of the string. The fifth corresponds to 3:2 — taking two thirds of the length of the string.

Without going into the details, it is possible to work out a few more of these relationships: taking three quarters of the original string gives the musical interval called the fourth (for example, C to the F above it); taking nine-eighths of the original string gives the interval called the tone (for example, C to the D above it).

These correspondences were known to musicians in ancient Greece. They had made the fundamental observation that pairs of strings whose lengths make exact simple ratios — like 2:1, 3:2 and 4:3 — sound good together. Other pairs of strings which do not have such a relationship generally sound discordant. (You can read more about why some notes sound good together in the *Plus* article
The magical mathematics of music.) From then until about the seventeenth century it was common — at least among people interested in the mathematics of music — to use these ratios as the definitions of the simplest musical intervals.

Over the years there were further developments in music, and by the middle of the sixteenth century it was normal to add a few extra ratios to those listed above. The ratio 5:4 was called the major third (for example, from C up to E); 6:5 was the minor third (E to G).

### Musical arithmetic

There was a correspondence between ratios and intervals; there was also a correspondence between the mathematical relationships of different ratios and the musical relationships of different intervals. For example, combining two musical intervals together, gives you another — a fourth plus a fifth is an octave; a major third plus a minor third is a fifth. More complicated musical intervals like semitones were usually defined by looking at the difference between some pair of more simple intervals, just as the tone was defined as the difference between a fifth and a fourth.

But what exactly do I mean by an octave being a fifth plus a fourth? And how does combining these intervals correspond with mathematically manipulating the ratios?

Remember how we originally found these ratios: if I have a given string, and then take two thirds of it, I've gone up a musical fifth (say from C up to G). If I take three quarters of the new string, I've gone up a musical fourth more (say from G up to the next C). Three quarters of two thirds is one half, so that I have one half of the original string, and the total musical interval I have gone through is an octave (from C to the C above it). That is, a fifth plus a fourth equals an octave, and the corresponding equation in ratios is 3:2 × 4:3 = 2:1.

So you can see that when we add two musical intervals together we must multiply the corresponding ratios. Similarly, when we subtract one interval from another we must divide one ratio by the other: a fifth minus a fourth is a tone; 3:2 / 4:3 = 9:8.

Here's where the problems start. Musicians like to talk about the relative sizes of intervals, and about how many times one interval will go into another. (This kind of thing is useful for building and tuning instruments, and for composing music in several parts.) How many times, for instance, does a fifth go into an octave? That is, how many times does 3:2 go into 2:1? Remember, we are asking not how many times do you add 3:2 to itself to get 2:1, but how many times do you multiply 3:2 by itself to get 2:1?

In terms of our piece of string, asking how many times a fifth goes into an octave corresponds to asking: "how many times can I keep taking two thirds of a string before I have halved the length of the string?" Clearly, the answer lies between 1 and 2: 2/3 of a string is longer than half of the string, but 4/9 of the string (the result of taking 2/3, and then 2/3 again) is shorter than half of
the string. In terms of ratios this translates to 3:2 is less than 2:1, but (3:2)^{2} = 9:4 is greater than 2:1. So, somewhere in between there must be a power of 3:2 which is exactly equal to 2:1.

### Euclid to the rescue

If you know how logarithms work, you may be able to see how to get an exact value for *x* from the equation (3:2)^{x} = (2:1). (But don't worry if you can't — by the end of the seventeenth century, nearly a hundred years after the invention of logarithms, only Descartes, Newton, and perhaps half a dozen others had managed it.) Before the invention of logarithms in 1614 there was
no way to get an exact answer, so people tried various approximations. One is to use Euclid's algorithm to try to find a highest common factor for the fifth and the octave. You might like to try it out for yourself and see what happens before reading on: always remember that when we add and subtract musical intervals we multiply and divide the corresponding ratios.

Here are the results of applying Euclid's algorithm to an octave and a fifth. As well as the ratios, I've given the musical names for the intervals that appear.

Interval | Ratio | |
---|---|---|

a - n × b = c, where b > c |
Corresponding equation for ratios | |

octave - fifth = fourth | 2:1 / 3:2 = 4:3 | (1) |

fifth - fourth = tone | 3:2 / 4:3 = 9:8 | (2) |

fourth - 2 tones = semitone (e.g. E to F) |
4:3 / (9:8)^{2} = 256:243 |
(3) |

tone - 2 semitones = comma | 9:8 / (256:243)^{2} = 531441:524288 |
(4) |

There weren't any standard names for the musical intervals smaller than a comma; but we can continue the mathematics still further. (I've given the factorisations of the numbers rather than writing them out in full).

Interval | Ratio |
---|---|

semitone - 3 commas = 'X' | 256:243 / (531441:524288)^{3}= (2 ^{8}:3^{5}) / (3^{12} : 2^{19} )^{3}= 2 ^{65} : 3^{41} |

comma - 'X' = 'Y' | (3^{12} : 2^{19}) / (2^{65} : 3^{41})= 3 ^{53} : 2^{84} |

'X' - 5'Y' = 'Z' | (2^{65} : 3^{41}) / (3^{53} : 2^{84})^{5}= 2 ^{485} : 3^{306} |

You could continue this indefinitely. However, if we want to get some approximate result that will be actually useful, we could cut off the algorithm at some point and pretend that one interval went exactly into another, with no remainder. If the real remainder is small enough, that will give us a useful approximation.

For example, suppose I pretend that the semitone goes exactly into the tone. That is:

tone - 2 semitones = 0 | ||

Then | ||

tone = 2 semitones | (5) | |

so | ||

fourth = 2 tones + semitone (by 3) = 5 semitones (by 5) |
(6) | |

fifth= fourth + tone (by 2) = 7 semitones (by 5 and 6) |
(7) | |

octave = fifth + fourth (by 1) = 12 semitones (by 5 and 7) |
(8) |

So Euclid's algorithm tells us is that a reasonable approximation to the number of fifths in an octave is 7/12, because a fifth is roughly 7 semitones and an octave is roughly 12 of them.

How many steps (counting both black and white notes) in an octave, and how many in a fifth?

Take a look at the piano keyboard, in the image on the left, and count the number of steps (including both black and white notes) in an octave, and the number in a fifth. The piano keyboard embodies the approximation that we have just worked out (taking a tone = 2 semitones). But it is only an approximation, and it involves changing every fifth from a ratio of 3:2 to something slightly different.

What if that approximation didn't seem good enough? What if we were to take the Euclidean algorithm one stage further, and then stop it? You might want to try this out. What about two or three stages further?

I won't show all of the working here, but the results are the approximations that a fifth is 24/41 of an octave, or 31/53, or 179/306 (if you take the algorithm one, two or three stages further). You might think that dividing the octave into 41 or 53 or 306 has nothing to do with real music. But in the sixteenth and seventeenth centuries several people designed instruments with strange numbers of notes in each octave. The division of the octave into 53 was the official musical tuning in China in the eighteenth century. But I don't think anyone has ever tried to make a real instrument with 306 notes in the octave.

So Leibniz's correspondent, Henfling, had a good point to make. You can use Euclid's algorithm to compare the relative sizes of different musical intervals, and you can use it to find approximations for the number of fifths there are in an octave. You might like to experiment with applying the Euclidean algorithm to other musical questions like the number of tones in an octave or the number of major thirds in a fifth or in an octave (the ratio definitions of these intervals were given above).

After the invention of logarithms this method eventually became irrelevant, and after scientists learned more about the workings of the ear it seemed less important to have exact ratios or approximations to them at all. But some interesting mathematics comes out of this, and an unusual way of comparing the sizes of different ratios — one that was used by Henfling, and his fellow mathematical musicians, until the end of the seventeenth century.

### Further reading

- On the NRICH website you can find three problems that are based on this article: Tuning and ratio, Euclid's Algorithm and musical intervals and Rarity. NRICH also has an interesting article on the maths of church bells.
- You might find my article about some early attempts to do experiments on musical sound interesting.
- I follow up some of the ideas about logarithms in a forthcoming article in Infinity magazine, published by Tarquin.
- For more information about maths and music in general I'd recommend the excellent book Music and Mathematics: from Pythagoras to Fractals by Fauvel, Flood, and Wilson published by OUP.
- Read past
*Plus*articles on Maths and Music

### About the author

Benjamin Wardhaugh studied in Cambridge and London, receiving a BA in mathematics and an MMus in composition. He currently lives in Oxford, where he hopes soon to receive a doctorate in history. His research focuses on mathematical approaches to music in seventeenth-century England, and more generally on the emergence of the idea of applied mathematics. He is also a keen amateur musician,
playing the bassoon in various ensembles. And he was once a member of the NRICH team (*Plus*'s sister site), back in 2000-2002.