(35S) Bézout or EGCD

[Gerald H]

Bézout (or extended Euclidean algorithm) finds integer solutions for C, E & GCD( X , Y ) in the equation

C * X + E * Y = GCD( X , Y ).

For example, for stack

Y: 666,777
X: 777,666

The programme returns

Z: 111 (our GCD)
Y: -3,233 (E)
X: 2,772 (C)

& indeed

2,772 * 777,666 + -3,233 * 666,777 = 111

1 LBL B
2 1►E►F-1►C►D
3 R↓
4 REGY
5 REGY
6 INT/
7 +/-
8 ENTER
9 RCL* D
10 RCL+ E
11 x<> D
12 STO E
13 R↓
14 ENTER
15 RCL* F
16 RCL+ C
17 x<> F
18 STO C
19 R↓
20 REGY
21 *
22 REGZ
23 +
24 x≠0?
25 GTO B004
26 R↓
27 RCL E
28 RCL C
29 RTN

Should the GCD be 1, then E is the multiplicative inverse of Y modulo X & C the multiplicative inverse of X modulo Y.