Euclidean Algorithm

Introduction

Although we have functions that can compute our gcd\gcdeasily 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.

Euclidean Algorithm

Important Remark

If a=bq+ra = b \cdot q + rand d=gcd(a,b)d = \gcd(a, b) then drd | r. Therefore gcd(a,b)=gcd(b,r)\gcd(a, b) = \gcd(b, r)

Algorithm

We write the following:

a=q0b+r0b=q1r0+r1r0=q2r1+r2rn2=rn1qn1+rnrn=0 a = q_0 \cdot b + r_0 \\ b = q_1 \cdot r_0 + r_1 \\ r_0 = q_2 \cdot r_1 + r_2 \\ \vdots \\ r_{n-2} = r_ {n-1} \cdot q_{n - 1} + r_n \\ r_n = 0

Or iteratively rk2=qkrk1+rkr_{k-2} = q_k \cdot r_{k-1} + r_k until we find a 00. Then we stop

Now here's the trick:

gcd(a,b)=gcd(b,r0)=gcd(r0,r1)==gcd(rn2,rn1)=rn1=d\gcd(a, b) = gcd(b, r_0) = gcd(r_0, r_1) = \dots = \gcd(r_{n-2}, r_{n-1}) = r_{n-1} = d

If d=gcd(a,b)d = \gcd(a, b) then dd divides r0,r1,...rn1r_0, r_1, ... r_{n-1}

Pause and ponder. Make you you understand why that works.

Example:

Calculate gcd(24,15)\gcd(24, 15)

24=115+915=19+69=16+36=23+03=gcd(24,15)24 = 1 \cdot 15 + 9 \\ 15 = 1 \cdot 9 + 6 \\ 9 = 1 \cdot 6 + 3 \\ 6 = 2 \cdot 3 + 0 \Rightarrow 3 = \gcd(24, 15)

Code

def my_gcd(a, b):
# If a < b swap them
if a < b:
a, b = b, a
# If we encounter 0 return a
if b == 0:
return a
else:
r = a % b
return my_gcd(b, r)
print(my_gcd(24, 15))
# 3

Exercises:

  1. Pick 2 numbers and calculate their gcd\gcdby hand.

  2. Implement the algorithm in Python / Sage and play with it. Do not copy paste the code

Extended Euclidean Algorithm

This section needs to be expanded a bit.

Bezout's identity

Let d=gcd(a,b)d = \gcd(a, b). Then there exists u,vu, v such that au+bv=dau + bv = d

The extended euclidean algorithm aims to find d=gcd(a,b), and u,vd = \gcd(a, b), \text{ and }u, vgiven a,ba, b

# In sage we have the `xgcd` function
a = 24
b = 15
g, u, v = xgcd(a, b)
print(g, u, v)
# 3 2 -3
print(u * a + v * b)
# 3 -> because 24 * 2 - 15 * 3 = 48 - 45 = 3