Il teorema cinese del resto spiegato

Un numero dà resto 2 diviso per 3, resto 3 diviso per 5 e resto 2 diviso per 7. Che numero è? Provando i numeri uno per uno si arriva a 23 dopo un po', ma la domanda nasconde un teorema: finché i divisori non hanno fattori comuni, c'è sempre esattamente una risposta sotto il loro prodotto, e la si trova senza provare nulla. Il teorema ha circa 1.500 anni ed è ancora al lavoro nei calendari, nell'aritmetica dei computer e nella crittografia che protegge il web.

Tre file di segni per i numeri che danno resto 2 mod 3, 3 mod 5 e 2 mod 7, allineati in una sola colonna sul 23
Tre file di segni per i numeri che danno resto 2 mod 3, 3 mod 5 e 2 mod 7, allineati in una sola colonna sul 23

Un problema dal Sunzi Suanjing

Il Sunzi Suanjing, un libro di aritmetica cinese del III–V secolo, chiede un numero di cose che, contate a tre a tre, lascia 2, contate a cinque a cinque lascia 3 e contate a sette a sette lascia 2. La sua risposta è 23, e il suo metodo è quello che si insegna ancora: prendi 70 per ogni cosa avanzata contando a tre, 21 per ogni cosa avanzata contando a cinque e 15 per ogni cosa avanzata contando a sette, somma e togli 105 quante volte puoi. 2 × 70 + 3 × 21 + 2 × 15 = 233, e 233 − 2 × 105 = 23. Una poesia dell'epoca Ming ha conservato i numeri 70, 21, 15 e 105 nella memoria per secoli. Qin Jiushao diede un metodo generale nel 1247, lo stesso problema compare nel Liber Abaci di Fibonacci del 1202, e Carl Friedrich Gauss enunciò il teorema nella sua forma moderna nelle Disquisitiones Arithmeticae del 1801.

Una pagina di un’edizione Qing del Sunzi Suanjing, il trattato aritmetico cinese del III–V secolo che chiede un numero che lasci 2, 3 e 2 quando si conta per tre, per cinque e per sette.
Una pagina di un’edizione Qing del Sunzi Suanjing, il trattato aritmetico cinese del III–V secolo che chiede un numero che lasci 2, 3 e 2 quando si conta per tre, per cinque e per sette.
Carl Friedrich Gauss, in un ritratto di Christian Albrecht Jensen del 1840. Introdusse la notazione di congruenza a ≡ b (mod n) nelle Disquisitiones Arithmeticae del 1801.
Carl Friedrich Gauss, in un ritratto di Christian Albrecht Jensen del 1840. Introdusse la notazione di congruenza a ≡ b (mod n) nelle Disquisitiones Arithmeticae del 1801.

Che cosa dice il teorema

Prendi dei moduli n₁, n₂, …, nₖ di cui nessuna coppia ha un fattore comune, e dei resti qualsiasi a₁, a₂, …, aₖ. Allora esiste esattamente un numero intero x da 0 a N − 1, dove N = n₁ × n₂ × … × nₖ, che diviso per nᵢ dà resto aᵢ, per ogni i. Tutte le altre soluzioni differiscono da questa per un multiplo di N. Nella notazione dell'aritmetica modulare: il sistema x ≡ aᵢ (mod nᵢ) ha una soluzione, unica mod N. Detto in un altro modo, un numero da 0 a N − 1 e la lista dei suoi resti portano esattamente la stessa informazione: 3 × 5 × 7 = 105 numeri e 3 × 5 × 7 = 105 possibili liste di resti, ognuna usata una volta.

Costruire la soluzione

I numeri 70, 21 e 15 non sono magici. Ognuno dà resto 1 diviso per il proprio modulo e resto 0 diviso per gli altri: 70 = 2 × 35 è un multiplo di 5 e di 7 e diviso per 3 dà resto 1. In generale si prende Nᵢ = N / nᵢ, che è un multiplo di ogni modulo tranne nᵢ, e lo si moltiplica per yᵢ, l'inverso di Nᵢ mod nᵢ. L'inverso esiste perché Nᵢ e nᵢ non hanno fattori comuni, e l'algoritmo di Euclide esteso lo trova: esegue le divisioni di Euclide per il massimo comune divisore e risale fino all'identità di Bézout 1 = s × nᵢ + t × Nᵢ, così che t è l'inverso. Allora x = a₁N₁y₁ + a₂N₂y₂ + …, ridotto mod N, soddisfa ogni equazione, perché ogni termine soddisfa la propria equazione e scompare in tutte le altre.

Un'equazione alla volta

C'è un secondo metodo, che non ha bisogno del prodotto di tutti i moduli. Ogni soluzione di x ≡ 2 (mod 3) ha la forma x = 2 + 3t. Sostituendola nell'equazione successiva si ha 2 + 3t ≡ 3 (mod 5), quindi 3t ≡ 1 (mod 5), e moltiplicando per 2, l'inverso di 3 mod 5, si ottiene t ≡ 2 (mod 5). Allora x = 2 + 3 × 2 = 8, e le prime due equazioni insieme dicono x ≡ 8 (mod 15). Ripetendo con la terza equazione, 8 + 15t ≡ 2 (mod 7) dà t ≡ 1, quindi x ≡ 23 (mod 105). Questa sostituzione mantiene i numeri più piccoli, è il modo in cui di solito un computer risolve questi sistemi, e funziona anche quando i moduli hanno un fattore comune.

