The Euclidean algorithm is an efficient method for computing the greatest common divisor of two integers. It was first described by the ancient Greek mathematician Euclid and is one of the oldest algorithms in common use. It can be used to reduce fractions, solve Diophantine equations, and prove theorems in number theory. It has been generalized to other types of numbers such as Gaussian integers and polynomials.
University of Washington
Autumn 2021
CSE 311 introduces theoretical computer science, the theory background necessary for other CSE courses, and how to construct rigorous, formal arguments. Topics include logic, set theory, modular arithmetic, induction, regular expression, and relations.
No concepts data
+ 33 more concepts