extended_euclidean_algorithm.py

"""
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)

https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
"""

# @Author: 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
from __future__ importannotations

importsys


defextended_euclidean_algorithm(a: int, b: int) ->tuple[int, int]:
"""
 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
ifabs(a) ==1:
returna, 0
elifabs(b) ==1:
return0, b

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

whileremainder!=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

# sign correction for negative numbers
ifa<0:
old_coeff_a=-old_coeff_a
ifb<0:
old_coeff_b=-old_coeff_b

returnold_coeff_a, old_coeff_b


defmain():
"""Call Extended Euclidean Algorithm."""
iflen(sys.argv) <3:
print("2 integer arguments required")
return1
a=int(sys.argv[1])
b=int(sys.argv[2])
print(extended_euclidean_algorithm(a, b))
return0


if__name__=="__main__":
raiseSystemExit(main())