modinverse.py

def extended_euclidian(a, b):
    if b == 0:
        return a, 1, 0
    gcd, s, t = extended_euclidian(b, a % b)
    s, t = t, s - int(a / b) * t
    return gcd, s, t

print("Alphabet length:")
length = int(input())
print("Key:")
key = int(input())

gcd, _, inverse = extended_euclidian(length, key)
if gcd != 1:
    print("Alphabet length/key combination is ambiguous, could not determine inverse key")
else:
    print(f'Inverse key: {inverse}')