Congruència

De Viquipèdia

Congruència és un terme utilitzat en la teoria de nombres, per a designar que dos nombres enters $a$ i $b$ tenen el mateix residu al dividir-los per un nombre natural $m$ , anomenat el mòdul; aquest s'expressa utilitzant la notació: $a \equiv b ({\rm mod} m)$ que s'expressa dient que $a$ és congruent amb $b$ mòdul $m$ . Una altra definició equivalent és que el mòdul $m$ divideix exactament a la diferència $a - b$ .

Per exemple, $12\equiv 17 ({\rm mod} 5)$ perquè obtenim el mateix residu (2) si dividim 12 entre 5 i 17 entre 5.

El terme congruència s'utilitza a més amb dos sentits lleugerament diferents: per una banda amb el sentit d'identitat matemàtica; com exemple d'aquest us tenim el petit teorema de Fermat que assegura que per a cada primer $p$ i cada enter $a$ no divisible per $p$ tenim la congruència:

$a^{p-1} \equiv 1 ({\rm mod} p).$

Per altra banda s'utilitza en el sentit d'equació, on apareixen una o més incògnites, i ens preguntem si una congruència té solució i en cas afirmatiu, quines són totes les seves solucions, per exemple la congruència $x^2 - 5 \equiv 0 ({\rm mod} 11)$ , té solució, i totes les seves solucions venen donades per $x \equiv 4$ i $x\equiv 7 ({\rm mod} m)$ , és a dir $x$ pot ser qualsevol enter de les successions $11 k + 4$ i $11 k + 7$ . Contràriament, la congruència $x^2-2 \equiv 0 ({\rm mod} m)$ , no té solució.

La notació i la terminologia van ser introduïdes per Carl Friedrich Gauss en el seu llibre Disquisitiones Arithmeticae el 1801. La seva utilització s'ha extès a molts altres entorns en els que podem parlar de divisibilitat, per exemple a polinomis amb coeficients en un cos, a ideals d'anells de nombres algebraics, etc.

[edita] Propietats

La congruència té moltes propietats en comú amb la igualtat, per citar algunes:

La congruència per a un mòdul fix $m$ és una relació d'equivalència ja que es verifiquen les propietats:

1) reflexiva: $a \equiv a ({\rm mod} m)$

2) simètrica: si $a \equiv b ({\rm mod} m)$ llavors també $b \equiv a ({\rm mod} m)$

3) transitiva: si $a \equiv b ({\rm mod} m)$ i $b \equiv c ({\rm mod} m)$ llavors també $a \equiv c ({\rm mod} m)$ .

Si $a$ és coprimer amb $m$ i $a \equiv b ({\rm mod} m)$ , llavors $b$ també és coprimer amb $m$ . Encara més si $a \equiv b ({\rm mod} m)$ , llavors el màxim comú divisor de $a$ i $m$ és el mateix que el màxim comú divisor de $b$ i $m$