Metodi e tecniche per risolvere le congruenze

Esistono diverse tecniche per risolvere un’equazione di congruenza della forma:

$$ ax \equiv b \pmod{m} $$

Ecco le principali:

Metodo dell’inverso modulo

Se il coefficiente \( a \) è invertibile modulo \( m \), ovvero se \( \gcd(a, m) = 1 \), esiste un inverso moltiplicativo \( a^{-1} \) modulo \( m \). In tal caso, si può moltiplicare entrambi i membri per \( a^{-1} \) per ottenere:

\[
x \equiv a^{-1} b \pmod{m}
\]

L’inverso \( a^{-1} \) può essere calcolato con l’algoritmo esteso di Euclide.

Esempio

Prendo come esempio la congruenza:

\[ 7x \equiv 5 \pmod{13} \]

Verifico se \(7\) è invertibile modulo \(13\)

Un numero è invertibile modulo \(m\) se è coprimo con \(m\), cioè se \(\gcd(7, 13) = 1\).

Poiché \(7\) e \(13\) sono primi tra loro, \(7\) ha un inverso modulo \(13\).

Quindi, posso calcolare l'inverso moltiplicativo di \(7\) modulo \(13\)

L'inverso di \(7\) modulo \(13\) è un numero \(7^{-1}\) tale che:

$$ 7 \cdot 7^{-1} \equiv 1 \pmod{13} $$

Per trovare \(7^{-1}\), uso l'algoritmo esteso di Euclide per risolvere:

\[ 7y \equiv 1 \pmod{13} \]

Scrivo l'identità di Bézout per \(7\) e \(13\):

\[ 13 = 1 \cdot 7 + 6 \]

\[ 7 = 1 \cdot 6 + 1 \]

\[ 6 = 6 \cdot 1 + 0 \]

Retrocedendo:

\[ 1 = 7 - 1 \cdot 6 \]

E sostituendo \(6 = 13 - 1 \cdot 7\):

\[ 1 = 7 - 1 \cdot (13 - 1 \cdot 7) \]

\[ 1 = 7 - 1 \cdot 13 + 1 \cdot 7 \]

\[ 1 = 2 \cdot 7 - 1 \cdot 13 \]

Dunque l'inverso moltiplicativo di 7 modulo 13 è il numero 2.

\[ 7^{-1} \equiv 2 \pmod{13} \]

Una volta trovato l'inverso moltiplicativo, moltiplico entrambi i membri della congruenza iniziale per \(7^{-1} = 2\):

\[ 2 \cdot (7x) \equiv 2 \cdot 5 \pmod{13} \]

\[ (2 \cdot 7)x \equiv 10 \pmod{13} \]

Poiché \(2 \cdot 7 = 14 \equiv 1 \pmod{13}\), ottengo:

\[ x \equiv 10 \pmod{13} \]

Pertanto, la soluzione della congruenza è $ x=10 $

Metodo di riduzione per divisione per il massimo comune divisore

Se \( \gcd(a, m) = d > 1 \), l’equazione ha soluzioni se e solo se \( d \) divide \( b \). In tal caso, si divide tutto per \( d \), ottenendo una congruenza equivalente modulo \( m/d \).

Esempio

Considero la congruenza:

\[ 6x \equiv 9 \pmod{15} \]

Calcolo il massimo comune divisore

\[ \gcd(6, 15) = 3 \]

Poiché \( \gcd(6, 15) \) divide \( 9 \), la congruenza ha soluzioni.

Se invece \( \gcd(6, 15) \) non dividesse \( 9 \), non ci sarebbero soluzioni.

Divido entrambi i termini per \\( \gcd(6, 15) = 3 \)

\[ \frac{6}{3} x \equiv \frac{9}{3} \pmod{\frac{15}{3}} \]

\[ 2x \equiv 3 \pmod{5} \]

In questo modo posso risolvere una congruenza più semplice.

A questo punto cerco l’inverso moltiplicativo di \(2\) modulo \(5\), ovvero un numero \( y \) tale che:

\[ 2y \equiv 1 \pmod{5} \]

Essendo molto semplice, mi basta provare vari valori per trovarlo:

• \( 2 \cdot 1 = 2 \not\equiv 1 \pmod{5} \)
• \( 2 \cdot 2 = 4 \not\equiv 1 \pmod{5} \)
• \( 2 \cdot 3 = 6 \equiv 1 \pmod{5} \)

Quindi, l'inverso di \( 2 \) modulo \( 5 \) è \( 2^{-1} \equiv 3 \pmod{5} \).

Moltiplico entrambi i lati della congruenza per \(3\):

