Fixed extended euclidean algorithm

TheAlgorithms · poyea · Feb 27, 2019 · Feb 25, 2019 · Feb 26, 2019 · Feb 26, 2019
commit 67254c861c17486cb2b853ab2a647a9fdfced22a
diff --git a/Maths/extended_euclidean_algorithm.py b/Maths/extended_euclidean_algorithm.py
@@ -2,31 +2,42 @@
 # @Date:   2019-02-25T12:08:53-06:00
 # @Email:  silentcat@protonmail.com
 # @Last modified by:   silentcat
-# @Last modified time: 2019-02-25T12:36:52-06:00
+# @Last modified time: 2019-02-26T07:07:38-06:00
 
 import sys
 
 # Finds 2 numbers a and b such that it satisfies
 # the equation am + bn = gcd(m, n) (a.k.a Bezout's Identity)
 def extended_euclidean_algorithm(m, n):
-    a = 1; aprime = 0; b = 0; bprime = 1
-    q = 0; r = 1
-    c = m; d = n
+    a = 0; aprime = 1; b = 1; bprime = 0
+    q = 0; r = 0
+    if m > n:
+        c = m; d = n
+    else:
+        c = n; d = m
 
-    while r != 0:
-        q = c / d
+    while True:
+        q = int(c / d)
         r = c % d
-        c = n
+        if r == 0:
+            break
+        c = d
         d = r
 
-        t = a
-        a = aprime
-        aprime = int(t - q*a)
+        t = aprime
+        aprime = a
+        a = t - q*a
 
-        t = b
-        b = bprime
-        bprime = int(t - q*b)
-    return (a, b)
+        t = bprime
+        bprime = b
+        b = t - q*b
+
+    pair = None
+    if m > n:
+        pair = (a,b)
+    else:
+        pair = (b,a)
+    return pair
 
 def main():
     if len(sys.argv) < 3: