DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets has posted 5883 posts at DZone. View Full User Profile

Euclid's Extended Algorithm

06.22.2007
| 4954 views |
  • submit to reddit
        Basically Euclid's algorithm for finding the largest common denominator, this one is modified in order to obtain the numbers d, x, y, where d is the dennominator and they check the following equation:
d = ax + by

def euclidExtended(a, b):
  if b == 0:
    return a, 1, 0
  dd, xx, yy = euclidExtended(b, a % b)
  d, x, y = dd, yy, xx - int(a / b) * yy
  return d, x, y