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 n_1, ..., n_k enters primers entre ells dos a dos (és a dir Mcd (ni, nj) = 1 sempre que ij). Llavors per a tots els enters a_1, ..., a_k, existeix un enter x, únic mòdul n=\prod_{i=1}^k n_i i tal que


\begin{matrix}
x \equiv a_1\pmod{n_1}\\ 
\ldots \\ 
x \equiv a_k\pmod{n_k}\\
\end{matrix}

Una solució x es pot trobar com segueix:

Per a cada i, els enters n_i\, i \hat n_i = \frac{n}{n_i} són primers entre ells, i segons el teorema de Bachet-Bézout, es poden trobar enters u_i\, i v_i\, tals que  u_in_i + v_i\hat n_i= 1. Si es posa e_i = v_i\hat n_i, llavors es té

e_i \equiv 1 \pmod{n_i} \,

i

e_i \equiv 0 \pmod{n_j}\, per ji.

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

 x = \sum_{i=1}^k a_i e_i\

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

x \equiv 2 \pmod{3}\,
x \equiv 3 \pmod{5}\,
x \equiv 2 \pmod{7} \,

llavors s'obté

  • n_1 = 3 i \hat n_1 = 35, o 2\hat n_1\equiv 1 \pmod{3} per tant e_1 = 70
  • n_2 = 5 i \hat n_2 = 21, o \hat n_2\equiv 1 \pmod{5} per tant e_2 = 21
  • n_3 = 7 i \hat n_3= 15, o \hat n_3\equiv 1 \pmod{7} per tant e_3 = 15

una solució per a x és llavors x = 2 \times 70 + 3 \times 21 + 2 \times 15 = 233

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 a_i \equiv a_j \pmod {Pgcd(n_i,n_j)}\, per a tot i i j. Totes les solucions x són congruents mòdul el mcm dels ni.

Exemple: resoldre el sistema

x \equiv 3 \pmod{4} \,
x \equiv 5\pmod{6} \,

equival a resoldre el sistema

x \equiv 3 \pmod{4} \,
x \equiv 1 \pmod{2} \,
x \equiv 1 \pmod{2} \,
x \equiv 2\pmod{3} \,

equival al sistema

x \equiv 3 \pmod{4} \,
x \equiv 2\pmod{3}\,
  • n_1 = 4 et \hat n_1 = 3, or 3\hat n_1\equiv 1 \pmod{4} ja que e_1 = 9
  • n_2 = 3 et \hat n_2 = 4, or \hat n_2\equiv 1 \pmod{3} ja que e_2 = 4

Una solució és per tant x = 3 \times 9 + 2 \times 4 = 35 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:


 \left\{\begin{array}{l}
 x\equiv r \pmod a \\
 x\equiv s \pmod b
\end{array}\right.

de 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 congruents al 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ó


\begin{matrix}
\phi:&\mathbb{Z}/n\mathbb{Z} &\longrightarrow& \mathbb{Z}/n_1\mathbb{Z}\times\cdots\times\mathbb{Z}/n_k\mathbb{Z}\\
 &\alpha &\longmapsto& (\alpha[n_1],\dots,\alpha[n_k])
\end{matrix}

és un isomorfisme d'anells.

Per demostrar-ho cal fixar-se primer en què els dos conjunts \mathbb{Z}/n\mathbb{Z} i \mathbb{Z}/n_1\mathbb{Z}\times\cdots\times\mathbb{Z}/n_k\mathbb{Z} tenen el mateix nombre d'elements. Com que \phi\, é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 \alpha=0[n_i] per a i=1, \dots, k, és a dir si \alpha és un múltiple de cada n_i, llavors \alpha=0[n], és a dir \alpha és un múltiiple del producte n_1\dots n_k. Això resulta de la hipòtesi de què els n_i 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 \alpha_i-\alpha_j 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

f : R/uR \rightarrow R/u_1R \times \cdots \times
R/u_k R

tal que

x \;\mathrm{mod}\,uR \rightarrow (x \;\mathrm{mod}\,u_1R) \times \cdots \times
(x \;\mathrm{mod}\,u_kR)

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

r u_i + s u/u_i = 1

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

e_i \equiv 1 \pmod{u_i} \quad\mathrm{et}\quad
e_i \equiv 0 \pmod{u_j}

per a ji.

Llavors la inversa és la transformació

g : R/u_1R \times \cdots \times R/u_kR
\rightarrow R/uR

tal que

(a_1 \;\mathrm{mod}\,u_1R) \times \cdots \times (a_k \;\mathrm{mod}u_kR) \rightarrow
\sum_{i=1..k} a_i e_i \pmod{uR}

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 R/I \, en R/I_1 \times \cdots \times R/I_k que a x \;\mathrm{mod}\,I li associa (x \;\mathrm{mod}\,I_1) \times \cdots \times (x \;\mathrm{mod} I_k).

Exemple dels polinomis[modifica | modifica el codi]

Un cas freqüent que il·lustra el paràgraf precedent es dóna per l'anell \mathbb K[X] dels polinomis. Si x0, x1, ..., xn són n+1 elements de \mathbb K 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: E_i = {(X-x_0)(X-x_1)...(X-x_{i-1})(X-x_{i+1})...(X-x_n) \over(x_i-x_0)(x_i-x_1)...(x_i-x_{i-1})(x_i-x_{i+1})...(x_i-x_n)}.

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 P = \sum_{i=0}^n y_i E_i. 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]