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]