Sebastian Timosson: Euklides algoritm - i teori och praktik

Abstract.

Euclid’s algorithm, named after the ancient Greek mathematician Euclid, is a fundamental method in mathematics for computing the greatest com- mon divisor (GCD) of two integers. Despite its ancient origins, Euclid’s algorithm remains relevant and widely used today due to its efficiency and its numerous theoretical and practical applications. This paper explores the depth of Euclid’s algorithm, its complexity, and its performance in both worst-case and average-case scenarios. We also examine a modified version of Euclid’s algorithm and compare its performance with the orig- inal version. Furthermore, we delve into the algorithm’s role in number theory, including its connection to the fundamental theorem of arithmetic and prime factorization. The paper includes proofs of key theorems such as B´ezout’s identity and Euclid’s lemma, which are central to the under- standing of these topics. The exploration of these concepts provides a deeper understanding of the structure and properties of these mathematical structures and the central role of Euclid’s algorithm within them.