Esercizio sistema di congruenze
Ho un sistema di due congruenze, il seguente:
x = 4 mod 6
x = 2 mod 5
Io l'ho risolto in questo modo:
4+6k = 2 mod 5
6k = -2 mod 5
-k = 2 mod 5 ---> k = -2 mod 5
4+6*(-2) uguale -8 ed è una soluzione particolare
Tutte le soluzioni sarebbero:
{-8+30s | s appartenente a Z}
E' sbagliata? Perchè come soluzione corretta a me darebbero 22+30s
Dov'è che sbaglio?
Grazie.
x = 4 mod 6
x = 2 mod 5
Io l'ho risolto in questo modo:
4+6k = 2 mod 5
6k = -2 mod 5
-k = 2 mod 5 ---> k = -2 mod 5
4+6*(-2) uguale -8 ed è una soluzione particolare
Tutte le soluzioni sarebbero:
{-8+30s | s appartenente a Z}
E' sbagliata? Perchè come soluzione corretta a me darebbero 22+30s
Dov'è che sbaglio?
Grazie.
Risposte
Conosci il teorema cinese del resto? Se sì applicando quello i sistemi si risolvono semplicemente!
Infatti:
${(x \equiv 4(6)),(x \equiv 2(5)):}$
Osserva preliminarmante che: $1*6+(-1)*5 = 1$
Allora osserviamo che:
$e_1=-5 = (-1)*5$
$e_2=6=1*6$
da cui:
${(e_1 \equiv 1(6)),(e_1 \equiv 0(5)):}$
ed analogamente:
${(e_2 \equiv 0(6)),(e_2 \equiv 1(5)):}$
se prendiamo come soluzione:
$x=4*e_1+2*e_2=4*(-5)+2*6=-8$
otteniamo ciò che cerchiamo modulo $30$. Come hai trovato tu! il punto è che $-8$ e $22$ sono la stessa classe resto modulo $30$
Non sbagli di certo!!!
Infatti:
${(x \equiv 4(6)),(x \equiv 2(5)):}$
Osserva preliminarmante che: $1*6+(-1)*5 = 1$
Allora osserviamo che:
$e_1=-5 = (-1)*5$
$e_2=6=1*6$
da cui:
${(e_1 \equiv 1(6)),(e_1 \equiv 0(5)):}$
ed analogamente:
${(e_2 \equiv 0(6)),(e_2 \equiv 1(5)):}$
se prendiamo come soluzione:
$x=4*e_1+2*e_2=4*(-5)+2*6=-8$
otteniamo ciò che cerchiamo modulo $30$. Come hai trovato tu! il punto è che $-8$ e $22$ sono la stessa classe resto modulo $30$
Non sbagli di certo!!!
Cavolo! E' vero! 
Come ho fatto a non vederlo subito?!
Comunque, si, lo conosco il teorema cinese del resto.. solamente che per sistemi a due congruenze mi è stato insegnato che si può risolvere anche nel modo che ho scritto sopra solamente che ero io che a colpo d'occhio sono rimasto cieco al fatto che modulo 30 -8 e 22 sono la stessa cosa.
Grazie in ogni caso per la spiegazione
Come ho fatto a non vederlo subito?!Comunque, si, lo conosco il teorema cinese del resto.. solamente che per sistemi a due congruenze mi è stato insegnato che si può risolvere anche nel modo che ho scritto sopra
solamente che ero io che a colpo d'occhio sono rimasto cieco al fatto che modulo 30 -8 e 22 sono la stessa cosa.Grazie in ogni caso per la spiegazione
Avrei un'altra domanda però.
Applicando il teorema cinese al seguente sistema:
$\{(x-=8 mod5),(x-=9 mod6 ),(x-=10 mod7):}$
dovrei calcolare gli inversi di:
$6*7$ mod 5
$5*7$ mod 6
$6*5$ mod 7
Nel caso uno avesse un sistema più "complicato" e non riuscisse a trovare a colpo d'occhio gli inversi, che metodo può utilizzare per trovarli?
Grazie ancora!
Applicando il teorema cinese al seguente sistema:
$\{(x-=8 mod5),(x-=9 mod6 ),(x-=10 mod7):}$
dovrei calcolare gli inversi di:
$6*7$ mod 5
$5*7$ mod 6
$6*5$ mod 7
Nel caso uno avesse un sistema più "complicato" e non riuscisse a trovare a colpo d'occhio gli inversi, che metodo può utilizzare per trovarli?
Grazie ancora!
Osserva che parti con il calcolo di $N=5*6*7$
Poi trovi i vari:
$N_1=N/5=42$
$N_2=N/6=35$
$N_3=N/7=30$
da qui parti sapendo che $gcd(42,5)=1$ e calcoli $a,b in ZZ$ tale che:
$42*(-2)+5*(13)=1$
quindi:
$-84 \equiv 1 (5)$
$-84 \equiv 0 (6)$
$-84 \equiv 0 (7)$
analogamente calcolo da $gcd(35,6)=1 Rightarrow 35*(-1)+6*6=1$:
$-35 \equiv 0 (5)$
$-35 \equiv 1 (6)$
$-35 \equiv 0 (7)$
ed anche da $gcd(30,7)=1 Rightarrow 30*(-3)+7*13=1$:
$-90 \equiv 0 (5)$
$-90 \equiv 0 (6)$
$-90 \equiv 1 (7)$
La soluzione finale è dunque:
$(-84)*8 + (-35)*9 + (-90)*10 \equiv -1659 \equiv -189 \equiv 21 (210)$
Come vedi il modo per calcolare gli inversi è eseguire il calcolo dei coeffienti di Bezout. Osserva che nella tua formulazione hai invertito i termini di calcolo e quindi confuso i conti...
Poi trovi i vari:
$N_1=N/5=42$
$N_2=N/6=35$
$N_3=N/7=30$
da qui parti sapendo che $gcd(42,5)=1$ e calcoli $a,b in ZZ$ tale che:
$42*(-2)+5*(13)=1$
quindi:
$-84 \equiv 1 (5)$
$-84 \equiv 0 (6)$
$-84 \equiv 0 (7)$
analogamente calcolo da $gcd(35,6)=1 Rightarrow 35*(-1)+6*6=1$:
$-35 \equiv 0 (5)$
$-35 \equiv 1 (6)$
$-35 \equiv 0 (7)$
ed anche da $gcd(30,7)=1 Rightarrow 30*(-3)+7*13=1$:
$-90 \equiv 0 (5)$
$-90 \equiv 0 (6)$
$-90 \equiv 1 (7)$
La soluzione finale è dunque:
$(-84)*8 + (-35)*9 + (-90)*10 \equiv -1659 \equiv -189 \equiv 21 (210)$
Come vedi il modo per calcolare gli inversi è eseguire il calcolo dei coeffienti di Bezout. Osserva che nella tua formulazione hai invertito i termini di calcolo e quindi confuso i conti...
Tutto chiaro. Adesso ho capito. Grazie mille! 
Di nulla e auguri di buon anno!
Non capisco come faccio a fare tutta questa confusione
Ho un altro piccolo problemino.
Per consolidare bene il metodo di risoluzione ho affrontato altri esercizietti facili dicendo "Ma va, mi devon tornare subito!" tipo questo:
$\{(x-=5 mod10),(x-=7 mod11):}$
ed ho risolto così:
5+10k $-=$ 7 mod 11
10k $-=$ 2 mod 11
-k$-=$ -2 mod11
k $-=$ 2 mod 11
5+(10*2) = -15
tutte le soluzioni sarebbero:
-15+ 110s s appartenente a Z
La soluzione dovrebbe essere 95. Ma 95 e -15 sono la stessa cosa modulo 110 o erro?
Perchè c'è 'sto problema sul cambio di segno? perchè se cambio il segno sia a k che al due per far diventare k positivo la soluzione non torna.. ma se lascio tutto col segno meno davanti si..
dove sta l'inghippo?
Non capisco come mai mi incasino su queste sciocchezze..
Grazie ancora per l'infinita pazienza!
EDIT:
E questo:
$\{(x-=7 mod12),(x-=4 mod5):}$
Che mi torna -65 invece dovrebbe tornare 19. Ho anche cercato bene l'inverso utilizzando bezou per non sbagliarmi.. e nonostante tutto non mi torna
Ho un altro piccolo problemino.
Per consolidare bene il metodo di risoluzione ho affrontato altri esercizietti facili dicendo "Ma va, mi devon tornare subito!" tipo questo:
$\{(x-=5 mod10),(x-=7 mod11):}$
ed ho risolto così:
5+10k $-=$ 7 mod 11
10k $-=$ 2 mod 11
-k$-=$ -2 mod11
k $-=$ 2 mod 11
5+(10*2) = -15
tutte le soluzioni sarebbero:
-15+ 110s s appartenente a Z
La soluzione dovrebbe essere 95. Ma 95 e -15 sono la stessa cosa modulo 110 o erro?
Perchè c'è 'sto problema sul cambio di segno? perchè se cambio il segno sia a k che al due per far diventare k positivo la soluzione non torna.. ma se lascio tutto col segno meno davanti si..
dove sta l'inghippo?
Non capisco come mai mi incasino su queste sciocchezze..
Grazie ancora per l'infinita pazienza!
EDIT:
E questo:
$\{(x-=7 mod12),(x-=4 mod5):}$
Che mi torna -65 invece dovrebbe tornare 19. Ho anche cercato bene l'inverso utilizzando bezou per non sbagliarmi.. e nonostante tutto non mi torna
"SickBoy88":
Non capisco come faccio a fare tutta questa confusione
Ho un altro piccolo problemino.
Per consolidare bene il metodo di risoluzione ho affrontato altri esercizietti facili dicendo "Ma va, mi devon tornare subito!" tipo questo:
$\{(x-=5 mod10),(x-=7 mod11):}$
ed ho risolto così:
5+10k $-=$ 7 mod 11
10k $-=$ 2 mod 11
Da qui al punto sotto come passi??
-k$-=$ -2 mod11
k $-=$ 2 mod 11
5+(10*2) = -15
tutte le soluzioni sarebbero:
-15+ 110s s appartenente a Z
La soluzione dovrebbe essere 95. Ma 95 e -15 sono la stessa cosa modulo 110 o erro?
I due numeri sono comunque congruenti, infatti:
$95-(-15)=1*110$
Il secondo esercizio:
$N=12*5=60$
Osserva che:
$12*(-2)+5*5 =1$
$-24 \equiv 1(5)$
$-24 \equiv 0(12)$
Analogamente:
$25 \equiv 0(5)$
$25 \equiv 1(12)$
La soluzione è dunque:
$-24*4+7*25=79(60) \equiv 19(60) \equiv -41(60)$
Ah ok, ora mi torna. Grazie!
Da quel punto a quello sotto ci passavo in quanto 10 è congruo a -1 modulo 11 e quindi mettevo -1 al posto di 10 e moltiplicavo -1 l'altro membro..
Sbagliavo?
Da quel punto a quello sotto ci passavo in quanto 10 è congruo a -1 modulo 11 e quindi mettevo -1 al posto di 10 e moltiplicavo -1 l'altro membro..
Sbagliavo?
Sì, mettere $-1$ al posto di $10$ non cambia nulla...
$10k \equiv -k(11)$
ma da qui:
$-k \equiv 2(11)$
$k \equiv 9(11)$
ed arrivi al fantomatico $95$
$10k \equiv -k(11)$
ma da qui:
$-k \equiv 2(11)$
$k \equiv 9(11)$
ed arrivi al fantomatico $95$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo