Sistema di congruenze lineari con moduli non coprimi
salve,
ho il seguente sistema di congruenze lineari
da risolvere e da trovare esplicitamente tutte le soluzioni positive [tex]\le 10000[/tex]
[tex]\begin{cases} x \equiv 7 (mod 196) \\ x \equiv 105 (mod 154) \end{cases}[/tex]
ho verificato che ogni congruenza sia risolvibile infatti
[tex]MCD(1,196) | 7[/tex]
[tex]MCD(1,154) | 105[/tex]
però il teorema cinese del resto nn può essere applicato in quanto
[tex]MCD(196,154) \ne 1[/tex]
poichè
[tex]196 = 2^2 \cdot 7^2[/tex]
[tex]154 = 2 \cdot 7 \cdot 11[/tex]
ho considerato la prima congruenza come un sistema spezzato in due congruenze di moduli rispettivamente 4 e 49
ma senza successo poichè mentre 4 e 49 sono coprimi non lo sono con 154.
ho anche pensato di sostituire la prima nella seconda ma nn so se è corretto e comunque non sono stato in grado di ultimarlo:
ho considerato la prima e la seconda congruenza come:
[tex]x + 196y = 7[/tex]
[tex]x + 154y = 105[/tex]
dalla prima ottengo
[tex]x = -196y + 7[/tex]
sostituendo nella seconda:
[tex]-196y + 7 + 154y = 105 \Rightarrow[/tex]
[tex]-42y = 98[/tex]
ma nn credo che vada bene
cortesemente potreste darmi consiglio su come dovrei procedere?
mille grazie.
ho il seguente sistema di congruenze lineari
da risolvere e da trovare esplicitamente tutte le soluzioni positive [tex]\le 10000[/tex]
[tex]\begin{cases} x \equiv 7 (mod 196) \\ x \equiv 105 (mod 154) \end{cases}[/tex]
ho verificato che ogni congruenza sia risolvibile infatti
[tex]MCD(1,196) | 7[/tex]
[tex]MCD(1,154) | 105[/tex]
però il teorema cinese del resto nn può essere applicato in quanto
[tex]MCD(196,154) \ne 1[/tex]
poichè
[tex]196 = 2^2 \cdot 7^2[/tex]
[tex]154 = 2 \cdot 7 \cdot 11[/tex]
ho considerato la prima congruenza come un sistema spezzato in due congruenze di moduli rispettivamente 4 e 49
ma senza successo poichè mentre 4 e 49 sono coprimi non lo sono con 154.
ho anche pensato di sostituire la prima nella seconda ma nn so se è corretto e comunque non sono stato in grado di ultimarlo:
ho considerato la prima e la seconda congruenza come:
[tex]x + 196y = 7[/tex]
[tex]x + 154y = 105[/tex]
dalla prima ottengo
[tex]x = -196y + 7[/tex]
sostituendo nella seconda:
[tex]-196y + 7 + 154y = 105 \Rightarrow[/tex]
[tex]-42y = 98[/tex]
ma nn credo che vada bene
cortesemente potreste darmi consiglio su come dovrei procedere?
mille grazie.
Risposte
il teorema cinese va sempre sfruttato al massimo e usato in maniera saggia.
quando tu trovi una congruenza modulo [tex]m*n[/tex] con [tex]\text{MCD}\leftm,n\right)=1[/tex] allora spezzala sempre in due congruenza, ti semplifica la vita.
[tex]\begin{cases} x \equiv 7 (mod 196) \\ x \equiv 105 (mod 154) \end{cases}[/tex]
come hai osservato questo sistema diventa
[tex]\begin{cases} x \equiv 7 \bmod 49 \\ x \equiv 7 \equiv 3 \bmod 4 \\ x \equiv 105 \equiv 1 \bmod 2 \\ x \equiv 105 \equiv 0 \bmod 7 \\ x \equiv 105 \equiv 6 \bmod 11 \end{cases}[/tex]
come noterai facilmente la seconda implica la terza e la prima implica la quarta.
allora devi solo occuparti delle equivalenze:
[tex]\begin{cases} x \equiv 7 \bmod 49 \\ x \equiv 3 \bmod 4 \\ x \equiv 6 \bmod 11 \end{cases}[/tex]
che è facile facile.
il procedimento è sempre: spezzo il più possibile le congruenze che ho, e dove si sovrappongono vado a vedere cosa capita volta per volta.
quando tu trovi una congruenza modulo [tex]m*n[/tex] con [tex]\text{MCD}\leftm,n\right)=1[/tex] allora spezzala sempre in due congruenza, ti semplifica la vita.
[tex]\begin{cases} x \equiv 7 (mod 196) \\ x \equiv 105 (mod 154) \end{cases}[/tex]
come hai osservato questo sistema diventa
[tex]\begin{cases} x \equiv 7 \bmod 49 \\ x \equiv 7 \equiv 3 \bmod 4 \\ x \equiv 105 \equiv 1 \bmod 2 \\ x \equiv 105 \equiv 0 \bmod 7 \\ x \equiv 105 \equiv 6 \bmod 11 \end{cases}[/tex]
come noterai facilmente la seconda implica la terza e la prima implica la quarta.
allora devi solo occuparti delle equivalenze:
[tex]\begin{cases} x \equiv 7 \bmod 49 \\ x \equiv 3 \bmod 4 \\ x \equiv 6 \bmod 11 \end{cases}[/tex]
che è facile facile.
il procedimento è sempre: spezzo il più possibile le congruenze che ho, e dove si sovrappongono vado a vedere cosa capita volta per volta.
quindi da:
[tex]\begin{cases} x \equiv 7 \bmod 49 \\ x \equiv 3 \bmod 4 \\ x \equiv 6 \bmod 11 \end{cases}[/tex]
dovrei continuare in questo modo:
pongo:
[tex]N = 49 \cdot 4 \cdot 11 = 2156[/tex]
[tex]N_1 = \frac{N}{49} = \frac{2156}{49} = 44[/tex]
[tex]N_2 = \frac{N}{4} = \frac{2156}{4} = 539[/tex]
[tex]N_3 = \frac{N}{11} = \frac{2156}{11} = 196[/tex]
ora risolvo le seguenti congruenze:
[tex]44x_1 \equiv 7 (mod 49)[/tex]
[tex]539x_2 \equiv 3 (mod 4)[/tex]
[tex]196x_3 \equiv 6 (mod 11)[/tex]
riduco in base ai rispettivi moduli e semplifico:
[tex]44x_1 \equiv 7 (mod 49)[/tex]
[tex]3x_2 \equiv 3 (mod 4)[/tex] qui [tex]MCD(3,4) = 1[/tex] divido per 3 [tex]\Rightarrow x_2 \equiv 1 (mod 4)[/tex]
[tex]9x_3 \equiv 6 (mod 11)[/tex] qui [tex]MCD(9,11) = 1[/tex] divido per 3 [tex]\Rightarrow 3x_3 \equiv 2 (mod 11)[/tex]
per la prima:
calcolo il [tex]MCD(44,49)[/tex] tramite algoritmo Euclideo
[tex]49 = 44 \cdot 1 + 5[/tex]
[tex]44 = 5 \cdot 8 + 4[/tex]
[tex]5 = 4 \cdot 1 + 1[/tex]
[tex]4 = 1 \cdot 4 + 0[/tex]
isolo i resti e sostituisco:
[tex]5 = 49 - 44 \cdot 1[/tex]
[tex]4 = 44 - 5 \cdot 8 = 44 - (49-44) \cdot 8[/tex]
[tex]1 = 5 - 4 \cdot 1 =[/tex]
[tex]= 49 - 44 - \left [ 44 - \left ( 49 - 44 \right ) \cdot 8 \right] =[/tex]
[tex]= 49 - 44 \cdot 2 + 49 \cdot 8 - 44 \cdot 8 =[/tex]
[tex]49 \cdot 9 - 44 \cdot 10[/tex]
quindi da:
[tex]1 = 49 \cdot 9 - 44 \cdot 10[/tex]
moltiplico per 7:
[tex]49 \cdot 63 - 44 \cdot 70 = 7[/tex]
[tex]49 \cdot 63 + 44 \cdot \left ( -70 \right ) = 7[/tex]
ottengo che il numero che moltiplicato per 44 mi da 7 in mod 49 è -70.
[tex]x_1 \equiv -70 \equiv 28 (mod 49)[/tex]
per la seconda e terza si trovano le soluzioni a tentativi.
In conclusione le singole soluzioni sono:
[tex]x_1 \equiv 28 (mod 49)[/tex]
[tex]x_2 \equiv 1 (mod 4)[/tex]
[tex]x_3 \equiv 8 (mod 11)[/tex]
tutte e sole le soluzioni del sistema sono del tipo [tex]\bar{x} + h \cdot 2156[/tex] dove
[tex]\bar{x} = N_1 \cdot x_1 + N_2 \cdot x_2 + N_3 \cdot x_3[/tex]
perciò:
[tex]\bar{x} = 44 \cdot 28 + 539 \cdot 1 + 196 \cdot 8 = 3339[/tex]
infine:
[tex]\bar{x} + h \cdot 2156 \Rightarrow 3339 + 2156h[/tex]
dal momento che [tex]3339 \equiv 1183 (mod 2156)[/tex] ottengo
tutte le soluzioni sono:
[tex]1183 + 2156h[/tex]
le mie domande:
è giusto così?
bisogna fare tutti questi calcoli ogni volta o c'è un procedimento più breve?
il procedimento che avevo accennato io all'inizio dove si sostituisce da subito l'una nell'altra era valido?
inoltre non mi è chiaro questo punto:
cioè praticamente da [tex]1183 + 2156h[/tex] con [tex]h \in \mathbb{Z}[/tex] vado a sostituire da zero fino a un valore valido in questo modo?
[tex]1183 + 2156 \cdot (0) = 1183[/tex]
[tex]1183 + 2156 \cdot (1) = 3339[/tex]
[tex]1183 + 2156 \cdot (2) = 1183 + 4312 = 5495[/tex]
[tex]1183 + 2156 \cdot (3) = 1183 + 6468 = 7651[/tex]
[tex]1183 + 2156 \cdot (4) = 1183 + 8624 = 9807[/tex]
quindi sono solo 5 le soluzioni?
ancora grazie mille davvero!
[tex]\begin{cases} x \equiv 7 \bmod 49 \\ x \equiv 3 \bmod 4 \\ x \equiv 6 \bmod 11 \end{cases}[/tex]
dovrei continuare in questo modo:
pongo:
[tex]N = 49 \cdot 4 \cdot 11 = 2156[/tex]
[tex]N_1 = \frac{N}{49} = \frac{2156}{49} = 44[/tex]
[tex]N_2 = \frac{N}{4} = \frac{2156}{4} = 539[/tex]
[tex]N_3 = \frac{N}{11} = \frac{2156}{11} = 196[/tex]
ora risolvo le seguenti congruenze:
[tex]44x_1 \equiv 7 (mod 49)[/tex]
[tex]539x_2 \equiv 3 (mod 4)[/tex]
[tex]196x_3 \equiv 6 (mod 11)[/tex]
riduco in base ai rispettivi moduli e semplifico:
[tex]44x_1 \equiv 7 (mod 49)[/tex]
[tex]3x_2 \equiv 3 (mod 4)[/tex] qui [tex]MCD(3,4) = 1[/tex] divido per 3 [tex]\Rightarrow x_2 \equiv 1 (mod 4)[/tex]
[tex]9x_3 \equiv 6 (mod 11)[/tex] qui [tex]MCD(9,11) = 1[/tex] divido per 3 [tex]\Rightarrow 3x_3 \equiv 2 (mod 11)[/tex]
per la prima:
calcolo il [tex]MCD(44,49)[/tex] tramite algoritmo Euclideo
[tex]49 = 44 \cdot 1 + 5[/tex]
[tex]44 = 5 \cdot 8 + 4[/tex]
[tex]5 = 4 \cdot 1 + 1[/tex]
[tex]4 = 1 \cdot 4 + 0[/tex]
isolo i resti e sostituisco:
[tex]5 = 49 - 44 \cdot 1[/tex]
[tex]4 = 44 - 5 \cdot 8 = 44 - (49-44) \cdot 8[/tex]
[tex]1 = 5 - 4 \cdot 1 =[/tex]
[tex]= 49 - 44 - \left [ 44 - \left ( 49 - 44 \right ) \cdot 8 \right] =[/tex]
[tex]= 49 - 44 \cdot 2 + 49 \cdot 8 - 44 \cdot 8 =[/tex]
[tex]49 \cdot 9 - 44 \cdot 10[/tex]
quindi da:
[tex]1 = 49 \cdot 9 - 44 \cdot 10[/tex]
moltiplico per 7:
[tex]49 \cdot 63 - 44 \cdot 70 = 7[/tex]
[tex]49 \cdot 63 + 44 \cdot \left ( -70 \right ) = 7[/tex]
ottengo che il numero che moltiplicato per 44 mi da 7 in mod 49 è -70.
[tex]x_1 \equiv -70 \equiv 28 (mod 49)[/tex]
per la seconda e terza si trovano le soluzioni a tentativi.
In conclusione le singole soluzioni sono:
[tex]x_1 \equiv 28 (mod 49)[/tex]
[tex]x_2 \equiv 1 (mod 4)[/tex]
[tex]x_3 \equiv 8 (mod 11)[/tex]
tutte e sole le soluzioni del sistema sono del tipo [tex]\bar{x} + h \cdot 2156[/tex] dove
[tex]\bar{x} = N_1 \cdot x_1 + N_2 \cdot x_2 + N_3 \cdot x_3[/tex]
perciò:
[tex]\bar{x} = 44 \cdot 28 + 539 \cdot 1 + 196 \cdot 8 = 3339[/tex]
infine:
[tex]\bar{x} + h \cdot 2156 \Rightarrow 3339 + 2156h[/tex]
dal momento che [tex]3339 \equiv 1183 (mod 2156)[/tex] ottengo
tutte le soluzioni sono:
[tex]1183 + 2156h[/tex]
le mie domande:
è giusto così?
bisogna fare tutti questi calcoli ogni volta o c'è un procedimento più breve?
il procedimento che avevo accennato io all'inizio dove si sostituisce da subito l'una nell'altra era valido?
inoltre non mi è chiaro questo punto:
trovare esplicitamente tutte le soluzioni positive [tex]\le 10000[/tex]
cioè praticamente da [tex]1183 + 2156h[/tex] con [tex]h \in \mathbb{Z}[/tex] vado a sostituire da zero fino a un valore valido in questo modo?
[tex]1183 + 2156 \cdot (0) = 1183[/tex]
[tex]1183 + 2156 \cdot (1) = 3339[/tex]
[tex]1183 + 2156 \cdot (2) = 1183 + 4312 = 5495[/tex]
[tex]1183 + 2156 \cdot (3) = 1183 + 6468 = 7651[/tex]
[tex]1183 + 2156 \cdot (4) = 1183 + 8624 = 9807[/tex]
quindi sono solo 5 le soluzioni?
ancora grazie mille davvero!
per me l'esercizio è finito dove ti ho indicato, per il teorema cinese del resto le soluzione esiste, ed è unica modulo il prodotto dei moduli.
poi se proprio vuoi (o devi) fare i conti, il tuo procedimento mi pare giusto, magari hai fatto qualche errore di calcolo, ma poco importa.
quindi sì va bene così.
le soluzioni minori di 10000 sono quelle, se i conti sono giusti.
poi se proprio vuoi (o devi) fare i conti, il tuo procedimento mi pare giusto, magari hai fatto qualche errore di calcolo, ma poco importa.
quindi sì va bene così.
le soluzioni minori di 10000 sono quelle, se i conti sono giusti.
ok ti ringrazio!
c'è un procedimento alternativo invece di usare il teorema cinese del resto?
c'è un procedimento alternativo invece di usare il teorema cinese del resto?
un altro procedimento spero corretto per calcolare la soluzione del sistema dovrebbe essere il seguente.
dato il mio sistema di partenza:
[tex]\begin{cases} x \equiv 7 \pmod{196} \\ x \equiv 105 \pmod{154} \end{cases}[/tex]
procedo così:
scrivo la prima congruenza sotto forma di equazione:
[tex]x + 196h = 7[/tex]
e mi ricavo la x:
[tex]x = 7 - 196h[/tex]
sostituisco la [tex]x[/tex] appena trovata nella seconda congruenza:
[tex]7-196h \equiv 105 \pmod{154}[/tex]
[tex]-196h \equiv 98 \pmod{154}[/tex]
[tex]112h \equiv 98 \pmod{154}[/tex]
[tex]h \equiv 5 \pmod{154}[/tex]
sostituisco la [tex]h[/tex] nella [tex]x[/tex] della prima congruenza:
perciò da [tex]x = 7 - 196h[/tex] sostituisco e ottengo:
[tex]x= 7 - 196 \cdot 5 = 7 - 980 = -973 \equiv 1183 \pmod{2156}[/tex]
quest'ultimo modulo 2156 è il [tex]mcm(196, 154)[/tex]
il risultato è lo stesso che si ottiene col procedimento precedente.
domande:
dovrebbe essere corretto come modo alternativo di procedere o sbaglio?
se è giusto, perchè viene preso proprio il [tex]mcm(196, 154)[/tex] come modulo della soluzione finale?
dato il mio sistema di partenza:
[tex]\begin{cases} x \equiv 7 \pmod{196} \\ x \equiv 105 \pmod{154} \end{cases}[/tex]
procedo così:
scrivo la prima congruenza sotto forma di equazione:
[tex]x + 196h = 7[/tex]
e mi ricavo la x:
[tex]x = 7 - 196h[/tex]
sostituisco la [tex]x[/tex] appena trovata nella seconda congruenza:
[tex]7-196h \equiv 105 \pmod{154}[/tex]
[tex]-196h \equiv 98 \pmod{154}[/tex]
[tex]112h \equiv 98 \pmod{154}[/tex]
[tex]h \equiv 5 \pmod{154}[/tex]
sostituisco la [tex]h[/tex] nella [tex]x[/tex] della prima congruenza:
perciò da [tex]x = 7 - 196h[/tex] sostituisco e ottengo:
[tex]x= 7 - 196 \cdot 5 = 7 - 980 = -973 \equiv 1183 \pmod{2156}[/tex]
quest'ultimo modulo 2156 è il [tex]mcm(196, 154)[/tex]
il risultato è lo stesso che si ottiene col procedimento precedente.
domande:
dovrebbe essere corretto come modo alternativo di procedere o sbaglio?
se è giusto, perchè viene preso proprio il [tex]mcm(196, 154)[/tex] come modulo della soluzione finale?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo