Solving a Single Congruence Equation

[Albert Chan]

Another way to do inverse is to force even coef., thus easily reduced.
(make sure mul/div factors co-prime to the modulo)

Same example, solve 12345 x ≡ 1 (mod 17789)

12345 x ≡ -5444 x ≡ 1 ≡ -17788 (mod 17789)
1361 x ≡ 4447 (mod 17789)

(12345 - 9*1361) x ≡ 1 - 9*4447 (mod 17789)

96 x ≡ -40022 ≡ -75600 (mod 17789)
2 x ≡ -1575 ≡ 16214 (mod 17789)
x ≡ 8107 (mod 17789)

If N is large, we can solve another, with smaller modulo:
x ≡ (4447 - 17789 k) / 1361 (mod 17789) → 17789 k ≡ 4447 (mod 1361)

96 k ≡ 4447 ≡ 5808 (mod 1361)
2 k ≡ 121 ≡ -1240 (mod 1361)
k ≡ -620 (mod 1361)

x ≡ (4447 - 17789 * -620) / 1361 ≡ 8107 (mod 17789)