Relació de congruència

En matemàtiques i en particular en àlgebra abstracta, una relació de congruència o simplement una congruència és una relació d'equivalència que és compatible amb algunes operacions algebraiques.

Aritmètica modular

L'exemple típic de congruència és la congruència sobre els enters que es fa servir en aritmètica modular.

En aquest context congruència és el terme que es fa servir per a designar que dos nombres enters $a$ i $b$ tenen el mateix residu en ser dividits per un nombre natural $m$, anomenat el mòdul; aquest s'expressa utilitzant la notació:$a\equiv b(\mathrm{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(\mathrm{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 a exemple d'aquest ús 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(\mathrm{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(\mathrm{mod}11)$, té solució, i totes les seves solucions venen donades per $x\equiv 4$ i $x\equiv 7(\mathrm{mod}11)$, és a dir x pot ser qualsevol enter de les successions 11k+4 i 11k+7. Contràriament, la congruència $x^2-2\equiv 0(\mathrm{mod}11)$, 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 estè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.

Relació d'equivalència

• 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(\mathrm{mod}m)$.

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

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

Compatibilitat amb les operacions d'addició i multiplicació dels enters

• Si $a\equiv b(\mathrm{mod}m)$ i k és un enter llavors també es compleix

$a+k\equiv b+k(\mathrm{mod}m)$ i :$ka\equiv kb(\mathrm{mod}m)$

• Si a més k és coprimer amb m, llavors podem trobar un enter $k^{-1}$, tal que

$k{k}^{-1}\equiv 1(\mathrm{mod}m)$

i llavors té perfecte sentit parlar de la divisió i també és cert que

$\frac{a}{k}\equiv \frac{b}{k}(\mathrm{mod}m)$

on per definició posem $a/k=a{k}^{-1}$.

• Com a conseqüència de l'anterior, si tenim dos congruències amb igual mòdul:

$a\equiv b(\mathrm{mod}m)$ i $c\equiv d(\mathrm{mod}m)$

podem sumar-les, restar-les o multiplicar-les de manera que també es verifiquen les congruències

$a+c\equiv b+d(\mathrm{mod}m)$ i $ac\equiv bd(\mathrm{mod}m)$

Aquestes propietats permeten definir l'aritmètica modular.

Àlgebra lineal

Dues matrius reals A i B es diu que són congruents si existeix una matriu invertible real P tal que

$P^{\mathrm{\top }}AP=B.$

Al definir la relació de congruència d'aquesta manera resulta que dues matrius són congruents si i només si representen la mateixa forma bilineal respecte de diferents bases. Aquesta relació és una relació d'equivalència.

Àlgebra universal

En àlgebra universal la idea es generalitza: Una relació de congruència sobre una àlgebra A és un subconjunt del producte directe A × A que és al mateix temps una relació d'equivalència en A i una subàlgebra de A × A.

Vegeu també

• Aritmètica modular
• Congruència sobre els enters