Soluzioni di un sistema di congruenze?
ciao a tutti, non ho capito bene come risolvere il seguente esercizio
trovare tutte le soluzioni del sistema di congruenze:
$\{(8x -= 23 (17)),(7x -= 12 (24)):}$
non ho capito come si procede, so ke dopo bisognerebbe applicare il teorema cinese del resto
trovare tutte le soluzioni del sistema di congruenze:
$\{(8x -= 23 (17)),(7x -= 12 (24)):}$
non ho capito come si procede, so ke dopo bisognerebbe applicare il teorema cinese del resto
Risposte
poichè $MCD (17,24) = 1$ e verificando che ogni singola congruenza ammetta singolarmente soluzione il sistema è possibile ridurlo ad un sistema equivalente che è
$\{(X -= 6 mod17),(X -= 12 mod24):}$
ed a questo applicare il teorema cinese del resto; ma pur facendolo, e risolvendo il sistema equivalente, le soluzioni non vanno bene per il sistema iniziale.
Sono andato a controllare se la mia semplificazione del sistema fosse corretta e credo di sì.
Se qualcuno mi riesce a spiegare l'errore nella semplificazione. Sono partito da un lemma che dice che un sistema del tipo
$\{(a_1x -= b_1 mod n_1),(....),(a_sx -= b_s mod n_s):}$ può essere sostituito con un nuovo sistema equivalente $\{(x -= b'_1 mod n'_1),(...),(x -= b'_s mod n'_s):}$ dove con $n'_k$ indico $n_k / d_k$ con $k= 1,....s$ e $d_K = MCD (a_k,n_k)$
$\{(X -= 6 mod17),(X -= 12 mod24):}$
ed a questo applicare il teorema cinese del resto; ma pur facendolo, e risolvendo il sistema equivalente, le soluzioni non vanno bene per il sistema iniziale.
Sono andato a controllare se la mia semplificazione del sistema fosse corretta e credo di sì.
Se qualcuno mi riesce a spiegare l'errore nella semplificazione. Sono partito da un lemma che dice che un sistema del tipo
$\{(a_1x -= b_1 mod n_1),(....),(a_sx -= b_s mod n_s):}$ può essere sostituito con un nuovo sistema equivalente $\{(x -= b'_1 mod n'_1),(...),(x -= b'_s mod n'_s):}$ dove con $n'_k$ indico $n_k / d_k$ con $k= 1,....s$ e $d_K = MCD (a_k,n_k)$
Mi sembra che hai mischiato due modi di semplificazione.
Per la risoluzione, prima si calcolano separatamente i due sistemi lineari mod n, si trova l'insieme delle soluzioni della prima congruenza, poi la seconda e si risolve il sistema con il teorema cinese del resto.
Prima congruenza:
$ 8x -= 23 mod 17 $
Siccome $(8,17) = 1$ sono coprimi e 1 divide 23 allora la congruenza è compatibile.
Non si può semplificare come si è fatto perchè in $QQ$ non c'è un divisore comune.
Calcoliamo quindi l'inverso di 8 mod 17 tramite l'algoritmo di Euclide:
$17 = 2 * 8 + 1 $
quindi riscrivendolo come combinazione lineare:
$1 = (1)17 + (-2)8$ quindi l'inversa di 8 mod 17 è -2 mod 17, ma il primo esponente positivo è 15, quindi l'inversa è 15 mod 17.
Moltiplicando a destra e sinistra quindi si ha:
$ (15)*8x -= (15)*23 mod 17$
quindi si ha: $x -= 1 mod 17$
il procedimento per la seconda congruenza, se è invertibile, cioè il M.C.D è uguale ad 1, è equivalente. Se serve ti propongo la soluzione completa (se non ho fatto errori di calcolo), ma prova a continuare te.
Per la risoluzione, prima si calcolano separatamente i due sistemi lineari mod n, si trova l'insieme delle soluzioni della prima congruenza, poi la seconda e si risolve il sistema con il teorema cinese del resto.
Prima congruenza:
$ 8x -= 23 mod 17 $
Siccome $(8,17) = 1$ sono coprimi e 1 divide 23 allora la congruenza è compatibile.
Non si può semplificare come si è fatto perchè in $QQ$ non c'è un divisore comune.
Calcoliamo quindi l'inverso di 8 mod 17 tramite l'algoritmo di Euclide:
$17 = 2 * 8 + 1 $
quindi riscrivendolo come combinazione lineare:
$1 = (1)17 + (-2)8$ quindi l'inversa di 8 mod 17 è -2 mod 17, ma il primo esponente positivo è 15, quindi l'inversa è 15 mod 17.
Moltiplicando a destra e sinistra quindi si ha:
$ (15)*8x -= (15)*23 mod 17$
quindi si ha: $x -= 1 mod 17$
il procedimento per la seconda congruenza, se è invertibile, cioè il M.C.D è uguale ad 1, è equivalente. Se serve ti propongo la soluzione completa (se non ho fatto errori di calcolo), ma prova a continuare te.
a livello abbastanza meccanico&pratico ti conviene "isolarti la x" nel senso (ad esempio nella prima equazione) trovare l'inverso di 8 in $ZZ_17$ e moltiplicare ad ambo i membri di quella congruenza l' $8^(-1)$ trovato. Così avrai $x-=a (17)$. Fai lo stesso con l'altra equazione. Avrai allora :
$\{(x-=a (17)),(x-=b (24)) :}$ e allora potrai osservare che *$x-=a (24)$ vuol dire $x=24t+a$ $tinZZ$ alchè sostituendo questa x alla seconda equazione (ora avrai t come incognita) potrai risolvere una semplice equazione congruenziale.Riportando il tuo risultato ottenuto per t in $x=24t+a tinZZ$ avrai a cosa è congrua la tua x modulo il $m.c.m.(17,24)$. Ovviamente prima di svolgere tutta questa parte meccanica è indispensabile conoscere la teoria e vedere che sono verificate tutte le condizioni del teorema cinese dei resti.
*Piccola osservazione : potevi partire anche dalla prima equazione ma a me in uni hanno insegnato a partire dal numero (24) + grande per semplificare i calcoli
$\{(x-=a (17)),(x-=b (24)) :}$ e allora potrai osservare che *$x-=a (24)$ vuol dire $x=24t+a$ $tinZZ$ alchè sostituendo questa x alla seconda equazione (ora avrai t come incognita) potrai risolvere una semplice equazione congruenziale.Riportando il tuo risultato ottenuto per t in $x=24t+a tinZZ$ avrai a cosa è congrua la tua x modulo il $m.c.m.(17,24)$. Ovviamente prima di svolgere tutta questa parte meccanica è indispensabile conoscere la teoria e vedere che sono verificate tutte le condizioni del teorema cinese dei resti.
*Piccola osservazione : potevi partire anche dalla prima equazione ma a me in uni hanno insegnato a partire dal numero (24) + grande per semplificare i calcoli
perdono ham_burst non avevo letto il tuo post 
Ben venga il tuo post, amplia di molto la spiegazione (se è giusta la mia parte) con la teoria. Very Good 
grazie 
!
P.S. ho corretto errore di battitura
!P.S. ho corretto errore di battitura
Grazie... ho capito!
poi la risoluzione è semplice, non riuscivo a capire solo perché la semplificazione non fosse corretta!
poi la risoluzione è semplice, non riuscivo a capire solo perché la semplificazione non fosse corretta!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo