[PYTHON] Euclidean algorithm and extended Euclidean algorithm

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]