Extended Euclidean algorithm

Description:

• Let $a,b\in N^{+}$, $a,b$ not both 0. Then, there exist $s,t\in Z$ such that $sa+tb=gcd(a,b)$theorem
• Extended Euclidean algorithm
  • Find two integers $a$ and $b$ such that $1914a+899b=gcd(1914,899)$
  • First use Euclid’s algorithm to find the GCD:
    • $1914=2\times 899+116$
    • $899=7\times 116+87$
    • $116=1\times 87+29$
    • $87=3\times 29+0$
  • From this, the last non-zero remainder (GCD) is $29$.
  • Now we use the extended algorithm:
    • $29=116+(-1)\times 87$
    • $87=899+(-7)\times 116$​
  • Substituting for 8787 in the first equation, we have
  • $29=116+(-1)\times (899+(-7)\times 116)$
  • $=(-1)\times 899+8\times 116$
  • $=(-1)\times 899+8\times (1914+(-2)\times 899)$
  • $=8\times 1914+(-17)\times 899$​

Implementation:

• def extended_gcd(a, b):
  if b == 0:
  return (a, 1, 0)
  else: s, t, d = extended_gcd(b, a % b)
  return (d, t, s - a // b * t)