Teorema cinese del resto
In matematica, il termine teorema cinese del resto comprende diversi risultati in algebra astratta e teoria dei numeri.
Congruenza simultanea di interi
[modifica | modifica wikitesto]La formulazione originale del teorema, contenuta in un libro scritto nel III secolo dal matematico cinese Sun Tsu e successivamente ripubblicata in un libro del 1247 scritto da Qin Jiushao[1], è una affermazione riguardante le congruenze simultanee (si veda la voce aritmetica modulare). Si supponga che n1, ..., nk siano interi a due a due coprimi (il che significa che MCD(ni , nj ) = 1 quando i ≠ j). Allora, comunque si scelgano degli interi a1, ..., ak, esiste un intero x soluzione del sistema di congruenze
Inoltre, tutte le soluzioni x di questo sistema sono congruenti modulo il prodotto n = n1...nk.
Si può trovare una soluzione x come segue. Per ogni i gli interi ni e n/ni sono coprimi, e utilizzando l'algoritmo di Euclide esteso si possono trovare due interi r e s tali che r ni + s n/ni = 1. Ponendo ei = s n/ni, si ottiene
Una soluzione del sistema di congruenze è quindi:
Trovare le soluzioni
[modifica | modifica wikitesto]Si definisca il seguente sistema (con ):
Sia
Siano poi le soluzioni alle congruenze ; la soluzione sarà data da:
Nel caso in cui si sarebbe potuto scomporre il sistema di congruenze in un sistema più grande rendendo ogni primo.[2] Ad esempio:
sarebbe diventato
ovvero
Enunciato per domini ad ideali principali
[modifica | modifica wikitesto]Per un dominio ad ideali principali R il teorema cinese del resto assume la forma seguente: se u1, ..., uk sono elementi di R che sono a due a due coprimi, e u denota il prodotto u1...uk, allora l'anello quoziente R/uR e il prodotto di anelli R/u1R x ... x R/ukR sono isomorfi mediante l'omomorfismo di anelli
tale che
L'isomorfismo inverso può essere costruito come segue. Per ogni i, gli elementi ui e u/ui sono coprimi, e per questo esistono due elementi r e s in R tali che
Sia ei = s u/ui. Allora l'inverso di f è la mappa
tale che
Si noti che questa formulazione è una generalizzazione del teorema precedente riguardante le congruenze di interi: l'anello Z degli interi è un dominio ad ideali principali, la suriettività della mappa f mostra che ogni sistema di congruenze nella forma
può essere risolto per trovare la x, e la iniettività della mappa f mostra che tutte le soluzioni x sono congruenti modulo u.
Enunciato per anelli generici
[modifica | modifica wikitesto]La forma generale del teorema cinese del resto, che implica tutte le formulazioni precedenti, può essere formulata per gli anelli e gli ideali. Se R è un anello e I1, ..., Ik sono ideali (bilateri) di R che sono coprimi a due a due (il che significa che Ii + Ij = R ogni volta che i ≠ j), allora il prodotto I di questi ideali è uguale alla loro intersezione, e l'anello quoziente R/I è isomorfo all'anello prodotto R/I1 x R/I2 x ... x R/Ik mediante l'isomorfismo
tale che
Applicazioni del teorema cinese del resto
[modifica | modifica wikitesto]Nell'algoritmo RSA i calcoli vengono fatti modulo , dove è un prodotto di due numeri primi e . Di solito la dimensione di è di 1024, 2048 o 4096 bit, cosa che rende i calcoli molto lunghi. Usando il teorema cinese del resto questi calcoli possono essere trasportati dall'anello all'anello . La somma delle dimensioni in bit di e è la dimensione in bit di , in questo modo i calcoli vengono molto semplificati.
Un'altra applicazione potenziale del teorema cinese del resto è il problema di contare i soldati in un esercito. Il generale può fare allineare i soldati in gruppi di 2, 3, 5, 7, 11, e così via, e conta i soldati rimanenti che non possono formare gruppi completi. Dopo che è stato fatto un numero sufficiente di questi test, il generale può calcolare facilmente quanti soldati formano l'esercito, trasformando un conteggio che impiegherebbe alcune ore in un altro che impiega pochi minuti.
Il fatto che un numero molto grande possa essere rappresentato da un piccolo numero di resti relativamente piccoli è anche l'idea centrale dei sistemi di numeri residui.
Note
[modifica | modifica wikitesto]- ^ Giovanni Giuseppe Nicosia, Cinesi, scuola e matematica, Lulu, Bologna, 2010, pagina 62, sezione 3.2.23
- ^ Massimo Gobbino, Dispense olimpioniche, 2006.
Bibliografia
[modifica | modifica wikitesto]- Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, New York, 1976. ISBN 0-387-90163-9 (capitolo 5.7).
- Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Section 4.3.2 (pp.286–291), exercise 4.6.2–3 (p. 456).
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 31.5: The Chinese remainder theorem, pp. 873–876.
Collegamenti esterni
[modifica | modifica wikitesto]- (EN) Chinese remainder theorem, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
- (EN) Eric W. Weisstein, Teorema cinese del resto, su MathWorld, Wolfram Research.
- Teorema cinese del resto a cut-the-knot
Controllo di autorità | LCCN (EN) sh97002778 · GND (DE) 4470755-1 · J9U (EN, HE) 987007558793905171 |
---|