\[ (3 \cdot 2) x \equiv 3 \cdot 3 \pmod{5} \]

\[ 6x \equiv 9 \pmod{5} \]

Poiché \(6 \equiv 1 \pmod{5}\) e \(9 \equiv 4 \pmod{5}\) ottengo:

\[ x \equiv 4 \pmod{5} \]

Questo vuol dire che la congruenza ha infinite soluzioni del tipo

\[ x = 4 + 5k, \quad k \in \mathbb{Z} \]

Tra queste, la soluzione generale della congruenza iniziale è 4:

Metodo della sostituzione

Per piccoli moduli, si può risolvere la congruenza provando i possibili valori di \( x \) (brute force).

Esempio

Considero la congruenza:

\[ 3x \equiv 4 \pmod{7} \]

Poiché il modulo è piccolo (\(7\)), posso provare direttamente i valori \(x = 0, 1, 2, \dots, 6\) e trovare il valore che soddisfa la congruenza.

Calcolo \( 3x \mod 7 \) per diversi valori di \( x \):

• \( x = 0 \Rightarrow 3(0) = 0 \not\equiv 4 \pmod{7} \)
• \( x = 1 \Rightarrow 3(1) = 3 \not\equiv 4 \pmod{7} \)
• \( x = 2 \Rightarrow 3(2) = 6 \not\equiv 4 \pmod{7} \)
• \( x = 3 \Rightarrow 3(3) = 9 \equiv 2 \pmod{7} \)
• \( x = 4 \Rightarrow 3(4) = 12 \equiv 5 \pmod{7} \)
• \( x = 5 \Rightarrow 3(5) = 15 \equiv 1 \pmod{7} \)
• \( x = 6 \Rightarrow 3(6) = 18 \equiv 4 \pmod{7} \) ✅

Ho trovato che \( x = 6 \) soddisfa la congruenza:

\[ 3x \equiv 4 \pmod{7} \]

\[ 3 \cdot 6 \equiv 4 \pmod{7} \]

\[ 18 \equiv 4 \pmod{7} \]

Quindi la soluzione generale della congruenza è $ x=6 $ mentre le altre soluzioni sono $ x = 4 + 7k $ con k intero $ k \in \mathbb{Z} $ .

Metodo di scomposizione del modulo

Quando il modulo \( m \) può essere scomposto in fattori primi \( m = p_1^{k_1} p_2^{k_2} \dots p_n^{k_n} \), si può applicare il Teorema Cinese del Resto per decomporre la congruenza in congruenze modulo i fattori primi di \( m \).

Esempio

Considero la congruenza:

\[ 34x \equiv 12 \pmod{77} \]

Posso scomporre \( 77 \) nei suoi fattori primi:

\[ 77 = 7 \times 11 \]

Quindi posso riscrivere la congruenza come un sistema di congruenze più semplici:

\[ \begin{cases} 34x \equiv 12 \pmod{7} \\ \\ 34x \equiv 12 \pmod{11} \end{cases} \]

A questo punto risolvo le congruenze separate

Sapendo che $ 34 \equiv 6 \pmod{7} $ e $ 12 \equiv 5 \pmod{7} $

\[ \begin{cases} 6x \equiv 5 \pmod{7} \\ \\ 34x \equiv 12 \pmod{11} \end{cases} \]

Inoltre, poiché $ 34 \equiv 1 \pmod{11} $ e $ 12 \equiv 1 \pmod{11} $

\[ \begin{cases} 6x \equiv 5 \pmod{7} \\ \\ x \equiv 1 \pmod{11} \end{cases} \]

Per semplificare ulteriormente $ 6x \equiv 5 \pmod{7} $ trovo l'inverso moltiplicativo $ y=6^{-1} $ ossia quel valore che $ 6 \cdot y \equiv 1 \mod 7 $

• $ 6 \cdot 1 \equiv 6 \mod 7 $
• $ 6 \cdot 2 \equiv 12 \equiv 5 \mod 7 $
• $ 6 \cdot 3 \equiv 18 \equiv 4 \mod 7 $
• $ 6 \cdot 4 \equiv 24 \equiv 3 \mod 7 $
• $ 6 \cdot 5 \equiv 30 \equiv 2 \mod 7 $
• $ 6 \cdot 6 \equiv 36 \equiv 1 \mod 7 $

Quindi, l'inverso moltiplicativo di $ 6 $ è $ y = 6^{-1} = 6 $

Moltiplico entrambi i lati della prima congruenza per l'inverso moltiplicativo $ 6^{-1}=6 $

