Méthode de division mutuelle euclidienne et méthode de division mutuelle euclidienne étendue

Méthode de division mutuelle euclidienne

Étant donné les entiers $ a, b (a> b) $, si $ a $ est divisé par $ b $ et le reste est $ r $. En utilisant le fait que les promesses maximales de $ a $ et $ b $ et les promesses maximales de $ b $ et $ r $ sont égales (principe de division), les promesses maximales de $ a et b $ peuvent être calculées en répétant la division. Comment le trouver.

algorithme

Entiers d'entrée $ a, b $ Engagement maximum de sortie $ d $

1. a_0 = a,a_1 = b
2. Lorsque $ a_i = 0 $, définissez $ d = a_ {i-1} $ et terminez
3. Revenir à 2 comme $ 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]

Méthode de division mutuelle euclidienne étendue

Une méthode pour trouver une solution d'une équation linéaire indéfinie en utilisant le mécanisme suivant. Lorsque vous recherchez $ ax + by = d $, définissez $ 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}] Puis $[\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}] $ Appel. $[\begin{array}{cc} q_i & 1 \ 1 & 0 \ end {array}] Soit $ L_i $ l'inverse de $. $[\begin{array}{cc} a_i \ a_{i+1} \end{array}]=L_i [\begin{array}{cc} a_{i-1} \ a_i \end{array}] $ Si vous répétez ceci, $[\begin{array}{cc} d \ 0 \end{array}]=L_i,\dots,L_2 [\begin{array}{cc} a \ b \end{array}] $ Il devient.

algorithme

Entiers d'entrée $ a, b $ Sortie: Entiers $ x, y $ avec engagements maximum $ d $ et $ ax + by = d $

1. Définissez $ a_0 = a $, $ a_1 = b $.
2. Définissez $ x_0 = 1 $, $ x_1 = 0 $, $ y_0 = 0 $, $ y_1 = 1 $.
3. Quand $ a_i = 0 $, $ d = a_i − 1 $, $ x = x_ {i − 1} $, $ y = y_ {i − 1} $ et le processus se termine.
4. $ a_ {i − 1} = a_iq_i + a_ {i + 1} $ définit $ a_ {i + 1} $ et $ q_i $. x_{i+1} = x_{i−1} − q_ix_i y_i+1=y_i−1−q_iy_i Revenir à 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]