Trovare tutte le soluzioni di una congruenza
Salve ragazzi,
torno oggi con un nuovo quesito e vi ringrazio già da ora per la vostra pazienza.
Assodato che la risoluzione di una congruenza avviene tramite la risoluzione dell'equazione diofantea $ax+by=c$ mi chiedevo, come faccio ad ottenere le altre soluzioni? Esiste un modo semplice per farlo? Grazie!
torno oggi con un nuovo quesito e vi ringrazio già da ora per la vostra pazienza.
Assodato che la risoluzione di una congruenza avviene tramite la risoluzione dell'equazione diofantea $ax+by=c$ mi chiedevo, come faccio ad ottenere le altre soluzioni? Esiste un modo semplice per farlo? Grazie!
Risposte
Un metodo che conosco è questo. Utilizza il lemma di Bezout.
Avendo una congruenza del tipo $ax-=b(modn)$ con $a!=0$ questa si risolve prima di tutto riducendo $a,b$ a modulo $n$
esempio :
una volta ridotto i coefficienti, ti calcoli il massimo comune divisore tra $(a,n)=d$.
Ci sono due casi, se $d|b$ allora la congruenza ammette $d$ soluzioni modulo $n$ e infinite in $ZZ$ . Altrimenti, nessuna. Se $d|b$
Detta $x_0$ una soluzione particolare , tutte le soluzioni in $ZZ$ possibili sono date da $x_k=x_0+k(n/d)$ al variare di $k$ in $ZZ$.
Se le si vogliono modulo $n$ , allora si avranno $d$ soluzioni modulo $n$ e si ottengono detta $x_0$ una soluzione particolare $x_k=x_0+k(n/d)$ con $ k in {0,1,2,...,d-1}$. Se non ti è chiaro il perché chiedi.
Come si trova $x_0$?
dividendo tutto per $d$ ottieni una congruenza del tipo $a/dx-=b/d(modn/d)$
banalmente si ha che $(a/d,n/d)=1$.
E per il lemma di bezout , $EE s,t in ZZ : (a/d)s+(n/d)t=1$
ti calcoli $s$.
Dopodiché una soluzione particolare è data da $x_0=b/d*s$
le altre modulo $n$ si trovano come detto in precedenza.
esempio :
EDIT : Ho aggiustato il messaggio
Avendo una congruenza del tipo $ax-=b(modn)$ con $a!=0$ questa si risolve prima di tutto riducendo $a,b$ a modulo $n$
esempio :
una volta ridotto i coefficienti, ti calcoli il massimo comune divisore tra $(a,n)=d$.
Ci sono due casi, se $d|b$ allora la congruenza ammette $d$ soluzioni modulo $n$ e infinite in $ZZ$ . Altrimenti, nessuna. Se $d|b$
Detta $x_0$ una soluzione particolare , tutte le soluzioni in $ZZ$ possibili sono date da $x_k=x_0+k(n/d)$ al variare di $k$ in $ZZ$.
Se le si vogliono modulo $n$ , allora si avranno $d$ soluzioni modulo $n$ e si ottengono detta $x_0$ una soluzione particolare $x_k=x_0+k(n/d)$ con $ k in {0,1,2,...,d-1}$. Se non ti è chiaro il perché chiedi.
Come si trova $x_0$?
dividendo tutto per $d$ ottieni una congruenza del tipo $a/dx-=b/d(modn/d)$
banalmente si ha che $(a/d,n/d)=1$.
E per il lemma di bezout , $EE s,t in ZZ : (a/d)s+(n/d)t=1$
ti calcoli $s$.
Dopodiché una soluzione particolare è data da $x_0=b/d*s$
le altre modulo $n$ si trovano come detto in precedenza.
esempio :
EDIT : Ho aggiustato il messaggio
Dunque, per risolverla dovrei procedere risolvendo la diofantea ax+ny=b quindi, MCD(a,n) dovrebbe darmi il numero di soluzioni della congruenza, dico bene? verificato ovviamente che MCD(a,n) divida b altrimenti la congruenza non avrebbe soluzioni!
guarda su, penso che sono stato completo adesso 
.
.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo