Python code to calculate Euclid’s coefficients

Python code for calculating Euclid’s coefficients

\PMlinkescapetext{
def ExtGCD(x,y):
  m,n=x,y
  b,d=0,1
  p,t=1,0
  while (m!=0):
    q = n//m  # yes, //
    n,m=m,n-q*m
    d,b=b,d-q*b
    t,p=p,t-q*p
  return (t*x+d*y,t,d)

print ExtGCD(523,541) # Example from the parent entry
}

and it displays

\PMlinkescapetext{
>>> (1, 30, -29)
}

since

$$1=tx+dy=30\cdot 523-29\cdot 541$$

Title	Python code to calculate Euclid’s coefficients
Canonical name	PythonCodeToCalculateEuclidsCoefficients
Date of creation	2013-03-22 15:15:31
Last modified on	2013-03-22 15:15:31
Owner	drini (3)
Last modified by	drini (3)
Numerical id	7
Author	drini (3)
Entry type	Algorithm
Classification	msc 11A05