Teorema cinese del resto

Da Wikipedia, l'enciclopedia libera.

In matematica, il termine teorema cinese del resto comprende diversi risultati in algebra astratta e teoria dei numeri.

Indice

1 Congruenza simultanea di interi
2 Enunciato per domini ad ideali principali
3 Enunciato per anelli generici
4 Applicazioni del teorema cinese del resto
5 Bibliografia
6 Collegamenti esterni

[modifica] Congruenza simultanea di interi

La formulazione originale del teorema, contenuta in un libro scritto nel III secolo dal matematico cinese Sun Tzu e successivamente ripubblicata in un libro del 1247 scritto da Qin Jiushao, è una affermazione riguardante le congruenze simultanee (si veda la voce aritmetica modulare). Si supponga che n₁, ..., n_k siano interi a due a due coprimi (il che significa che mcd(n_i, n_j) = 1 quando i ≠ j). Allora, comunque si scelgano degli interi a₁, ..., a_k, esiste un intero x soluzione del sistema di congruenze

$x \equiv a_i \pmod{n_i} \quad\mathrm{per}\; i = 1, \ldots, k.$

Inoltre, tutte le soluzioni x di questo sistema sono congruenti modulo il prodotto n = n₁...n_k.

Si può trovare una soluzione x come segue. Per ogni i gli interi n_i e n/n_i sono coprimi, e utilizzando l'algoritmo di Euclide esteso si possono trovare due interi r e s tali che r n_i + s n/n_i = 1. Ponendo e_i = s n/n_i, si ottiene

$e_i \equiv 1 \pmod{n_i} \quad\mathrm{e}\quad e_i \equiv 0 \pmod{n_j}$

per j ≠ i. Una soluzione del sistema di congruenze è quindi

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

Per esempio, si consideri il problema di trovare un intero x tale che

$x \equiv 2 \pmod{3}$

$x \equiv 3 \pmod{4}$

$x \equiv 2 \pmod{5}.$

Usando l'algoritmo di Euclide esteso per 3 e 4×5 = 20, si trova che (-13) × 3 + 2 × 20 = 1, cioè e₁ = 40. Usando l'algoritmo per 4 e 3×5 = 15, si ottiene che (-11) × 4 + 3 × 15 = 1. Quindi e₂ = 45. Infine, usando l'algoritmo euclideo per 5 e 3×4 = 12, si ha che 5 × 5 + (-2) × 12 = 1, e dunque e₃ = -24. Una soluzione x è quindi 2 × 40 + 3 × 45 + 2 × (-24) = 167. Tutte le altre soluzioni sono congruenti a 167 modulo 60, il che significa che sono tutte congruenti a 47 modulo 60.

A volte le congruenze simultanee possono essere risolte anche se i valori di n_i non sono coprimi a due a due. Il criterio precisamente è il seguente: una soluzione x esiste sse a_i ≡ a_j (mod mcd(n_i, n_j)) per tutti i valori di i e j. Tutte le soluzioni x sono congruenti modulo il minimo comune multiplo degli n_i.

Usando il metodo delle sostituzioni successive si possono spesso ottenere soluzioni delle congruenze simultanee, anche quando i moduli non sono coprimi a due a due.

[modifica] Enunciato per domini ad ideali principali

Per un dominio ad ideali principali R il teorema cinese del resto assume la forma seguente: se u₁, ..., u_k sono elementi di R che sono a due a due coprimi, e u denota il prodotto u₁...u_k, allora l'anello quoziente R/uR e il prodotto di anelli R/u₁R x ... x R/u_kR sono isomorfi mediante l'omomorfismo di anelli

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

tale che

$f(x +uR) = (x + u_1R, \ldots , x +u_kR) \quad\mbox{ per ogni } x\in R.$

L'isomorfismo inverso può essere costruito come segue. Per ogni i, gli elementi u_i e u/u_i sono coprimi, e per questo esistono due elementi r e s in R tali che

r u i + s u / u i = 1.

Sia e_i = s u/u_i. Allora l'inverso di f è la mappa

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

tale che

$g(a_1+u_1R,\ldots ,a_k+u_kR)= \left( \sum_{i=1}^k a_i e_i \right) + uR \quad\mbox{ per ogni }a_1,\ldots,a_k\in R.$

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

$x \equiv a_i \pmod{u_i} \quad\mathrm{for}\; i = 1, \ldots, k$

può essere risolto per trovare la x, e la iniettività della mappa f mostra che tutte le soluzioni x sono congruenti modulo u.

[modifica] Enunciato per anelli generici

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 I₁, ..., I_k sono ideali (two-sided) di R che sono coprimi a due a due (il che significa che I_i + I_j = 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/I₁ x R/I₂ x ... x R/I_k mediante l'isomorfismo

$f : R/I \rightarrow R/I_1 \times \cdots \times R/I_k$

tale che

$f(x + I) = (x +I_1, \ldots , x+I_k) \quad\mbox{ per ogni } x\in R.$

[modifica] Applicazioni del teorema cinese del resto

Nell'algoritmo RSA i calcoli vengono fatti modulo $n$ , dove $n$ è un prodotto di due numeri primi $p$ e $q$ . Di solito la dimensione di $n$ è 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 $\Z_n$ all'anello $\Z_p \times Z_q$ . La somma delle dimensioni in bit di $p$ e $q$ è la dimensione in bit di $n$ , e questo fatto rende $p$ e $q$ sensibilmente più piccoli di $n$ . 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.

[modifica] Bibliografia

Tom M. Apostol (1976): Introduction to Analytic Number Theory, Springer-Verlag, New York. ISBN 0-387-90163-9 (Chapter 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 (page 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.