Risoluzione sistemi di congruenze lineari
Salve a tutti, sono nuovo e spero di non aver cannato sezione al primo topic!!
Qualcuno potrebbe spiegarmi passo dopo passo come risolvere il seguente sistema di congruenze?
3x=1mod10
4x=2mod7
Poi tutti gli altri sistemi si risolvono nella stessa maniera vero?
Grazie anticipatamente!!!!
Qualcuno potrebbe spiegarmi passo dopo passo come risolvere il seguente sistema di congruenze?
3x=1mod10
4x=2mod7
Poi tutti gli altri sistemi si risolvono nella stessa maniera vero?
Grazie anticipatamente!!!!
Risposte
Per risolvere la prima congruenza ti basta trovare l'inverso moltiplicativo di $3$ modulo $10$. In generale si usa l'identità di Bezout, in questo caso si può andare a tentativi, e osservare che $3 \cdot 7 = 21 \equiv 1 \mod 10$, quindi $7$ è l'inverso moltiplicativo di $3$ modulo $10$. Moltiplicando per $7$ si ottiene dunque
$x \equiv 7 \mod 10$
Per risolvere la seconda puoi ragionare analogamente.
$x \equiv 7 \mod 10$
Per risolvere la seconda puoi ragionare analogamente.
Infatti hai che:
${(3x\equiv 1(10)),(4x\equiv2(7)):} Rightarrow {(x\equiv 7(10)),(x\equiv4(7)):}$
E da qui procedi con il teorema cinese del resto!
${(3x\equiv 1(10)),(4x\equiv2(7)):} Rightarrow {(x\equiv 7(10)),(x\equiv4(7)):}$
E da qui procedi con il teorema cinese del resto!
Grazie per le risposte!!! 
...Purtroppo non ci ho capito niente!!! Conosco il teorema cinese del resto ma non so applicarlo!!!!una spiegazione un pò più terra terra?
...Purtroppo non ci ho capito niente!!! Conosco il teorema cinese del resto ma non so applicarlo!!!!una spiegazione un pò più terra terra?
Ordunque:
${(3x\equiv 1(10)),(4x\equiv2(7)):} Rightarrow {(x\equiv 7(10)),(x\equiv4(7)):}$
qui per arrivare da sinistra a destra ho moltiplicato per gli inversi, che notoriamente si trovano mediante la divisione di Euclide estera (detta anche teorema di Bezout), ovvero:
$3*7-10*2=1 Rightarrow 3*7 \equiv 1(10)$
ed anche:
$4*2-7*1=1 Rightarrow 4*2 \equiv 1 (7)$
Da qui andiamo al sistema:
${(x\equiv 7(10)),(x\equiv4(7)):}$
Per risolverlo procediamo come segue, sia $N=10*7$ e abbiamo $n_1=N/10 = 7$, $n_2=N/7=10$ per usare il teorema cinese del resto deve essere $gcd(10,7)=1$, allora per bezout abbiamo che tra $n_1, n_2$:
$s_10*n_1 + r_10*10 =1$
$3*7 - 10*2 =1$
ed anche:
$s_7*n_1 + r_7*7 =1$
$3*7 - 10*2 =1$
Denominiamo:
$e_i=n_i*s$
ovvero nel nostro caso:
$e_1=21$
$e_2=-20$
allora la soluzione al problema è:
$x= 21*7+4*(-20)=67 mod(70)$
infatti:
$67 \equiv 7(10)$
$67 \equiv 4(7)$.
Tutto chiaro?
${(3x\equiv 1(10)),(4x\equiv2(7)):} Rightarrow {(x\equiv 7(10)),(x\equiv4(7)):}$
qui per arrivare da sinistra a destra ho moltiplicato per gli inversi, che notoriamente si trovano mediante la divisione di Euclide estera (detta anche teorema di Bezout), ovvero:
$3*7-10*2=1 Rightarrow 3*7 \equiv 1(10)$
ed anche:
$4*2-7*1=1 Rightarrow 4*2 \equiv 1 (7)$
Da qui andiamo al sistema:
${(x\equiv 7(10)),(x\equiv4(7)):}$
Per risolverlo procediamo come segue, sia $N=10*7$ e abbiamo $n_1=N/10 = 7$, $n_2=N/7=10$ per usare il teorema cinese del resto deve essere $gcd(10,7)=1$, allora per bezout abbiamo che tra $n_1, n_2$:
$s_10*n_1 + r_10*10 =1$
$3*7 - 10*2 =1$
ed anche:
$s_7*n_1 + r_7*7 =1$
$3*7 - 10*2 =1$
Denominiamo:
$e_i=n_i*s$
ovvero nel nostro caso:
$e_1=21$
$e_2=-20$
allora la soluzione al problema è:
$x= 21*7+4*(-20)=67 mod(70)$
infatti:
$67 \equiv 7(10)$
$67 \equiv 4(7)$.
Tutto chiaro?
Allora in linea di massima ho capito e sto provando a risolvere l'esercizio da me...però non mi tornano i conti con il teorema di bezout della prima congruenza...
3x=1mod10
10=3*3+1
o no?
e allora il 7 da dove viene?
3x=1mod10
10=3*3+1
o no?
e allora il 7 da dove viene?
Hai ragione!
$10=3*3+1$
in modulo però hai che:
$3*3+1 \equiv 0(10)$
Allora:
$-3*3\equiv 1 (10)$
ovvero che $-3$ è l'inverso che cerchi, ovvero $7$ visto che $-3\equiv 7(10)$
$10=3*3+1$
in modulo però hai che:
$3*3+1 \equiv 0(10)$
Allora:
$-3*3\equiv 1 (10)$
ovvero che $-3$ è l'inverso che cerchi, ovvero $7$ visto che $-3\equiv 7(10)$
Dunque leggendo dal mio libro la risoluzione dell'esercizio dice questo...
Essendo (10,7)=1 il sistema ammette soluzioni e tali soluzioni possono essere calcolate con il seguente modo: si calcolano le soluzioni delle singole congruenze ciascuna moltiplicata per il prodotto di tutti i moduli tranne quello relativo alla congruenza in questione; la soluzione modulo il prodotto dei moduli risulterà essere la somma di tali soluzioni, ciascuna moltiplicata per il prodotto dei moduli delle altre.
Nel nostro caso quindi abbiamo
7*3x=1 mod10 10*4x=2mod7
che equivalgono a
x=1mod10 -2x=2mod7
per la prima ci sono...ma la seconda?
Essendo (10,7)=1 il sistema ammette soluzioni e tali soluzioni possono essere calcolate con il seguente modo: si calcolano le soluzioni delle singole congruenze ciascuna moltiplicata per il prodotto di tutti i moduli tranne quello relativo alla congruenza in questione; la soluzione modulo il prodotto dei moduli risulterà essere la somma di tali soluzioni, ciascuna moltiplicata per il prodotto dei moduli delle altre.
Nel nostro caso quindi abbiamo
7*3x=1 mod10 10*4x=2mod7
che equivalgono a
x=1mod10 -2x=2mod7
per la prima ci sono...ma la seconda?
Non riesco a capire come risolvere questo sistema di congruenza. In quanto il teorema del resto cinese non lo posso applicare perché gli ideali non sono a due a due coprirmi. Come posso fare a risolverlo?
Grazie mille in anticipo
X=32 mod 49
X=4 mod 21
X=3 mod 17
Grazie mille in anticipo
X=32 mod 49
X=4 mod 21
X=3 mod 17
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo