Sistema di equazioni congruenziali
Non capito come fare il seguente esercizio, so che bisogna applicare il teorema cinese del resto, ma non riesco a trovare una spiegazione che mi soddisfi....
Mi date una mano, con la spiegazione del teorema, poi provo a risolverlo io l'esercizio, che è:
Risolvere in Z:
$\{(xequiv1 mod 4),(xequiv-3 mod 7),(xequiv3 mod 5):} $
**edit avanzamento,
Prima di tutto mi riscrivo il sistema come:
$\{(xequiv1 mod 4),(xequiv4 mod 7),(xequiv3 mod 5):} $
Ora devo trovolare la soluzione di $ (xequiv1 mod 4) $ tramite teorema cinese del resto, giusto? e qui iniziano i problemi!! =( =(
Mi date una mano, con la spiegazione del teorema, poi provo a risolverlo io l'esercizio, che è:
Risolvere in Z:
$\{(xequiv1 mod 4),(xequiv-3 mod 7),(xequiv3 mod 5):} $
**edit avanzamento,
Prima di tutto mi riscrivo il sistema come:
$\{(xequiv1 mod 4),(xequiv4 mod 7),(xequiv3 mod 5):} $
Ora devo trovolare la soluzione di $ (xequiv1 mod 4) $ tramite teorema cinese del resto, giusto? e qui iniziano i problemi!! =( =(
Risposte
la prima congruenza algebrica ha soluzione [tex]x-1=4k[/tex] per [tex]k \in Z[/tex], quindi [tex]x=1+4k[/tex], che sostituita nella seconda congruenza algebrica....
"GundamRX91":
la prima congruenza algebrica ha soluzione [tex]x-1=4k[/tex] per [tex]k \in Z[/tex], quindi [tex]x=1+4k[/tex], che sostituita nella seconda congruenza algebrica....
per ora tutto chiaro.... la seconda equazione se scrivo bene è : $ 1+4kequiv4 mod 7 $ e ottengo che $ x=3k+3 $??
[tex]1+4k \equiv 4_(_m_o_d_7_)[/tex] è giusto, ma dopo quella [tex]x[/tex] da dove salta fuori? La tua incognita e' ancora [tex]k[/tex] ed è su quella che devi ragionare, ma a quel punto devi introdurre il concetto di inverso moltiplicativo....
"GundamRX91":
[tex]1+4k \equiv 4_(_m_o_d_7_)[/tex] è giusto, ma dopo quella [tex]x[/tex] da dove salta fuori? La tua incognita e' ancora [tex]k[/tex] ed è su quella che devi ragionare, ma a quel punto devi introdurre il concetto di inverso moltiplicativo....
Il mio problema è proprio questa fase... è qui che mi blocco con questo tipo di esercizio!
Allora [tex]1+4k \equiv 4 _(_m_o_d_7_)[/tex] diventa [tex]4k \equiv 4-1_(_m_o_d_7_)[/tex], da cui [tex]4k \equiv 3_(_m_o_d_7_)[/tex].
Ti ritrovi quindi ad avere una congruenza algebrica nella forma [tex]ax \equiv b_(_m_o_d_n_)[/tex], ok; siccome il coefficiente dell'incognita è diverso da [tex]1[/tex] allora devi trovare l'inverso moltiplicativo di [tex]4k_(_m_o_d_7_)[/tex], e lo calcoli risolvendo la congruenza [tex]4k \equiv 1_(_m_o_d_7_)[/tex] (che si risolve come hai visto prima....). Trovato l'inverso moltiplicativo puoi semplificare [tex]4k \equiv 3_(_m_o_d_7_)[/tex] ....
Ti ritrovi quindi ad avere una congruenza algebrica nella forma [tex]ax \equiv b_(_m_o_d_n_)[/tex], ok; siccome il coefficiente dell'incognita è diverso da [tex]1[/tex] allora devi trovare l'inverso moltiplicativo di [tex]4k_(_m_o_d_7_)[/tex], e lo calcoli risolvendo la congruenza [tex]4k \equiv 1_(_m_o_d_7_)[/tex] (che si risolve come hai visto prima....). Trovato l'inverso moltiplicativo puoi semplificare [tex]4k \equiv 3_(_m_o_d_7_)[/tex] ....
Però, scusa, quale parte della teoria non ti è chiara?
"GundamRX91":
Però, scusa, quale parte della teoria non ti è chiara?
trovo problemi con l'inverso moltiplicativo a dire il vero...
In pratica te l'ho già indicato come si trova l'inverso moltiplicativo .... Tu sai che un anello [tex]Z_n[/tex] è definito dalle classi dei resti modulo n e alcune di queste classi ammettono l'inverso moltiplicativo (esattamente in numero di [tex]\phi(n)[/tex], la funzione di Eulero). Un elemento [tex][a]_n[/tex] di [tex]Z_n[/tex] ammette inverso moltiplicativo quando esiste un elemento [tex][x]_n[/tex] tale che [tex][a]_n[x]_n=[1]_n[/tex], o equivalentemente quando [tex]ax \equiv 1 _(_m_o_d_n_)[/tex].
ok...quindi l'inverso moltiplicativo di 4 (mod 7) è 2.
Moltiplico entrambi i membri dell'equazione per 2 e ottengo : $k \equiv6(mod7)
quindi $k=6+7z$ con $z \in Z$.
Poi che dovrei fare?? dove dovrei sostituire questo??
Moltiplico entrambi i membri dell'equazione per 2 e ottengo : $k \equiv6(mod7)
quindi $k=6+7z$ con $z \in Z$.
Poi che dovrei fare?? dove dovrei sostituire questo??
Esatto, l'inverso moltiplicativo è [tex]2[/tex]. Ora sostiutisci [tex]k=6+7z[/tex] in [tex]x=1+4k[/tex] e al termine sostituirai la [tex]x[/tex] così trovata nell'ultima congruenza algebrica [tex]x \equiv 3_(_m_o_d_5_)[/tex].
Poi provi a proseguire da solo....
Poi provi a proseguire da solo....
Mi stavo chiedendo... dove applichi il teorema cinese del resto, cioè è l'inversa moltiplicativa? non credo...
Lo applichi esattamente come stai facendo in questo esercizio 
fatto!! $ x = [53] mod 140 $
Si 
Spero di essere stato chiaro, nel caso chiedi pure così ripasso anche io
Spero di essere stato chiaro, nel caso chiedi pure così ripasso anche io
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo