ROUGH DRAFT authorea.com/103007
Main Data History
Export
Show Index Toggle 0 comments

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. 
Procedure of the Euclidean Algorithm:
We start with our \(a\) and \(b\) values and see how many times we can divide \(a\) by \(b\) then we multiply \(b\)  by \(q\) (quotient) and add the \(r\) (remainder). For the next line, we move our \(b\) value and our \(r\) value in a diagonal pattern and go through the process of dividing \(\frac{a}{b}\). This process can be continued until we get to a \(0\) remainder. The last non-zero remainder is our \(gcd.\)