In this thesis we briefly look at the rules related to the greatest common divisor and the lowest common multiple of two integers and we describe the Euclidean algorithm. We study connections between Euclidean algorithm and continued fractions, Wirsing's method for determining the distribution function and how Knuth calculated the distribution of partial quotients in Euclidean algorithm using this method. Next Lehmer's algorithm is described and how it improves Euclidean algorithm, greatest common divisor and the multiplicative inverse mod n for a natural number n. We implement both Euclidean algorithm and Lehmer's algorithm in order to compare their speed. We also confirm the calculated distributions of partial quotients in Euclidean algorithm through an experiment.
|
