The Euclidean Algorithm
An algorithm must be seen to be believed.
Donald Knuth, The Art of Computer Programming, Vol. 1, 1999
The Euclidean Algorithm1 is a very powerful device. We will apply it to three problems:
We will show how the proofs are created and how they are polished for the final version. ...