Ax ≡ b (modulo n) (1)
If d = gcd(a, n) and d is divisible by b, then b/d is an integer. According to Pei Shu's theorem, there is an integer pair (r, s) (which can be obtained by division) that makes ar+sn=d, so x0=rb/d is a solution of equation (1). Other solutions are all about n/d and x congruences. x≡x0+(n/d)* t(mod n)(0≤t≤d- 1)。
For example, the equation
12x≡20(28 models)
D = gcd( 12，28) = 4。 Note that 4 = 12 *(2)+28 * 1, so x0≡5 *(2)≡- 10≡4(mod 7) is a solution. For module 28, t = 1, x ≡ 4+(28/4) *1≡1(mod 28); t=2，x≡4+(28/4)* 2≡ 18(mod 28)； t=3，x≡4+(28/4)*3≡25 (mod 28)。 All solutions are {4, 1 1,18,25}.