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.
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.
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.
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