Il teorema cinese dei resti (esempio di calcolo)
Un sistema di congruenze lineari nella forma $$ \begin{cases} x ≡ r_1 \mod n_1 \\ x ≡ r_2 \mod n_2 \\ \vdots \\ x ≡ r_n \mod n_n \end{cases} $$ se per ogni i≠j $$ MCD(n_i,n_j)=1 $$ ammette un'unica soluzione x modulo N=n1·n2···nn $$ x = \frac{N}{n_1} x_1 +\frac{N}{n_2} x_2 +...+\frac{N}{n_n} x_n \mod N $$ dove x1, x2, x3 sono le soluzioni del sistema $$ \begin{cases} x ≡ x_1 \frac{N}{n_1} \mod n_1 \\ x ≡ x_2 \frac{N}{n_2} \mod n_2 \\ \vdots \\ x ≡ x_n \frac{N}{n_n} \mod n_n \end{cases} $$
Detto in altri termini, se i moduli delle congruenze lineari del sistema sono coppie di interi coprimi, esiste una soluzione x del sistema ed è unica.
Attenzione. Il teorema cinese dei resti trova la soluzione del sistema del sistema di congruenze lineari soltanto se i moduli sono coprimi tra loro. Se i moduli non sono coprimi, la soluzione va cercata con altri metodi.
Un esempio pratico
Ho il seguente sistema di congruenze lineari
$$ \begin{pmatrix} x ≡ 3 \mod 4 \\ 2x ≡ 1 \mod 3 \\ x ≡ 4 \mod 5 \end{pmatrix} $$
I moduli sono coprimi tra loro.
$$ MCD(4.3) = 1 \\ MCD(4.5) = 1 \\ MCD(3.5) = 1 $$
Quindi, posso applicare il teorema dei resti cinese.
Trasformo il sistema nella forma del sistema equivalente
$$ \begin{pmatrix} x ≡ 3 \mod 4 \\ 2x ≡ 1 \mod 3 \\ x ≡ 4 \mod 5 \end{pmatrix} $$
$$ \begin{pmatrix} x ≡ 3 \mod 4 \\ x ≡ 2 \mod 3 \\ x ≡ 4 \mod 5 \end{pmatrix} $$
- Spiegazione
- Nella prima congruenza x=3 mi permette di soddisfare la congruenza x ≡ 3 mod 4 ossia 3 ≡ 3 mod 4
- Nella seconda congruenza x=2 mi permette di soddisfare la congruenza 2x ≡ 1 mod 3 ossia 2(2) ≡ 1 mod 3 che diventa 4 ≡ 1 mod 3 equivalente a 1 ≡ 1 mod 3
- Nella terza congruenza x=4 mi permette di soddisfare la congruenza x ≡ 4 mod 5 ossia 4 ≡ 4 mod 4
A questo punto calcolo il prodotto dei moduli
$$ N = n_1 \cdot n_2 \cdot n_3 = 4 \cdot 3 \cdot 5 = 60 $$
Sostituisco l'incognita x con la corrispondente espressione (N/ni)xi
$$ \begin{pmatrix} x ≡ 3 \mod 4 \\ x ≡ 2 \mod 3 \\ x ≡ 4 \mod 5 \end{pmatrix} $$
$$ \begin{pmatrix} \frac{N}{n_1} x_1 ≡ 3 \mod 4 \\ \frac{N}{n_2} x_2 ≡ 2 \mod 3 \\ \frac{N}{n_3} x_3 ≡ 4 \mod 5 \end{pmatrix} $$
$$ \begin{pmatrix} \frac{60}{4} x_1 ≡ 3 \mod 4 \\ \frac{60}{3} x_2 ≡ 2 \mod 3 \\ \frac{60}{5} x_3 ≡ 4 \mod 5 \end{pmatrix} $$
$$ \begin{pmatrix} 15 x_1 ≡ 3 \mod 4 \\ 20 x_2 ≡ 2 \mod 3 \\ 12 x_3 ≡ 4 \mod 5 \end{pmatrix} $$
Semplifico le congruenze lineari
$$ \begin{pmatrix} 3 x_1 ≡ 3 \mod 4 \\ 2 x_2 ≡ 2 \mod 3 \\ 2 x_3 ≡ 4 \mod 5 \end{pmatrix} $$
Spiegazione. Il resto di 15 diviso 4 è 3. Il resto di 20 diviso 3 è 2. Il resto di 12 diviso 5 è 2.
Le soluzioni sono x1=1, x2=1, x3=2.
$$ \begin{pmatrix} 3 x_1 ≡ 3 \mod 4 \\ 2 x_2 ≡ 2 \mod 3 \\ 2 x_3 ≡ 4 \mod 5 \end{pmatrix} $$
$$ \begin{pmatrix} 3 (1) ≡ 3 \mod 4 \\ 2 (1) ≡ 2 \mod 3 \\ 2 (2) ≡ 4 \mod 5 \end{pmatrix} $$
$$ \begin{pmatrix} 3 ≡ 3 \mod 4 \\ 2 ≡ 2 \mod 3 \\ 4 ≡ 4 \mod 5 \end{pmatrix} $$
A questo punto posso trovare la soluzione unica dell'intero sistema di congruenze lineari usando la formula
$$ x = \frac{N}{n_1} x_1 + \frac{N}{n_2} x_2 + \frac{N}{n_3} x_3 $$
$$ x = \frac{60}{4} x_1 + \frac{60}{3} x_2 + \frac{60}{5} x_3 $$
$$ x = 15 x_1 + 20 x_2 + 12 x_3 $$
$$ x = 15 (1) + 20 (1) + 12 (2) $$
$$ x = 59 $$
E' la soluzione (x=59) del sistema di congruenze lineari.
Verifica. $$ \begin{pmatrix} x ≡ 3 \mod 4 \\ 2x ≡ 1 \mod 3 \\ x ≡ 4 \mod 5 \end{pmatrix} $$ $$ \begin{pmatrix} 59 ≡ 3 \mod 4 \\ 2(59) ≡ 1 \mod 3 \\ 59 ≡ 4 \mod 5 \end{pmatrix} $$ $$ \begin{pmatrix} 3 ≡ 3 \mod 4 \\ 1 ≡ 1 \mod 3 \\ 4 ≡ 4 \mod 5 \end{pmatrix} $$ La soluzione soddisfa tutte le congruenze lineari del sistema.
Come risolvere una congruenza con il teorema cinese dei resti
Se il modulo \( n \) è un numero composto, posso usare il teorema cinese dei resti per risolvere una congruenza \( a^b \mod n \) scomponendo il modulo nei suoi fattori primi, ossia \( n = p_1 p_2 \dots p_k \).
Questo mi permette di calcolare separatamente \( a^b \) per il modulo di ciascun fattore primo e poi ricostruire la soluzione finale combinando i risultati.
A cosa serve? Questa tecnica di risoluzione delle congruenze è particolarmente utile quando i fattori primi di \( n \) sono piccoli, perché mi facilita i calcoli modulari rispetto a operare direttamente su \( n \).
Esempio
Considero la congruenza
$$ 5^{89} \mod 77 $$
In questo caso il modulo è un numero composto $ 77 = 7 \times 11 $, quindi posso usare il teorema cinese dei resti e calcolare la congruenza \( 5^{89} \) modulo 7 e modulo 11 separatamente.
$$ 5^{89} \mod 7 $$
$$ 5^{89} \mod 11 $$
1] Calcolo di \( 5^{89} \mod 7 \)
Poiché il modulo è un numero primo ( 7 ) posso usare il Piccolo Teorema di Fermat.
$$ a^{p-1} \equiv 1 \mod p $$
Per \( p = 7 \):
$$ 5^6 \equiv 1 \mod 7 $$
Scompongo l'esponente \( 89 \) in multipli di 6 ossia $ 89 = 6 \times 14 + 5 $
Quindi riscrivo la congruenza in questo modo
$$ 5^{89} = (5^6)^{14} \cdot 5^ \mod 7 $$
Poiché \( 5^6 \equiv 1 \mod 7 \), sostituisco \( 5^6 \) con \( 1 \)
$$ 5^{89} \equiv 1^{14} \cdot 5^5 $$
$$ 5^{89} \equiv 5^5 \mod 7 $$
Sapendo che \( 5^2 \equiv 25 \equiv 4 \mod 7 \) e \( 5^5 = 5^2 \cdot 5^2 \cdot 5 \)
$$ 5^{89} \equiv 25 \cdot 5^2 \cdot 5 \mod 7 $$
$$ 5^{89} \equiv 4 \cdot 25 \cdot 5 \mod 7 $$
$$ 5^{89} \equiv 4 \cdot 4 \cdot 5 \mod 7 $$
$$ 5^{89} \equiv 16 \cdot 5 \mod 7 $$
$$ 5^{89} \equiv 2 \cdot 5 \equiv 10 \mod 7 $$
$$ 5^{89} \equiv 3 \mod 7 $$
2] Calcolo di \( 5^{89} \mod 11 \)
Uso di nuovo il Piccolo Teorema di Fermat con \( p = 11 \):
$$ a^{p-1} \equiv 1 \mod p $$
$$ 5^{10} \equiv 1 \mod 11 $$
Scompongo \( 89 \) in multipli di 10 ossia \( 89 = 10 \times 8 + 9 \)
$$ 5^{89} = (5^{10})^8 \cdot 5^9 \mod 11 $$
Poiché \( 5^{10} \equiv 1 \mod 11 \), otteniamo:
$$ 5^{89} \equiv 1^8 \cdot 5^9 \mod 11 $$
$$ 5^{89} \equiv 5^9 \mod 11 $$
Ora calcolo \( 5^9 \mod 11 \) sapendo che $ 5^2 = 25 \equiv 3 \mod 11 $ e $ 5^4 = (5^2)^2 = 3^2 = 9 \mod 11 $
$$ 5^{89} \equiv 5^9 \mod 11 $$
$$ 5^{89} = (5^4)^2 \cdot 5 \mod 11 $$
$$ 5^{89} = 9^2 \cdot 5 \mod 11 $$
$$ 5^{89} = 81 \cdot 5 \equiv 4 \cdot 5 \mod 11 $$
$$ 5^{89} = 20 \equiv 9 \mod 11 $$
$$ 5^{89} \equiv 9 \mod 11 $$
3] Ricostruzione con il Teorema Cinese dei Resti
Metto i due risultati in un sistema
\[
\begin{cases}
x \equiv 3 \mod 7 \\
x \equiv 9 \mod 11
\end{cases}
\]
Poi, in base alla prima congruenza $ x \equiv 3 \mod 7 $, scrivo \( x \) nella forma:
$$ x = 7k + 3 $$
Sostituisco $ x $ nella seconda congruenza:
$$ 7k + 3 \equiv 9 \mod 11 $$
$$ 7k + 3 - 3 \equiv 9 - 3 \mod 11 $$
$$ 7k \equiv 6 \mod 11 $$
Trovo l'inverso moltiplicativo di \( 7 \) modulo \( 11 \), cioè il numero \( m \) tale che $ m \equiv 1 \mod 11 $
$$ 7 \cdot 1 = 7 \equiv 7 \mod 11 $$
$$ 7 \cdot 2 = 14 \equiv 3 \mod 11 $$
$$ 7 \cdot 3 = 21 \equiv 10 \mod 11 $$
$$ 7 \cdot 4 = 28 \equiv 6 \mod 11 $$
$$ 7 \cdot 5 = 35 \equiv 2 \mod 11 $$
$$ 7 \cdot 6 = 42 \equiv 9 \mod 11 $$
$$ 7 \cdot 7 = 49 \equiv 5 \mod 11 $$
$$ 7 \cdot 8 = 56 \equiv 1 \mod 11 $$
Quindi, l'inverso moltiplicativo è $ 7^{-1} \equiv 8 \mod 11 $
Nota. In altre situazioni, se il calcolo diventa troppo complesso, posso cercare l'inverso moltiplicativo usando l'algoritmo euclideo esteso.
Moltiplichiamo entrambi i lati per 8:
$$ k \equiv 6 \cdot 8 \equiv 48 \equiv 4 \mod 11 $$
Sostituisco \( k = 4 \) in \( x = 7k + 3 \):
$$ x = 7(4) + 3 = 28 + 3 = 31 $$
Quindi il risultato corretto è:
$$ 5^{89} \equiv 31 \mod 77 $$
E così via.
