Output details
11 - Computer Science and Informatics
Teesside University
On Euclid's algorithm and elementary number theory
<12> This paper shows how the lessons that have been learnt in algorithm design can significantly improve mathematical practice. The focus is on how to derive number-theoretical results from Euclid’s algorithm. New results include distributivity properties of the greatest common divisor and new algorithms for efficiently enumerating the rationals in two different ways. The algorithm provides the definitive link between two well-known trees of rationals. The concise, systematic nature of the methods shown may have impact on technology transfer from Computing Science to Mathematics. This paper appeared in an SCP special issue containing a selection of the best papers of MPC2008.