Il teorema del resto cinese

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?

mod m , n m n".

La notazione indica "il resto del quoziente tra e Usando questa notazione, possiamo

così riformulare la domanda:

x (se esiste) soddisfa le relazioni?

Quale numero

mod x , 3 2

mod x , 5 3

mod x , 7 2 x 23.

Senza scervellarsi più di tanto, con un po' di intuito si trova la risposta

Questo valore è corretto, come potete verificare calcolando i resti richiesti

mod x , 3 = 2

x , 5 3

mod =

mod x , 7 = 2 y 758:

Questo valore non è l'unico. Un altro valore è

mod y , 3 = 2

y , 5 3

mod =

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:

m , m , ... , m

dato un insieme di interi privi di fattori comuni diversi da 1 e un altro insieme di interi

1 2 n

a , , , <

a ... a 0 a m

qualunque tali che , l'insieme di equazioni sul resto

1 2 n i i

mod x , m a , mod x , m a , ... , mod x , m a ha una soluzione intera.

1 1 2 2 n n

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

x

come determinare il numero . . . w

M m m ...... m i

. Poi, per ogni troviamo un numero soddisfacente la

Definiamo per prima cosa 1 2 n i

relazione

M

.

mod w , m 1

i i

m

i m non hanno fattori comuni diversi da 1). Il

(Possiamo ottenere questo risultato poiché i numeri

numero dato dall'espressione

M

. .

a

x w

i i m

i

i

è il numero cercato. M

. m

w

Com'è possibile? Il numero dà come resto 1 quando è diviso da e 0 quando è diviso da

i i

m

i M

. .

m. a w

qualunque altro numero Così il numero i i m

i

a m m.

restituisce come resto quando è diviso da e 0 quando è diviso da qualunque altro Per esempio,

i i

se consideriamo la somma

M M

. . . .

a a

w w

1 1 2 2

m m

1 2 m a m a

e dividiamo questa somma per otteniamo come resto e se dividiamo per otteniamo .

1 1 2 2

Questa proprietà vale analogamente anche per la somma estesa a tutti i termini:

M

. .

a w

i i m

i

i a

Illustriamo ora come fa Mathcad a trovare questo numero per un dato insieme di n valori di e per un

m.

insieme di n valori di a , , , m , , ,

a ... a m ... m

Supponiamo che gli interi e siano stati memorizzati rispettivamente nei

1 2 n 1 2 n m:

vettori e (definiti come variabili globali). Calcoliamo il prodotto dei valori di

a m

N rows m

i 1 .. N

M m

i

i w

Calcoliamo il valore degli interi . Ciò comporta una programmazione di Mathcad per eseguire

i M

. m

j è diviso da , poniamo i resti 0 uguali a 2 (per

l'ordinamento. Troviamo tutti i resti quando i

m

i j

metterli fuori gioco) e quindi ordiniamo i resti per individuare i più piccoli che danno come resto 1.

j 1 .. max m M

.

R if j < m , mod j , m , 2

j , i i i

m

i

I j

j < >

i

w mod csort augment R , I , 1 , m

i 1 , 2 i

w = 16 x

Calcoliamo la soluzione come specificato dal Teorema Cinese del Resto:

M

. .

x w

a

i i m

i

i

Troviamo ora la più piccola soluzione positiva:

.

x mod x , M M x

< 0

Questa è la nostra risposta: