Vés al contingut

Teorema de congruència lineal

De la Viquipèdia, l'enciclopèdia lliure

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

(mod n)      (1)

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

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

Exemple

[modifica]

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

(mod 6)

en canvi hi ha un enter x que verifica:

(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

[modifica]

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

[modifica]

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.