fork download
copy 
  1. def egcd(a, b):
  2.     x,y, u,v = 0,1, 1,0
  3.     while a != 0:
  4.         q, r = b//a, b%a
  5.         m, n = x-u*q, y-v*q
  6.         b,a, x,y, u,v = a,r, u,v, m,n
  7.     gcd = b
  8.     return gcd, x, y
  9.  
  10. print( egcd(12,25))
Success #stdin #stdout 0.03s 9720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(1, -2, 1)
https://ideone.com/9cCd7q
Extended Euclid's algorithm
language:
Python 3 (python  3.9.5)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!