# Euclidean algorithm

Given the integers $a, b (a> b)$, if $a$ is divided by $b$ and the remainder is $r$. Using the fact that the greatest common divisor of $a$ and $b$ is equal to the greatest common divisor of $b$ and $r$ (the principle of division), the greatest common divisor of $a and b$ is calculated by repeating the division. How to find it.

## algorithm

Input integers $a, b$ Output: Greatest common divisor $d$

1. a_0 = a,a_1 = b
2. When $a_i = 0$, set $d = a_ {i-1}$ and finish.
3. Return to 2 as $a_ {i-1} = a_iq_i + a_ {i + 1}$

## code

#### euclid.py


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

A method of finding one solution of a linear indefinite equation using the following mechanism. When finding $ax + by = d$, set $a_0 = a, a_1 = b$.

[\begin{array}{cc} a_{i-1} \\ a_i \end{array}]= [\begin{array}{cc} a_iq_i+a_{i+1} \\ a_i \end{array}] Then $[\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}]$ Call. $[\begin{array}{cc} q_i & 1 \ 1 & 0 \ end {array}] Let the inverse matrix of$ be $L_i$. $[\begin{array}{cc} a_i \ a_{i+1} \end{array}]=L_i [\begin{array}{cc} a_{i-1} \ a_i \end{array}]$ If you repeat this, $[\begin{array}{cc} d \ 0 \end{array}]=L_i,\dots,L_2 [\begin{array}{cc} a \ b \end{array}]$ It becomes.

## algorithm

Input integers $a, b$ Output: Integers $x, y$ with the greatest common divisor $d$ and $ax + by = d$

1. Set $a_0 = a$, $a_1 = b$.
2. Set $x_0 = 1$, $x_1 = 0$, $y_0 = 0$, $y_1 = 1$.
3. When $a_i = 0$, $d = a_i−1$, $x = x_ {i−1}$, $y = y_ {i−1}$ and the process ends.
4. $a_ {i−1} = a_iq_i + a_ {i + 1}$ defines $a_ {i + 1}$ and $q_i$. x_{i+1} = x_{i−1} − q_ix_i y_i+1=y_i−1−q_iy_i Return to 3.

## code

#### exEuclid.py


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]