Solving a Single Congruence Equation

[Albert Chan]

There is no need to walk the whole chain of inverses.

For x ≡ 1/1223334444 (mod 9988776655), gcd intermediates are even, final inverse is positive.
We can guess where it should end up.

1/3 ≡ -6 (mod 19)    → x ≈ |floor(−6/19 * 9988776655)| = 3154350523
1/19 ≡ +7 (mod 22) → x ≈ |floor(+7/22 * 9988776655)| = 3178247117

x is between above limits.
We can extrapolation in smaller steps, to scale to correct inverses.

\(\displaystyle \left|{6 \over 19} - {7 \over 22}\right|
= {1 \over 19×22}
= {1 \over 418}
< {1 \over 274}
\)

1/211 ≡ (-1)⁴ floor(-6/19 * 274) ≡ -87 (mod 274)

Redo previous example, skipping unneeded calculations.

9988776655 → (-1)^6 floor(115031/362280 * 9988776655) = 3171632349
1223334444
202101103
10727826
9000235
1727591
362280 → (-1)^5 floor(-87/274 * 362280) = 115031 ; 362280*1727591 ≈ 626e9
278471
83809
27044
2677
274 → (-1)^3 floor(7/22 * 274) = -87 ; 274*2677=733498
211
63
22 → (-1)^2 floor(1/3 * 22) = 7 ; 22*63=1386
19
3 → 1 ; 3*19=57
1 = gcd

4th scalings gives: 1/1223334444 ≡ 3171632349 (mod 9988776655)