# Małe twierdzenie Fermata
# Odwrotność a modulo m
# Założenie: m jest liczbą pierwszą
def gcd(a,b):
    if (b == 0):
        return a
    else:
        return gcd(b, a % b)

# Funkcja obliczająca x^y modulo m
def power(x,y,m):
    if (y == 0):
        return 1
    p = power(x, y // 2, m) % m
    p = (p * p) % m
    return p if(y % 2 == 0) else (x * p) % m

# Funkcja znajdująca odwrotność a modulo m
def modInverse(a,m):
    if (gcd(a, m) != 1):
        print("Odwrotność nie istnieje")
    else:
        # Jeżeli a i m są względnie pierwsze, to
        # # odwrotność jest równa a^(m-2) modulo m
        print("Odwrotność modulo to", power(a, m - 2, m))

a = 3
m = 11
modInverse(a, m)