Congruenze lineari
Ciao a tutti,
Ho un problema con le congruenze lineari, ad esempio $ 124x $ congruente $ 17 mod 71$.
In questo caso $MCD (124, 71) = 1$ e quindi dovrei trovare l'inverso di $a mod n$, ma non ne vengo fuori.
Dal mio libro non si capisce e su internet trovo 1000 teoremi, a questo punto vi chiedo: come si risolvono le congruenze lineari?
Grazie!
Ho un problema con le congruenze lineari, ad esempio $ 124x $ congruente $ 17 mod 71$.
In questo caso $MCD (124, 71) = 1$ e quindi dovrei trovare l'inverso di $a mod n$, ma non ne vengo fuori.
Dal mio libro non si capisce e su internet trovo 1000 teoremi, a questo punto vi chiedo: come si risolvono le congruenze lineari?
Grazie!
Risposte
Devi usare l'algoritmo di Euclide generalizzato per esprimere il massimo comun divisore come combinazione lineare di $a$ e $n$. A quel punto, se $mcd(a,n) | c$ (nel tuo caso $c=17$), moltiplichi la combinazione per $\frac{c}{mcd(a,n)}$ e ottieni la combinazione lineare per $c$. In questo modo determini $x$.
Nel tuo caso, con l'algoritmo di euclide generalizzato, si trova che $124 \cdot (-4) + 71 \cdot 7 = 1$ e quindi, moltiplicando per $17$, si ha $124 \cdot (-68) + 71 \cdot 119 = 1$. Ma allora le soluzioni sono $x= -68 + 71k, k \in \mathbb{Z}$ e, riportando il $-68$ tra $0$ e $71$, puoi scrivere: $x = 3 + 71h, h \in \mathbb{Z}$. Scritta sotto forma di congruenza questo vuol dire che: $$x = 3 \mod 71$$
Nel tuo caso, con l'algoritmo di euclide generalizzato, si trova che $124 \cdot (-4) + 71 \cdot 7 = 1$ e quindi, moltiplicando per $17$, si ha $124 \cdot (-68) + 71 \cdot 119 = 1$. Ma allora le soluzioni sono $x= -68 + 71k, k \in \mathbb{Z}$ e, riportando il $-68$ tra $0$ e $71$, puoi scrivere: $x = 3 + 71h, h \in \mathbb{Z}$. Scritta sotto forma di congruenza questo vuol dire che: $$x = 3 \mod 71$$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo