Sistema di congruenze lineari

[peppe1187]

Ragazzi io ho questo sistema di congruenze lineari:

$\{(2x-=1(mod 3)),(7x-=5(mod 22)):}$

devo controllare se posso applicare il Teorema Cinese del Resto, l'$MCD(3,22)=1$, quindi posso applicarlo.

$N=66$
$N_1=22$
$N_2=3$

e riscrivo il sistema ausiliario:

$\{(22y_1-=1(mod 3)),(3y_2-=1(mod 22)):}$

e calcolo i rispettivi valori di $y_1$ e $y_2$:

$y_1=1 (mod3)$
$y_2=15(mod22)$

ora calcolo il valore di $C=(N_1*b_1*y_1)+(N_2*b_2*y_2)$ dove $b_1$ e $b_2$ sono le congruenze del sistema iniziale che si vogliono verificare.
quindi ho $C=(22*1*1)+(3*5*15)=247$
metto il valore 247 in classe di resto $ZZ_66$ (devo mettere 247 in classe di resto $=N$, giusto!?) e ottengo $[49]_66$ quindi secondo i miei calcoli $x=49+66k$

con $k=0$, $x=49$, la sostituisco nel sistema iniziale e le congruenze non sono verificate!!!

Cosa sbaglio?
Questo sistema è irrisolvibile?

Grazie per le eventuali risposte

[Lorin1]

Premetto che ho fatto l'esame di algebra parecchi mesi fa, ma qualcosina sui sistemi dovrei ricordarla.

Allora, una volta verificato che $(3,22)=1$ andiamo a trovare le soluzioni.

$2x=1(mod 3)$
A suo tempo io ragionavo così: Visto che $mod 3$ ci troviamo in $ZZ_3$, $[2]_3$ è invertibile in questo campo e il suo inverso è proprio $[2]_3$ quindi moltiplico primo e secondo membro per $[2]_3$ e ottengo:

$x=2(mod 3)$ e quindi $x=2$ è soluzione.

$7x=5(mod 22)$
Qui tecnicamente dovrebbe essere un pò più difficile trovare la soluzione, ma se al posto della $x$ io sostituisco $7$ ottengo $49=5 (mod 22)$ ed è soddisfatta l'equazione, quindi $x=7$ è soluzione.

La soluzione finale sarà: $x= 2*22 + 7*3=65$
Quindi l'insieme delle soluzione del sistema sarà: $x=65 +66k$

[hamming_burst]

Ciao, non so che tipo di metodo ti abbiano insegnato per risolvere questo sistema lineare, ma io non lo conosco. Forse è più funzionale il tuo, ma risolvendolo con il metodo che ho imparato trovo un'altra soluzione.
Io provo a proporvi la mia soluzione, è più laboriosa, ma è più facile secondo me.

Per la risoluzione, prima si calcolano separatamente i due sistemi lineari mod n, si trova l'insieme delle soluzioni della prima congruenza, poi la seconda e si risolve il sistema con il teorema cinese del resto.

Prima congruenza:

$ 2x -= 1 mod 3$

Siccome $(2,3)=1 $sono coprimi e 1 divide 1 allora la congruenza è compatibile ed invertibile.

Calcoliamo quindi l'inverso di 2 mod 3 tramite l'algoritmo di Euclide:

$3 = 1*2+1$

quindi riscrivendolo come combinazione lineare:

$1=(1)3+(-1)2$ quindi l'inversa di 2 mod 3 è -1 mod 3, ma il primo esponente positivo è 2, quindi l'inversa è 2 mod 3.

Moltiplicando a destra e sinistra quindi si ha:

$(2)*2x -= (2)*1 mod17$

quindi si ha: $ x-=2mod3 $

Seconda Congruenza:

$ 7x -= 5 mod 22$

Siccome $(7,22)=1 $sono coprimi e 1 divide 5 allora la congruenza è compatibile ed invertibile.

Calcoliamo quindi l'inverso di 7 mod 22 tramite l'algoritmo di Euclide:

