authorea.com/103007

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:

## Share on Social Media