Reciprocitat quadràtica

La reciprocitat quadràtica és el primer teorema «profund» que troba qui estudia teoria de nombres: l'enunciat es llegeix en trenta segons, però ningú entén d'entrada per què hauria de ser cert. Anem a poc a poc: per què la pregunta és natural, què diu exactament la llei, per què Gauss hi va tornar vuit vegades, i què construeixes quan cliques les caselles de l'element interactiu.

1. Quins números tenen arrel quadrada?

En els nombres reals, la pregunta «té arrel quadrada?» és avorrida: sí per als positius, no per als negatius, i s'ha acabat. Però quan treballem mòdul un primer p —és a dir, en el món on només compten els residus de dividir per p— la pregunta es torna genuïnament difícil.

Fem-ho amb p = 7. Els números amb què treballem són {1, 2, 3, 4, 5, 6}. Quins són quadrats d'algú? Provem-ho tot: 1²=1, 2²=4, 3²=9≡2, 4²=16≡2, 5²=25≡4, 6²=36≡1. Els resultats són {1, 2, 4}. Els altres —{3, 5, 6}— no són el quadrat de ningú mòdul 7.

Això ja diu una cosa curiosa. Mòdul 7, el número 2 sí que té arrel quadrada (és 3, o també 4), tot i que √2 no és un enter al món normal. I en canvi el 3 tampoc no ho és aquí. No hi ha manera òbvia de saber quin cas és quin sense calcular-ho. Els que sí que ho són s'anomenen residus quadràtics de p.

2. El símbol de Legendre

Escriure «a és residu quadràtic mòdul p» cada vegada és pesat, així que Legendre va introduir una notació que sembla una fracció però no ho és:

$\left(\frac{a}{p}\right)=+1$ si a és residu quadràtic,   $\left(\frac{a}{p}\right)=-1$ si no ho és.

La gràcia d'escollir +1 i −1 (i no «sí» i «no») és que aquests valors es multipliquen bé: resulta que (a/p)·(b/p) = (ab/p). En paraules: el producte de dos residus quadràtics és un residu quadràtic; el producte de dos no-residus també ho és; i el producte d'un de cada dona un no-residu. És exactament l'aritmètica dels signes. Això converteix el símbol de Legendre en una eina de càlcul, no només en una etiqueta.

Hi ha una fórmula que ho lliga amb l'exponenciació, el criteri d'Euler: (a/p) ≡ a^((p−1)/2) (mod p). Comprovem-ho amb p = 7 i a = 2: 2³ = 8 ≡ 1 (mod 7), i efectivament el 2 era residu quadràtic. Amb a = 3: 3³ = 27 ≡ 6 ≡ −1 (mod 7), i efectivament el 3 no ho era. Aquesta fórmula és la que fa que tot plegat sigui calculable de pressa, cosa que serà important quan parlem de criptografia.

3. La llei

Ara ve el salt. Tenim dos primers senars diferents, p i q, i ens fem dues preguntes que semblen no tenir res a veure:

Pregunta A: és q un residu quadràtic mòdul p?  →  (q/p)
Pregunta B: és p un residu quadràtic mòdul q?  →  (p/q)

Pensa-hi un moment. La pregunta A viu íntegrament dins l'aritmètica mòdul p: hi intervenen els números 1..p−1 i les seves potències. La pregunta B viu dins un món completament diferent, l'aritmètica mòdul q. Són dos universos separats, amb elements diferents i operacions diferents. No hi ha cap raó evident perquè la resposta d'un tingui res a veure amb la de l'altre.

I tanmateix:

Per què l'exponent es tradueix en una regla tan simple? Perquè (p−1)/2 és senar exactament quan p ≡ 3 (mod 4). Així que el producte dels dos exponents és senar —i per tant (−1) elevat a això dona −1— només quan tots dos ho són. En qualsevol altre cas l'exponent és parell i el resultat és +1, o sigui que els dos símbols tenen el mateix signe.

