The Euclidean Algorithm, also known as Euclid’s Algorithm, is
used in discrete mathematics to find the greatest common divisor of two natural
numbers, namely \(a\) and \(b\). The greatest common divisor is typically denoted as \(gcd\left(a,b\right).\) In general, the Euclidean Algorithm is used
within numerous applications like solving Diophantine equations, constructing
continued fractions, and is even used when dividing in modular arithmetic.
There are some properties that go along with finding the \(gcd\left(a,b\right)\) in the Euclidean Algorithm: