Skip to content

Instantly share code, notes, and snippets.

@skychan

skychan/egcd.py

Created August 4, 2017 03:09
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save skychan/8c21d22f7698af718f93d780a933a612 to your computer and use it in GitHub Desktop.
Save skychan/8c21d22f7698af718f93d780a933a612 to your computer and use it in GitHub Desktop.
Download ZIP
Extended Eculdiean algorithm
Raw
egcd.py
def egcd(a,b):
if b == 0:
return a, 1, 0
c, x, y = egcd(b, a%b)
return c, y, x - (a//b) *y
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment