Teorema xinès del residu

De Viquipèdia
Dreceres ràpides: navegació, cerca

El teorema xinès del residu és un resultat d'aritmètica modular que tracta de la resolució de sistemes de congruències. Aquest resultat establert inicialment sobre Z/nZ es generalitza en teoria d'anells. Aquest teorema es fa servir en la teoria de nombres.

Història[modifica | modifica el codi]

La forma original del teorema, continguda en un llibre del matemàtic xinès Qin Jiushao publicat el 1247, és un resultat en relació amb els sistemes de congruències (vegeu aritmètica modular). Però es troba rastre d'un problema anàleg al llibre de Sun Zi, el Sunzi suanjing datant del segle III:

Quants soldats té l'exèrcit de Han Xing si, formats en 3 columnes, queden dos soldats, formats en 5 columnes, queden tres soldats i, formats en 7 columnes, queden dos soldats?

Es pot pensar que els Xinesos, a base de fer càlculs astronòmics poguessin estar interessats en concordances de calendari i que hagin arribat a interessar-se per preguntes del tipus:

A quants dies del solstici d'hivern caurà la lluna plena?

Si la qüestió es fa mentre que queden 6 dies abans del solstici d'hivern i 3 dies abans de la lluna plena, la pregunta es tradueix en:

Existeix un enter x tal que el residu de la divisió de x entre 365 dóna 6 i el residu de la divisió de x entre 28 dóna 3?

La resolució proposada per Sun Zi per al problema dels soldats és la següent:

Multiplica el residu de la divisió entre 3, és a dir 2, per 70, afegeix-li el producte del residu de la divisió entre 5, és a dir 3, per 21 després afegeix el producte del residu de la divisió entre 7, és a dir 2 per 15. Mentre el nombre sigui més gran que 105, resta-li 105.

Però la solució no explica més que imperfectament el mètode emprat.

Finalment, seria una llàstima no presentar aquest problema en relació amb pirates i un tresor, exemple citat molt freqüentment per il·lustrar el teorema dels residus xinesos:

Una banda de 17 pirates posseeix un tresor constituït de peces d'or d'igual valor. Projecten de partir-se-les a parts iguales, i de donar-ne la resta al cuiner xinès. Aquest rebria llavors 3 peces. Però els pirates es barallen, i sis d'ells moren. Un nou repartiment donaria al cuiner 4 peces. En un naufragi ulterior, sols se salven, el tresor, sis pirates i el cuiner, i el repartiment donaria llavors 5 peces d'or a aquest últim. Quina és la fortuna mínima que pot esperar el cuiner si decideix enverinar la resta dels pirates?

L'aritmètica modular ha tornat a subministrar eines que fan aquest tipus de problema més fàcil de resoldre.

Sistema de congruències d'enters[modifica | modifica el codi]

Teorema[modifica | modifica el codi]

Siguin , ..., enters primers entre ells dos a dos (és a dir Mcd (ni, nj) = 1 sempre que ij). Llavors per a tots els enters , ..., , existeix un enter x, únic mòdul i tal que

Una solució x es pot trobar com segueix:

Per a cada i, els enters i són primers entre ells, i segons el teorema de Bachet-Bézout, es poden trobar enters i tals que . Si es posa , llavors es té

i

per ji.

Una solució d'aquest sistema de congruències és per tant

De forma més general, totes les solucions x d'aquest sistema són congruents mòdul el producte n


Exemple[modifica | modifica el codi]

El problema dels soldats es redueix a

llavors s'obté

  • i , o per tant
  • i , o per tant
  • i , o per tant

una solució per a x és llavors

i les solucions són tots els enters congruents amb 233 mòdul 105, és a dir a 23 mòdul 105.

Generalització a nombres no primers entre ells[modifica | modifica el codi]

A vegades, els sistemes de congruències poden ser resolts encara que els ni no siguin primers entre ells dos a dos. Existeix una solució x si i només si per a tot i i j. Totes les solucions x són congruents mòdul el mcm dels ni.

Exemple: resoldre el sistema

equival a resoldre el sistema

equival al sistema

  • et , or ja que
  • et , or ja que

Una solució és per tant o qualsevol altre nombre congruent amb 11 mòdul 12

El mètode de les substitucions successives sovint pot donar les solucions dels sistemes de congruències, fins i tot quan els mòduls no són primers entre ells dos a dos.

Interpretació mecànica[modifica | modifica el codi]

La resolució del sistema següent:

d'incògnita x passa pel càlcul del mcm de a i b.

