Euclid’s method of finding the highest common factor (or greatest common divisor) is often referred to as the first algorithm (though surely long division came earier? Maybe someone who knows can answer) and certainly it was the first thing I was taught in secondary school math classes (in Northern Ireland – where the school had a very traditional maths curriculum that no doubt my father and his father would have recognised – in England, later, I was taught a “new maths” curriculum that was heavy on matrix multiplication).
Recently it came up again in some computer literature I read and I was puzzled enough to spend five minutes with a piece of paper proving to myself it was correct (not something I would ever have done when I was 11). So I thought I’d share the proof with all of you…
Stating the algorithm: Take two numbers . To find the highest common factor of and which we call here .
if then otherwise .
. If then it is plain that , otherwise , if then , plainly and so .
To show this is the highest common factor, assume that there is a higher common factor, , then and and so . But we already know that . So if , then , which is a contradiction. Hence .
Update: small error in the proof, now fixed.
- New math equals trouble, education expert says (cbc.ca)
- Computer science in schools: they do a better job in Scotland (guardian.co.uk)
- Improving Math Education (thescamdog.wordpress.com)