Aiuto nella dimostrazione del teorema cinese del resto!
Ciao, c'è qualcuno che mi aiuta un po' a capire la dimostrazione di questo teorema?Ci sono parecchi punti che non riesco a capire...
la dimostrazione è la seguente:
Si fissa $M=m_1*m_2*.....m_n$ e analogamente si definiscono degli $M_i = \frac{M}{m_i}$. Ora, siccome $(M_i,m_i) = 1$ $M_i$ ammette un inverso. ovvero vale la relazione $M_i*x_i \cong 1$ mod $m_i$ , da qui moltiplicando per $b_i$ ambo i membri si ha $M_i*x_i*b_* \cong b_i$ mod $m_i$ e fin qui tutto ok.
Ora, si considera $z = sum_{i}M_i*x_i*b_i$ e si dice che questa è la soluzione ma io non capisco perché!
Il libro afferma che, dato un $j$, $z \cong b_j$ mod $j$, in quanto tutti i membri di quella somma si annullano tranne quello di posto $j$ ... ma a sinistra della congruenza c'è una somma, a destra un numero! Io sono sempre stato abituato a una relazione numero $\cong$ numero, questo passaggio quindi mi sembra proprio assurdo!
Poi non capisco ancora...come si mette in relazione quella somma con il sistema di equazioni di partenza?E dove sta scritto che esiste un unica soluzione modulo M?L'M l'abbiamo tirato fuori noi nella dimostrazione...
la dimostrazione è la seguente:
Si fissa $M=m_1*m_2*.....m_n$ e analogamente si definiscono degli $M_i = \frac{M}{m_i}$. Ora, siccome $(M_i,m_i) = 1$ $M_i$ ammette un inverso. ovvero vale la relazione $M_i*x_i \cong 1$ mod $m_i$ , da qui moltiplicando per $b_i$ ambo i membri si ha $M_i*x_i*b_* \cong b_i$ mod $m_i$ e fin qui tutto ok.
Ora, si considera $z = sum_{i}M_i*x_i*b_i$ e si dice che questa è la soluzione ma io non capisco perché!
Il libro afferma che, dato un $j$, $z \cong b_j$ mod $j$, in quanto tutti i membri di quella somma si annullano tranne quello di posto $j$ ... ma a sinistra della congruenza c'è una somma, a destra un numero! Io sono sempre stato abituato a una relazione numero $\cong$ numero, questo passaggio quindi mi sembra proprio assurdo!
Poi non capisco ancora...come si mette in relazione quella somma con il sistema di equazioni di partenza?E dove sta scritto che esiste un unica soluzione modulo M?L'M l'abbiamo tirato fuori noi nella dimostrazione...
Risposte
ti faccio un esempio pratico, supponi di avere 3 equazioni modulari, $i=1,2,3$
Il sistema di equazioni è
$X = b_1 mod m_1$
$X = b_2 mod m_2$
$X = b_3 mod m_3$
la soluzione sarà $X=M_1*x_1*b_1 + M_2*x_2*b_2 + M_3*x_3*b_3$
X risolve la equazione $X=b_1 mod m_1$, infatti il primo termine è $b_1$ dato che $x_1*M_1=1$ essendo $(M_1,m_1)=1$. Il secondo termine di X è $ M_2*x_2*b_2$. $M_2=M/m_2=m_1*m_3$ quindi $ M_2*x_2*b_2=m_1*(m_3*x_2*b_2)=m_1*Q$ dove Q è un numero intero, da cui $ M_2*x_2*b_2=0 mod m_1$. Stesso discorso per il terzo termine. In altre parole quella somma ha tutti i contributi nulli tranne l'i-simo che è $b_i$
Questo discorso lo puoi fare per la seconda e terza equazione modulare. Il passaggio concettuale che devi fare è quello di generalizzare usando gli indici i e j al posto di casi concreti, avrai che, fissato un i, $X=0+0+...+b_i+0+...0$
Per quanto riguarda l'unicità (a meno di congruenza modulo M) della soluzione: sia $X'$ una nuova soluzione, sappiamo che $AAi X-=b_i mod m_i$ cioè $AAi m_i|(X-X')$ (m divide la differenza), quindi essendo $M=m_1*...*m_n$ allora $M|(X-X')$ cioè $X$ e $X'$ sono congrui modulo M
spero di esserti stato utile
Il sistema di equazioni è
$X = b_1 mod m_1$
$X = b_2 mod m_2$
$X = b_3 mod m_3$
la soluzione sarà $X=M_1*x_1*b_1 + M_2*x_2*b_2 + M_3*x_3*b_3$
X risolve la equazione $X=b_1 mod m_1$, infatti il primo termine è $b_1$ dato che $x_1*M_1=1$ essendo $(M_1,m_1)=1$. Il secondo termine di X è $ M_2*x_2*b_2$. $M_2=M/m_2=m_1*m_3$ quindi $ M_2*x_2*b_2=m_1*(m_3*x_2*b_2)=m_1*Q$ dove Q è un numero intero, da cui $ M_2*x_2*b_2=0 mod m_1$. Stesso discorso per il terzo termine. In altre parole quella somma ha tutti i contributi nulli tranne l'i-simo che è $b_i$
Questo discorso lo puoi fare per la seconda e terza equazione modulare. Il passaggio concettuale che devi fare è quello di generalizzare usando gli indici i e j al posto di casi concreti, avrai che, fissato un i, $X=0+0+...+b_i+0+...0$
Per quanto riguarda l'unicità (a meno di congruenza modulo M) della soluzione: sia $X'$ una nuova soluzione, sappiamo che $AAi X-=b_i mod m_i$ cioè $AAi m_i|(X-X')$ (m divide la differenza), quindi essendo $M=m_1*...*m_n$ allora $M|(X-X')$ cioè $X$ e $X'$ sono congrui modulo M
spero di esserti stato utile
Utilissimo, la prima parte me l'hai praticamente chiarita grazie mille! 
La seconda non l'ho capita bene invece...praticamente vogliamo dimostrare la proposizione:
$x'$ soluzione del sistema $\iff x \cong x'$ mod $M$.
La $\leftarrow$ la dimostro facilmente per definizione: se $x$ è soluzione e $x'$ è congruente a $x$ allora anche $x'$ è soluzione.
Nella $\rightarrow$ io so che $x'$ è soluzione, quindi deve valere che $z' \cong b_i$ mod $m_i$, da qui come arrivo a dimostrare che è congruente a $z$ mod $M$? Perché per adesso io so che sono entrambe soluzioni, ma potrebbero essere distinte..il tuo passaggio sul dividere la differenza non mi è molto chiaro..
La seconda non l'ho capita bene invece...praticamente vogliamo dimostrare la proposizione:
$x'$ soluzione del sistema $\iff x \cong x'$ mod $M$.
La $\leftarrow$ la dimostro facilmente per definizione: se $x$ è soluzione e $x'$ è congruente a $x$ allora anche $x'$ è soluzione.
Nella $\rightarrow$ io so che $x'$ è soluzione, quindi deve valere che $z' \cong b_i$ mod $m_i$, da qui come arrivo a dimostrare che è congruente a $z$ mod $M$? Perché per adesso io so che sono entrambe soluzioni, ma potrebbero essere distinte..il tuo passaggio sul dividere la differenza non mi è molto chiaro..
la definizione di congruenza è $ a-=_n b hArr a-b=kn $ con K intero.
Essendo X e X' soluzioni del sistema di equazioni, per ogni i accade che $X-=_(m_i) b_i$ e che $X'-=_(m_i) b_i$. Per la transitività della relazione di congruenza allora $X-=_(m_i) X'$ che, per definizione di congruenza, implica $(X-X')=k*m_i$ per ogni i, ossia $m_i|(X-X')$ per ogni i. M è il prodotto degli $m_i$ divisori di $X-X'$ e (cosa importante) primi tra loro a due a due, quindi anche M divide $X-X'$, da cui la congruenza modulo M fra X e X'
Essendo X e X' soluzioni del sistema di equazioni, per ogni i accade che $X-=_(m_i) b_i$ e che $X'-=_(m_i) b_i$. Per la transitività della relazione di congruenza allora $X-=_(m_i) X'$ che, per definizione di congruenza, implica $(X-X')=k*m_i$ per ogni i, ossia $m_i|(X-X')$ per ogni i. M è il prodotto degli $m_i$ divisori di $X-X'$ e (cosa importante) primi tra loro a due a due, quindi anche M divide $X-X'$, da cui la congruenza modulo M fra X e X'
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo