Solving a Single Congruence Equation

[Albert Chan]

Getting to the "2nd best" convergents might be messy, we can do guesses.
You get to the same result even if the guesses were off.

Example: With modulo N=17789, solve 12345 x ≡ 1

12345 ≡ -5444

N/5444 ≈ 3.2676 ≈ 13/4, 13*(12345 x ≡ 1) → (384 x ≡ 13)

N/384 ≈ 46.3255 ≈ 139/3, 139*(384 x ≡ 13) → (9 x ≡ 1807)

N/9 ≈ 1976.5555 ≈ 3953/2, 3953*(9 x ≡ 1807) → (-x ≡ 9682) → (x ≡ 8107)

Warning: make sure guess scaling is co-prime to the modulo.