Solving a Single Congruence Equation

[Albert Chan]

It may be easier to solve A x ≡ B (mod N) problem using continued fraction.
It is the same as Euclid extended gcd method, without tracking multiples for A and N

Example 5 x ≡ 3 (mod 17)

17/5 = 3 + 1/(2 + 1/2)

Drop the last term, we get 3 + 1/2 = 7/2

-> 7*5 - 2*17 = 1, so 7 ≡ 1/5 (mod 17)

x ≡ 3/5 ≡ 3*7 ≡ 4 (mod 17)