El que fa que això sigui profund no és la fórmula, és que existeixi cap relació. És com descobrir que saber si plou a Barcelona et diu, amb certesa i sense excepcions, si plou a Tòquio. La informació hauria de ser independent, i no ho és.

4. Les dues lleis complementàries

La llei principal parla de dos primers senars. Falten dos casos especials, que es demostren a part i que completen l'eina de càlcul:

Per a −1: (−1/p) = +1 exactament quan p ≡ 1 (mod 4). O sigui, −1 té arrel quadrada mòdul p si i només si p és de la forma 4k+1. Mòdul 5, per exemple, −1 ≡ 4 = 2². Mòdul 7, en canvi, −1 ≡ 6 no és quadrat de ningú (ja ho hem vist a la llista de dalt).

Per a 2: (2/p) = +1 exactament quan p ≡ ±1 (mod 8). Els primers per als quals 2 té arrel quadrada són 7, 17, 23, 31, 41, 47… i, mirats mòdul 8, són tots ±1.

5. Gauss i les vuit demostracions

Euler ja havia observat el patró experimentalment, i Legendre en va publicar un enunciat el 1785, però la seva demostració tenia un forat: donava per bo un fet que ell mateix no havia demostrat. Gauss hi va arribar el 1796, amb 19 anys, i en va donar la primera demostració completa, publicada dins les Disquisitiones Arithmeticae el 1801. En deia el seu theorema aureum, el teorema auri.

El fet que hauria de fer-nos pensar és que Gauss no s'hi va aturar. Al llarg de la seva vida en va publicar vuit demostracions diferents, cadascuna per un camí distint. Avui se'n coneixen més de dues-centes. Un teorema no rep aquest tracte perquè sigui difícil; el rep perquè els matemàtics intueixen que encara no l'entenen del tot i cada demostració nova n'ensenya una cara diferent. Aquesta intuïció era correcta, com es veurà al punt 9.

6. Què fem a l'element interactiu

La càpsula no et demana que apliquis la fórmula: et demana que construeixis les dades des de zero i comprovis la llei tu mateix. És l'ordre invers a com s'explica normalment, i és deliberat.

Quan cliques els botons k=1, k=2, … del bloc A, cada clic calcula k² mod p en directe i n'il·lumina el resultat a la tira de números de sota. Al principi la tira està apagada; a mesura que cliques, s'hi van encenent posicions. El que estàs fent, literalment, és omplir la columna de quadrats de la taula de multiplicar mòdul p. Quan hagis clicat fins a (p−1)/2, la tira ja no canviarà més —i aquí es veu, de manera tangible i no com una afirmació d'un llibre, que només la meitat dels números hi surten.

En aquell moment la tira es torna a acolorir sencera: verd per als que hi són (+1) i vermell per als que no (−1). Això és el símbol de Legendre de tots els números alhora, d'un cop d'ull. Fes el mateix al bloc B amb un altre primer q, i el panell de comparació desglossa els quatre ingredients: p mod 4, q mod 4, si p era residu de q, si q era residu de p, i si les dues respostes han coincidit.

El mode Repte inverteix la feina: primer has de predir si coincidiran, i només després es comprova. Hi ha dos tipus de ronda: una on construeixes les taules (i pots verificar-ho comptant) i una de ràpida on no hi ha taules i l'única eina disponible és la regla del mod 4. La segona és la que t'obliga a fer servir la llei de veritat en lloc de comptar.

7. Aplicacions pràctiques

Càlcul ràpid de símbols de Legendre. La llei és, sobretot, un algorisme. Per saber si 219 és residu quadràtic mòdul 383 no cal provar 191 números: s'aplica la reciprocitat per anar girant i reduint els símbols, igual que l'algorisme d'Euclides va reduint una fracció, fins a arribar a casos trivials. Es fa en microsegons.

