Welcome, guest | Sign In | My Account | Store | Cart

Extended Euclidean Algorithm (Python recipe) by Samuel James Erickson
ActiveState Code (http://code.activestate.com/recipes/578631/)

given input of integers a and b, this program returns GCD(a,b) along with integers x and y such that ax+by=GCD(a,b).

Python, 32 lines
Download
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# Author: Sam Erickson
# Date: 2/23/2016
#
# Program Description: This program gives the integer coefficients x,y to the
# equation ax+by=gcd(a,b) given by the extended Euclidean Algorithm. 

def extendedEuclid(a,b):
    """
    Preconditions - a and b are both positive integers.
    Posconditions - The equation for ax+by=gcd(a,b) has been returned where
                    x and y are solved.
    Input - a : int, b : int
    Output - ax+by=gcd(a,b) : string
    """
    b,a=max(a,b),min(a,b)
    # Format of euclidList is for back-substitution
    euclidList=[[b%a,1,b,-1*(b//a),a]]
    while b%a>0:
        b,a=a,b%a 
        euclidList.append([b%a,1,b,-1*(b//a),a])
    if len(euclidList)>1:
        euclidList.pop()
        euclidList=euclidList[::-1]
        for i in range(1,len(euclidList)):
            euclidList[i][1]*=euclidList[i-1][3]
            euclidList[i][3]*=euclidList[i-1][3]
            euclidList[i][3]+=euclidList[i-1][1]
        
    expr=euclidList[len(euclidList)-1]
    strExpr=str(expr[1])+"*"+str(expr[2])+" + "+str(expr[3])+"*"+str(expr[4]) \
                +" = "+str(euclidList[0][0])
    return strExpr
Tags: algorithm, common, discrete, divisor, euclid, extended, gcd, greatest, logarithm