Teoria elemental de nombres: Euclides, Bézout, congruències i teorema xinès

L'aritmètica modular és el que fa funcionar la criptografia, les sumes de comprovació, els generadors de nombres pseudoaleatoris i mitja informàtica. I tot es construeix sobre dues eines molt concretes: l'algorisme d'Euclides i la identitat de Bézout. Si les domines, la resta del tema són conseqüències.

Euclides i Bézout

Per a dos enters no tots dos nuls, el màxim comú divisor és el més gran dels divisors comuns positius. L'algorisme d'Euclides es basa en una observació elemental: de la divisió $a = bq + r$ se'n dedueix que qualsevol divisor comú d'$a$ i $b$ ho és de $b$ i $r$, i a l'inrevés. Per tant

$$\gcd(a,b) = \gcd(b,r),$$

i repetint el procés els residus decreixen estrictament, de manera que s'acaba arribant a zero. L'últim residu no nul és el màxim comú divisor.

La conseqüència pràctica és que l'equació diofàntica $ax + by = c$ té solució entera si i només si el màxim comú divisor divideix $c$. I si $(x_0, y_0)$ n'és una, totes les altres són

$$x = x_0 + \frac{b}{d}t, \qquad y = y_0 - \frac{a}{d}t, \qquad t\in\mathbb{Z},$$

amb $d$ el màxim comú divisor. Els denominadors són importants: sense dividir per $d$, els salts són massa grans i et deixes solucions.

Congruències

Escriure que $a$ i $b$ són congruents mòdul $m$ vol dir que $m$ divideix la seva diferència. Les congruències es poden sumar i multiplicar lliurement, cosa que les fa molt còmodes.

L'invers d'$a$ mòdul $m$ existeix si i només si $a$ i $m$ són coprimers, i la prova és Bézout: si $au + mv = 1$, aleshores $au\equiv 1$ mòdul $m$, o sigui que $u$ és l'invers. El recíproc també surt: un invers dona exactament aquesta identitat.

De manera més general, $ax\equiv b \pmod m$ té solució si i només si $d = \gcd(a,m)$ divideix $b$, i llavors hi ha exactament $d$ classes de solucions mòdul $m$.

Teorema xinès dels residus

Si els mòduls són coprimers dos a dos, el sistema de congruències $x\equiv a_i \pmod{m_i}$ té una única solució mòdul el producte $M$ de tots ells. Una fórmula explícita és

$$x = \sum_i a_i\,M_i\,u_i, \qquad M_i = \frac{M}{m_i}, \qquad u_i M_i \equiv 1 \pmod {m_i}.$$

La idea és que cada sumand val el que ha de valer en el seu mòdul i s'anul·la en tots els altres, perquè conté els seus factors. La unicitat surt de veure que la diferència de dues solucions és divisible per tots els mòduls i, per ser coprimers, pel producte.

A la pràctica, amb pocs mòduls, és més ràpid el mètode de substitució successiva que la fórmula.

Una observació pràctica sobre l'ordre de les operacions: en aritmètica modular convé reduir en cada pas en comptes de calcular el número sencer i reduir al final. Multiplicar dos residus petits i reduir dona el mateix resultat que multiplicar els números originals, i evita treballar amb xifres enormes. Aquesta propietat és la que fa que l'aritmètica modular sigui computacionalment barata, i és la base de tot el que ve a continuació.

Fermat, Euler i exponenciació

El petit teorema de Fermat diu que si $p$ és primer i no divideix $a$, aleshores $a^{p-1}\equiv 1 \pmod p$. Euler el generalitza: si $a$ i $m$ són coprimers,

$$a^{\varphi(m)}\equiv 1 \pmod m,$$

on $\varphi$ compta els enters de $1$ a $m$ coprimers amb $m$. Tots dos es demostren igual: multiplicar per una unitat permuta el conjunt de les classes invertibles, i comparant el producte de totes elles abans i després surt el resultat.

L'exponenciació binària calcula potències modulars amb un nombre logarítmic de multiplicacions: escrius l'exponent en binari i vas elevant al quadrat i multiplicant. Combinat amb Euler per reduir l'exponent, permet calcular potències astronòmiques a mà o amb molt poc càlcul.

Exercici resolt: sistema de dues congruències

Resol el sistema $x\equiv 2\pmod 3$ i $x\equiv 3\pmod 5$.

Comprovació prèvia: $3$ i $5$ són coprimers, o sigui que hi ha solució única mòdul $15$.

Mètode de substitució. De la primera, $x = 2 + 3k$ per a algun enter $k$. Substituint a la segona:

$$2 + 3k \equiv 3 \pmod 5 \quad\Longrightarrow\quad 3k\equiv 1 \pmod 5.$$

L'invers de $3$ mòdul $5$ és $2$, perquè $3\cdot 2 = 6\equiv 1$. Multiplicant, $k\equiv 2\pmod 5$, o sigui $k = 2 + 5t$.

Desfent: $x = 2 + 3(2+5t) = 8 + 15t$, és a dir

$$x \equiv 8 \pmod{15}.$$

Verificació: $8 = 2\cdot 3 + 2$, o sigui $8\equiv 2\pmod 3$; i $8 = 5 + 3$, o sigui $8\equiv 3\pmod 5$. Les dues condicions es compleixen.

Exercici resolt: equació diofàntica

Troba totes les solucions enteres de $6x + 15y = 9$.

Pas 1 — hi ha solució? $\gcd(6,15) = 3$, i $3$ divideix $9$. Sí que n'hi ha.

Pas 2 — simplificar. Dividint tot per $3$: $2x + 5y = 3$.

Pas 3 — una solució particular. A ull, $x = -1$ i $y = 1$ funciona: $-2 + 5 = 3$.

Pas 4 — la família completa. Amb l'equació ja simplificada, els coeficients són coprimers i els salts són directament els coeficients creuats:

$$x = -1 + 5t, \qquad y = 1 - 2t, \qquad t\in\mathbb{Z}.$$

Verificació amb $t = 1$: $x = 4$, $y = -1$, i $6\cdot 4 + 15\cdot(-1) = 24 - 15 = 9$. Correcte.

L'error a evitar: si haguessis aplicat els salts amb els coeficients originals ($x = -1 + 15t$) t'hauries deixat dues de cada tres solucions. Simplificar primer pel màxim comú divisor evita aquest problema.