extended euclidean algorithm finds 2 numbers a and b such that it satisfies the equation am bn gcdm n a k a bezout s identity https en wikipedia orgwikiextendedeuclideanalgorithm s sharma silentcat date 20190225t12 08 5306 00 email silentcatprotonmail com last modified by pikulet last modified time 20201002 extended euclidean algorithm finds 2 numbers a and b such that it satisfies the equation am bn gcdm n a k a bezout s identity extendedeuclideanalgorithm1 24 1 0 extendedeuclideanalgorithm8 14 2 1 extendedeuclideanalgorithm240 46 9 47 extendedeuclideanalgorithm1 4 1 0 extendedeuclideanalgorithm2 4 1 0 extendedeuclideanalgorithm0 4 0 1 extendedeuclideanalgorithm2 0 1 0 base cases sign correction for negative numbers call extended euclidean algorithm if lensys argv 3 print2 integer arguments required return 1 a intsys argv1 b intsys argv2 printextendedeuclideanalgorithma b return 0 if name main raise systemexitmain s sharma silentcat date 2019 02 25t12 08 53 06 00 email silentcat protonmail com last modified by pikulet last modified time 2020 10 02 extended euclidean algorithm finds 2 numbers a and b such that it satisfies the equation am bn gcd m n a k a bezout s identity extended_euclidean_algorithm 1 24 1 0 extended_euclidean_algorithm 8 14 2 1 extended_euclidean_algorithm 240 46 9 47 extended_euclidean_algorithm 1 4 1 0 extended_euclidean_algorithm 2 4 1 0 extended_euclidean_algorithm 0 4 0 1 extended_euclidean_algorithm 2 0 1 0 base cases sign correction for negative numbers call extended euclidean algorithm
from __future__ import annotations

import sys


def extended_euclidean_algorithm(a: int, b: int) -> tuple[int, int]:
    
    
    if abs(a) == 1:
        return a, 0
    elif abs(b) == 1:
        return 0, b

    old_remainder, remainder = a, b
    old_coeff_a, coeff_a = 1, 0
    old_coeff_b, coeff_b = 0, 1

    while remainder != 0:
        quotient = old_remainder // remainder
        old_remainder, remainder = remainder, old_remainder - quotient * remainder
        old_coeff_a, coeff_a = coeff_a, old_coeff_a - quotient * coeff_a
        old_coeff_b, coeff_b = coeff_b, old_coeff_b - quotient * coeff_b

    
    if a < 0:
        old_coeff_a = -old_coeff_a
    if b < 0:
        old_coeff_b = -old_coeff_b

    return old_coeff_a, old_coeff_b


def main():
    
    if len(sys.argv) < 3:
        print("2 integer arguments required")
        return 1
    a = int(sys.argv[1])
    b = int(sys.argv[2])
    print(extended_euclidean_algorithm(a, b))
    return 0


if __name__ == "__main__":
    raise SystemExit(main())