“The first algorithm”

Wikipedia:Torus knot as rendered by Wikipedia:... — Image via Wikipedia

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…

Euclid’s algorithm

Stating the algorithm: Take two numbers $M,N: N > M$ . To find the highest common factor of $M$ and $N$ which we call here $hcf(N,M)$ .

$L = N mod M$ if $L = 0$ then $hcf(N, M) = M$ otherwise $hcf(N, M) = hcf(M, L)$ .

Proof

$L = N mod M$ . If $L = 0$ then it is plain that $hcf(N, M) = M$ , otherwise $N = yM + L$ , if then $M mod L = 0$ , plainly $M = zL$ and so $N = yzL + L = (yz + 1)L$ .

To show this is the highest common factor, assume that there is a higher common factor, $R$ , then $N = aR$ and $M = bR$ and so $N = bR + cR$ . But we already know that $N = yzL + L = (yz + 1)L$ . So if $R > L$ , then $c < 1$ , which is a contradiction. Hence $R \equiv L$ .