Test de primalitat de Solovay–Strassen. Combina el criteri d'Euler amb la reciprocitat: si p és primer, a^((p−1)/2) ha de coincidir amb el símbol de Jacobi (a/p) per a tot a. Si per a algun a no coincideix, p segur que és compost. Va ser un dels primers tests probabilístics pràctics i va ajudar a fer viable la criptografia de clau pública.

Criptografia. El criptosistema de Goldwasser–Micali, el primer amb seguretat semàntica demostrable, xifra bits amagant-los com a residus quadràtics: un 0 és un residu, un 1 és un no-residu amb símbol de Jacobi +1. La seva seguretat es basa en el fet que distingir-los sense conèixer la factorització del mòdul es creu computacionalment difícil.

Arrels quadrades mòdul p. Saber que una arrel existeix i trobar-la són coses diferents. L'algorisme de Tonelli–Shanks la troba, però abans cal saber que n'hi ha: el símbol de Legendre és el filtre previ. Això s'usa constantment en criptografia de corbes el·líptiques, on cal recuperar la coordenada y d'un punt a partir de la x.

8. Curiositats

El teorema més demostrat de la història. Se'n coneixen més de 240 demostracions publicades, per camins que van de la combinatòria elemental a la teoria de funcions el·líptiques. Cap altre teorema s'hi acosta. El catàleg que en manté Franz Lemmermeyer és, en si mateix, un mapa de bona part de la teoria de nombres.

Gauss va tenir un bon mes. Al seu diari matemàtic hi va anotar la demostració el 8 d'abril de 1796. Feia menys d'un mes que havia descobert com construir el polígon regular de 17 costats amb regle i compàs, un problema obert des dels grecs. Tenia 19 anys.

La demostració de comptar punts. Una de les més boniques (Eisenstein) consisteix a comptar punts de coordenades enteres dins d'un rectangle dividit per una diagonal. Els dos costats del compte donen els dos símbols de Legendre, i el rectangle sencer dona l'exponent (p−1)/2 · (q−1)/2. Tot el teorema es redueix a comptar els punts d'una graella de dues maneres diferents.

Els residus no es reparteixen tan uniformement com sembla. Encara que hi ha exactament tants residus com no-residus, la seva distribució dins l'interval no és equilibrada: hi ha un biaix mesurable a favor dels residus a la primera meitat, per a primers p ≡ 3 (mod 4). El fenomen es coneix com a biaix de Txebixev i encara té preguntes obertes associades.

El nom «reciprocitat» és literal. La paraula no és decorativa: expressa que la relació entre p i q es pot llegir en totes dues direccions, i que conèixer-ne una banda determina l'altra. És la mateixa idea que després batejarà famílies senceres de teoremes —reciprocitat cúbica, biquadràtica, d'Artin— tots descendents d'aquest.

9. Connexió amb altres àrees

Aquí és on la història es fa gran. Gauss intuïa que la reciprocitat quadràtica no era un fet aïllat sinó el primer cas visible d'un patró molt més ample, i va dedicar anys a buscar-ne les versions cúbica i biquadràtica. Les va trobar, i per fer-ho va haver d'inventar-se un món nou: els enters de Gauss, números de la forma a+bi — un altre motiu per passar-se per la càpsula del Pla d'Argand.

Tenia raó. Al llarg del segle XX es va desenvolupar la teoria de cossos de classes i, amb ella, la llei de reciprocitat d'Artin, que engloba la quadràtica com un cas particular gairebé trivial. Encara més enllà hi ha el programa de Langlands, una xarxa de conjectures que relaciona teoria de nombres i anàlisi harmònica, i que sovint es descriu, sense gaire exageració, com «una gran generalització de la reciprocitat quadràtica». Bona part de la matemàtica dels últims cent anys —incloent-hi les eines amb què Andrew Wiles va demostrar l'últim teorema de Fermat el 1994— viu en aquesta línia de descendència.

Dit d'una altra manera: el que comproves clicant caselles en aquesta càpsula és l'exemple més petit i més accessible d'un dels fils conductors més importants de tota la matemàtica moderna.