Sistema di congruenze lineari: Teorema cinese del resto

[Neptune2]

Salve a tutti,
mi sto un pò arabattando sul teorema cinese del resto per trovare le soluzioni di un sistema di congruenze lineari.

Partiamo già dal fatto che non ci ha detto come trasformare un sistema dalla forma:

$\{(a1x -= b1 (mod n1)),(a2x -= b2 (mod n2)):}$

alla forma:

$\{(x -= r1 (mod n1)),(x -= r2 (mod n2)):}$

Tolto questo, passiamo ad un esercizio direttamente nella seconda forma, ovvero:

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

Allora sappiamo che mcd(3,5,7) = 1, quindi c'è una sola soluzione (e già in questa forma qui non saprei dire come si fa a capire se sono compatibili o meno, ma forse se è scritta in questa formula si sa già che lo sono?)

Chiamamo $N$ il prodotto dei moduli, ovvero:

$N= 3*5*7=105$

$N1 = 5*7$
$N2 = 3*7$
$N3 = 3*5$
[ovvero moltiplichiamo i vari moduli tranne quelli nella posizione k-esima per trovare N1,N2,N3]

A questo punto iniziamo a calcolarci la prima congruenza lineare che sarà:

$35*x1 -= 1 (mod 3)$ ovvero dobbiamo trovare questa $x1$

Per farlo ci ricolleghiamo all'equazione diofantea associata che è

$35x+3y = 1$

$mcd (35,3) = 1$ quindi dobbiamo calcolarci l'identità di bezout t.c: $1=35x+3y$

Mi calcolo bezout ed ottengo che:

$1= 35*(-1)+3*(10)$

ovvero $x1 = -1 * c/d$ ove c è il terzo termine dell'equazione diofantea, d è l'mcd, quindi ottengo che $x1 = -1 *1/1 = -1$

$-1$ però non è l'unica soluzione però individua l'unica classe di congruenza di soluzioni essendo che $d=1$ (ove d è l'mcd prima calcolato$.

Ora, per calcolarci la nostra soluzione, che chiamiamo $C$, dobbiamo fare la sommatoria di tutti gli $r_k*N_k*x_k$ o almeno cosi dice la formula che ho sugli appunti.

$N_k$ me la sono calcolata all'inizio;
$x_k$ me la sono appena calcolata;

Quello che non capisco è quella $r_k$ il resto di che cosa sarebbe? ovvero in questa prima congruenza del sistema, la $r_1$ quale sarebbe?
Questo esercizio ce l'ho già svolto dalla professoressa e dice che $r_1 = 2$ ma non si capisce da dove lo tira fuori.

Vi ringrazio in anticipo per la pazienza che state avendo con me in questi giorrni
Neptune.

[Neptune2]

Mi dicono dalla regia che i resti sono da prendere "nella formula iniziale" ovvero rispettivamente $2,3,2$ ?

Ora mi manca solo una regola generale per semplificare un sistema in modo tale da poterci applicare il teorema cinese dei resti.

Ad esempio, mi dite che passaggi devo fare per semplificare il seguente sistema?

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

[Lord K]

Nella seconda equazione quando trovi l'inverso di $2$ ti porti alla forma normale che è:

${(x\equiv4(5)),(x\equiv2^(-1)*3(7)),(x\equiv1(2)):}$

[gladior-votailprof]

Allora capisco la tua preoccupazione anche io sto affrontanto questo argomento. Posso dirti che potresti pure procedere con l'equazioni diofantee, anche perchè non sempre è applicabile questo teorema.
Il teorema cinese del resto è solo una condizione sufficiente per la risolubilità di un sistema , puo anche capitare che esso abbia soluzione anche se i moduli non sono a due a due coprimi.
Se è di tuo interesse posso proporti degli esercizio da me svolti.

[Neptune2]

"Lord K":Nella seconda equazione quando trovi l'inverso di $2$ ti porti alla forma normale che è:

${(x\equiv4(5)),(x\equiv2^(-1)*3(7)),(x\equiv1(2)):}$

Ovviamente la seconda equazione rimance comunue $(mod 7) giusto? ci siamo solo calcolati l'inverso?

xGladior: Certo che possono interessarmi alcuni esercizi svolti, mi porterei solo avanti con i lavori

[Lord K]

Io tendo a scrivere $(n)$ al posto di $(mod n)$

[Neptune2]

Volevo proporvi quest'altro problema, devo risolvere il seguente sistema:

$\{(3x -= 2 (mod 7)),(4x -= (p+8) (mod 6)):}$

La prima congruenza la semplifichiamo facilmente in:

$x -= 3 (mod 7)$

Sulla seconda ho un pò di confusione in testa, perchè la professoressa ha iniziato con un mettodo, poi ha replicato dicendo "che forse era meglio dimostrarla in un'altra maniera" ed in fine l'ha dimostrata con un terzo metodo ancora. Quindi nei miei appunti ho tre metodi che si intrecciano e non ci capisco nulla, e vorrei sapere voi come lo trattereste questo $p+8$

Provo comunque ad abbozzare una soluzione:

Quindi dobbiamo semplificare questa:

$4x -= (p+8) (mod 6)$

Inanzi tutto per vedere se è compatibile ci calcoliamo l'mcd tra il primo membro della congruenza il modulo e dobbiamo vedere se divide il secondo membro della congruenza, ovvero:

$mcd(4,6) = 2$ per essere compatibile $2| p+8$ ovvero $p+8$ deve essere un multiplo di 2 quindi:

$p+8= 2*h$ con $h in ZZ$ per far si che questa congruenza sia compatibile.

Quindi ci riscriviamo la congruenza sostituendo $2*h$ nella nostra formula e abbiamo che:

$4x -= 2*h (mod 6)$

Possiamo dividere tutto per $2$ ed abbiamo:

$2x -= h (mod 3)$

ovvero $3|2x -h$ con $h in ZZ$ e X che non conosciamo.

Prendiamoci quindi una qualsiasi $h$ ad esempio $h = 1$ otteniamo:

$3|2x - 1$ , x allora sarà il più piccolo intero che soddisfa questa formula ovvero $x = -1$

Sostituendolo nella formula avremo quindi che:

$x -= -1 (mod 3)$

Per semplicità dei calcoli vediamo di riportarci ad una congruenza con un numero negativo, ovvero vediamo a cosa è congruo $-1$ tra i numeri positiv ed otteniamo:

$-1 -= r (mod 3)$ ovvero $3| -1 -r$ ovvero $r = 2$

Ovvero $-1 -= 2 (mod 3)$

e quindi possiamo dire per transitività che:

$x -= 2 (mod 3)$ che ne dite? o è sbagliato?