Teorema xinès del residu

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

Distribució dels guerrers de terracota de Xi'an en columnes separades per murs de terra. Una utilitat bàsica del teorema xinès del residu és el de comptar grans exèrcits simplement fent-los formar en grups i mirant els soldats sobrants en cada distribució.

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 dona 6 i el residu de la divisió de x entre 28 dona 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

Teorema

Siguin $n_{1}$, ..., $n_{k}$ enters primers entre ells dos a dos (és a dir Mcd (n_i, n_j) = 1 sempre que i ≠ j). 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_{i}n_{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 j ≠ i.

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

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

A vegades, els sistemes de congruències poden ser resolts encara que els n_i 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 n_i.

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

La resolució del sistema següent:

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

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-èsima dent coincideixi amb la s-èsima 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.

$\left\{{\begin{array}{l}x\equiv 4[15]\\x\equiv 10[12]\end{array}}\right.$ m.c.m.(12,15)=60 . la solució x ∈ [1,60] : x = 34 .

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-èsimes de la unitat, que té una estructura de grup isomorf de manera natural amb la de Z/nZ.

Resultat per als anells

Als anells Z/nZ

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 n_i, 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 que els $n_{i}$ són primers dos a dos.

En el cas on els n_i 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 n_i i n_j divideix $\alpha _{i}-\alpha _{j}$ per a tota parella i,j.

En un anell principal

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

$f:R/uR\rightarrow R/u_{1}R\times \cdots \times R/u_{k}R$

tal que

$x\;\mathrm {mod} \,uR\rightarrow (x\;\mathrm {mod} \,u_{1}R)\times \cdots \times (x\;\mathrm {mod} \,u_{k}R)$

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

$ru_{i}+su/u_{i}=1$

Fixant e_i = s u/u_i. Es té:

$e_{i}\equiv 1{\pmod {u_{i}}}\quad \mathrm {et} \quad e_{i}\equiv 0{\pmod {u_{j}}}$

per a j ≠ i.

Llavors la inversa és la transformació

$g:R/u_{1}R\times \cdots \times R/u_{k}R\rightarrow R/uR$

tal que

$(a_{1}\;\mathrm {mod} \,u_{1}R)\times \cdots \times (a_{k}\;\mathrm {mod} u_{k}R)\rightarrow \sum _{i=1..k}a_{i}e_{i}{\pmod {uR}}$

Resultat per als anells generals

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 I₁, ..., I_k ideals de R que són primers entre ells dos a dos (això vol dir que I_i + I_j = R quan i ≠ j), 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/I₁ x R/I₂ x ... x R/I_k 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

Un cas freqüent que il·lustra el paràgraf precedent es dona per l'anell $\mathbb {K} [X]$ dels polinomis. Si x₀, x₁, ..., x_n són n+1 elements de $\mathbb {K}$ diferents dos a dos, llavors es pot prendre U_i = X - x_i. Els polinomis U_i són primers entre ells dos a dos, i el teorema xinès del residu s'aplica. Es prenen per E_i 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, E_i és divisible entre U_j, de manera que E_i ≡ 0 mòdul U_j. D'altra banda, mòdul U_i, X ≡ x_i, de manera que E_i ≡ 1 mòdul U_i.

Dir que un polinomi P és tal que P(x_i) = y_i per a tot i, és equivalent a dir que P ≡ y_i mòdul U_i. 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

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

• (anglès) Teorema xinés del residu