Congruències lineals

Diem que a és congruent amb b mòdul m si a i b donen el mateix residu en dividir-los per m. S'escriu a ≡ b mod m.

Per exemple: 17 ≡ 5 mod 2.

Una equació lineal en congruències és una equació de la forma: ax+b ≡ 0 mod m Si p és una solució de l'equació també ho són p+m, p+2m, p+3m,....

• Si M=mcd(a,m)=1 hi ha una solució.
• Si M=mcd(a,m)#1 i M és divisor de b hi ha M solucions.
• Si M=mcd(a,m)#1 i M no és divisor de b, no hi ha solució.