Euclidean Algorithm

I have recently found the Euler’s algorithm in math (I think the “algorithm” part was something that made me connect to programming) while I was practicing solving diophantine equations, and Euler’s Algorithm was a major part of it. It’s really interesting to see how some math concepts are easy to implement but are hard to fully understand/prove, but this one is simple and nice! It can be used to find the greatest common denominator of two large numbers (the importance of this is self explanatory), cryptography, and data compression.

Using Euler’s Algorithm helps one find the greatest common factor since subtracting the lesser number from the larger number will not change the greatest common factor. The goal is to reach 0 for the GCF that’s left. For an algorithm (in python) for the iterative implementation:

def gcd(a, b);
while b!= 0:
a, b = b, a % b
return a
a = 70
b =80
ans = gcd(a, b)
print(ans)

Which is really short and will output 10. It’s pretty easy to understand, where when we subtract the two numbers from each other, the greatest common factor would still be a factor of the final value after the subtraction. Nice!

Essentially it works such that:

If we have two numbers a and b, then we can create the follow set of equations (note that the remainders r_i will have to be less than r_i-1, and q_i will be the quotients):

a = bq + r
b = rq₁ + r₁
r = r₁q₂ + r₂,

And so on. We will continue this sequence until we have that r_i-1 = r_iq_i+1, so the greatest common divisor of a and b will be r_i.

For example, we can have the numbers 130 and 80 , where we can make the following relationships and continue the sequence until we get a r_i of zero.

130 = 80(1) + 50
80 = 50(1) + 30
50 = 30(1) + 20
30 = 20(1) + 10
20 = 10(2).

From this, we can see that the greatest common divisor from the Euclidean Algorithm would be 10.

Overall, it’s one of those really smooth things in math that I have been using in my recent self-studying of abstract algebra. It’s fun to see how something I learned in middle school came back!