it.wikipedia.org

Teorema cinese del resto - Wikipedia

Da Wikipedia, l'enciclopedia libera.

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

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 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}}}\quad \mathrm {per} \quad j\neq i.$

Una soluzione del sistema di congruenze è quindi:

$x=\sum _{i=1}^{k}a_{i}e_{i}.\$

Si definisca il seguente sistema (con $MCD(n_{1},n_{2})=MCD(n_{1},n_{3})=MCD(n_{2},n_{3})=1$ ):

${\begin{cases}x\equiv a_{1}{\pmod {n_{1}}}\\x\equiv a_{2}{\pmod {n_{2}}}\\x\equiv a_{3}{\pmod {n_{3}}}\end{cases}}$

Sia $N=n_{1}\cdot n_{2}\cdot n_{3}$

$N_{1}=n_{2}n_{3}$

$N_{2}=n_{1}n_{3}$

$N_{3}=n_{1}n_{2}$

Siano poi $y_{i}$ le soluzioni alle congruenze $N_{i}y_{i}\equiv 1{\pmod {n_{i}}}$ ; la soluzione sarà data da:

$x\equiv a_{1}N_{1}y_{1}+a_{2}N_{2}y_{2}+a_{3}N_{3}y_{3}{\pmod {N}}$

Nel caso in cui $MCD(n_{1},n_{2},n_{3})>1$ si sarebbe potuto scomporre il sistema di congruenze in un sistema più grande rendendo ogni $n_{i}$ primo.^[2] Ad esempio: ${\begin{cases}x\equiv 2{\pmod {6}}\\x\equiv 2{\pmod {3}}\end{cases}}$

sarebbe diventato

${\begin{cases}x\equiv 2{\pmod {3}}\\x\equiv 0{\pmod {2}}\\x\equiv 2{\pmod {3}}\end{cases}}$

ovvero

${\begin{cases}x\equiv 0{\pmod {2}}\\x\equiv 2{\pmod {3}}\end{cases}}$

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_{1}R\times \cdots \times R/u_{k}R$

tale che

$f(x+uR)=(x+u_{1}R,\ldots ,x+u_{k}R)\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

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

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

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

tale che

$g(a_{1}+u_{1}R,\ldots ,a_{k}+u_{k}R)=\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 {per} \;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.

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 (bilateri) 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.$

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 $\mathbb {Z} _{n}$ all'anello $\mathbb {Z} _{p}\times \mathbb {Z} _{q}$ . La somma delle dimensioni in bit di $p$ e $q$ è la dimensione in bit 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.

^ Giovanni Giuseppe Nicosia, Cinesi, scuola e matematica, Lulu, Bologna, 2010, pagina 62, sezione 3.2.23
^ Massimo Gobbino, Dispense olimpioniche, 2006.

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.

Resto, teorema cinese del, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
(EN) Chinese remainder theorem, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
(EN) Eric W. Weisstein, Chinese Remainder Theorem, su MathWorld, Wolfram Research.
(EN) Chinese remainder theorem, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
Teorema cinese del resto a cut-the-knot

V · D · M

Algebra

Numeri

Naturali · Interi · Razionali · Irrazionali · Algebrici · Trascendenti · Reali · Complessi · Numero ipercomplesso · Numero p-adico · Duali · Complessi iperbolici

Principi fondamentali

Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza · Relazione d'ordine · Associatività della potenza

Algebra elementare

Equazione · Disequazione · Polinomio · Triangolo di Tartaglia · Teorema binomiale · Teorema del resto · Lemma di Gauss · Teorema delle radici razionali · Regola di Ruffini · Criterio di Eisenstein · Criterio di Cartesio · Disequazione con il valore assoluto · Segno · Metodo di Gauss-Seidel · Polinomio simmetrico · Funzione simmetrica

Elementi di Calcolo combinatorio

Fattoriale · Permutazione · Disposizione · Combinazione · Dismutazione · Principio di inclusione-esclusione

Concetti fondamentali di Teoria dei numeri

Primi	Numero primo · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Crivello di Atkin · Test di primalità · Teorema fondamentale dell'aritmetica
Divisori	Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Criteri di divisibilità · Divisore
Aritmetica modulare	Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Funzione φ di Eulero · Teorema di Wilson · Reciprocità quadratica

Teoria dei gruppi

