@@ -0,0 +1,447 @@
+# extended gcd and inverse mod%0A%0Adef extgcd(a, b):%0A    if (abs(a) %3E= abs(b)):%0A        if a %25 b == 0:%0A            v1 = %5Bb, 0, 1%5D%0A            return v1%0A        else:%0A            q = a // b%0A            r = a %25 b%0A            D, s, t = extgcd(b, r)%0A            v2 = %5BD, t, s - t*q%5D%0A            return v2%0A    else:%0A        return extgcd(abs(b), abs(a))%0A%0Adef modinv(a, n):    %0A    if (gcd(a, n) == 1):%0A        _, _, m = extgcd(a, n)%0A        return m %25 n %0A

Create ExtendedGreatestCommonDivisor.py