Untitled
unknown
plain_text
a year ago
1.1 kB
2
Indexable
Never
def euclidGCD(a, b): # sourcery skip: assign-if-exp, reintroduce-else if a < 0 or b < 0: return None if a < b: return euclidGCD(b, a) if a % b == 0: print(f"{a} = {b} * {a//b} + {a%b}") return b print(f"{a} = {b} * {a//b} + {a%b}") return euclidGCD(b, a % b) x, y = 0, 1 def extEuclidGCD(a, b): global x, y if (a == 0): x, y = 0, 1 return b gcd = extEuclidGCD(b % a, a) x1, y1 = x, y x, y = y1 - (b // a) * x1, x1 return gcd def moduloInverse(a, b): # sourcery skip: assign-if-exp gcd = extEuclidGCD(a, b) if gcd != 1: return None else: return (x % b + b) % b while True: a = input("Enter the first number: ") b = input("Enter the second number: ") try: a = int(a) b = int(b) break except ValueError: print("Invalid input. Try again.") print(f"GCD: {euclidGCD(a, b)}") print(f"GCD using extended: {extEuclidGCD(a, b)}") print(f"Modular multiplicative inverse is: {moduloInverse(a, b)} ")