Calcolatore del Teorema Cinese del Resto

Benvenuti nel Calcolatore del Teorema Cinese del Resto, un potente strumento di teoria dei numeri che risolve sistemi di congruenze simultanee utilizzando il Teorema Cinese del Resto (CRT). Sia che tu stia studiando l'aritmetica modulare, preparandoti per gare di matematica, lavorando su problemi di crittografia o esplorando la teoria dei numeri, questo calcolatore fornisce una soluzione completa passo dopo passo con una visualizzazione interattiva che mostra come le classi di congruenza si allineano nella soluzione unica.

Che cos'è il Teorema Cinese del Resto?

Il Teorema Cinese del Resto (CRT) è un risultato fondamentale nella teoria dei numeri che garantisce l'esistenza e l'unicità di una soluzione a un sistema di congruenze simultanee, a condizione che i moduli siano a due a due coprimi. Il teorema fu descritto per la prima volta dal matematico cinese Sunzi (孫子) nella sua opera Sunzi Suanjing (孫子算經) intorno al III secolo d.C.

Formalmente, dato il sistema:

Se tutti i moduli \(m_1, m_2, \ldots, m_k\) sono a due a due coprimi (ovvero, \(\gcd(m_i, m_j) = 1\) per ogni \(i \neq j\)), allora esiste una soluzione unica \(x\) modulo \(M = m_1 \times m_2 \times \cdots \times m_k\).

Come funziona l'algoritmo CRT

La prova costruttiva fornisce l'algoritmo utilizzato da questo calcolatore:

Passaggio 1: Calcolare M

Calcola il prodotto di tutti i moduli:

Passaggio 2: Calcolare ogni Mᵢ

Per ogni congruenza \(i\), calcola \(M_i = M / m_i\). Questo è il prodotto di tutti i moduli eccetto \(m_i\).

Passaggio 3: Trovare gli Inversi Modulari

Per ogni \(i\), trova \(y_i\) tale che \(M_i \cdot y_i \equiv 1 \pmod{m_i}\) utilizzando l'Algoritmo di Euclide Esteso. Poiché \(M_i\) e \(m_i\) sono coprimi (tutti i moduli sono a due a due coprimi), questo inverso esiste sempre.

Passaggio 4: Costruire la Soluzione

La soluzione generale è \(x + k \cdot M\) per ogni intero \(k\), il che significa che la soluzione si ripete ogni \(M\) interi.

Come usare questo calcolatore

1. Inserisci le tue congruenze: Per ogni equazione \(x \equiv a \pmod{m}\), inserisci il resto \(a\) e il modulo \(m\). Inizia con 2 congruenze e clicca su "Aggiungi Congruenza" per aggiungerne altre (fino a 10).
2. Controlla i tuoi moduli: Tutti i moduli devono essere interi positivi ≥ 2 e a due a due coprimi. Il calcolatore lo verifica automaticamente.
3. Clicca su "Risolvi Sistema": Il calcolatore applica l'algoritmo CRT e mostra la soluzione unica insieme ai passaggi dettagliati.
4. Rivedi la visualizzazione: La retta numerica mostra come le classi di congruenza di ogni equazione si intersecano nella soluzione.
5. Verifica: La sezione di verifica conferma che la soluzione soddisfa ogni congruenza originale.

Comprendere i Risultati

• Soluzione Minima Non Negativa (x₀): La soluzione unica nell'intervallo [0, M−1]
• Soluzione Generale: Tutti gli interi della forma x₀ + kM dove k è un intero qualsiasi
• Tabella di Verifica: Conferma x₀ mod mᵢ = aᵢ per ogni congruenza
• Analisi Passo-Passo: Mostra Mᵢ, l'inverso modulare yᵢ e la somma parziale aᵢ·Mᵢ·yᵢ per ogni equazione
• Retta Numerica: Rappresentazione visiva di come le classi di resto si allineano nella soluzione

Applicazioni del Teorema Cinese del Resto

Il Classico Problema di Sunzi

Il problema originale tratto dal Sunzi Suanjing chiede: "Ci sono certe cose il cui numero è sconosciuto. Se le contiamo per tre, ne avanzano due; per cinque, ne avanzano tre; e per sette, ne avanzano due. Quante cose ci sono?"

Questo si traduce in: \(x \equiv 2 \pmod{3}\), \(x \equiv 3 \pmod{5}\), \(x \equiv 2 \pmod{7}\). Usando il CRT, la risposta è x = 23 (e più in generale, 23 + 105k per ogni intero non negativo k).

Quando il CRT non si applica?

• Moduli non coprimi: Se una coppia di moduli condivide un fattore comune maggiore di 1, il CRT standard non garantisce una soluzione. Una soluzione potrebbe comunque esistere se i resti sono compatibili, ma questo calcolatore richiede moduli a due a due coprimi per l'algoritmo standard.
• Singola congruenza: Il CRT richiede almeno 2 congruenze. Una singola congruenza \(x \equiv a \pmod{m}\) ha già la soluzione banale x = a.

Algoritmo di Euclide Esteso

L'Algoritmo di Euclide Esteso è essenziale per il CRT perché trova l'inverso modulare. Dati gli interi \(a\) e \(b\), trova gli interi \(x\) e \(y\) tali che:

Quando \(\gcd(a, b) = 1\), allora \(x\) è l'inverso modulare di \(a\) modulo \(b\), ovvero \(a \cdot x \equiv 1 \pmod{b}\).

Domande Frequenti

Che cos'è il Teorema Cinese del Resto?

Il Teorema Cinese del Resto (CRT) afferma che se si ha un sistema di congruenze simultanee x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₖ (mod mₖ), dove tutti i moduli sono a due a due coprimi, allora esiste un'unica soluzione modulo M = m₁ × m₂ × ... × mₖ. Questo teorema fu descritto per la prima volta dal matematico cinese Sunzi nel III secolo.

Cosa significa 'a due a due coprimi'?

A due a due coprimi significa che ogni coppia di moduli non condivide alcun fattore comune eccetto 1. Ad esempio, {3, 5, 7} sono a due a due coprimi perché mcd(3,5)=1, mcd(3,7)=1 e mcd(5,7)=1. Tuttavia, {4, 6, 5} NON sono a due a due coprimi perché mcd(4,6)=2.

Come si risolve un sistema di congruenze passo dopo passo?

Per risolvere usando il CRT: (1) Verificare che tutti i moduli siano a due a due coprimi. (2) Calcolare M = prodotto di tutti i moduli. (3) Per ogni congruenza, calcolare Mᵢ = M/mᵢ. (4) Trovare l'inverso modulare yᵢ di Mᵢ modulo mᵢ usando l'Algoritmo di Euclide Esteso. (5) Calcolare la soluzione x = Σ(aᵢ × Mᵢ × yᵢ) mod M. La soluzione generale è x + k×M per ogni intero k.

Quali sono le applicazioni del Teorema Cinese del Resto?

Il CRT ha molte applicazioni pratiche: la crittografia RSA lo utilizza per una decrittazione efficiente. L'informatica lo usa per l'aritmetica dei grandi numeri. L'elaborazione dei segnali lo applica nei codici a correzione d'errore. Viene utilizzato anche per problemi di pianificazione e calendari.

Cosa succede se i moduli non sono coprimi?

Se i moduli non sono a due a due coprimi, il CRT standard non si applica direttamente. In alcuni casi, una soluzione può esistere se vengono soddisfatte condizioni di compatibilità (i resti devono essere coerenti modulo il MCD). Altrimenti, il sistema di congruenze è incoerente.

Risorse Aggiuntive

• Teorema Cinese del Resto - Wikipedia
• Algoritmo di Euclide Esteso - Wikipedia
• Aritmetica Modulare - Wikipedia