Solving a Single Congruence Equation

[Albert Chan]

(03-10-2019 12:45 AM)Albert Chan Wrote:  If N is large, we can solve another, with smaller modulo:
x ≡ (4447 - 17789 k) / 1361 (mod 17789) → 17789 k ≡ 4447 (mod 1361)

Example, solve 1223334444 x ≡ 1 (mod 9988776655)

List Euclid GCD intermediates, build inverses in reverse order.

9988776655 → 3171632349
1223334444 → -388432661
202101103 → 64171061
10727826 → -3406295
9000235 → 2857751
1727591 → -548544
362280 → 115031
278471 → -88420
83809 → 26611
27044 → -8587
2677 → 850
274 → -87
211 → -floor(-20/63 * 211) = 67
63 → -floor(7/22 * 63) = -20
22 → -floor(-6/19 * 22) = 7
19 → -floor(1/3 * 19) = -6
3  → 1 ; 1^-1 ≡ 1 (mod 3)
1 = gcd

9988776655 * -388432661 + 1223334444 * 3171632349 = 1

→ 1/9988776655 ≡ -388432661 (mod 1223334444)
→ 1/1223334444 ≡ 3171632349 (mod 9988776655)