This algorithm helps us get the greatest common divisor(gcd) of 2 integers. In other words, the result of our computation is the highest possible number `(lets say 1)`

that we can divide by two given numbers `(4 and 5)`

which will give a remainder `(or you could say left over after a division)`

of zero for both given numbers. Lets break this down a little bit :

our two numbers earlier were `4`

and `5`

, but these could be any random numbers which follow two rules :

1st >> one number must be larger than the other.

2nd >> both must not be even numbers.

The euclidian algorithm formula is `q = a * b + r`

where the letters are placeholders for numbers forexample

```
5 = 4 * 1 + 1 or
11 = 2 * 5 + 1
```

Lets get our hands a little dirty and see how we arrived to the answers of 5 and 11 above:

`now is the time to open your editor and create a python file so we can write some simple code. my file is called index.py`

When calculating we always have our 2 numbers, remember earlier we chose `(4 and 5)`

. These numbers replace `q`

and `a`

whereby `q`

takes the bigger number `(5)`

and `a`

the smaller `(4)`

so `5 = 4 * b + r`

therefore in `index.py`

```
# formula is q = a * b + r
q = 5
a = 4
```

our task is to find numbers to replace `b`

and `r`

to complete our equation. according to the Euclidian theorem, `b`

is the number of times `a`

goes into (divides) `q`

while `r`

is the remainder of that operation.

so `5`

goes into `4`

once with a remainder of `1`

so we will equate our remainder to `r`

and our initial answer to b. In python we could use an inbuilt function called `divmod( )`

to do this computation and it takes the two numbers as arguments and returns a quotient and remainder as the result in an array therefore in `index.py`

```
# formula is q = a * b + r
q = 5
a = 4
result = divmod(q,a)
b = result[0]
r = result[1]
```

However according to the Euclidian theorem, our remainder must be zero so if `r`

isn't `0`

we aren't done. It states that we have to place `a`

in the position of `q`

and `r`

in the position of `a`

or simply replace our initial values that were used in the calculation by new values following the above procedure therefore in `index.py`

```
# formula is q = a * b + r
q = 5
a = 4
result = divmod(q,a)
b = result[0]
r = result[1]
q = a
a = r
```

Take a scenario where you didn't use `(4 and 5)`

, probably (11 and 5). You will have to repeat the calculations until `r = 0`

. When `r = 0`

, we obtain the gcd from the value of r just exactly before you did the last calculation to obtain `r = 0`

for us to get the desired final result therefore in `index.py`

we can use a for loop to do our calculations over and over until `r = 0`

:

```
# formula is q = a * b + r
q = 5
a = 4
result = divmod(q,a)
b = result[0]
r = result[1]
q = a
a = r
finalResult = 0 #initialize a variable outside the for loop so
#that it is accessed globally
for i in range(q):
finalResult = r #store our gcd value as the loop is starting so
#that we can capture the previous value of r
#before the calculation which equates `r = 0`
result = divmod(q,a)
b = result[0]
r = result[1]
if r == 0:
break #constantly check the current value in r and make sure
#when it is 0 you can stop the loop
q = a
a = r
print(finalresult)
```

And that's it folks, Enjoy

Find me on twitter

## Top comments (0)