Sistemi di congruenze lineari

[Nikita~27]

Buon pomeriggio,
qualcuno saprebbe dirmi come si passa da un sistema di congruenze lineari come questo

${ ( 2x \equiv 3 (mod 5) ),( 2x ≡ 5 (mod 7) ),( 3x ≡ 2 (mod 13) ):}$

a questo

${ ( x ≡ 4 (mod 5) ),( x ≡ 6 (mod 7) ),(x ≡ 5 (mod 13) ):}$

Mi manca questo passaggio fondamentale che certamente mi sfugge. Grazie.

[Gi81]

E' semplice: in ogni equazione si moltiplicano entrambi i membri per un fattore opportuno, in modo da semplificare la scrittura. E' un po' come quando alle superiori si risolve un'equazione di primo grado: per trovare la soluzione si moltiplica per l'inverso del coefficiente della $x$.
Ad esempio l'equazione $6x= 1$ si risolve moltiplicando ambo i membri per $1/6$.

Qui abbiamo $2x -= 3 (mod 5)$. Dobbiamo moltiplicare per l'inverso di $2$ in $ZZ_5$.
Qual è quel numero che moltiplicato per $2$ dà $1$ in $ZZ_5$? E' $3$. Infatti $2*3=6-=1 (mod 5)$.
Dunque $2x-= 3 (mod 5)=> 3*2 x-=3*3 (mod 5)=> x-=4 (mod 5)$

Analogamente nelle altre due equazioni.

[Nikita~27]

Perdonami, non mi è chiaro il modo con cui trovare l'inverso e come semplificando si possa arrivare a $x≡4(mod5)$.
Potresti spiegarmi per favore?

[Gi81]

Il modo più veloce per trovare l'inverso è ... andare per tentativi
(su campi piccoli, come $ZZ_5$, $ZZ_7$ e $ZZ_{13}$ non ci vuole molto).

Una volta trovato, prendi la tua equazione e moltiplichi ambo i membri per l'inverso che hai trovato.
A sinistra otterrai $1*x$, cioè $x$, a destra devi fare due conti.

Nell'equazione $2x-=3 (mod 5)$ ho trovato l'inverso di $2$ in $ZZ_5$. Non è difficile: è uno tra $1,2,3$ e $4$.
Dato che $2*1=2$,$2*2=4$, $2*3=6-=1$ e $2*4=8-=3$, l'inverso è $3$.

Moltiplico a destra e a sinistra per $3$, ottenendo $6x= 9 (mod 5)$.
Ma, ovviamente, $6-=1 (mod 5)$ e $9-=4 (mod 5)$, dunque l'equazione diventa $x-=4 (mod 5)$

[Nikita~27]

Quindi, prendendo per esempio la seconda congruenza del sistema, e se non ho capito male, dovrebbe accadere una cosa del genere:
$2x≡5(mod7) rArr 4*2x \equiv4*5(mod 7) rArr8x\equiv20(mod7)rArr 8 \equiv1(mod7)^^ 20\equiv6(mod7)rArr$
$rArr x\equiv 6(mod7)$

Corretto?

[Gi81]

Corretto

[Nikita~27]

"Gi8":Corretto

Grazie mille

[Nikita~27]

Ho trovato un sistema in cui è presente questa congruenza:

$2x \equiv 14(mod6)$

Come faccio a trovare l'inversa di $2$ se già $2*3 = 6$?

Ho provato a semplificare tutto per $2$ ottenendo la congruenza $x \equiv 7(mod3)$, ma poi il risultato, dopo aver svolto e applicato il teorema cinese dei resti, non corrisponde a quello indicato... Ho sbagliato a semplificare dividendo per $2$? Se sì, qual è il modo corretto di procedere?

[Gi81]

Dato che $(ZZ_6, *)$ non è un gruppo, non tutti i suoi elementi hanno inverso.

Ma hai risolto bene: $2x-=14 (mod 6)<=> 2x-14=6h <=> 2(x-7)=2*3h<=> x-7=3h <=> x-=7 (mod 3)$.
Non hai sbagliato, è proprio quello il modo di procedere.

[Nikita~27]

Sarà meglio che posti l'intero esercizio, perchè sbaglio sicuramente qualcosa...

${ ( 3x\equiv2(mod5) ),( 2x\equiv14(mod6) ):} rArr { ( x\equiv1(mod5)\ \ \ \ \ \ \M.C.D.(1,5)=1\ \ \ \ \ \ \R_1=3 ),( x\equiv7(mod3)\ \ \ \ \ \ \M.C.D.(1,3)=1 \ \ \ \ \ \ \R_2=5):}$

$3x\equiv1(mod5)\ \ \ \ \ \M.C.D.(5,3)=1$
Dopo aver usato l'algoritmo di Euclide e aver applicato l'identità di Bèzout ottengo
$(10+5h,-5-3h), \ h in mathbb(Z)$ quindi $x_1=10$

$5x\equiv7(mod3)\ \ \ \ \ \M.C.D.(5,3)=1$
Come sopra
$(-3+3h, 6-5h), h in mathbb(Z)$ quindi $x_2=-3$

Le soluzioni congrue del sistema sono $R=3*5=15$
Una soluzione del sistema è $bar(x) = 3*10+5*(-3)=30-15=15$
La più piccola soluzione positiva è $R- bar(x) = 0$

Tutte le soluzioni del sistema sono $0+15h, \ \ \ \ \h in mathbb(Z)$

Mentre ciò che dovrei ottenere è $82+30h$...

[Gi81]

Sbagli nel primo passaggio. $3x-=2 (mod 5)=> x-=4 (mod 5)$.
(tu hai scritto $x-=1 (mod 5)$)

[Gi81]

Ricapitolando, la prima equazione , cioè $3x-=2 (mod 5)$, diventa $x-=4 (mod 5)$.
La seconda equazione, cioè $2x-= 14 (mod 6)$, diventa $x-=7 (mod 3)$, cioè $x-=1 (mod 3)$ (perchè $7-=1 (mod 3)$).

Dunque bisogna risolvere ${(x-=4 (mod 5)),(x-=1 (mod 3)):}$
La soluzione dovrebbe essere $x-=4 (mod 15)$

[Nikita~27]

Grazie, l'ho risolta

[Nikita~27]

Un altro problema...
$6x \equiv 8(mod14)$ divido tutto per $2$ ed ottengo$3x\equiv4(mod7)$. Ma $3$ non ha inverso in $mathbb(Z)_7$... Che si fa?

[Gi81]

Sì che ce l'ha

[Nikita~27]

Ma $3*2=6$, $3*3=9$... Nessuno che mi dia un $8$...

[Nikita~27]

A meno che non debba considerare un numero negativo $-2*3=-6$.
Può essere?

[Gi81]

Non è obbligatorio che dia $8$. Deve dare un numero congruo a $1$ modulo $7$.
$3*5=15-= 1 (mod 7)$.
Anche $-2$ va bene, infatti $-2*3= -6 -= 1 (mod 7)$.

Ora, ne abbiamo trovati due, cioè $-2$ e $5$. L'inverso però deve essere unico.
Però noi non ci facciamo ingannare e notiamo che $-2 -=5 (mod 7)$, dunque tutto torna.

[Nikita~27]

Perchè $−2\equiv5(mod7)$?

[Gi81]

Per definizione

[Nikita~27]

Forse è meglio se imparo il metodo per sostituzione da usare quando le $x$ non sono già nella forma $ax = 1$ asd