Risoluzione sistemi di congruenze lineari

[merlo]

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!!!!

[Tipper]

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.

[Lord K]

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!

[merlo]

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?

[Lord K]

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?

[merlo]

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?

[Lord K]

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)$

[merlo]

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?

[Stemate]

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