A senior thesis by Ethan Stieha, Fall 2016
Introduction: The Euclidean Algorithm was first published in 300 B.C. yet still remains widely useful in solving the greatest common divisor of two computationally large natural numbers. The algorithm provides a step by step process to reduce natural numbers into remainders derived from the division theorem with the same common divisors. While the algorithm itself is rather simple, it has several unique behaviors that make it fascinating to study. As years pass, mathematicians consistently rely on the Euclidean algorithm to be well-conditioned, and provide accurate computational results.
Summary: The thesis defines and illustrates the algorithm. It uses experimental methods to investigate the likelihood of each outcome of the algorithm. It then uses both experimental and rigorous methods to examine the case when the outcome is 1, that is, the two inputs are relatively prime.