$22 = 3*7+1$

quindi riscrivendolo come combinazione lineare:

$1=(1)22+(-3)7$ quindi l'inversa di 7 mod 22 è -3 mod 22, ma il primo esponente positivo è 19, quindi l'inversa è 19 mod 22.

Moltiplicando a destra e sinistra quindi si ha:

$(19)*7x -= (19)*5 mod22$

quindi si ha: $ x-=95mod22 $ semplificandolo si ottiene un sistema equivalente, quindi si ha $ x-=7mod22 $

Il sistema da risolvere quindi diventa: $\{(x-=2mod3),(x-=7 mod 22):}$

Troviamo il MCD tra 3 e 22, $(3,22)=1$ Priviamo che il sistema è compatibile:
$(3,22)$ divide $7-2$
$1$|$5$ OK Quindi per il teorema cinese del resto $Sol=!0 $ Inoltre $7-2=5=5*(3,22)=5⋅1$

Calcolo la soluzione particolare con Euclide:

$ 22 = 7*3+1$ | $ 1 = (1)22 + (-7)3$
$ 3 = 3*1+0$

Quindi:

$7 - 2 = 5 = 5*(3,22) = 5 * ((1)22+(-7)3) = (5)22+(-35)3$
$7 - 2 = (5)22 + (-35)3$
$7 - (5)22 = 2 + (-35)3$
$-103 = -103$

Ne segue che c=-103 è una soluzione particolare.
Calcolo m.c.m:

$[3,22]=(3*22)/((3,22))=66$

$Sol={-103+k[3,22]|kuuZZ}=[-103]_66=[29]_66$

Dovrebbe essere giusto, se trovate errori ditelo.
Spero che i passaggi siano chiari, lo so che è lunga da fare così ma almeno a me vengono sempre. Se hai problemi basta chiedere

Ciao

EDIT:
aggiornate le formule

[Lorin1]

"ham_burst":Ciao, non so che tipo di metodo ti abbiano insegnato per risolvere questo sistema lineare, ma io non lo conosco. Forse è più funzionale il tuo, ma risolvendolo con il metodo che ho imparato trovo un'altra soluzione.
Io provo a proporvi la mia soluzione, è più laboriosa, ma è più facile secondo me.

Per la risoluzione, prima si calcolano separatamente i due sistemi lineari mod n, si trova l'insieme delle soluzioni della prima congruenza, poi la seconda e si risolve il sistema con il teorema cinese del resto.

Prima congruenza:

$ 2x -= 1 mod 3$

Siccome $(2,3)=1 $sono coprimi e 1 divide 1 allora la congruenza è compatibile ed invertibile.

Calcoliamo quindi l'inverso di 2 mod 3 tramite l'algoritmo di Euclide:

$3 = 1*2+1$

quindi riscrivendolo come combinazione lineare:

$1=(1)3+(-1)2$ quindi l'inversa di 2 mod 3 è -1 mod 3, ma il primo esponente positivo è 2, quindi l'inversa è 2 mod 3.

Moltiplicando a destra e sinistra quindi si ha:

$(2)*2x -= (2)*1 mod17$

quindi si ha: $ x-=2mod3 $

Seconda Congruenza:

$ 7x -= 5 mod 22$

Siccome $(7,22)=1 $sono coprimi e 1 divide 5 allora la congruenza è compatibile ed invertibile.

Calcoliamo quindi l'inverso di 7 mod 22 tramite l'algoritmo di Euclide:

$22 = 3*7+1$

quindi riscrivendolo come combinazione lineare:

$1=(1)22+(-3)7$ quindi l'inversa di 7 mod 22 è -3 mod 22, ma il primo esponente positivo è 19, quindi l'inversa è 19 mod 22.

Moltiplicando a destra e sinistra quindi si ha:

$(19)*7x -= (19)*5 mod22$

quindi si ha: $ x-=95mod22 $ semplificandolo si ottiene un sistema equivalente, quindi si ha $ x-=7mod22 $

