Congruència sobre els enters

La congruència sobre els enters és una relació que permet identificar diversos enters diferents. Va ser estudiada per primera vegada en tant que estructura pel matemàtic alemany Carl Friedrich Gauss al final del segle xviii i presentada al públic en el seu Disquisitiones arithmeticae el 1801. Avui es fa servir habitualment en teoria de nombres, àlgebra i en criptografia. Constitueix el fonament de la branca de la matemàtica anomenada aritmètica modular.

En aritmètica modular, no es raona directament sobre els nombres sinó sobre els residus de la seva divisió euclidiana entre un cert enter: el mòdul (que s'escriurà n al llarg de l'article). Es parla llavors de congruència entre dos o més nombres si els seus residus són iguals.

La història, les eines desenvolupades per a l'aritmètica modular així com les seves aplicacions es tracten a l'article Aritmètica modular.

Idea intuïtiva: Aritmètica del rellotge

La mesura del temps en un rellotge dona un exemple d'aritmètica modular.

L'aritmètica modular és un sistema aritmètic d'enters modificats, on els nombres tornen a començar a comptar des de zero quan arriben a un cert valor.

Es pot agafar com a exemple l'aritmètica del rellotge, on es considera l'addició de les hores indicades per l'agulla petita d'un rellotge: per exemple, si es comença a les 7 hores i s'hi afegeixen 8 hores, llavors en comptes de trobar-nos a les 15 hores (com en la suma normal), resultem ser a les 3 hores. De la mateixa manera, si es comença a mitjanit i s'espera que passin 7 hores cinc vegades seguides, ens trobem a les 11 hores (en lloc de les 35).

Fonamentalment, quan s'arriba a 12, es recomença a zero; es treballa mòdul 12. Per reprendre l'exemple precedent, es diu que 11 i 35 són congruents mòdul 12. Els nombres 11, 23, 35, 47, ... es consideren iguals quan es treballa mòdul 12.

Per generalitzar aquest concepte, es pot imaginar fàcilment un rellotge que contingui un nombre arbitrari d'hores, i fer càlculs amb un nou mòdul qualsevol.

Congruència mòdul n

Definició

Dos enters a i b s'anomenen congruents mòdul n, on n és un enter superior o igual a 2, si es verifica una de les condicions següents (que com que són equivalents entre si llavors també es verifiquen les altres):

1. la seva diferència és divisible entre n;
2. el residu de la divisió euclidiana de a entre n és igual al de la divisió de b entre n;
3. existeix un enter k tal que a-b=kn;
4. $a-b\in n\mathbb {Z} =(n)$, l'ideal de tots els enters divisible entre n.

Notació

Si a i b són congruents mòdul n, s'escriu:

$a\equiv b\;(\operatorname {m{\grave {o}}d} \ n)$ o també $a\equiv b\ (n)$ o $a\equiv b\ [n]$.

en tots els casos es llegeix «a és congruent amb b mòdul n».

Per exemple :

26 ≡ 12 (mòd 14).

El caràcter utilitzat és ≡. Tanmateix, per comoditat, de vegades se substitueix per = fins i tot si això és absolutament fals. L'abreviatura «mòd» de mòdul sovint es posa sense l'accent reflectint l'expressió llatina modulo. Quan el mòdul de les congruències és sempre el mateix o molt evident s'acostuma a ometre d'aquesta notació i es deixa únicament el símbol de congruència ≡.

Propietats

Relació d'equivalència

La congruència mòdul n té les següents propietats:

• Reflexiva:

Per a tot enter a, a ≡ a (mòd n)

• Simètrica:

Per a qualsevol parell d'enters a i b, a ≡ b (mòd n) ⇔ b ≡ a (mòd n)

• Transitiva:

Per a qualsevulla enters a, b i c, si a ≡ b (mòd n) i b ≡ c (mòd n) llavors a ≡ c (mòd n)

Per tant és una relació d'equivalència.

Propietats algebraiques

A més, té les següents propietats algebraiques destacables:

Si

a₁ ≡ b₁ (mòd n) i a₂ ≡ b₂ (mòd n)

llavors

a₁ + a₂ ≡ b₁ + b₂ (mòd n)

i

a₁a₂ ≡ b₁b₂ (mòd n).

Finalment, amb un enter natural, q superior o igual a 1, s'obté:

a₁^q ≡ b₁^q (mòd n).

