Aiuto teorema cinese del resto
Salve a tutti, mi sono appena iscritta a questo forum perchè ho bisogno di aiuto. In realtà avrei bisogno di chiarimenti riguardo un argomento di matematica discreta, ovvero il teorema cinese del resto. Non riesco a capire come faccio a calcolare la soluzione di una singola congruenza. (mi spiace per la richiesta ma purtroppo quando hanno spiegato queste cose io ero in ospedale e quindi ho capito veramente poco circa l'argomento). Ecco la mia richiesta: siccome ho gli appunti della lezione dove sta un esercizio svolto, se lo scrivo, sareste così gentili da chiarirmi le idee? Spero di sì. Ecco l'esercizio svolto dalla professoressa.
(quello riportato qui sotto è un sistema)
{ x ≡ 2 (mod 3)
{ x ≡ 3 (mod 5)
{ x ≡ 2 (mod 7)
Osserviamo che 3, 5, 7 sono primi tra loro e quindi il sistema ammette soluzioni.
n₁= 3
n₂ = 5
n₃ = 7
n = 3 * 5 * 7 = 105
n^₁ = n/n₁ = 105/3 = 35
n^₂ = n/n₂ = 105/5 = 21
n^₃ = n/n₃ = 105/7 = 15
considero:
35z ≡ 1(mod 3) l₁ = 2
21z ≡ 1(mod 5) l₂ = 1
15z ≡ 1(mod 7) l₃ = 1
_
x = 2*35*2 + 3*21*1 + 2*15*1 = 233 (233 soluzione del teorema cinese)
233 + 105k k∈Z
233 - 2 * 105 = 23 (23 è la più piccola soluzione positiva del sistema)
Ecco il mio dubbio.. ho capito come si svolge l'esercizio ma non riesco proprio a capire come faccio a calcolare l₁ l₂ l₃.
Sareste così gentili da aiutarmi?
Vi ringrazio anticipatamente.
(quello riportato qui sotto è un sistema)
{ x ≡ 2 (mod 3)
{ x ≡ 3 (mod 5)
{ x ≡ 2 (mod 7)
Osserviamo che 3, 5, 7 sono primi tra loro e quindi il sistema ammette soluzioni.
n₁= 3
n₂ = 5
n₃ = 7
n = 3 * 5 * 7 = 105
n^₁ = n/n₁ = 105/3 = 35
n^₂ = n/n₂ = 105/5 = 21
n^₃ = n/n₃ = 105/7 = 15
considero:
35z ≡ 1(mod 3) l₁ = 2
21z ≡ 1(mod 5) l₂ = 1
15z ≡ 1(mod 7) l₃ = 1
_
x = 2*35*2 + 3*21*1 + 2*15*1 = 233 (233 soluzione del teorema cinese)
233 + 105k k∈Z
233 - 2 * 105 = 23 (23 è la più piccola soluzione positiva del sistema)
Ecco il mio dubbio.. ho capito come si svolge l'esercizio ma non riesco proprio a capire come faccio a calcolare l₁ l₂ l₃.
Sareste così gentili da aiutarmi?
Vi ringrazio anticipatamente.
Risposte
"GundamRX91":
tramite l'algoritmo euclideo, perchè?
no niente xD mi era venuto un dubbio amletico. Cmq credo di aver capito quanto mi hai spiegato prima. Domani semmai posto il procedimento così vediamo se è uguale
Questo è il mio modo di svolgere il sistema di equazioni lineari proposto da gundam.
Mi sembra molto simile al suo, farò solo qualche commento in più perchè siano chiari i miei ragionamenti
e soprattutto per mettere i riferimenti alla teoria
$\{(x -= 2_(mod_5)),(x -= 1_(mod_3)),(x -= 6_(mod_14)),(x -= 5_(mod_1)):}$
il sistema ammette soluzione in quanto $MCD(5,3,14,11)=1$ e questo è una delle ipotesi richieste dal teorema cinese del resto, cioè che tali numeri siano coprimi.
Parto dalla prima equazione:
(1): $x -= 2_(mod_5) <=> x=2 + 5k $
questa equivalenza segue dalla definizione della congruenza $-=_(5)$
Prendo la seconda equazione:
Sia $x -=_3 1$
$=>2 + 5k -=_3 1 $ : ho sostituito x usando la (1)
$=>5k -=_3 1-2 $ : ho sottratto 2 da entrambi i lati
$=>5k -=_3 -1 $
A questo punto c'è un passaggio interessante. Per risolvere questa equazione devo lavorare con le classi di equivalenza
e quindi osservo che:
$5k -=_3 -1 <=> [5]_3 [k]_3 = [-1]_3 $
Questo segue dalla definizione di classe di equivalenza e dal fatto che le operazioni di somma e prodotto sono compatibili con le classi di equivalenza. A questo punto prendo i rappresentanti canonici per semplificare i calcoli:
$[2]_3 [k]_3 = [2]_3 $
Tutti questo passaggi teorici, compreso quest'ultimo, devono essere chiari per poter proseguire.
A questo punto, osservo che posso scrivere questa uguaglianza:
(2): $[k]_3 = ([2]_3)^(-1) [2]_3 $ : ho moltiplicato entrambi i lati a sx per $([2]_3)^(-1)$
Questo è il passaggio fondamentale: ho potuto fare questa operazione perchè 5 e 3
soddisfano l'ipotesi di essere coprimi e quindi nell'anello $Z_3$ l'elemento $[2]_3$
(che è la stessa cosa di $[5]_3$) è invertibile.
Anche in questo caso la base teorica è essenziale, sopratutto ricordare perchè
in un anello tipo $Z_n$ gli elementi coprimi con n sono invertibili.
A questo punto devo calcolare $([2]_3)^(-1)$ cioè, usando la definizione, devo trovare l'elemento
di $Z_3$ tale che $([2]_3)^(-1) [2]_3 = [1]_3$
Osservo che, in questo particolare caso, questo elemento è proprio lo stesso $[2]_3$, infatti
$[2]_3 [2]_3 = [4]_3 = [1]_3$.
Perciò riprendendo la formula (2) si ottiene
$[k]_3 = ([2]_3)^(-1) [2]_3 = [2]_3 [2]_3 = [1]_3 $
A questo punto ho trovato k, nel senso che tutti gli elementi della classe $[1]_3$
vanno bene e quindi prendo il rappresentante canonico cioè metto k=1.
Sostituisco nella formula (1):
(1): $x=2 + 5k = 2+ 5 = 7$
A questo punto ho trovato x=7, e questo significa che questa x è soluzione della
prima e della seconda equazione, infatti:
$\{(7 -= 2_(mod_5)),(7 -= 1_(mod_3)):}$
Adesso devo ricordare la seconda fondamentale parte del teorema: dato che 7 è una soluzione
del sistema allora tutte le altre soluzioni sono gli elementi della classe di equivalenza
$[7]_{3*5} = [7]_15 $. Infatti anche 22, 37, 42 sono soluzioni delle prime due equazioni.
Allora l'equazione $x-=_15 7$ può sostituire le prime due equazioni e quindi il sistema iniziale è equivalente al sistema
$\{(x -= 7_(mod_15)),(x -= 6_(mod_14)),(x -= 5_(mod_1)):}$
A questo punto ripeto il procedimento su questo nuovo sistema e arrivo alla soluzione.
Io mi fermo qui perchè ci ho messo un bel pò e devo proseguire con lo studio.
Comunque mi rendo conto che questo teorema implica la conoscenza di un bel pò di teoria
e perciò diventerà facile quando sarà assimilata la teoria.
Mi sembra molto simile al suo, farò solo qualche commento in più perchè siano chiari i miei ragionamenti
e soprattutto per mettere i riferimenti alla teoria
$\{(x -= 2_(mod_5)),(x -= 1_(mod_3)),(x -= 6_(mod_14)),(x -= 5_(mod_1)):}$
il sistema ammette soluzione in quanto $MCD(5,3,14,11)=1$ e questo è una delle ipotesi richieste dal teorema cinese del resto, cioè che tali numeri siano coprimi.
Parto dalla prima equazione:
(1): $x -= 2_(mod_5) <=> x=2 + 5k $
questa equivalenza segue dalla definizione della congruenza $-=_(5)$
Prendo la seconda equazione:
Sia $x -=_3 1$
$=>2 + 5k -=_3 1 $ : ho sostituito x usando la (1)
$=>5k -=_3 1-2 $ : ho sottratto 2 da entrambi i lati
$=>5k -=_3 -1 $
A questo punto c'è un passaggio interessante. Per risolvere questa equazione devo lavorare con le classi di equivalenza
e quindi osservo che:
$5k -=_3 -1 <=> [5]_3 [k]_3 = [-1]_3 $
Questo segue dalla definizione di classe di equivalenza e dal fatto che le operazioni di somma e prodotto sono compatibili con le classi di equivalenza. A questo punto prendo i rappresentanti canonici per semplificare i calcoli:
$[2]_3 [k]_3 = [2]_3 $
Tutti questo passaggi teorici, compreso quest'ultimo, devono essere chiari per poter proseguire.
A questo punto, osservo che posso scrivere questa uguaglianza:
(2): $[k]_3 = ([2]_3)^(-1) [2]_3 $ : ho moltiplicato entrambi i lati a sx per $([2]_3)^(-1)$
Questo è il passaggio fondamentale: ho potuto fare questa operazione perchè 5 e 3
soddisfano l'ipotesi di essere coprimi e quindi nell'anello $Z_3$ l'elemento $[2]_3$
(che è la stessa cosa di $[5]_3$) è invertibile.
Anche in questo caso la base teorica è essenziale, sopratutto ricordare perchè
in un anello tipo $Z_n$ gli elementi coprimi con n sono invertibili.
A questo punto devo calcolare $([2]_3)^(-1)$ cioè, usando la definizione, devo trovare l'elemento
di $Z_3$ tale che $([2]_3)^(-1) [2]_3 = [1]_3$
Osservo che, in questo particolare caso, questo elemento è proprio lo stesso $[2]_3$, infatti
$[2]_3 [2]_3 = [4]_3 = [1]_3$.
Perciò riprendendo la formula (2) si ottiene
$[k]_3 = ([2]_3)^(-1) [2]_3 = [2]_3 [2]_3 = [1]_3 $
A questo punto ho trovato k, nel senso che tutti gli elementi della classe $[1]_3$
vanno bene e quindi prendo il rappresentante canonico cioè metto k=1.
Sostituisco nella formula (1):
(1): $x=2 + 5k = 2+ 5 = 7$
A questo punto ho trovato x=7, e questo significa che questa x è soluzione della
prima e della seconda equazione, infatti:
$\{(7 -= 2_(mod_5)),(7 -= 1_(mod_3)):}$
Adesso devo ricordare la seconda fondamentale parte del teorema: dato che 7 è una soluzione
del sistema allora tutte le altre soluzioni sono gli elementi della classe di equivalenza
$[7]_{3*5} = [7]_15 $. Infatti anche 22, 37, 42 sono soluzioni delle prime due equazioni.
Allora l'equazione $x-=_15 7$ può sostituire le prime due equazioni e quindi il sistema iniziale è equivalente al sistema
$\{(x -= 7_(mod_15)),(x -= 6_(mod_14)),(x -= 5_(mod_1)):}$
A questo punto ripeto il procedimento su questo nuovo sistema e arrivo alla soluzione.
Io mi fermo qui perchè ci ho messo un bel pò e devo proseguire con lo studio.
Comunque mi rendo conto che questo teorema implica la conoscenza di un bel pò di teoria
e perciò diventerà facile quando sarà assimilata la teoria.
Dave fondamentalmente usiamo lo stesso metodo e concordo sul fatto che deve essere chiara la teoria. Grazie.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo