Calcolatore del Teorema Cinese del Resto: Risolvi i Sistemi Modulari Passo dopo Passo
Un calcolatore del teorema cinese del resto risolve un sistema di congruenze simultanee — affermazioni come x ≡ 2 (mod 3) e x ≡ 3 (mod 5) — combinandole in una singola congruenza modulo il prodotto (o il minimo comune multiplo) dei singoli moduli. Il metodo risale a circa 1.500 anni fa al testo matematico cinese Sunzi Suanjing, e oggi supporta le ottimizzazioni della crittografia RSA, i calcoli di calendario e i codici di correzione degli errori, oltre a essere un elemento fondamentale dei corsi di matematica discreta e teoria dei numeri. Questa guida ti spiega come funziona internamente il calcolatore, come verificare se un sistema ha una soluzione, come trovare gli inversi modulari da cui dipende il metodo, due esempi completamente risolti — uno con moduli coprimi a coppie e uno senza — più errori comuni e problemi di pratica.
Contenuto
- 01Che Cos'è il Teorema Cinese del Resto?
- 02Come Funziona un Calcolatore del Teorema Cinese del Resto?
- 03Come Verificare se i Moduli Sono Compatibili?
- 04Che Cos'è un Inverso Modulare e Come lo Trovi?
- 05Esempio Svolto: Risolvere Congruenze Coprime a Coppie
- 06Esempio Svolto: Riconciliare i Moduli Non Coprimi
- 07Ricostruire la Più Piccola Soluzione Non Negativa
- 08Quali Sono i Più Comuni Errori del Teorema Cinese del Resto?
- 09Problemi di Pratica: Metti alla Prova le Tue Competenze del Calcolatore del Teorema Cinese del Resto
Che Cos'è il Teorema Cinese del Resto?
Il Teorema Cinese del Resto (TCR) afferma che se hai un sistema di congruenze x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₙ (mod mₙ), e i moduli m₁, m₂, ..., mₙ sono coprimi a coppie (ogni coppia non ha fattore comune se non 1), allora c'è esattamente una soluzione per x modulo M, dove M = m₁ × m₂ × ... × mₙ. Il teorema prende il nome dalla sua prima apparizione nota nel testo cinese del 3º-5º secolo Sunzi Suanjing (Manuale di Aritmetica del Maestro Sun), che poneva l'enigma ormai classico: trova un numero che lascia resto 2 quando diviso per 3, resto 3 quando diviso per 5, e resto 2 quando diviso per 7. Questo enigma — e il metodo TCR che lo risolve — riappare costantemente al di fuori dell'aula: la crittografia RSA usa il TCR per accelerare la decrittazione lavorando con moduli più piccoli invece di uno enorme, gli informatici lo usano per rappresentare i grandi numeri come tuple di residui più piccoli per l'aritmetica più veloce, e i sistemi di calendario lo usano per riconciliare cicli di lunghezze diverse (giorni della settimana, giorni del mese e cicli degli anni bisestili).
Teorema Cinese del Resto: per i moduli coprimi a coppie m₁, ..., mₙ, il sistema x ≡ aᵢ (mod mᵢ) ha esattamente una soluzione modulo M = m₁ × m₂ × ... × mₙ.
Come Funziona un Calcolatore del Teorema Cinese del Resto?
Un calcolatore del teorema cinese del resto automatizza quattro fasi che sono noiose da seguire a mano una volta che un sistema ha tre o più congruenze, soprattutto i calcoli dell'inverso modulare. Internamente, tratta ogni congruenza come una coppia (aᵢ, mᵢ), conferma che i moduli possono essere usati insieme, e poi costruisce la soluzione unica usando una somma ponderata piuttosto che tentativi ed errori. Comprendere queste quattro fasi è ciò che ti permette di verificare l'output di un calcolatore, o risolvere lo stesso problema a mano in un esame dove nessun calcolatore è consentito.
1. Passo 1: Controlla i moduli
Conferma che ogni coppia di moduli è coprima (mcd = 1). Se una coppia condivide un fattore comune, il calcolatore passa al controllo di compatibilità descritto nella sezione successiva invece della formula standard.
2. Passo 2: Calcola il modulo combinato M
Moltiplica tutti i moduli insieme: M = m₁ × m₂ × ... × mₙ. Questo è il modulo della risposta finale combinata.
3. Passo 3: Trova ogni prodotto parziale e il suo inverso modulare
Per ogni congruenza i, calcola Mᵢ = M / mᵢ (il prodotto di tutti i moduli tranne mᵢ), quindi trova l'inverso modulare di Mᵢ modulo mᵢ — chiamalo yᵢ, dove Mᵢ × yᵢ ≡ 1 (mod mᵢ).
4. Passo 4: Combina e riduci
Somma aᵢ × Mᵢ × yᵢ su ogni congruenza, quindi riduci quella somma modulo M per ottenere l'unica soluzione più piccola non negativa x.
La formula dietro ogni calcolatore del teorema cinese del resto: x ≡ Σ (aᵢ × Mᵢ × yᵢ) mod M, dove Mᵢ = M/mᵢ e yᵢ è l'inverso modulare di Mᵢ mod mᵢ.
Come Verificare se i Moduli Sono Compatibili?
La versione da manuale del Teorema Cinese del Resto richiede moduli coprimi a coppie, ma i sistemi reali — soprattutto quelli che compaiono nei problemi di pianificazione o crittografia — spesso hanno moduli che condividono fattori. Una versione generalizzata del TCR si applica ancora, ma solo se il sistema supera prima un controllo di compatibilità: per ogni coppia di congruenze x ≡ aᵢ (mod mᵢ) e x ≡ aⱼ (mod mⱼ), le due devono concordare sulla sovrapposizione, il che significa aᵢ ≡ aⱼ (mod mcd(mᵢ, mⱼ)). Se questo controllo fallisce anche per una sola coppia, il sistema non ha alcuna soluzione, indipendentemente da tutto il resto — e un buon calcolatore lo segnala invece di restituire un numero sbagliato.
1. Passo 1: Calcola mcd(mᵢ, mⱼ) per ogni coppia di moduli
Per un sistema a due congruenze, c'è solo una coppia da controllare. Per un sistema a tre congruenze, controlla tutte e tre le coppie.
2. Passo 2: Riduci entrambi i residui modulo quel mcd
Prendi aᵢ mod mcd(mᵢ, mⱼ) e aⱼ mod mcd(mᵢ, mⱼ). Se corrispondono, la coppia è compatibile.
3. Passo 3: Esempio di un sistema incompatibile
Prendi x ≡ 1 (mod 4) e x ≡ 0 (mod 6). mcd(4, 6) = 2. Riduci: 1 mod 2 = 1, e 0 mod 2 = 0. Poiché 1 ≠ 0, nessun intero soddisfa entrambe le congruenze — il sistema non ha soluzione, e un calcolatore del teorema cinese del resto dovrebbe segnalare esattamente questo invece di forzare una risposta.
Regola di compatibilità per i moduli non coprimi: x ≡ aᵢ (mod mᵢ) e x ≡ aⱼ (mod mⱼ) possono entrambi essere veri solo se aᵢ ≡ aⱼ (mod mcd(mᵢ, mⱼ)).
Che Cos'è un Inverso Modulare e Come lo Trovi?
L'inverso modulare di un numero a modulo m è un altro numero b tale che a × b ≡ 1 (mod m) — gioca lo stesso ruolo di 1/a nella divisione ordinaria, ma limitato ai numeri interi all'interno di un modulo fisso. Un inverso modulare esiste se e solo se mcd(a, m) = 1, che è esattamente il motivo per cui il Teorema Cinese del Resto standard richiede moduli coprimi a coppie: garantisce che ogni Mᵢ abbia un inverso mod mᵢ. Il modo più affidabile per trovare un inverso modulare a mano è l'algoritmo euclideo esteso, che esegue l'algoritmo mcd ordinario in avanti e poi all'indietro per esprimere 1 come una combinazione di a e m.
1. Passo 1: Esegui l'algoritmo euclideo in avanti
Trova l'inverso di 4 mod 7. Dividi ripetutamente: 7 = 1×4 + 3, quindi 4 = 1×3 + 1, quindi 3 = 3×1 + 0. I resti sono 3, quindi 1, quindi 0, confermando mcd(4, 7) = 1, quindi esiste un inverso.
2. Passo 2: Lavora all'indietro per isolare 1
Dalla penultima riga, 1 = 4 − 1×3. Sostituisci 3 = 7 − 1×4 dalla prima riga: 1 = 4 − 1×(7 − 1×4) = 2×4 − 1×7.
3. Passo 3: Leggi l'inverso
L'equazione 1 = 2×4 − 1×7 significa 2×4 ≡ 1 (mod 7), quindi l'inverso di 4 mod 7 è 2. Controllo rapido: 4 × 2 = 8 = 7 + 1, che è infatti ≡ 1 (mod 7).
Per i moduli piccoli, è spesso più veloce testare i candidati direttamente: moltiplica a per 1, 2, 3, ... mod m finché il prodotto non è 1. Per i moduli più grandi, l'algoritmo euclideo esteso è molto più affidabile.
Esempio Svolto: Risolvere Congruenze Coprime a Coppie
Questo è il classico problema di Sunzi Suanjing: trova x tale che x ≡ 2 (mod 3), x ≡ 3 (mod 5), e x ≡ 2 (mod 7). I moduli 3, 5 e 7 sono coprimi a coppie, quindi la formula TCR standard si applica direttamente.
1. Passo 1: Calcola M
M = 3 × 5 × 7 = 105.
2. Passo 2: Calcola ogni Mᵢ e il suo inverso
M₁ = 105/3 = 35. 35 mod 3 = 2, e l'inverso di 2 mod 3 è 2 (poiché 2×2 = 4 ≡ 1 mod 3). M₂ = 105/5 = 21. 21 mod 5 = 1, e l'inverso di 1 mod 5 è 1. M₃ = 105/7 = 15. 15 mod 7 = 1, e l'inverso di 1 mod 7 è 1.
3. Passo 3: Combina
x ≡ (a₁×M₁×y₁) + (a₂×M₂×y₂) + (a₃×M₃×y₃) mod M = (2×35×2) + (3×21×1) + (2×15×1) mod 105 = 140 + 63 + 30 mod 105 = 233 mod 105 = 23.
4. Passo 4: Verifica
23 ÷ 3 = 7 resto 2 ✓. 23 ÷ 5 = 4 resto 3 ✓. 23 ÷ 7 = 3 resto 2 ✓. La più piccola soluzione non negativa è x = 23, e ogni altra soluzione è 23 + 105k per qualsiasi intero k.
x ≡ 23 (mod 105) — la stessa risposta che un calcolatore del teorema cinese del resto restituisce istantaneamente, e lo stesso puzzle che ha aperto questo ramo della teoria dei numeri più di mille anni fa.
Esempio Svolto: Riconciliare i Moduli Non Coprimi
Ora risolvi x ≡ 3 (mod 4) e x ≡ 1 (mod 6), dove 4 e 6 non sono coprimi (condividono un fattore di 2). La formula standard dell'esempio coprime a coppie non si applica direttamente, ma il sistema può comunque avere una soluzione unica modulo il minimo comune multiplo dei moduli, a condizione che superi prima il controllo di compatibilità.
1. Passo 1: Controlla la compatibilità
mcd(4, 6) = 2. Riduci entrambi i residui: 3 mod 2 = 1, e 1 mod 2 = 1. Corrispondono, quindi il sistema è compatibile e una soluzione esiste.
2. Passo 2: Trova il modulo combinato
Invece di moltiplicare 4 × 6 = 24, usa il minimo comune multiplo: mcm(4, 6) = 12. La soluzione sarà unica modulo 12, non 24.
3. Passo 3: Sostituisci e risolvi
Scrivi x = 4k + 3 dalla prima congruenza, quindi sostituisci nella seconda: 4k + 3 ≡ 1 (mod 6), quindi 4k ≡ −2 ≡ 4 (mod 6). Entrambi i lati e il modulo condividono un fattore di mcd(4, 6) = 2, quindi dividi l'intera congruenza per 2: 2k ≡ 2 (mod 3). L'inverso di 2 mod 3 è 2, quindi k ≡ 2×2 ≡ 1 (mod 3).
4. Passo 4: Ricostruisci x
k = 3j + 1 per qualsiasi intero j, quindi x = 4(3j + 1) + 3 = 12j + 7. La più piccola soluzione non negativa è x = 7.
5. Passo 5: Verifica
7 mod 4 = 3 ✓. 7 mod 6 = 1 ✓. Quindi x ≡ 7 (mod 12) è corretto, e dividere la congruenza per il fattore condiviso — piuttosto che ignorarlo — è il passo che rende il TCR non-coprime funzionante.
Quando i moduli condividono un fattore comune, non puoi usare la formula coprime a coppie così com'è — devi dividere la congruenza risultante per mcd(mᵢ, mⱼ) prima di trovare l'inverso, altrimenti l'inverso non esisterà.
Ricostruire la Più Piccola Soluzione Non Negativa
Ogni sistema del teorema cinese del resto che supera il suo controllo di compatibilità ha infinite soluzioni intere, non solo una — ma sono tutte congruenti l'una all'altra modulo M (o modulo mcm(m₁, ..., mₙ) nel caso non-coprime). Per convenzione, un calcolatore segnala il più piccolo rappresentante non negativo di quella famiglia infinita, il valore x₀ che soddisfa 0 ≤ x₀ < M, perché è la risposta canonica unica più facile da enunciare, confrontare e verificare. Ogni altra soluzione è semplicemente x₀ più o meno un multiplo di M.
1. Ridurre una somma intermedia negativa
La somma ponderata nel Passo 4 del metodo della calcolatrice può risultare negativa se un residuo aᵢ è negativo o se un inverso modulare è stato calcolato come rappresentante negativo. Se la somma è, diciamo, S = −37 e M = 45, aggiungi M ripetutamente finché il risultato non è non negativo: −37 + 45 = 8, quindi la più piccola soluzione non negativa è x₀ = 8, non −37.
2. L'insieme completo di soluzioni
Una volta che hai x₀, l'insieme completo di soluzioni è ogni intero della forma x₀ + kM per k = ..., −2, −1, 0, 1, 2, .... Nell'esempio Sunzi sopra, è 23, 128, 233, ... e anche −82, −187, e così via — ma 23 è quello che riporti a meno che non sia richiesto un intervallo specifico.
Un risultato intermedio negativo o sovradimensionato non è sbagliato — semplicemente non è stato ridotto ancora. Aggiungi o sottrai multipli di M finché il valore non si trova in [0, M).
Quali Sono i Più Comuni Errori del Teorema Cinese del Resto?
La maggior parte degli errori nei problemi TCR provengono dal saltare un controllo piuttosto che da un calcolo finale difettoso, ecco perché vale la pena rallentare all'inizio di un problema piuttosto che alla fine.
1. Applicare la formula coprime ai moduli non coprimi
Se uno qualsiasi dei due moduli condivide un fattore, calcolare M come il loro prodotto diretto e cercare gli inversi modulari nel modo standard fallirà silenziosamente o produrrà una risposta sbagliata — controlla sempre mcd(mᵢ, mⱼ) = 1 per ogni coppia per primo.
2. Confondere un inverso modulare con una frazione ordinaria
L'inverso di 4 mod 7 è 2, non 1/4 — gli inversi modulari sono numeri interi trovati tramite l'algoritmo euclideo esteso (o moltiplicazione per prova per i moduli piccoli), mai frazioni.
3. Non ridurre correttamente i numeri negativi modulo m
−2 mod 6 è 4, non −2 e non 2 — continua ad aggiungere il modulo finché il risultato non è nell'intervallo [0, m). Truncare o prendere il valore assoluto invece di aggiungere il modulo è una frequente fonte di risposte sbagliate.
4. Dimenticare di dividere per il fattore condiviso nei sistemi non-coprime
Quando i moduli condividono un fattore comune, una congruenza come 4k ≡ 4 (mod 6) deve essere divisa per mcd(4, 6) = 2 per diventare 2k ≡ 2 (mod 3) prima di poter trovare un inverso — 4 non ha alcun inverso mod 6, poiché mcd(4, 6) ≠ 1.
5. Fermarsi prima di ridurre la somma finale modulo M
La somma ponderata dal Passo 4 (ad esempio, 233 nel problema Sunzi) non è la risposta finale — deve essere ridotta modulo M (233 mod 105 = 23) per raggiungere la più piccola soluzione non negativa.
Se la tua risposta non soddisfa ogni congruenza originale quando la sostituisci, controlla di nuovo il test di compatibilità e gli inversi modulari per primo — è lì che accade quasi ogni errore TCR effettivamente.
Problemi di Pratica: Metti alla Prova le Tue Competenze del Calcolatore del Teorema Cinese del Resto
Lavora su questi tre sistemi a mano, verificando prima la coprimità a coppie o la compatibilità, prima di confrontarli con le soluzioni qui sotto. Il secondo problema è deliberatamente irrisolvibile — riconoscerlo è altrettanto importante che trovare una risposta numerica quando esiste.
1. Problema 1 (coprime a coppie)
Risolvi: x ≡ 1 (mod 3), x ≡ 4 (mod 5), x ≡ 6 (mod 7). Risposta: M = 105. M₁ = 35 con inverso 2 mod 3 ; M₂ = 21 con inverso 1 mod 5 ; M₃ = 15 con inverso 1 mod 7. Somma = (1×35×2) + (4×21×1) + (6×15×1) = 70 + 84 + 90 = 244. 244 mod 105 = 34. Verifica: 34 mod 3 = 1 ✓, 34 mod 5 = 4 ✓, 34 mod 7 = 6 ✓. Soluzione: x ≡ 34 (mod 105).
2. Problema 2 (moduli incompatibili — nessuna soluzione)
Risolvi: x ≡ 2 (mod 8), x ≡ 5 (mod 12). mcd(8, 12) = 4. Riduci: 2 mod 4 = 2, e 5 mod 4 = 1. Poiché 2 ≠ 1, il sistema è incompatibile e non ha soluzione — un calcolatore del teorema cinese del resto dovrebbe restituire questa conclusione piuttosto che un numero scorretto.
3. Problema 3 (moduli non-coprime compatibili)
Risolvi: x ≡ 5 (mod 9), x ≡ 2 (mod 6). mcd(9, 6) = 3. Riduci: 5 mod 3 = 2, e 2 mod 3 = 2 — compatibile. mcm(9, 6) = 18. Scrivi x = 9k + 5, sostituisci: 9k + 5 ≡ 2 (mod 6) → 9k ≡ −3 ≡ 3 (mod 6). Dividi per mcd(9, 6) = 3 : 3k ≡ 1 (mod 2) → k ≡ 1 (mod 2). Quindi k = 2j + 1, ottenendo x = 9(2j+1) + 5 = 18j + 14. Verifica: 14 mod 9 = 5 ✓, 14 mod 6 = 2 ✓. Soluzione: x ≡ 14 (mod 18). Se vuoi verificare ogni inverso modulare e passo di riduzione su un problema come questo, il risolutore di problemi di matematica passo dopo passo di Solvify ti spiegherà ogni fase nello stesso modo di questa guida.
Il modo più veloce per sviluppare una vera padronanza del Teorema Cinese del Resto è risolvere un mix di sistemi coprimi, non-coprimi-ma-compatibili e incompatibili — riconoscere in quale caso ti trovi è metà dell'abilità.
Articoli correlati
Calcolatore del Teorema dei Resti: Come Trovare i Resti Passo dopo Passo
Un concetto di resto diverso ma correlato — questa guida copre il teorema del resto polinomiale, un contesto utile prima di affrontare le congruenze modulari.
Calcolatore dell'Eliminazione di Gauss: Risolvi i Sistemi Lineari Passo dopo Passo
Un altro metodo di calcolatore sistematico e algoritmico — confronta come l'eliminazione di Gauss e il Teorema Cinese del Resto riducono ciascuno un sistema a una risposta unica.
Risoluzione di Problemi Matematici Passo dopo Passo: Un Quadro Ripetibile per Qualsiasi Problema
Il quadro in 5 fasi di questa guida si applica direttamente ai problemi TCR: identificare ciò che è dato, scegliere un metodo, lavorare sistematicamente e verificare il risultato.
Risolutori matematici
Risolutore Smart Scan
Scatta una foto di un sistema di congruenza o un problema di teoria dei numeri e ottieni una soluzione istantanea del Teorema Cinese del Resto passo dopo passo.
Soluzioni Passo dopo Passo
Vedi ogni inverso modulare, controllo di compatibilità e passo di riduzione spiegati, non solo il residuo finale.
Tutor Matematico IA
Poni domande di follow-up su inversi modulari, moduli coprimi, o perché un sistema non ha soluzione, con risposte adattate al tuo problema esatto.
Materie correlate
Fondamenti di Algebra
La familiarità con frazioni e resti rende l'aritmetica modulare e il Teorema Cinese del Resto molto più facili da imparare.
Calcolatore del Rango di Matrice
Un altro metodo di calcolatore algoritmico e adiacente alla teoria dei numeri — una pratica utile per la stessa mentalità sistematica e passo dopo passo che il TCR richiede.