Es pot parlar d'una certa «compatibilitat» amb les operacions d'addició i de multiplicació dels enters, és a dir de «compatibilitat» amb l'estructura d'anell de (ℤ,+,*). Aquestes propietats permeten definir l'àmbit de l'aritmètica modular: els conjunts quocients ℤ/nℤ.

Anell de residus ℤ/nℤ

Construcció

Les propietats precedents mostren que dos nombres congruents entre ells mòdul n són intercanviables en una addició o una multiplicació, si el càlcul es fa amb una congruència mòdul n. La idea porta llavors a agrupar tots els nombres congruents entre ells mòdul n en una mateixa classe que es diu una classe d'equivalència i a no treballar més que amb un representant particular d'aquesta classe. Com que tots els nombres de la mateixa classe tenen igual residu en la divisió entre n, es privilegien els residus de la divisió entre n i es treballa sobre un conjunt notat $\mathbb {Z} _{n}$ o $\mathbb {Z} /n\mathbb {Z}$ compost pels n elements $\{{\overline {0}},{\overline {1}},\cdots {\overline {n-1}}\}$ o més simplement {0, 1, 2..., n - 1} conjunt dels residus mòdul n, que es diu anell residual mòdul n o també anell quocient.

Sobre aquest conjunt es pot definir una addició i una multiplicació anàlogues a les definides sobre els enters:

• Addició: a dos residus a i b, s'associa el residu de a + b mòdul n. S'hauria de trobar teòricament una altra notació per a la suma, però, per motius de simplicitat, es conserva la mateixa notació que pren llavors un sentit diferent.
• : així a l'anell de les congruències mòdul 6, s'escriu 3 + 2 = 5 però 4 + 2 = 0 ja que la suma de 4 i 2 dona de residu 0 mòdul 6
• Multiplicació: a dos residus a i b, s'associa el residu de a ⋅ b mòdul n. Per les mateixes raons que anteriorment, s'utilitza per a símbol producte el mateix símbol que en el conjunt dels enters
• : així a l'anell de les congruències mòdul 6, s'escriu 2 ⋅ 2 = 4, però 2 ⋅ 5 = 4 (ja que el producte de 2 per 5 dona de residu 4 al dividir-lo entre 6) i fins i tot 2 ⋅ 3 = 0

Llavors es poden construir les següents taules d'operacions:

Taula de sumar en ℤ/6ℤ + 0 1 2 3 4 5 0 0 1 2 3 4 5 1 1 2 3 4 5 0 2 2 3 4 5 0 1 3 3 4 5 0 1 2 4 4 5 0 1 2 3 5 5 0 1 2 3 4

Taula de multiplicar en ℤ/6ℤ × 0 1 2 3 4 5 0 0 0 0 0 0 0 1 0 1 2 3 4 5 2 0 2 4 0 2 4 3 0 3 0 3 0 3 4 0 4 2 0 4 2 5 0 5 4 3 2 1

Aquestes operacions tenen gairebé les mateixes propietats que l'addició i la multiplicació en ℤ.

• l'addició és commutativa (els termes es poden permutar), associativa (al sumar 3 termes es pot fer indiferentment la suma dels dos primers i afegir l'últim o la suma dels dos últims afegir-hi el primer), posseeix un element neutre (afegir 0 no canvia res) i cada element posseeix un oposat.
• : Un matís significatiu en comparació amb l'addició en ℤ, és que, en ℤ, l'oposat de a és - a ja que a + (- a) = 0. Ara bé, a l'anell de les congruències mòdul n, l'oposat de - a és n - a ja que a + (n - a) = 0 (la suma de a i de n - a dona residu 0 en la divisió entre n). Tanmateix, -a i n - a són intercanviables mòdul n, la tria de n - a en comptes de - a és degut al fet que s'escull com a representant EL nombre comprès entre 0 i n - 1.
• la multiplicació és commutativa, associativa, posseeix un element neutre (multiplicar per 1 no canvia res) i continua sent distributiva per a l'addició.

D'un conjunt proveït de dues operacions que tenen aquestes propietats se'n diu un anell.

Simplificació i equacions

L'única operació que es té el costum de fer en ℤ en comptes de fer-la a l'anell ℤ/nℤ és la simplificació.

En efecte si 2a = 4 en ℤ, se sap que a = 2. Però, en ℤ/6ℤ, si 2a = 4, se sap només que 2a té per residu 4 en la divisió entre 6 per tant a té per a residu 2 en la divisió entre 3. Per tant a pot tenir per a residu en la divisió entre 6 o bé 2 o bé 5. Més simplement: es té 2 ⋅ 2 = 2 ⋅ 5 sense tenir tanmateix 2 = 5.

