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$$