Solving a Single Congruence Equation

[Albert Chan]

CAS> c := dfc(9988776655/1223334444)      → [8,6,18,1,5,4,1,3,3,10,9,1,3,2,1,6,3]
CAS> dfc2f( reverse(c) )                               → 9988776655 / 3171632349

Building of inverses are equivalent to convergents of reversed continued fraction coefficients.
(with alternative signs, starting from 1^-1 ≡ +1 (mod m))

9988776655  8 *388432661+64171061 = 3171632349
1223334444  6 *64171061+3406295 = 388432661 -
202101103  18 *3406295+2857751 = 64171061
10727826    1 *2857751+548544 = 3406295 -
9000235     5 *548544+115031 = 2857751
1727591     4 *115031+88420 = 548544 -
362280      1 *88420+26611 = 115031
278471      3 *26611+8587 = 88420 -
83809       3 *8587+850 = 26611
27044      10 *850+87 = 8587 -
2677        9 *87+67 = 850
274         1 *67+20 = 87 -
211         3 *20+7 = 67
63          2 *7+6 = 20 -
22          1 *6+1 = 7
19          6 *1+0 = 6 -
3                    1
1 = gcd