Il sistema da risolvere quindi diventa: $\{(x-=2mod3),(x-=7 mod 22):}$

Troviamo il MCD tra 3 e 22, $(3,22)=1$ Priviamo che il sistema è compatibile:
$(3,22)$ divide $7-2$
$1$|$5$ OK Quindi per il teorema cinese del resto $Sol=!0 $ Inoltre $7-2=5=5*(3,22)=5⋅1$

Calcolo la soluzione particolare con Euclide:

$ 22 = 7*3+1$ | $ 1 = (1)22 + (-7)3$
$ 3 = 3*1+0$

Quindi:

$7 - 2 = 5 = 5*(3,22) = 5 * ((1)22+(-7)3) = (5)22+(-35)3
$7 - 2 = (5)22 + (-35)3$
$7 - (5)22 = 2 + (-35)3$
$-103 = -103$

Ne segue che c=-103 è una soluzione particolare.
Calcolo m.c.m:

$[3,22]=(3*22)/((3,22))=66$

$Sol={-103+k[3,22]|kuuZZ}=[-103]_66=[29]_66$

Dovrebbe essere giusto, se trovate errori ditelo.
Spero che i passaggi siano chiari, lo so che è lunga da fare così ma almeno a me vengono sempre. Se hai problemi basta chiedere

Ciao

Per quanto riguarda la prima soluzione, alla fine tu usi il teorema di Bezout e l'algoritmo di Euclide. Sono due strade diverse ma che portano allo stesso risultato, forse come dicevi il mio è più veloce. Per quanto riguarda la seconda, fino al calcolo della soluzione (che poi è la stessa) mi trovo, ma non mi trovo con il calcolo delle soluzioni perchè io faccio come dire la moltiplicazione a croce: cioè moltiplico la prima soluzione con il modulo della seconda equazione, e la seconda soluzione con il modulo della prima equazione.

[peppe1187]

Innanzitutto vi ringrazio per le risposte, il metodo di Lorin mi è abbastanza chiaro mentre quello di ham_burst purtroppo non mi è molto chiaro

"Lorin":
Quindi l'insieme delle soluzione del sistema sarà: $x=65 +66k$

si ma queste soluzioni non soddisfano le congruenze iniziali..

"ham_burst":
Calcoliamo quindi l'inverso di 7 mod 22 tramite l'algoritmo di Euclide:

22=3⋅7+1

quindi riscrivendolo come combinazione lineare:

1=(1)22+(-3)7 quindi l'inversa di 7 mod 22 è -3 mod 22, ma il primo esponente positivo è 19, quindi l'inversa è 19 mod 22.

poi non mi è chiaro questo passaggio...


EDIT EDIT:
ho capito l'errore che facevo nel mio metodo risolutivo, il sistema originale:

$\{(2x-=1(mod 3)),(7x-=5(mod 22)):}$

trovando gli inversi di 2 in $ZZ_4$ e 7 in $ZZ_22$ risultava poi:

$\{(x-=2(mod 3)),(x-=7(mod 22)):}$

Applico il mio metodo risolutivo, ossia il Teorema Cinese del Resto:

$N=66$
$N_1=22$
$N_2=3$

riscrivo il sistema ausiliario:

$\{(22y_1-=1(mod 3)),(3y_2-=1(mod 22)):}$

e calcolo i rispettivi valori di $y_1$ e $y_2$:

$y_1=1 (mod3)$
$y_2=15(mod22)$

ora calcolo il valore di $C=(N_1*b_1*y_1)+(N_2*b_2*y_2)$ dove $b_1$ e $b_2$ sono le congruenze del sistema iniziale che si vogliono verificare.

quindi ho $C=(22*2*1)+(3*7*15)=359$

metto il valore 359 in classe di resto $ZZ_66$ e ho come soluzione finale lo stesso valore di ham_burst $[29]_66$ che verifica le congruenze

Grazie!!!!

[pabloleo]

caro peppe1187... i metodi risolutivi sono vari... quelli precedentemente proposti sono poco chiari...