Gruppi	Gruppo (finito · ciclico · abeliano) · Gruppo primario · Gruppo quoziente · Gruppo nilpotente · Gruppo risolubile · Gruppo simmetrico · Gruppo diedrale · Gruppo semplice · Gruppo sporadico · Gruppo mostro · Gruppo di Klein · Gruppo dei quaternioni · Gruppo generale lineare · Gruppo ortogonale · Gruppo unitario · Gruppo unitario speciale · Gruppo residualmente finito · Gruppo spaziale · Gruppo profinito · Out(F_n) · Parola · Prodotto diretto · Prodotto semidiretto · Prodotto intrecciato
Teoremi	Alternativa di Tits · Teorema di isomorfismo · Teorema di Lagrange · Teorema di Cauchy · Teoremi di Sylow · Teorema di Cayley · Teorema di struttura dei gruppi abeliani finiti · Lemma della farfalla · Lemma del ping-pong · Classificazione dei gruppi semplici finiti
Sottoinsiemi	Sottogruppo · Sottogruppo normale · Sottogruppo caratteristico · Sottogruppo di Frattini · Sottogruppo di torsione · Classe laterale · Classe di coniugio · Serie di composizione
Omomorfismo · Isomorfismo · Automorfismo interno · Automorfismo esterno · Permutazione · Presentazione di un gruppo · Azione di gruppo

Teoria degli anelli

Anello (artiniano · noetheriano · locale) · Caratteristica · Ideale (primo · massimale) · Dominio (a fattorizzazione unica · a ideali principali · euclideo) · Matrice · Anello semplice · Anello degli endomorfismi · Teorema di Artin-Wedderburn · Modulo · Dominio di Dedekind · Estensione di anelli · Teorema della base di Hilbert · Anello di Gorenstein · Base di Gröbner · Prodotto tensoriale · Primo associato

Teoria dei campi

Campo · Polinomio irriducibile · Polinomio ciclotomico · Teorema fondamentale dell'algebra · Campo finito · Automorfismo · Endomorfismo di Frobenius
Estensioni	Campo di spezzamento · Estensione di campi · Estensione algebrica · Estensione separabile · Chiusura algebrica · Campo di numeri · Estensione normale · Estensione di Galois · Estensione abeliana · Estensione ciclotomica · Teoria di Kummer
Teoria di Galois	Gruppo di Galois · Teoria di Galois · Teorema fondamentale della teoria di Galois · Teorema di Abel-Ruffini · Costruzioni con riga e compasso

Altre strutture algebriche

Magma · Semigruppo · Corpo · Spazio vettoriale · Algebra su campo · Algebra di Lie · Algebra differenziale · Algebra di Clifford · Gruppo topologico · Gruppo ordinato · Quasi-anello · Algebra di Boole

argomenti

Teoria delle categorie · Algebra lineare · Algebra commutativa · Algebra omologica · Algebra astratta · Algebra computazionale · Algebra differenziale · Algebra universale

V · D · M Teoria dei numeri
Numeri più usati	Naturali · Interi · Pari e dispari
Principi generali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza
Successioni di interi	Fattoriale · Successione di Fibonacci · Numero di Catalan · Numero di Perrin · Numero di Eulero · Successione di Mian-Chowla · Successione di Thue-Morse
Caratteristiche dei numeri primi	Numero primo · Lemma di Euclide · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Test di primalità · Teorema fondamentale dell'aritmetica · Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Teorema dei numeri primi
Funzioni aritmetiche	Funzione moltiplicativa · Funzione additiva · Convoluzione di Dirichlet · Funzione φ di Eulero · Funzione di Möbius · Funzione tau sui positivi · Funzione sigma · Funzione di Liouville · Funzione di Mertens
Aritmetica modulare	Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Criteri di divisibilità · Teorema di Fermat sulle somme di due quadrati · Teorema di Wilson · Legge di reciprocità quadratica
Congetture	Congettura di Goldbach · Congettura di Polignac · Congettura abc · Congettura dei numeri primi gemelli · Congettura di Legendre · Nuova congettura di Mersenne · Congettura di Collatz · Ipotesi di Riemann
Altro	Problema di Waring
Principali teorici	Fibonacci · Fermat · Gauss · Eulero · Legendre · Riemann · Dirichlet
Discipline connesse	Teoria algebrica dei numeri · Teoria analitica dei numeri · Crittografia · Teoria computazionale dei numeri

Controllo di autorità	LCCN (EN) sh97002778 · GND (DE) 4470755-1 · J9U (EN, HE) 987007558793905171