\[ \begin{cases} 6x \cdot 6 \equiv 5 \cdot 6 \pmod{7} \\ \\ x \equiv 1 \pmod{11} \end{cases} \]

\[ \begin{cases} 36x  \equiv 30 \pmod{7} \\ \\ x \equiv 1 \pmod{11} \end{cases} \]

Sapendo che $ 36 \equiv 1 \pmod{7} $ e $ 30 \equiv 2 \pmod{11} $

\[ \begin{cases} x  \equiv 2 \pmod{7} \\ \\ x \equiv 1 \pmod{11} \end{cases} \]

Ora, cerco un valore di \( x \) che soddisfi entrambe le congruenze. Per farlo, posso esprimere $ x $ in termini della prima congruenza:

\[ x = 2+7k, \quad k \in \mathbb{Z} \]

Sostituisco $ x = 2+7k $ nella seconda congruenza $ x \equiv 1 \pmod{11} $

\[ \begin{cases} x  \equiv 2 \pmod{7} \\ \\ 2+7k \equiv 1 \pmod{11} \end{cases} \]

\[ \begin{cases} x  \equiv 2 \pmod{7} \\ \\ 2+7k -2 \equiv 1 -2 \pmod{11} \end{cases} \]

\[ \begin{cases} x  \equiv 2 \pmod{7} \\ \\ 7k \equiv -1 \pmod{11} \end{cases} \]

Sapendo che $ -1 \equiv 10 \mod 11 $

\[ \begin{cases} x  \equiv 2 \pmod{7} \\ \\ 7k \equiv 10 \pmod{11} \end{cases} \]

Ora per semplificare $ 7k \equiv 10 \pmod{11} $ devo cercare l'inverso moltiplicativo di $ 7 $ ossia quel numero $ 7^{-1} $ tale che $ 7 \cdot 7^{-1} \equiv 1 \mod 11 $

• $ 7 \cdot 1 \equiv 7 \mod 11 $
• $ 7 \cdot 2 \equiv 14 \equiv 4 \mod 11 $
• $ 7 \cdot 3 \equiv 21 \equiv 10 \mod 11 $
• $ 7 \cdot 4 \equiv 28 \equiv 7 \mod 11 $
• $ 7 \cdot 5 \equiv 35 \equiv 2 \mod 11 $
• $ 7 \cdot 6 \equiv 42 \equiv 9 \mod 11 $
• $ 7 \cdot 7 \equiv 49 \equiv 5 \mod 11 $
• $ 7 \cdot 8 \equiv 56 \equiv 1 \mod 11 $

Quindi, l'inverso moltiplicativo $ 7^{-1} = 8 $ perché $ 7 \cdot 8 \equiv 1 \mod 11 $.

Moltiplico entrambi i lati della seconda congruenza per $ 7^{-1} = 8 $

\[ \begin{cases} x  \equiv 2 \pmod{7} \\ \\ 7k \cdot 8 \equiv 10 \cdot 8 \pmod{11} \end{cases} \]

\[ \begin{cases} x  \equiv 2 \pmod{7} \\ \\ 56k  \equiv 80 \pmod{11} \end{cases} \]

Sapendo che $ 56 \equiv 1 \mod 11 $ e $ 80 \equiv 3 \mod 11 $

\[ \begin{cases} x  \equiv 2 \pmod{7} \\ \\ k  \equiv 3 \pmod{11} \end{cases} \]

Questo vuol dire che $ k = 3 + 11 m $ dove $ m \in \mathbb{Z} $

Sostituisco $ k $ nell'equazione che determina la $ x $

\[ x = 2+7k, \quad k \in \mathbb{Z} \]

\[ x = 2 + 7(3+11m) \]

\[ x = 2 + 21 + 77m \]

\[ x = 23 + 77m \]

ovvero

$$ x \equiv 23 \mod 77 $$

Pertanto la soluzione della congruenza iniziale è $ x=23 $

Che è esattamente la soluzione della congruenza iniziale.

Verifica. Sostituisco $ x = 23 $ nella congruenza iniziale \[ 34x \equiv 12 \pmod{77} \] \[ 34 \cdot 23 \equiv 12 \pmod{77} \] \[ 782 \equiv 12 \pmod{77} \] \[ 12 \equiv 12 \pmod{77} \] Il risultato è corretto.

Il metodo di scomposizione mi ha permesso di risolvere la congruenza iniziale \( 34x \equiv 12 \pmod{77} \) decomponendola in due congruenze più semplici e poi ricostruendo la soluzione con il Teorema Cinese del Resto.

Metodo delle potenze successive

Se la congruenza è della forma:

$$ x^k \equiv b \pmod{m} $$

si può risolvere utilizzando il teorema di Eulero-Fermat o metodi specifici come il metodo di Tonelli-Shanks per radici quadrate modulo \( p \).

Ecco i passaggi del metodo delle potenze successive:

1. Si calcola il valore di \( k \) modulo \( \varphi(m) \)
   - Se \( m \) è primo, si usa il teorema di Fermat ovvero \( x^{p-1} \equiv 1 \pmod{p} \).
   - Se \( m \) è composto, si usa il teorema di Eulero, secondo cui: \[
   x^{\varphi(m)} \equiv 1 \pmod{m} \] dove \( \varphi(m) \) è la funzione di Eulero.
2. Si riduce l'esponente \( k \) modulo \( \varphi(m) \)
   - Se \( k \) è grande, si calcola \( k \mod \varphi(m) \) per semplificare la potenza.
3. L’esponenziazione modulare veloce
   - Si calcola \( x^k \) usando l'esponenziazione binaria modulare, un metodo efficiente per calcolare potenze modulari senza dover eseguire moltiplicazioni enormi.
4. Risolvere il problema inverso, se necessario
   - Se l’equazione è nella forma \( x^k \equiv b \pmod{m} \), potrebbe essere necessario trovare il logaritmo discreto o usare algoritmi specializzati come il metodo di Tonelli-Shanks per radici quadrate \( x^2 \equiv b \pmod{p} \) o l'algoritmo di Baby-step Giant-step per trovare \( x \) se \( k \) è grande e \( m \) è primo.

Farò due esempi pratici, nel primo esempio il modulo è un numero primo mentre nel secondo è un numero composto.

Esempio

Devo risolvere la congruenza:

\[ x^5 \equiv 3 \mod{7} \]

Poiché \( m=7 \) è un numero primo, posso usare il teorema di Fermat, che afferma che per ogni numero intero \( a \) non divisibile per \( 7 \):

\[ a^{7-1} = a^6 \equiv 1 \mod{7} \]

Questo significa che qualsiasi numero elevato alla sesta potenza modulo 7 dà sempre 1.

Quindi, qualsiasi esponente può essere ridotto modulo 6 perché, secondo il teorema, le potenze di qualsiasi numero $ a $ modulo 7 si ripetono ogni 6 passi.

Ora devo isolare x, quindi devo "eliminare" l’esponente 5.

Un modo per farlo è trovare l’inverso moltiplicativo dell'esponente $ d=5^{-1} $ di 5 trale che $ 5 \cdot 5^{-1} = 1 $ e moltiplicare entrambi i lati della congruenza.

\[ (x^5)^d \equiv 3^d \mod{7} \]

Quindi, devo trovare l'inverso $ d $

$$ 5d \equiv 1 \mod 6 $$

Nota. Per trovare l'inverso $ d=5^{-1} $ utilizzo il modulo 6 anziché 7 perché dal teorema di Fermat so già che qualsiasi esponente modulo 7 si ripetono ogni 6 passi. Quindi qualsiasi esponente si può ridurre modulo 6.

A questo punto cerco un numero \( d \) tale che: \( 5d \equiv 1 \mod{6} \) tramite l’algoritmo di Euclide esteso.

• $ 5 \cdot 1 = 5 \equiv 5 \mod 6 $
• $ 5 \cdot 2 = 10 \equiv 4 \mod 6 $
• $ 5 \cdot 3 = 15 \equiv 3 \mod 6 $
• $ 5 \cdot 4 = 20 \equiv 2 \mod 6 $
• $ 5 \cdot 5 = 25 \equiv 1 \mod 6 $

Pertanto, l’inverso di 5 modulo 6 è \( 5 \).

Nota. In alternativa avrei potuto trovare l'inverso risolvendo l'equazione diofantea: \[  5d \equiv 1 \mod{6} \] Scrivo il massimo comune divisore con l’algoritmo di Euclide: \[ 6 = 5 \cdot 1 + 1 \] Da cui ricavo: \[ 1 = 6 - 5 \cdot 1 \] Quindi: \[ d \equiv -1 \equiv 5 \mod{6} \] Pertanto, l’inverso di 5 modulo 6 è \( 5 \).

Ora elevo entrambi i lati alla quinta potenza modulo 7:

\[ (x^5)^5 \equiv 3^5 \mod{7} \]

\[ x^{25} \equiv 3^5 \mod{7} \]

A questo punto cerco di ridurre l’esponente \( 25 \) modulo \( 6 \)