Aquest problema matemàtic és una modelització d'un problema d'engranatges: una roda dentada de a dents engrana amb una cremallera horitzontal. Quantes dents han de passar perquè la seva r-èssima dent coincideixi amb la s-èssima dent d'una altra roda dentada que engrana amb la mateixa cremallera i que té b dents?

El mcm dels dos nombres a i b és el que permet comprendre el comportament periòdic d'aquest sistema: és el nombre de dents que separa dos contactes del mateix parell de dents (són les dents de la cremallera que són congruentsal mateix temps amb les dentes de les dues rodes dentades). Es pot doncs trobar la solució, si n'hi ha una, en l'interval [1,mcm(a,b)]. Hi ha una solució si el mcd(a, b) divideix r - s.

Interpretació gràfica d'un sistema de congruències

Es pot entendre de manera senzilla per què el càlcul sobre rodes dentades fa intervenir aritmètica modular, fixant-se que el conjunt de les dents d'una roda que en té n es pot parametritzar pel conjunt de les arrels n-èssimes de la unitat, que té una estructura de grup isomorf de forma natural amb la de Z/nZ.

Resultat per als anells[modifica | modifica el codi]

Als anells Z/nZ[modifica | modifica el codi]

El teorema xinès té una versió més abstracta: si n1..., nk són dos a dos primers entre ells llavors, notant n el producte de ni, l'aplicació

és un isomorfisme d'anells.

Per demostrar-ho cal fixar-se primer en què els dos conjunts i tenen el mateix nombre d'elements. Com que és un morfisme d'anells, n'hi ha prou amb veure que és injectiu per deduir-ne que és un isomorfisme. Per veure això n'hi ha prou amb mostrar que el nucli es redueix a 0 : si per a , és a dir si és un múltiple de cada , llavors , és a dir és un múltiiple del producte . Això resulta de la hipòtesi de què els són primers dos a dos.


En el cas on els ni no són primers entre ells, n és el seu mcm i el morfisme de més amunt no és que injectiu. Existeix una solució al problema inicial si i només si les dades són a la imatge, és a dir que el mcd de ni i nj divideix per a tota parella i,j.

En un anell principal[modifica | modifica el codi]

Per a un anell principal R, el teorema xinès del residu pren la forma següent: Si u1, ..., uk són els elements de R que són primers entre ells dos a dos, i u designa el producte u1...uk, llavors l'anell R/uR i l'anell producte R/u1R x ... x R/ukR són isomorfs per l'isomorfisme

tal que

L'isomorfisme invers es pot construir així. Per a cada i, els elements ui i u/ui són primers entre ells, i per tant, existeixen elements r i s a R amb

Fixant ei = s u/ui. Es té:

per a ji.

Llavors la inversa és la transformació

tal que

Resultat per als anells generals[modifica | modifica el codi]

Una de les formes més generals del teorema xinès del residu es pot formular en termes d'anell i d'ideal (per l'esquerra o per la dreta). Si R és un anell i I1, ..., Ik ideals de R que són primers entre ells dos a dos (això vol dir que Ii + Ij = R quan ij), llavors l'ideal producte I d'aquests ideals és igual a la seva intersecció, i l'anell quocient R/I és isomorf a l'anell producte R/I1 x R/I2 x ... x R/Ik via l'isomorfisme de en que a li associa .

Exemple dels polinomis[modifica | modifica el codi]

Un cas freqüent que il·lustra el paràgraf precedent es dóna per l'anell dels polinomis. Si x0, x1, ..., xn són n+1 elements de diferents dos a dos, llavors es pot prendre Ui = X - xi. Els polinomis Ui són primers entre ells dos a dos, i el teorema xinès del residu s'aplica. Es prenen per Ei els polinomis d'interpolació de Lagrange, definits per: .

Per a j diferent de i, Ei és divisible entre Uj, de manera que Ei ≡ 0 mòdul Uj. D'altra banda, mòdul Ui, X ≡ xi, de manera que Ei ≡ 1 mòdul Ui.

Dir que un polinomi P és tal que P(xi) = yi per a tot i, és equivalent a dir que P ≡ yi mòdul Ui. Tal polinomi P ve donat per . Cosa que es pot verificar per càlcul directe.

Aplicacions[modifica | modifica el codi]

El teorema xinès del residu es fa servir en particular en l'algoritme RSA en criptografia.

Permet representar grans nombres enters com n-tuples de residus de divisions euclidianes. Sota aquesta forma, operacions com l'addició o la multiplicació es poden fer en paral·lel en temps constant. En canvi, la comparació o la divisió no són trivials.

Enllaços externs[modifica | modifica el codi]