Il teorema del resto cinese
Nel primo secolo d. C. lo scrittore cinese Sun-Tse pose la domanda:
Quale numero diviso per 3, per 5 e per 7, dà come resti 2, 3 e 2 rispettivamente?
La notazione «mod m, n» indica «il resto del quoziente tra m e n». Usando questa notazione, possiamo così riformulare la domanda:
Quale numero x, se esiste, soddisfa le relazioni?
mod x, 3 = 2
mod x, 5 = 3
mod x, 7 = 2
Senza scervellarsi più di tanto, con un po' di intuito si trova la risposta x = 23.
Questo valore è corretto, come potete verificare calcolando i resti richiesti:
mod x, 3 = 2
mod x, 5 = 3
mod x, 7 = 2
Questo valore non è l'unico. Un altro valore è y = 758:
mod y, 3 = 2
mod y, 5 = 3
mod y, 7 = 2
Ma se noi scriviamo semplicemente una lista di divisori e li supponiamo resti di un numero incognito, come facciamo a sapere se tale numero esiste, e, se esiste, come facciamo a calcolarlo? La risposta è data dal Teorema Cinese del Resto.
Il Teorema
Il Teorema Cinese del Resto afferma:
Dato un insieme di interi m1, m2, ..., mn privi di fattori comuni diversi da 1 e un altro insieme di interi a1, a2, ..., an qualunque tali che 0 ≤ ai < mi, l'insieme di equazioni sul resto
mod x, m1 = a1, mod x, m2 = a2, ... , mod x, mn = an
ha una soluzione intera.
Il teorema ha preso questo nome, non solo perché era noto a Sun-Tse e agli antichi matematici Cinesi (era noto anche ai Greci, qualcuno afferma, ancor prima che ai Cinesi), ma anche come riconoscimento ai Cinesi per i loro precedenti lavori sulla teoria dei numeri.
Una prova
Come molti teoremi in matematica, la prova del Teorema Cinese del Resto è costruttiva; cioè, ci dice come determinare il numero x.
Definiamo per prima cosa M = m1m2......mn. Poi, per ogni i troviamo un numero wi soddisfacente la relazione
mod wi, M / mi = 1.
Possiamo ottenere questo risultato poiché i numeri mi e M / mi non hanno fattori comuni diversi da 1.
Il numero dato dall'espressione
x = a1w1M / m1 + a2w2M / m2 + ...
è il numero cercato.
Com'è possibile? Il numero wiM / mi dà come resto 1 quando è diviso da mi e 0 quando è diviso da qualunque altro numero m.
Così il numero aiwiM / mi restituisce come resto ai quando è diviso da mi e 0 quando è diviso da qualunque altro m.
Il problema di Sun-Tse
Nel primo secolo d. C. lo scrittore cinese Sun-Tse pose la domanda: quale numero diviso per 3, per 5 e per 7, dà come resti 2, 3 e 2 rispettivamente?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