Dal teorema di Fermat so che \( x^6 \equiv 1 \mod{7} \).

Quindi, mi basta usare le proprietà delle potenze e riscrivere l'esponente $ 25 = 6 \cdot 4 + 1 $

\[ x^{6 \cdot 4 + 1} \equiv 3^5 \mod{7} \]

\[ (x^6)^4 \cdot x \equiv 3^5 \mod{7} \]

Sapendo che \( x^6 \equiv 1 \mod{7} \).

\[ (1)^4 \cdot x \equiv 3^5 \mod{7} \]

\[ x \equiv 3^5 \mod{7} \]

Ora la congruenza diventa molto semplice da calcolare. Sapendo che $ 3^5 =3^2 \cdot 3^2 \cdot 3 $

\[ x \equiv 3^2 \cdot 3^2 \cdot 3 \mod{7} \]

Poiché \( 3^2 = 9 \equiv 2 \mod 7 \)

\[ x \equiv 2 \cdot 2 \cdot 3 \mod{7} \]

\[ x \equiv 12 \mod{7} \]

\[ x \equiv 5 \mod{7} \]

Quindi, $ x=5 $ è la soluzione della congruenza iniziale.

Nota. In alternativa, poiché i valori sono bassi, avrei anche potuto calcolare direttamente \( x \equiv 3^5 \mod{7} \) sostituendo \( 3^5=243 \) \[ x \equiv 243 \mod{7} \] Poiché \(243 \div 7 = 34 \text{ con resto } 5 \) \[x \equiv 5 \mod{7}\] Il risultato finale è sempre lo stesso.

Esempio 2

In questo esempio devo risolvere la congruenza:

\[ x^5 \equiv 3 \mod{14} \]

Poiché il modulo \( 14 \) è un numero composto \( 14 = 2 \cdot 7 \) devo utilizzare la funzione di Eulero:

\[ \varphi(14) = (2 - 1)(7 - 1) = 1 \times 6 = 6 \]

Quindi, in base al Teorema di Eulero, per ogni numero coprimo con 14:

\[ a^6 \equiv 1 \mod{14} \]

Questo significa che possiamo ridurre gli esponenti modulo 6, perché qualsiasi numero $ a $ nel modulo 14 ha un ciclo di 5 passi.

Per isolare \( x \) elevo entrambi i lati della congruenza per l'inverso moltiplicativo $ d $ dell'esponente 5.

\[ (x^5)^d \equiv 3^d \mod{14} \]

Ora, devo trovare un numero \( d \) tale che \(5d \equiv 1 \pmod{6} \)

- \( 5 \times 1 = 5  \mod{6} \)
- \( 5 \times 2 = 10 \equiv 4 \mod{6} \)
- \( 5 \times 3 = 15 \equiv 3 \mod{6} \)
- \( 5 \times 4 = 20 \equiv 2 \mod{6} \)
- \( 5 \times 5 = 25 \equiv 1 \mod{6} \) ✅

Ho trovato che l'inverso moltiplicativo di \( 5 \) modulo \( 6 \) è \( d = 5 \).

Quindi, elevo entrambi i lati della congruenza alla quinta potenza \( d = 5 \):

\[ (x^5)^5 \equiv 3^5 \mod{14} \]

\[ x^{25} \equiv 3^5 \mod{14} \]

Dal teorema di Eulero so già che \( x^6 \equiv 1 \mod{14} \), quindi possiamo ridurre \( 25 = 6 \cdot 4 + 1 \)

\[ x^{6 \cdot 4 + 1} \equiv 3^5 \mod{14} \]

\[ (x^6)^4 \cdot x \equiv 3^5 \mod{14} \]

\[ (1)^4 \cdot x \equiv 3^5 \mod{14} \]

Ora la congruenza diventa semplicemente:

\[ x \equiv 3^5 \mod{14} \]

Calcolo \( 3^5 \mod 14 \)

\[ x \equiv 243 \mod{14} \]

Sapendo che \( 243 \div 14 = 17 \text{ con resto } 5 \)

\[ x \equiv 5 \mod{14} \]

Ho trovato che la soluzione della congruenza iniziale è x = 5.

Metodo della tabella delle potenze

Utile quando la congruenza coinvolge esponenti, permette di trovare soluzioni per congruenze esponenziali cercando cicli nelle potenze di un numero modulo \( m \).

Metodo di interpolazione per congruenze polinomiali

Per congruenze della forma \( P(x) \equiv 0 \pmod{m} \), si possono usare metodi di interpolazione numerica, riducendole a congruenze modulo fattori primi di \( m \).

E così via.