Euclidean Algorithm

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:

The first two properties are very similar:
If \(a=0\), then the \(gcd\left(a,b\right)=b\)
If \(b=0\), then the \(gcd\left(a,b\right)=a\)
The third property is if \(a=bq+r\) where \(b\ne0,\) then the \(gcd\left(a,b\right)=gcd\left(b,r\right)\), where \(q\) is an integer and \(r\) is an integer between \(0\) and \(b-1\)
Notice that this property is important because it will let us take a more complex problem and break it down into a smaller problem which is not as difficult to solve.