Although we have functions that can compute our easily it's important enough that we need to give and study an algorithm for it: the euclidean algorithm.
It's extended version will help us calculate modular inverses which we will define a bit later.
If and then . Therefore
We write the following:
Or iteratively until we find a . Then we stop
Now here's the trick:
If then divides
def my_gcd(a, b):# If a < b swap themif a < b:a, b = b, a# If we encounter 0 return aif b == 0:return aelse:r = a % breturn my_gcd(b, r)print(my_gcd(24, 15))# 3
Pick 2 numbers and calculate their by hand.
Implement the algorithm in Python / Sage and play with it. Do not copy paste the code
Let . Then there exists such that
The extended euclidean algorithm aims to find given
# In sage we have the `xgcd` functiona = 24b = 15g, u, v = xgcd(a, b)print(g, u, v)# 3 2 -3print(u * a + v * b)# 3 -> because 24 * 2 - 15 * 3 = 48 - 45 = 3