Igualment, la propietat que s'utilitza constantment en els conjunts de nombres clàssics

«

perquè un producte de dos termes sigui nul, cal i n'hi ha prou que un dels termes ho sigui

»

no és sempre certa en ℤ/nℤ:

en ℤ/6ℤ, es té 2 ⋅ 3 = 0, sense que ni 2 ni 3 siguin nuls

Es diu que l'anell ℤ/6ℤ no és íntegre i que 2 i 3 són divisors de zero.

Per tant, la resolució d'equacions pot esdevenir una mica problemàtica quan hi entren en joc les multiplicacions:

• l'equació x + 2 = 1 en ℤ/6ℤ es resol afegint la mateixa quantitat (4) a cada membre x = 5 (ja que 2 + 4 = 0)
• l'equació 3x = 2 en ℤ/10ℤ es resol fixant-se en què 3 ⋅ 7 = 1 i que les equacions 3x = 2 i x = 7 ⋅ 2 són equivalents (es passa de l'una a l'altra multiplicant cada membre per 7 o 3). Llavors la solució és igual a 4 (ja que 2 × 7 té pre residu 4 mòdul 10)
• l'equació 2x = 3 en ℤ/10ℤ no té cap solució i l'equació 2x = 6 en té dues (3 i 8)

Es demostra que la resolució de l'equació ax = b d'incògnita x en ℤ/nℤ té una única solució si i només si a i n són primers entre ells

La recerca de solucions de l'equació $x^{2}\equiv a{\pmod {n}}$ que, segons els valors de n i de a, pot no tenir-ne cap, tenir-ne una, dues, o fins i tot més, dona lloc a l'estudi dels residus quadràtics i a l'enunciat de la llei de reciprocitat quadràtica.

Potències i petit teorema de Fermat

A partir de la multiplicació en ℤ/nℤ, és natural interessar-se per les potències successives. No hi ha més que n - 1 residus possibles, per tant n - 1 són els valors possibles per a^k, s'obté doncs necessàriament diverses vegades el mateix valor. Per tant, existeixen k i m tals que a^k i a^m tenen el mateix residu mòdul n. Com que la construcció de a^k es basa en una recurrència, de manera que es cau sobre un residu ja trobat anteriorment, se sap que la successió de les potències es fa cíclica a partir d'aquesta potència i es pot parar l'exploració.

Potències successives en ℤ/7ℤ 1 2 3 4 5 6 k = 0 1 1 1 1 1 1 k = 1 1 2 3 4 5 6 k = 2 ... 4 2 2 4 1 k = 3 ... 1 6 1 6 ... k = 4 ... ... 4 ... 2 ... k = 5 ... ... 5 ... 3 ... k = 6 1 1 1 1 1 1

Potències successives en ℤ/15ℤ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 k = 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 k = 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 k = 2 ... 4 9 1 10 6 4 4 6 10 1 9 4 1 k = 3 ... 8 12 ... 5 ... 13 2 9 ... ... 3 7 ... k = 4 ... 1 6 ... ... ... 1 1 ... ... ... 6 1 ... k = 5 ... ... 3 ... ... ... ... ... ... ... ... 12 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... k = 8 1 1 ... 1 ... ... 1 1 ... ... 1 ... 1 1

Una observació sobre les potències en ℤ/7ℤ i ℤ/15ℤ mostra que, en el primer cas, per a tot a coprimer amb 7 (és a dir no congruent amb 0 mòdul 7), es té a⁶ congruent amb 1 mòdul 7 i en el segon cas, només les successions que passen per 1 corresponen a enters primers amb 15, hi ha 8 enters coprimers amb 15 i s'observa que per a a coprimer amb 15, a⁸ és congruent amb 1 mòdul 15.

Aquestes dues observacions corresponen a dos teoremes:

• el petit teorema de Fermat que estableix que per a tot enter n primer i tot enter a primer amb n, $a^{n-1}\equiv 1{\pmod {n}}$
• el teorema d'Euler, generalització del teorema precedent, que precisa que, per a tot enter n més gran o igual a 2, i tot enter a primer amb n, $a^{\varphi (n)}\equiv 1{\pmod {n}}$, on φ(n), la funció Fi d'Euler, és el nombre d'enters comprès entre 1 i n - 1 i coprimers amb n.

Vegeu també

• Aritmètica modular
• Divisibilitat
• Criteri de divisibilitat
• Llista de criteris de divisibilitat
• Noció de mòdul