Moduli con un fattore comune

Se due moduli hanno un fattore comune, le loro equazioni si sovrappongono: x ≡ 1 (mod 4) dice già che x è dispari, e x ≡ 4 (mod 6) dice che x è pari, quindi nessun x le soddisfa entrambe. In generale x ≡ a (mod m) e x ≡ b (mod n) possono valere insieme esattamente quando a e b danno lo stesso resto nella divisione per g = gcd(m, n), cioè quando g divide a − b. La soluzione è allora unica mod lcm(m, n) = m × n / g, non mod m × n. Il vecchio indovinello del cesto di uova, che ne lascia 1 togliendole a 2, 3, 4, 5 o 6 alla volta e nessuna togliendole a 7 alla volta, ha la risposta 301, che si ripete ogni 420 = lcm(2, 3, 4, 5, 6, 7). Un sistema ha una soluzione esattamente quando ogni coppia delle sue equazioni è compatibile, quindi un sistema impossibile contiene sempre una coppia che si contraddice.

Calendari, computer e RSA

Nel 1583 Joseph Scaligero combinò tre cicli del calendario, il ciclo solare di 28 anni, il ciclo lunare di 19 anni e l'indizione di 15 anni, nel periodo giuliano di 28 × 19 × 15 = 7.980 anni. Per il teorema ogni anno ha la sua combinazione dei tre numeri di ciclo, e il periodo comincia nel 4713 a.C., l'ultimo anno in cui tutti e tre valevano 1; gli astronomi contano ancora i giorni giuliani da lì. I computer usano il teorema per calcolare con numeri enormi come liste di piccoli resti, che si possono sommare e moltiplicare separatamente e in parallelo, e poi unire alla fine. La decifratura RSA funziona allo stesso modo: c^d mod n con n = p × q si calcola come due potenze mod p e mod q unite con il teorema, circa quattro volte più velocemente di una potenza mod n. Gli schemi di condivisione di segreti, come quelli di Mignotte e di Asmuth e Bloom, nascondono un segreto in dei resti, in modo che solo un numero sufficiente di essi insieme lo riveli.

Ron Rivest, Adi Shamir e Len Adleman (da sinistra a destra)
Ron Rivest, Adi Shamir e Len Adleman (da sinistra a destra)

Provalo

Apri il risolutore per scrivere qualsiasi sistema di congruenze, fino a 20 equazioni e numeri fino a 200 cifre, oppure scegli uno degli esempi svolti: il problema di Sunzi, il cesto di uova, il periodo giuliano, due orari di autobus, la decifratura RSA e un sistema senza soluzione. Il procedimento è scritto con i tuoi numeri, con la costruzione o per sostituzione, con l'algoritmo di Euclide esteso per ogni inverso. L'immagine segna i numeri che soddisfano ogni equazione, così vedi l'unica colonna in cui si incontrano tutte, oppure dispone i resti di due equazioni in una tabella in cui ogni numero ha la sua cella.

Domande frequenti

La soluzione di un sistema di congruenze è unica?

Solo a meno di un multiplo del modulo. Se x = 23 risolve il problema di Sunzi, lo risolvono anche 23 + 105 = 128, 233 e −82, perché aggiungere 105 non cambia nessuno dei resti. Il teorema dice che c'è esattamente una soluzione da 0 a 104; con moduli che hanno fattori comuni, esattamente una sotto il loro minimo comune multiplo.

Perché i moduli devono essere coprimi?

Per la costruzione, perché Nᵢ deve avere un inverso mod nᵢ, e questo esiste solo quando non hanno fattori comuni. Per il teorema stesso, perché i fattori comuni fanno sovrapporre alcune equazioni: allora un sistema o non ha soluzioni o ne ha meno di diverse, e le soluzioni si ripetono ogni minimo comune multiplo invece che ogni prodotto.

Come si trova un inverso modulare a mano?

Con l'algoritmo di Euclide esteso. Per l'inverso di 15 mod 7: 15 = 2 × 7 + 1, quindi 1 = 15 − 2 × 7, e 15 × 1 ≡ 1 (mod 7): l'inverso è 1. Per 35 mod 3: 35 = 11 × 3 + 2 e 3 = 1 × 2 + 1, quindi 1 = 3 − 2 = 3 − (35 − 11 × 3) = 12 × 3 − 35, e l'inverso di 35 mod 3 è −1 ≡ 2. Per moduli piccoli si può anche provare semplicemente 1, 2, 3, … finché il prodotto dà resto 1.

Che cosa c'entra il teorema con gli orologi?

Un resto mod n è una posizione su un orologio con n ore. Due orologi con 3 e 5 ore, fatti partire insieme e avanzati di un'ora alla volta, mostrano ognuna delle 15 coppie di posizioni una volta prima di tornare all'inizio, perché 3 e 5 non hanno fattori comuni. Orologi con 4 e 6 ore tornano dopo 12 passi e mostrano solo 12 delle 24 coppie: una posizione dispari e una pari non compaiono mai insieme.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Apri il risolutore del teorema cinese del resto