Over a million developers have joined DZone.

Euclid's Extended Algorithm

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


The best of DZone straight to your inbox.

Please provide a valid email address.

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}