Rellotges que encaixen

Hi ha teoremes que es recorden per la seva dificultat i altres per la seva utilitat. El teorema xinès del residu es recorda per una tercera cosa: perquè converteix una pregunta que sembla d'endevinalla —«quin número deixa aquestes restes?»— en una descripció completa de com està feta l'aritmètica modular. Va néixer com un truc per comptar soldats i ha acabat sent la peça que fa que el teu navegador desxifri connexions quatre vegades més ràpid. Aquesta càpsula recorre el camí sencer: l'enigma, la demostració, el càlcul a mà, i el moment en què tot deixa de funcionar.

1. Un problema del segle IV

Al Sun Zi Suan Jing («Manual d'aritmètica de Sun Zi»), un text xinès escrit en algun moment entre els segles III i V, hi apareix aquest enunciat:

El que fa interessant l'enigma no és trobar el 23 —amb paciència, provant números, hi arribes—, sinó adonar-se que la pregunta té sempre resposta. Canvia les restes per les que vulguis: 1, 4 i 6; o 0, 0 i 1; o qualsevol de les 105 combinacions possibles. Sempre hi ha un número que les compleix, i sempre n'hi ha exactament un per sota de 105. Això no és evident en absolut, i és exactament el que afirma el teorema.

Sun Zi dona la resposta però no el mètode general. Aquest arriba set segles després, el 1247, amb Qin Jiushao i el seu Shushu Jiuzhang, que descriu un algorisme complet (el Da-yan shu, «mètode de la gran extensió») vàlid per a qualsevol nombre de mòduls. A Europa el resultat no es formula amb generalitat fins a Euler i, sobretot, fins a les Disquisitiones Arithmeticae de Gauss el 1801: 554 anys després de Qin.

2. Congruències: oblidar-ho tot menys la posició

La notació que fem servir avui és de Gauss, i és una de les grans invencions notacionals de la matemàtica. Escrivim

$$n\equiv a\left(\mathrm{mod}m\right)$$

per dir que n i a deixen la mateixa resta en dividir-los per m; equivalentment, que m divideix n − a. La força de la notació és que les congruències es comporten com igualtats: es poden sumar, restar i multiplicar terme a terme. Si n ≡ a i n′ ≡ a′ (mod m), aleshores n + n′ ≡ a + a′ i n·n′ ≡ a·a′.

El que no es pot fer alegrement és dividir, i aquesta excepció serà la clau de tot el que ve després.

3. L'enunciat, amb les dues meitats separades

Siguin m₁, m₂, …, m_k enters positius coprimers dos a dos (és a dir, mcd(m_i, m_j) = 1 sempre que i ≠ j), i sigui M = m₁·m₂·⋯·m_k. Aleshores, per a qualsevol elecció de restes a₁, …, a_k, el sistema

$$n\equiv a_1\left(\mathrm{mod}{m}_1\right),\dots ,n\equiv a_k\left(\mathrm{mod}{m}_k\right)$$

té solució, i la solució és única mòdul M.

Convé llegir amb cura què vol dir cada meitat, perquè totes dues diuen coses fortes. Existència vol dir que les condicions mai es contradiuen: siguin quines siguin les restes que demanis, hi ha un número que les satisfà totes alhora. Unicitat mòdul M vol dir que la solució no és una sola —n'hi ha infinites, separades exactament per M— sinó que dins de qualsevol finestra de M enters consecutius n'hi ha una i només una.

4. La demostració que no calcula res

Hi ha una demostració constructiva (la del punt 5, que és la que faràs servir per calcular) i n'hi ha una altra que no construeix res i que és, amb diferència, la més il·luminadora. Considera l'aplicació que envia cada número a la llista de les seves restes:

$$\Phi :\mathbb{Z}/M⟶\mathbb{Z}/m_1\times \cdots \times \mathbb{Z}/m_k$$

Primer: Φ és injectiva. Si dos números n i n′ tenen totes les restes iguals, aleshores cada m_i divideix la diferència n − n′. Com que els m_i són coprimers dos a dos, el seu producte M també divideix la diferència, i per tant n ≡ n′ (mod M): eren el mateix número. Aquest pas és l'únic lloc de tota la demostració on s'utilitza la coprimalitat, i és bo saber-ho, perquè és exactament el pas que fallarà al punt 8.

Segon: els dos conjunts tenen la mateixa mida. L'esquerra té M elements. La dreta té m₁·m₂·⋯·m_k = M combinacions possibles de restes.

I aquí acaba tot: una aplicació injectiva entre dos conjunts finits de la mateixa mida és forçosament exhaustiva. Per tant tota combinació de restes s'assoleix, i s'assoleix un sol cop. Existència i unicitat surten alhora, del pur comptatge, sense escriure ni una fórmula.

5. Com es calcula: substitució successiva

El mètode escrit és el mateix que faries servir per resoldre un sistema d'equacions lineals: aïllar una incògnita i substituir-la a la següent. Resolem el problema de Sun Zi.

Observa l'estructura: cada pas fusiona dues congruències en una de sola amb el mòdul multiplicat. Comences amb mòdul 3, passes a mòdul 15, acabes amb mòdul 105. Amb k condicions calen k−1 fusions, i el mòdul final és el producte de tots.

6. L'invers modular i l'algorisme d'Euclides estès

L'únic pas del càlcul que no és trivial és trobar l'invers: donat b i m coprimers, quin número b⁻¹ compleix b·b⁻¹ ≡ 1 (mod m)? Amb números petits es troba temptejant, però el mètode general és l'algorisme d'Euclides estès, i és el que mostra la vista «El càlcul».

La idea: l'algorisme d'Euclides ordinari calcula mcd(b, m) fent divisions successives. L'estès, a més, va arrossegant l'expressió de cada resta com a combinació de b i m. Quan arriba al mcd —que val 1 si són coprimers— tens una identitat x·b + y·m = 1. Llegint-la mòdul m, el terme y·m desapareix i queda x·b ≡ 1: aquest x és l'invers.

Que la identitat x·b + y·m = 1 existeixi exactament quan b i m són coprimers és el lema de Bézout, i és una altra manera de dir el mateix que ja hem vist: la coprimalitat és el permís per dividir.

7. Què fem a l'element interactiu

El mecanisme de la càpsula converteix el sistema de congruències en un objecte físic. Cada mòdul és una roda dentada amb tantes caselles com el seu mòdul: 3, 5 i 7. Hi ha un punter fix a dalt, i les rodes giren per sota. La casella que queda sota el punter és la resta actual d'aquell mòdul.

Quan augmentes n en una unitat, totes les rodes avancen una casella alhora —perquè la resta de tots els mòduls creix alhora—, però cadascuna torna al principi a un ritme diferent: la de 3 dona la volta tres cops més sovint que la de 9. Aquesta diferència de ritmes és tota la matèria del teorema.

Els objectius són les restes que busques, marcades amb un anell a la casella corresponent. Quan la marca d'una roda passa per sota del punter, aquella roda s'il·lumina en verd: aquella condició es compleix. El repte és trobar el moment en què totes hi coincideixen; aleshores el mecanisme es bloqueja amb un cadenat.

La segona vista, «El calendari», és la mateixa informació desplegada en línia recta: una fila per condició, amb marques a tots els n que la compleixen. Cada fila és un patró periòdic amb el seu propi ritme, i la fila de baix mostra les coincidències. Amb mòduls coprimers hi ha exactament una marca per període, i veure-la sola enmig de 105 columnes és la manera més directa d'entendre la unicitat.

La tercera, «El càlcul», mostra el mateix problema resolt a mà, amb totes les substitucions i els inversos calculats amb Euclides estès. Els números es corresponen exactament amb el que hi ha a les rodes.

8. Resolució del problema de Sun Zi amb l'element interactiu

El pas 5 és el que val la pena interioritzar, perquè és el mètode de substitució successiva descobert amb les mans: en comptes de provar els 105 números, en fusiones dos condicions i només mires un de cada 15. Amb mòduls més grans, la diferència entre les dues estratègies deixa de ser una comoditat i passa a ser la diferència entre possible i impossible.

9. Quan falla: mòduls no coprimers

Tot el que hem dit depèn d'una hipòtesi, i el joc de mòduls 4 · 6 serveix per veure què passa quan no es compleix. Com que mcd(4, 6) = 2, hi ha una restricció amagada: 4 i 6 són tots dos parells, de manera que la paritat de n queda determinada dues vegades, i les dues determinacions es poden contradir.

Concretament: si n ≡ a (mod 4), aleshores n té la mateixa paritat que a. Si també n ≡ b (mod 6), n té la mateixa paritat que b. Per tant a i b han de tenir la mateixa paritat, o no hi ha cap número possible.

Es pot comptar exactament el que s'ha perdut. Amb mòduls 4 i 6 hi ha 24 combinacions imaginables de restes, però només 12 són assolibles: exactament la meitat, les que tenen les dues restes de la mateixa paritat. L'aplicació Φ del punt 4 ha deixat de ser exhaustiva, i el motiu és que ha deixat de ser injectiva primer: ara hi ha números diferents amb les mateixes restes.

La condició general és aquesta: un sistema amb mòduls qualssevol té solució si i només si, per a cada parella, mcd(m_i, m_j) divideix a_i − a_j. Si es compleix, la solució és única mòdul mcm(m₁,…,m_k) en lloc del producte. La versió coprimera és el cas particular en què tots els mcd valen 1, la condició és automàtica i el mcm coincideix amb el producte.

10. La conseqüència estructural

Fins ara hem tractat el teorema com una eina de càlcul. La seva formulació moderna diu alguna cosa més ambiciosa: hi ha un isomorfisme d'anells

$$\mathbb{Z}/M\mathbb{Z}\cong \mathbb{Z}/m_1\mathbb{Z}\times \cdots \times \mathbb{Z}/m_k\mathbb{Z}$$

«Isomorfisme» vol dir que no és només que les mides coincideixin: la correspondència respecta les operacions. Sumar mòdul 105 és el mateix que sumar les tres restes per separat; multiplicar, igual. Les dues aritmètiques no s'assemblen, són la mateixa cosa escrita de dues maneres.

D'aquí surt, gairebé de franc, un resultat que d'altra manera costaria demostrar: la funció φ d'Euler és multiplicativa. Els elements invertibles d'un producte són els que són invertibles a cada component, així que φ(105) = φ(3)·φ(5)·φ(7) = 2·4·6 = 48. Aquesta multiplicativitat és el que permet calcular φ(n) a partir de la factorització de n, i és el que fa possible RSA.

11. Aparicions fora de les matemàtiques

Criptografia RSA. Desxifrar amb RSA vol dir calcular una potència modular enorme mòdul n = p·q. Amb el teorema, es fa dues vegades —una mòdul p, una mòdul q, amb exponents de la meitat de bits— i es recompon. Com que el cost d'una exponenciació modular creix aproximadament amb el cub de la longitud, dues operacions de mida meitat costen 2·(1/8) = 1/4 del total: una acceleració d'unes 4 vegades. Pràcticament totes les implementacions reals ho fan així.

Correcció d'errors. Els codis Reed–Solomon, presents als codis QR, als DVD i als sistemes RAID, reconstrueixen la informació original a partir de fragments redundants amb una versió polinòmica exacta d'aquest mateix argument: en comptes de restes mòdul enters, restes mòdul polinomis.

Repartiment de secrets. Els esquemes de Mignotte i d'Asmuth–Bloom trossegen una clau en k fragments —cadascun una resta mòdul un enter diferent— de manera que amb prou fragments es reconstrueix el secret i amb menys no se'n pot deduir res.

Calendaris. El 1583 Joseph Scaliger va definir el període julià combinant tres cicles: el cicle metònic de 19 anys, el cicle solar de 28 anys i la indicció romana de 15 anys. Com que són coprimers dos a dos, cada combinació de posicions dins dels tres cicles es dona un sol cop, i el període complet dura 19·28·15 = 7.980 anys. És el teorema xinès del residu convertit en cronologia.

Informàtica. L'aritmètica de residus permet operar amb enters gegants en paral·lel, sense arrossegament entre components. I les taules de hash de mida coprimera amb la longitud del pas eviten col·lisions periòdiques pel mateix motiu que les rodes coprimeres recorren totes les combinacions.

12. Curiositats

El general que comptava soldats. La tradició xinesa associa aquest mètode al general Han Xin (segle II aC): per saber quants homes li quedaven després d'una batalla els feia formar en files de 3, després de 5, després de 7, i només mirava quants en sobraven. Tres números petits en lloc d'un recompte llarg. La llegenda és probablement posterior als fets, però il·lustra perfectament la idea: si saps que l'exèrcit té menys de 105 homes, tres restes el determinen del tot.

Un atac que aprofita el teorema per trencar RSA. El 1997, Boneh, DeMillo i Lipton van descobrir que si un xip que desxifra amb RSA-CRT comet un sol error en una de les dues meitats del càlcul, comparant la signatura errònia amb la correcta es recupera la factorització de n amb un simple màxim comú divisor. L'optimització que fa RSA quatre vegades més ràpid és també la seva vulnerabilitat més coneguda, i per això les implementacions serioses verifiquen el resultat abans de retornar-lo.

Gödel el va fer servir per demostrar la incompletesa. Per codificar l'aritmètica dins d'ella mateixa, Gödel necessitava representar seqüències finites d'enters com un únic número. La seva funció β ho aconsegueix precisament amb aquest teorema: donada qualsevol seqüència, es poden triar mòduls coprimers i un número que deixi les restes desitjades. Un truc de comptar soldats, al cor d'un dels teoremes més importants del segle XX.

Les cigales. Diverses espècies de cigales nord-americanes emergeixen en cicles de 13 o 17 anys, tots dos primers. Dos cicles primers grans coincideixen molt rarament —13 i 17 només s'alineen cada 221 anys— i la hipòtesi més acceptada és que la coprimalitat amb els cicles dels depredadors és, precisament, el que els dona avantatge.

El nom. És un dels pocs teoremes que porta el nom d'una civilització i no d'una persona. Qin Jiushao mereixeria la seva part: el seu algorisme de 1247 era complet i general, i va quedar sense reconeixement a Occident fins que Alexander Wylie el va donar a conèixer el 1852, sis segles més tard.

13. Connexió amb altres àrees

Dins del bloc, aquesta càpsula és la baula entre les altres. El sedàs i el ritme dels primers et dona els mòduls: els primers són els mòduls coprimers per excel·lència, i tota descomposició en factors primers és una descomposició CRT esperant a passar. Reciprocitat quadràtica treballa amb residus mòdul un primer, i el teorema és el que permet passar de mòduls primers a mòduls compostos: per saber si alguna cosa és quadrat mòdul 105, n'hi ha prou de saber-ho mòdul 3, 5 i 7.

Cap a l'àlgebra, l'isomorfisme del punt 10 és un cas particular de la descomposició de grups abelians finits en producte de components primàries, que és el mateix teorema d'estructura que hi ha darrere de les Taules de Cayley: quan hi veus que Z/6 i Z/2 × Z/3 tenen la mateixa taula, estàs veient el teorema xinès del residu en format graella.

I cap a l'anàlisi, la idea de reconstruir un objecte a partir de les seves «projeccions» sobre components independents és exactament la que hi ha a Sèries de Fourier: allà les components són freqüències en lloc de mòduls, però el patró de pensament —descompondre en peces que no interfereixen, treballar-hi per separat, recompondre— és el mateix. No és casualitat que l'anàlisi harmònica sobre grups finits comenci, literalment, per aquest teorema.