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
Sono gli inversi moltiplicativi delle relative congruenze algebriche:
$35x -= 1_ (mod_3)$
da cui $3|35x-1$ , $35x-3y=1$ , per $y in ZZ$, che ha soluzione per $x=2$ e $y=23$
$21x -= 1_(mod_5)$
da cui $5|21x-1$ , $21x-5y=1$, per $y in ZZ$, che ha soluzione per $x=1$ e $y=4$
$15x -= 1_(mod_7)$
da cui $7|15x-1$ , $15x-7y=1$ per $y in ZZ$, che ha soluzione per $x=1$ e $y=2$
quindi hai che i rispettivi inversi moltiplicativi sono $l_1=2$, $l_2=1$ e $l_3=1$
$35x -= 1_ (mod_3)$
da cui $3|35x-1$ , $35x-3y=1$ , per $y in ZZ$, che ha soluzione per $x=2$ e $y=23$
$21x -= 1_(mod_5)$
da cui $5|21x-1$ , $21x-5y=1$, per $y in ZZ$, che ha soluzione per $x=1$ e $y=4$
$15x -= 1_(mod_7)$
da cui $7|15x-1$ , $15x-7y=1$ per $y in ZZ$, che ha soluzione per $x=1$ e $y=2$
quindi hai che i rispettivi inversi moltiplicativi sono $l_1=2$, $l_2=1$ e $l_3=1$
ma qui 35x−3y=1 , per y∈Z, che ha soluzione per x=2 e y=23, come calcoli la x? c'è una regola fissa?
Gli elementi invertibili di un gruppo moltiplicativo come $(ZZ_n,*)$ sono quegli elementi
che $AA[a]_n in ZZ_n$ , $EE[x]_n in Z_n$ tali che $[a]_n*[x]_n=[1]_n$
ovvero verificano la congruenza algebrica $ax -= 1_(mod_n)$ che si risolve come ti
ho indicato sopra.
che $AA[a]_n in ZZ_n$ , $EE[x]_n in Z_n$ tali che $[a]_n*[x]_n=[1]_n$
ovvero verificano la congruenza algebrica $ax -= 1_(mod_n)$ che si risolve come ti
ho indicato sopra.
forse credo di aver capito.. senti, non voglio abusa della tua gentilezza, però sei l'unica persona che a luglio mi risponde per darmi chiarimenti 
. Ho svolto un esercizio di cui non ho soluzioni, se lo scrivo tutto qui per intero, saresti così gentile da dirmi se l'ho svolto bene? ti ringrazio in anticipo
. Ho svolto un esercizio di cui non ho soluzioni, se lo scrivo tutto qui per intero, saresti così gentile da dirmi se l'ho svolto bene? ti ringrazio in anticipo
Prova a postarlo, poi vediamo se riesco a darti una mano... studio pure io 
si si se per te è un problema non ti preoccupare, ma se riesci a darmi una mano ne sarei grata. ecco qui l'esercizio:
mediante il teorema cinese del resto si risolva il sistema
{x≡2(mod 3)
{z≡3(mod2)
{x≡4(mod5)
{x≡5(mod 7)
3,2,5,7 sono primi tra loro, quindi il sistema ammette soluzioni
n₁ = 3
n₂ = 2
n₃ = 5
n₄ = 7
n = 3*2*5*7 = 210
n^₁ = 210/3 = 70
n^₂ = 210/2 = 105
n^₃ =210/5 = 42
n^₄ =210/7 = 30
considero:
70z ≡ 1(mod 3) l₁=1
105z ≡ 1(mod 2) l₂=1
42z ≡ 1(mod 5) l₃=3
30z ≡ 1(mod 7) l₄=4
X = 2*70*1 + 3*105*1 + 4*42*3 + 5*30*4 = 1559 (una soluzione del teorema cinese)
1559 + 210k k∈Z
1559 - 7*210 = 89 (è la più piccola soluzione positiva del sistema)
mediante il teorema cinese del resto si risolva il sistema
{x≡2(mod 3)
{z≡3(mod2)
{x≡4(mod5)
{x≡5(mod 7)
3,2,5,7 sono primi tra loro, quindi il sistema ammette soluzioni
n₁ = 3
n₂ = 2
n₃ = 5
n₄ = 7
n = 3*2*5*7 = 210
n^₁ = 210/3 = 70
n^₂ = 210/2 = 105
n^₃ =210/5 = 42
n^₄ =210/7 = 30
considero:
70z ≡ 1(mod 3) l₁=1
105z ≡ 1(mod 2) l₂=1
42z ≡ 1(mod 5) l₃=3
30z ≡ 1(mod 7) l₄=4
X = 2*70*1 + 3*105*1 + 4*42*3 + 5*30*4 = 1559 (una soluzione del teorema cinese)
1559 + 210k k∈Z
1559 - 7*210 = 89 (è la più piccola soluzione positiva del sistema)
Si, $x -= 89_(mod_210)$
"GundamRX91":
Si, $x -= 89_(mod_210)$
mi stai dicendo che l'ho fatto bene!?!?!?!!?!?
"Viir":
[quote="GundamRX91"]Si, $x -= 89_(mod_210)$
mi stai dicendo che l'ho fatto bene!?!?!?!!?!?[/quote]
guarda, non ho controllato proprio tutti i passaggi, però il risultato corrisponde al mio
ahahah, l'ultima domanda, tu le "l" come le calcoli???
io faccio così:
70z ≡ 1(mod 3)
(70 * 1 -1)/3 = 23 quindi l = 1
quindi vado a tentativi, è giusto?
io faccio così:
70z ≡ 1(mod 3)
(70 * 1 -1)/3 = 23 quindi l = 1
quindi vado a tentativi, è giusto?
$70x -= 1_(mod_3)$ cosa significa? Significa che $3|70x-1$ e questo dalla definizione di relazione di congruenza, ok?
Quindi affinchè questa relazione sia verificata $EE y in ZZ$ tale che $70x-1=3y$, da cui $70x-3y=1$
Ora quali sono gli interi $x$ e $y$ che risolvono questa equazione? $x=1$ e $y=13$, dove $x=1$ è l'inverso
moltiplicativo.
Che dici si va a tentativi??
Quindi affinchè questa relazione sia verificata $EE y in ZZ$ tale che $70x-1=3y$, da cui $70x-3y=1$
Ora quali sono gli interi $x$ e $y$ che risolvono questa equazione? $x=1$ e $y=13$, dove $x=1$ è l'inverso
moltiplicativo.
Che dici si va a tentativi??
Devo dare l'esame di algebra a settembre e grazie al vostro post ho realmente compreso questo teorema.
In realtà io l'ho studiato dal Facchini, dove la teoria è svolta solo per 2 equazioni.
Infatti ho preso spunto dagli esercizi proposti da viir e li ho risolti "a tappe": prima ho preso le prime 2 equazioni e
ne ho ricavato una nuova che equivale a entrambe. Poi ho preso questa nuova equazione e l'ho messa a sistema con
la terza equazione e così via. Temo purtroppo che spiegata così sia quasi incomprensibile...
Il senso del mio post è questo, volevo consigliare a viir di provare a risolvere un sistema di sole due equazioni in modo da essere sicura del perchè si calcolano gli inversi moltiplicativi, invece volevo sapere da gundam come si passa da 2 a n equazioni oppure semplicemente un consiglio su dove reperire questa informazione.
ciao, torno a dire, questi post a volte sono meglio dei libri...
In realtà io l'ho studiato dal Facchini, dove la teoria è svolta solo per 2 equazioni.
Infatti ho preso spunto dagli esercizi proposti da viir e li ho risolti "a tappe": prima ho preso le prime 2 equazioni e
ne ho ricavato una nuova che equivale a entrambe. Poi ho preso questa nuova equazione e l'ho messa a sistema con
la terza equazione e così via. Temo purtroppo che spiegata così sia quasi incomprensibile...
Il senso del mio post è questo, volevo consigliare a viir di provare a risolvere un sistema di sole due equazioni in modo da essere sicura del perchè si calcolano gli inversi moltiplicativi, invece volevo sapere da gundam come si passa da 2 a n equazioni oppure semplicemente un consiglio su dove reperire questa informazione.
ciao, torno a dire, questi post a volte sono meglio dei libri...
"dave lizewski":
Devo dare l'esame di algebra a settembre e grazie al vostro post ho realmente compreso questo teorema.
In realtà io l'ho studiato dal Facchini, dove la teoria è svolta solo per 2 equazioni.
Infatti ho preso spunto dagli esercizi proposti da viir e li ho risolti "a tappe": prima ho preso le prime 2 equazioni e
ne ho ricavato una nuova che equivale a entrambe. Poi ho preso questa nuova equazione e l'ho messa a sistema con
la terza equazione e così via. Temo purtroppo che spiegata così sia quasi incomprensibile...
Il senso del mio post è questo, volevo consigliare a viir di provare a risolvere un sistema di sole due equazioni in modo da essere sicura del perchè si calcolano gli inversi moltiplicativi, invece volevo sapere da gundam come si passa da 2 a n equazioni oppure semplicemente un consiglio su dove reperire questa informazione.
ciao, torno a dire, questi post a volte sono meglio dei libri...
eh.. io a tentativi sapevo si faceva... dave lizewski sapresti farmi ogni passaggio x calcolare l'inverso moltiplicativo?
Se non ho capito male, il tuo procedimento è quello che seguo io: posteresti un tuo esempio, giusto per conferma ?
"GundamRX91":
Se non ho capito male, il tuo procedimento è quello che seguo io: posteresti un tuo esempio, giusto per conferma ?
a chi ti stai riferendo Gundam??
"Viir":
[quote="GundamRX91"]Se non ho capito male, il tuo procedimento è quello che seguo io: posteresti un tuo esempio, giusto per conferma ?
a chi ti stai riferendo Gundam??[/quote]
scusa, mi riferivo a dave.... ho risposto dopo di te, ma senza aver visto prima la tua risposta
"GundamRX91":
[quote="Viir"][quote="GundamRX91"]Se non ho capito male, il tuo procedimento è quello che seguo io: posteresti un tuo esempio, giusto per conferma ?
a chi ti stai riferendo Gundam??[/quote]
scusa, mi riferivo a dave.... ho risposto dopo di te, ma senza aver visto prima la tua risposta
[/quote]ah ok xD, comunque aspetto con ansia vostri esempi espliciti
T_T 
viir ti faccio un esempio:
risolvere il seguente sistema cinese di equazioni congruenziali lineari:
$\{(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$
Parto dalla prima equazione e ricavo l'incognita: $x -= 2_(mod_5)$ , $5|x-2$, quindi $EE k in ZZ$ tale che $x-2=5k$ da cui $x=5k+2$
Ora sostituisco la $x$ trovata nella seconda equazione: $5k+2 -= 1_(mod_3)$ da cui $5k -= -1_(mod_3) -= 2_(mod_3)$
Calcolo l'inverso moltiplicativo, che è nella forma $ax -= 1_(mod_n)$: $5k -= 1_(mod_3)$ , $5k-3v=1$ per $v in ZZ$ , che ha soluzione per $k=2, v=3$
quindi $2$ è l'inverso moltiplicativo di $5k -= 2_(mod_3)$ che diventa quindi $k -=4_(mod_3) -= 1_(mod_3)$
Ora ricavo l'incognita $k$: $3|k-1$ , $k-1=3s$ per $s in ZZ$, da cui $k=3s+1$, che sostituisco nella $x$ della prima equazione: $x=5(3s+1)+2=15s+7$
Ora sostituisco la $x$ nella terza equazione: $15s+7 -= 6_(mod_14)$ che equivale a $15s -= 13_(mod_14)$
Calcolo l'inverso moltiplicativo (la faccio breve ehhhh ): $15s-14t=1$ per $t in ZZ$, da cui $s=1, t=1$,
quindi $15s -= 13_(mod_14)$ diventa $s -= 13_(mod_14)$
Ora ricavo l'incognita $s$: $14|s-13$ , $s-13=14t$ per $t in ZZ$ da cui $s=14t+13$, che sostituisco nella $x$ precedente:
$x=15(14t+13)+7=210t+202$ , che sostituisco nell'ultima equazione:
$210t+202 -= 5_(mod_11)$ che è equivalente a $210t -= 1_(mod_11)$
Calcolo l'inverso moltiplicativo (ormai dovreste averlo capito....): $210t-11u=1$ per $u in ZZ$ che ha soluzione per $t=1,u=19$
Quindi $210t -= 1_(mod_11)$ diventa $t -= 1_(mod_11)$ da cui $11|t-1$ , $t-1=11u$ , $t=11u+1$
Sostituisco alla $x$ precedente e ottengo: $x=210(11u+1)+202=2310u+412$
Quindi la nostra soluzione comune è $x -= 412_(mod_2310)$ salvo errori
risolvere il seguente sistema cinese di equazioni congruenziali lineari:
$\{(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$
Parto dalla prima equazione e ricavo l'incognita: $x -= 2_(mod_5)$ , $5|x-2$, quindi $EE k in ZZ$ tale che $x-2=5k$ da cui $x=5k+2$
Ora sostituisco la $x$ trovata nella seconda equazione: $5k+2 -= 1_(mod_3)$ da cui $5k -= -1_(mod_3) -= 2_(mod_3)$
Calcolo l'inverso moltiplicativo, che è nella forma $ax -= 1_(mod_n)$: $5k -= 1_(mod_3)$ , $5k-3v=1$ per $v in ZZ$ , che ha soluzione per $k=2, v=3$
quindi $2$ è l'inverso moltiplicativo di $5k -= 2_(mod_3)$ che diventa quindi $k -=4_(mod_3) -= 1_(mod_3)$
Ora ricavo l'incognita $k$: $3|k-1$ , $k-1=3s$ per $s in ZZ$, da cui $k=3s+1$, che sostituisco nella $x$ della prima equazione: $x=5(3s+1)+2=15s+7$
Ora sostituisco la $x$ nella terza equazione: $15s+7 -= 6_(mod_14)$ che equivale a $15s -= 13_(mod_14)$
Calcolo l'inverso moltiplicativo (la faccio breve ehhhh
): $15s-14t=1$ per $t in ZZ$, da cui $s=1, t=1$, quindi $15s -= 13_(mod_14)$ diventa $s -= 13_(mod_14)$
Ora ricavo l'incognita $s$: $14|s-13$ , $s-13=14t$ per $t in ZZ$ da cui $s=14t+13$, che sostituisco nella $x$ precedente:
$x=15(14t+13)+7=210t+202$ , che sostituisco nell'ultima equazione:
$210t+202 -= 5_(mod_11)$ che è equivalente a $210t -= 1_(mod_11)$
Calcolo l'inverso moltiplicativo (ormai dovreste averlo capito....): $210t-11u=1$ per $u in ZZ$ che ha soluzione per $t=1,u=19$
Quindi $210t -= 1_(mod_11)$ diventa $t -= 1_(mod_11)$ da cui $11|t-1$ , $t-1=11u$ , $t=11u+1$
Sostituisco alla $x$ precedente e ottengo: $x=210(11u+1)+202=2310u+412$
Quindi la nostra soluzione comune è $x -= 412_(mod_2310)$ salvo errori
tu l'MCD come lo calcoli?
tramite l'algoritmo euclideo, perchè?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo