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