Teorema de congruència lineal

En aritmètica modular, la qüestió de les condicions de resolució d'una congruència lineal es pot resoldre pel teorema de congruència lineal. Si a i b són enters qualssevulla i n un enter positiu, llavors la congruència

$ax\equiv b\,$ (mod n)      (1)

té una solució si i només si el m.c.d. de (a, n) divideix b'. Quant és així i x₀ és una solució de (1), llavors el conjunt de totes les solucions ve donat per

$\{x_{0}+k{\frac {n}{d}}\mid k\in \mathbb {Z} \}.$

En particular, existeixen exactament d solucions en el conjunt dels residus {0,1,2,...,n-1}.

Exemple

Par exemple, No hi ha cap enter x que verifiqui la relació següent:

$4x\equiv 3\,$ (mod 6)

en canvi hi ha un enter x que verifica:

$4x\equiv 2\,$ (mod 6).

Un altre exemple, l'equació ax ≡ 2 (mod 6) amb diferents valors de a dona

3x ≡ 2 (mod 6)

on d = m.c.d.(3,6) = 3 però com que 3 no divideix pas 2, no hi ha cap solució.

5x ≡ 2 (mod 6)

aquí d = m.c.d.(5,6) = 1, que divideix qualsevol b, i per tant existeix simplement una solució a {0,1,2,3,4,5} : x=4.

4x ≡ 2 (mod 6)

aquí d = m.c.d.(4,6) = 2, que divideix 2, i per tant existeixen exactament dues solucions en {0,1,2,3,4,5} : x=2 i x=5.

Resolució d'una congruència lineal

Si el m.c.d. d de a i de n divideix b, llavors es pot trobar una solució x de la congruència (1) : l'algorisme d'Euclides ampliat subministra els enters r i s que verifiquen la relació ra + sn = d. Llavors x = rb/d és la solució. Les altres solucions són els nombres congruents a x mòdul n/d.

Per exemple, la congruència

12x ≡ 20 (mod 28)

Té com a solució m.c.d. (12, 28) = 4, que divideix 20. L'algorisme d'Euclides ampliatal dona (-2)*12 + 1*28 = 4, això dona r = -2 i s = 1. En conseqüència, la solució és x = -2*20/4 = -10. Totes les altres solucions són congruents a -10 mòdul 7: són dons congruents a 4 mòdul 7.

Sistema de congruències lineals

Per repetició de l'ús del teorema de les congruències lineals, també es poden resoldre els sistemes de congruències lineals, com en l'exemple següent:

Trobar tots els enters x que verifiquen les relacions següents :

2x ≡ 2 (mod 6)

3x ≡ 2 (mod 7)

2x ≡ 4 (mod 8)

Per la resolució de la primera congruència utilitzant el mètode exposat més amunt, es troba x ≡ 1 (mod 3), que també es pot escriure com x = 3k + 1. Substituint en la segona congruència i simplificant, s'obté

9k ≡ −1 (mod 7)

La resolució d'aquesta congruència dona k ≡ 3 (mod 7), o k = 7l + 3. D'aquí resulta x = 3 (7l + 3) + 1 = 21l + 10. Substituint a la tercera congruència i simplificant s'obté

42l ≡ −16 (mod 8)

Que té la solució l ≡ 0 (mod 4), o l = 4m. Això dona x = 21(4m) + 10 = 84m + 10, o

x ≡ 10 (mod 84)

Que dona totes les solucions d'aquest sistema.

Article principal: Teorema dels residus xinesos