Encuentra la solución especial de la ecuación de congruencia lineal

ax ≡ b (módulo n) (1)

Si d = mcd(a, n) y d se pueden dividir entre b, entonces b/d es entero. Según el teorema de Peishu, existe un par de enteros (r, s) (que se puede obtener por división) tal que ar sn = d, por lo que x0 = rb/d es una solución a la ecuación (1). Las otras soluciones tienen que ver con la congruencia n/d y x. x≡x0 (n/d)* t(mod n)(0≤t≤d-1).

Por ejemplo, la ecuación

12x≡20 (28 ítems)

D = mcd(12, 28) = 4. Tenga en cuenta que 4 = 12 *(2) 28 * 1, por lo que x0≡5 *(2)≡-10≡4(mod 7) es una solución. Para módulo 28, t = 1, x≡4 (28/4)* 1≡11(mod t=2, x≡4 (28/4)* 2≡18(mod 28); x≡4 (28/4)*3≡25 (mod 28). Todas las soluciones son {4, 11, 18, 25}.