Euclidean Algorithm
The Euclidean algorithm is a method for finding the greatest common divisor (GCD) of two integers $a$ and $b$ $(a>b)$. It works by repeatedly dividing and taking the remainder $r$ of $a$ divided by $b$, using the division principle to find the GCD.
Algorithm
Input: Integers $a, b$ Output: GCD $d$
- Set $a_0 = a$, $a_1 = b$
- If $a_i = 0$, set $d = a_{i-1}$ and terminate.
- Compute $a_{i-1} = a_i q_i + a_{i+1}$ and return to step 2.
Program
def euclid(a,b):
a_list = []
if a < b:
a_list.append(b)
a_list.append(a)
if a >= b:
a_list.append(a)
a_list.append(b)
i = 0
while(a_list[-1]!=0):
a_list.append(a_list[i]%a_list[i+1])
i +=1
return a_list[-2]
Extended Euclidean Algorithm
The Extended Euclidean algorithm finds a solution to the linear Diophantine equation $ax + by = d$. Setting $a_0 = a$ and $a_1 = b$, it can be computed as follows.
$[\begin{array}{cc} a_{i-1} \ a_i \end{array}]= [\begin{array}{cc} a_iq_i+a_{i+1} \ a_i \end{array}]$ This gives us: $[\begin{array}{cc} a_{i-1} \ a_i \end{array}]= [\begin{array}{cc} q_i & 1 \ 1 & 0 \end{array}] [\begin{array}{cc} a_i \ a_{i+1} \end{array}] $ Let $L_i$ be the inverse of $[\begin{array}{cc} q_i & 1 \ 1 & 0 \end{array}]$. Then: $[\begin{array}{cc} a_i \ a_{i+1} \end{array}]=L_i [\begin{array}{cc} a_{i-1} \ a_i \end{array}] $ Repeating this process yields: $[\begin{array}{cc} d \ 0 \end{array}]=L_i,\dots,L_2 [\begin{array}{cc} a \ b \end{array}] $
Algorithm
Input: Integers $a, b$ Output: GCD $d$ and integers $x, y$ such that $ax + by = d$
- Set $a_0 = a$, $a_1 = b$
- Set $x_0 = 1$, $x_1 = 0$, $y_0 = 0$, $y_1 = 1$
- If $a_i = 0$, set $d = a_{i-1}$, $x = x_{i-1}$, $y = y_{i-1}$ and terminate.
- Determine $a_{i+1}$ and $q_i$ from $a_{i-1} = a_i q_i + a_{i+1}$. Compute $x_{i+1} = x_{i-1} - q_i x_i$ and $y_{i+1} = y_{i-1} - q_i y_i$, then return to step 3.
Program
def exEuclid(a,b):
a_list = []
if a < b:
a_list.append(b)
a_list.append(a)
if a >= b:
a_list.append(a)
a_list.append(b)
q = []
x = []
x.append(1)
x.append(0)
y = []
y.append(0)
y.append(1)
i = 0
while(a_list[-1]!=0):
a_list.append(a_list[i]%a_list[i+1])
q.append(a_list[i]//a_list[i+1])
x.append(x[-2]-q[-1]*x[-1])
y.append(y[-2]-q[-1]*y[-1])
i +=1
return x[-2],y[-2],a_list[-2]