Euclidean Algorithm meaning & python snippet

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