Congruenze maledette...
Ciao a tutti.
Sentite è una serata intera che cerco di risolvere un sistema di congruenze senza arrivare da nessuna parte. Perchè avrei delle mezze idee per risolvere il sistema, ma poi a metà strada mi sorgono in mente decine di domande tipo "e se facessi così?" oppure "ma posso fare questo tipo di semplificazione/divisione" etc etc??
Questo sostanzialmente perchè non ho ben chiara la teoria, ma dopo leggere e rileggere le stesse cose su ben 4 libri diversi non so + che cos'altro fare. Ho bisogno di capire come si svolgono gli esercizi per capirci qualcosa di più. Quindi vi chiedo: qualcuno è così gentile da risolvere questo sistema di congruenze (che dovrebbe anche essere abbastanza semplice) descrivendo in modo chiaro tutti i passaggi?
Dopo di chè farò qualche domanda su tutto quello che non mi è chiaro e su quello che non sono sicuro di poter fare quando lavoro con queste congruenze.. Spero ci sia qualche persona così gentile da prestarsi alla risposta di qualche post.. Vi ringrazio in anticipo:
Trovare tutti gli $x in ZZ$ tali che $\{(123x + 57 = 0 in ZZ_(72)),(x = 237 in ZZ_(73)) :}$
P.S. Per esempio $x = 237 in ZZ_(73)$ vuol dire $x-=237(mod 73)$, tanto per essere chiari, perchè forse da come l'ho scritto sopra non si capisce bene..
Grazie! Ciao!
Sentite è una serata intera che cerco di risolvere un sistema di congruenze senza arrivare da nessuna parte. Perchè avrei delle mezze idee per risolvere il sistema, ma poi a metà strada mi sorgono in mente decine di domande tipo "e se facessi così?" oppure "ma posso fare questo tipo di semplificazione/divisione" etc etc??
Questo sostanzialmente perchè non ho ben chiara la teoria, ma dopo leggere e rileggere le stesse cose su ben 4 libri diversi non so + che cos'altro fare. Ho bisogno di capire come si svolgono gli esercizi per capirci qualcosa di più. Quindi vi chiedo: qualcuno è così gentile da risolvere questo sistema di congruenze (che dovrebbe anche essere abbastanza semplice) descrivendo in modo chiaro tutti i passaggi?
Dopo di chè farò qualche domanda su tutto quello che non mi è chiaro e su quello che non sono sicuro di poter fare quando lavoro con queste congruenze.. Spero ci sia qualche persona così gentile da prestarsi alla risposta di qualche post.. Vi ringrazio in anticipo:
Trovare tutti gli $x in ZZ$ tali che $\{(123x + 57 = 0 in ZZ_(72)),(x = 237 in ZZ_(73)) :}$
P.S. Per esempio $x = 237 in ZZ_(73)$ vuol dire $x-=237(mod 73)$, tanto per essere chiari, perchè forse da come l'ho scritto sopra non si capisce bene..
Grazie! Ciao!
Risposte
Allora se non ho capito male il sistema è questo:
$\{(123x -= -57 (72)),(x -=237 (73)):}
Allora per prima cosa scrivi i coefficienti invece che in $ZZ$, in $ZZ_n$, rispetto al proprio modulo:
$\{(51x -= 15 (72)),(x -=18 (73)):}
Ora potresti usare o il Teorema Cinese Del Resto, oppure il metodo classico (che preferisco):
Risolviamo la prima congruenza: $51x = 15 + 72h$ con la divisione euclidea:
$72 = 51*1 + 21$
$51 = 21*2+9$
$21 = 9*2 + 3$
$9 = 3*3 + 0$
Prendi l'ultimo resto non nullo $=> 3 = 21 - 9*2 = 21 - (51-21*2)*2=21 - 51*2 +21*4 = 21*5 - 51*2 =(72-51*1)*5-51*2=72*5-51*3-51*4=72*5-51*7$
Moltiplica tutto in modo tale che al primo membro ti venga $15$: $15 = 3*5= (72*5-51*7)*5=72*25-51*35$.
La tua $x$ è il numero CON SEGNO che è vicino a $51$, quindi $x=-35 -= 37 ("mod" 72)=37+72h$
Sostituisci ora la $x$ ottenuta nella seconda congruenza: $37+72h -=18 (73) => 72h -= -19(73) => 72h = 54 + 73k$
Divisione euclidea:
$73=72*1+1$
$72=1*72+0$
Prendi l'ultimo resto non nullo $=> 1=73-72*1$
Moltiplica tutto in modo che al primo membro ti venga $54$: $54 = 1*54 = (73-72*1)*54 = 73*54 - 72*54$
La tua $h$ è il numero CON SEGNO che è vicino a $72$, quindi $h=-54 -= 19 ("mod" 73)=19+73k$
Il risultato finale è quindi: $x=37+72h =37+72*(19+73k)=37+1368 +5256k=1405 + 5256k$
Dovrebbe (spero) essere tutto giusto. Se hai altri dubbi e/o non ti è chiaro qualcosa chiedi!
Ciao
$\{(123x -= -57 (72)),(x -=237 (73)):}
Allora per prima cosa scrivi i coefficienti invece che in $ZZ$, in $ZZ_n$, rispetto al proprio modulo:
$\{(51x -= 15 (72)),(x -=18 (73)):}
Ora potresti usare o il Teorema Cinese Del Resto, oppure il metodo classico (che preferisco):
Risolviamo la prima congruenza: $51x = 15 + 72h$ con la divisione euclidea:
$72 = 51*1 + 21$
$51 = 21*2+9$
$21 = 9*2 + 3$
$9 = 3*3 + 0$
Prendi l'ultimo resto non nullo $=> 3 = 21 - 9*2 = 21 - (51-21*2)*2=21 - 51*2 +21*4 = 21*5 - 51*2 =(72-51*1)*5-51*2=72*5-51*3-51*4=72*5-51*7$
Moltiplica tutto in modo tale che al primo membro ti venga $15$: $15 = 3*5= (72*5-51*7)*5=72*25-51*35$.
La tua $x$ è il numero CON SEGNO che è vicino a $51$, quindi $x=-35 -= 37 ("mod" 72)=37+72h$
Sostituisci ora la $x$ ottenuta nella seconda congruenza: $37+72h -=18 (73) => 72h -= -19(73) => 72h = 54 + 73k$
Divisione euclidea:
$73=72*1+1$
$72=1*72+0$
Prendi l'ultimo resto non nullo $=> 1=73-72*1$
Moltiplica tutto in modo che al primo membro ti venga $54$: $54 = 1*54 = (73-72*1)*54 = 73*54 - 72*54$
La tua $h$ è il numero CON SEGNO che è vicino a $72$, quindi $h=-54 -= 19 ("mod" 73)=19+73k$
Il risultato finale è quindi: $x=37+72h =37+72*(19+73k)=37+1368 +5256k=1405 + 5256k$
Dovrebbe (spero) essere tutto giusto. Se hai altri dubbi e/o non ti è chiaro qualcosa chiedi!
Ciao
Ciao gygabyte017. Mi sembra di aver capito tutto di quello che hai scritto, però ho qualche domanda.
1)
Con questa frase intendi dire con quale modo trovare x e y che in questo caso sono 5 e 7, oppure cosa?
Cioè tu hai preferito un metodo ad un altro, a cosa ti riferisci? All'algoritmo di euclide esteso per trovare i 2 valori x e y?
2)
Perchè questa cosa? Cioè non capisco come tu abbia dedotto che bisognava moltiplicare per 15 (capisco perchè hai scelto 15, non capisco il motivo di dover moltiplicare per 15 proprio quell'elemento dell'uguaglianza)
I passaggi successivi li ho capito e non mi sembra ci sia niente di particolarmente strano.
Però ho problemi per quanto riguarda per esempio:
1)la divisione del modulo, cioè se è primo cosa si può fare, se non è primo cosa si può fare.
2)Quando si capisce subito se è irrisolubile una congruenza.
3)Quali sono i passaggi classici per risolvere sistemi di congruenze tipo questo, ma anche più semplici o più difficili
4)Cosa fare se per esempio un numero non ha inverso moltiplicativo in qualche modulo. Che si fà in quel caso? Tipo in questo esercizio mi sembra che 51 non ha inverso in modulo 72, infatti nel secondo passaggio cioè dopo la traccia, dopo che hai semplicemente trasformato i numeri troppo grossi negli equivalenti in modulo 72 e 73, io avrei cercato di trovare un inverso di 51 in mod72 in modo da restare solo con qualcosa tipo $x-=qualcosa (mod72)$. Ma ho scoperto che 51 non ha inverso, e quindi che ci posso fare? Niente?
Non mi vengono in mente altre domande, anche ne avrei una marea..
Grazie 1000 comunque semmai mi risponderai.. viste tutte le domande che ho fatto..
1)
Ora potresti usare o il Teorema Cinese Del Resto, oppure il metodo classico (che preferisco):
Con questa frase intendi dire con quale modo trovare x e y che in questo caso sono 5 e 7, oppure cosa?
Cioè tu hai preferito un metodo ad un altro, a cosa ti riferisci? All'algoritmo di euclide esteso per trovare i 2 valori x e y?
2)
Moltiplica tutto in modo tale che al primo membro ti venga 15
Perchè questa cosa? Cioè non capisco come tu abbia dedotto che bisognava moltiplicare per 15 (capisco perchè hai scelto 15, non capisco il motivo di dover moltiplicare per 15 proprio quell'elemento dell'uguaglianza)
I passaggi successivi li ho capito e non mi sembra ci sia niente di particolarmente strano.
Però ho problemi per quanto riguarda per esempio:
1)la divisione del modulo, cioè se è primo cosa si può fare, se non è primo cosa si può fare.
2)Quando si capisce subito se è irrisolubile una congruenza.
3)Quali sono i passaggi classici per risolvere sistemi di congruenze tipo questo, ma anche più semplici o più difficili
4)Cosa fare se per esempio un numero non ha inverso moltiplicativo in qualche modulo. Che si fà in quel caso? Tipo in questo esercizio mi sembra che 51 non ha inverso in modulo 72, infatti nel secondo passaggio cioè dopo la traccia, dopo che hai semplicemente trasformato i numeri troppo grossi negli equivalenti in modulo 72 e 73, io avrei cercato di trovare un inverso di 51 in mod72 in modo da restare solo con qualcosa tipo $x-=qualcosa (mod72)$. Ma ho scoperto che 51 non ha inverso, e quindi che ci posso fare? Niente?
Non mi vengono in mente altre domande, anche ne avrei una marea..
Grazie 1000 comunque semmai mi risponderai.. viste tutte le domande che ho fatto..
"John_Nash":
4) Cosa fare se per esempio un numero non ha inverso moltiplicativo in qualche modulo. Che si fà in quel caso? Tipo in questo esercizio mi sembra che 51 non ha inverso in modulo 72, infatti nel secondo passaggio cioè dopo la traccia, dopo che hai semplicemente trasformato i numeri troppo grossi negli equivalenti in modulo 72 e 73, io avrei cercato di trovare un inverso di 51 in mod72 in modo da restare solo con qualcosa tipo $x-=qualcosa (mod72)$. Ma ho scoperto che 51 non ha inverso, e quindi che ci posso fare? Niente?
Puoi fare cosi': dire $51x equiv 15\ mod(72)$ equivale a dire che $72 = 3*24$ divide $51x-15 = 3*(17x-5)$ (non e' un caso fortuito che 15 sia divisibile per 3: vedi (*)), ovvero $24$ divide $17x-5$, ovvero $17x equiv 5\ mod(24)$. E adesso $17$ e' invertibile $mod(24)$ con inverso $17$, quindi ottieni $x equiv 5*17 equiv -35 equiv 13\ mod(24)$.
(*) Naturalmente una congruenza del tipo $51x equiv alpha\ mod(72)$ ha soluzioni solo se $3=MCD(51,72)$ divide $alpha$.
In generale se esiste $x$ tale che $ax equiv b\ mod(c)$ allora $c$ divide $ax-b$, quindi $MCD(a,c)$ deve dividere $b$.
Il sistema di congruenze del tipo:
${(a_1 \equiv b_1 (n_1)),(a_2 \equiv b_2 (n_2)):}$
Sono di risoluzione semplice con entrambi i modi... meglio il CRT (Chinese Reminder Theorem) per più di due equazioni...
${(a_1 \equiv b_1 (n_1)),(a_2 \equiv b_2 (n_2)):}$
Sono di risoluzione semplice con entrambi i modi... meglio il CRT (Chinese Reminder Theorem) per più di due equazioni...
"John_Nash":
Ciao gygabyte017. Mi sembra di aver capito tutto di quello che hai scritto, però ho qualche domanda.
1)Ora potresti usare o il Teorema Cinese Del Resto, oppure il metodo classico (che preferisco):
Con questa frase intendi dire con quale modo trovare x e y che in questo caso sono 5 e 7, oppure cosa?
Cioè tu hai preferito un metodo ad un altro, a cosa ti riferisci? All'algoritmo di euclide esteso per trovare i 2 valori x e y?
No intendo che esiste un procedimento detto appunto Teorema Cinese del Resto che ti permette di risolvere qualunque sistema di congruenze, ma è molto meccanico, e noioso (secondo me
). Invece preferisco il metodo che ti ho fatto vedere (che però diventa un po' scomodo quando le congruenze nel sistema sono tante!)
2) [quote]Moltiplica tutto in modo tale che al primo membro ti venga 15
Perchè questa cosa? Cioè non capisco come tu abbia dedotto che bisognava moltiplicare per 15 (capisco perchè hai scelto 15, non capisco il motivo di dover moltiplicare per 15 proprio quell'elemento dell'uguaglianza)
[/quote]
Dunque: supponiamo che devi risolvere la congruenza $51x -=15(72)$. Facendo la divisione euclidea, trovi la relazione $ 3 = 72*5-51*7$
Hai quindi queste due equazioni:
$15 = 72h + 51x$ (la congruenza)
$ 3 = 72*5-51*7$ (la divisione euclidea)
Ora modifichiamo la seconda in modo tale che il primo membro venga uguale a quello della prima:
$ 15 = 72*25 - 51*35$
Ma allora $72h + 51x = 72*25 + 51*(-35)$ ! Da cui per confronto è chiaro che $x=-35$ ! Spero di essermi spiegato!
Per il resto appena ho tempo ti rispondo!
Se hai dubbi chiedi pure.
Ciao
"John_Nash":
Però ho problemi per quanto riguarda per esempio:
1)la divisione del modulo, cioè se è primo cosa si può fare, se non è primo cosa si può fare.
2)Quando si capisce subito se è irrisolubile una congruenza.
3)Quali sono i passaggi classici per risolvere sistemi di congruenze tipo questo, ma anche più semplici o più difficili
4)Cosa fare se per esempio un numero non ha inverso moltiplicativo in qualche modulo. Che si fà in quel caso? Tipo in questo esercizio mi sembra che 51 non ha inverso in modulo 72, infatti nel secondo passaggio cioè dopo la traccia, dopo che hai semplicemente trasformato i numeri troppo grossi negli equivalenti in modulo 72 e 73, io avrei cercato di trovare un inverso di 51 in mod72 in modo da restare solo con qualcosa tipo $x-=qualcosa (mod72)$. Ma ho scoperto che 51 non ha inverso, e quindi che ci posso fare? Niente?
Non mi vengono in mente altre domande, anche ne avrei una marea..
Grazie 1000 comunque semmai mi risponderai.. viste tutte le domande che ho fatto..
Come promesso rieccomi
:2) Ogni congruenza del tipo $ax-=b ("mod" n)$ è risolubile se e solo se $"MCD"(a,n) | b$. Quindi per ogni congruenza devi fare questa verifica, e se esiste almeno una congruenza che non verifica quella relazione allora tutto il sistema è irrisolubile.
3) Vediti l'esercizio svolto, si fanno tutti così!
4) Ti ha risposto martino
Wow gygabyte.. sei stato chiarissimo! 
Grazie mille, anche a Lord K e Martino.
Tanto per non far cadere il post nel dimenticatoio, visto che penso comunque di avere diverse lacune riguardo queste dannate congruenze, chi sarebbe così gentile da postare a caso 2-3 congruenze ed io rispondo con la soluzione che trovo, per vedere se ho capito o meno? Anche un sistema magari.. Così sono sicuro di aver capito in generale come lavorarci.. (ho un esame la prossima settimana su questi argomenti e se non mi esercito bene penso di prendere un brutto voto, cosa che non mi posso permettere... 
)
Grazie a tutti comunque siete gentilissimi, un forum di gente così disponibile è abbastanza raro..
Ciao!!
Grazie mille, anche a Lord K e Martino.Tanto per non far cadere il post nel dimenticatoio, visto che penso comunque di avere diverse lacune riguardo queste dannate congruenze, chi sarebbe così gentile da postare a caso 2-3 congruenze ed io rispondo con la soluzione che trovo, per vedere se ho capito o meno? Anche un sistema magari.. Così sono sicuro di aver capito in generale come lavorarci..
(ho un esame la prossima settimana su questi argomenti e se non mi esercito bene penso di prendere un brutto voto, cosa che non mi posso permettere... )Grazie a tutti comunque siete gentilissimi, un forum di gente così disponibile è abbastanza raro..
Ciao!!
di niente 
Eccoti accontentato :
$"1)" {(5x-=95 "(mod 15)"),(x-=43 "(mod 16)"),(27x-=65 "(mod 17)"):}$
$"2)" {(x-=25 "(mod 7)"),(18x-=10 "(mod 9)"),(43x-=11 "(mod 44)"):}$
$"3)" {(16x-=33 "(mod 7)"),(36x-=51 "(mod 5)"),(21x-=66 "(mod 9)"):}$
$"4)" {(1025x-=5312065 "(mod 8)"),(36x-=322 "(mod 5)"),(4x-=7 "(mod 3)"):}$
Buon lavoro!
Eccoti accontentato
:$"1)" {(5x-=95 "(mod 15)"),(x-=43 "(mod 16)"),(27x-=65 "(mod 17)"):}$
$"2)" {(x-=25 "(mod 7)"),(18x-=10 "(mod 9)"),(43x-=11 "(mod 44)"):}$
$"3)" {(16x-=33 "(mod 7)"),(36x-=51 "(mod 5)"),(21x-=66 "(mod 9)"):}$
$"4)" {(1025x-=5312065 "(mod 8)"),(36x-=322 "(mod 5)"),(4x-=7 "(mod 3)"):}$
Buon lavoro!
Grazie a tutti comunque siete gentilissimi, un forum di gente così disponibile è abbastanza raro..
Ciao!!
La matematica è un dono che non può essere tenuto solo per se stessi, deve essere condiviso con garbo e passione con tutti!
Approfitto del tuo topic per chiarirmi un dubbio. Devo risolvere il seguente sistema:
$x-=3 mod5$
$x-=5 mod6$
Ora,risolvendo la prima,ottengo $x=8+5h$ che sostituita nella seconda mi da $5h-=-3 mod 6$. Risolvendo l'equazione $5h+6k=1$ ottengo $h=-1$ e $k=1$: Moltiplicando per $-3$ ottengo definitivamente $h=3+6l$ che sostutuita nella prima mi da: $x=8+15+30l$ e quindi $x=23+30l$. Questo è il metodo delle sostituzioni se non sbaglio. Ora però,come devo fare se volessi usare il teorema cinese del resto? So che il modulo è dato dal prodotto dei moduli (in questo caso,infatti,30),ma non ho capito il procedimento del teorema. Grazie!!
$x-=3 mod5$
$x-=5 mod6$
Ora,risolvendo la prima,ottengo $x=8+5h$ che sostituita nella seconda mi da $5h-=-3 mod 6$. Risolvendo l'equazione $5h+6k=1$ ottengo $h=-1$ e $k=1$: Moltiplicando per $-3$ ottengo definitivamente $h=3+6l$ che sostutuita nella prima mi da: $x=8+15+30l$ e quindi $x=23+30l$. Questo è il metodo delle sostituzioni se non sbaglio. Ora però,come devo fare se volessi usare il teorema cinese del resto? So che il modulo è dato dal prodotto dei moduli (in questo caso,infatti,30),ma non ho capito il procedimento del teorema. Grazie!!
Allora, spiego in modo "operativo" come funziona in teorema cinese del resto.
PROCEDURA COMPLETA
Abbiamo il seguente sistema:
${(a_1x -= b_1 (mod n_1)),(vdots),(a_mx -= b_m (mod n_m)):}$
1) Per applicare il teorema, è necessario che $MCD(n_i,n_k)=1\qquad AAi!=k$
2) Controllare che sia risolubile, cioè che $AAk=1..m\qquad MCD(a_k,n_k) | b_k$
3) $AAk=1..m$, se $d_k=MCD(a_k,n_k)!=1$, sostituire la k-esima congruenza, con una equivalente (nel senso che ha le stesse soluzioni) ottenuta dividendo ogni elemento per $d_k$.
In altre parole, $a_kx -= b_k (mod n_k)$ diventa $(a_k)/(d_k)x -= (b_1)/(d_k) (mod (n_1)/(d_k)) = a'_kx -= b'_k (mod n'_k)$
Quindi, tutto il sistema iniziale viene riscritto così:
${(a_1x -= b_1 (mod n_1)),(vdots),(a_mx -= b_m (mod n_m)):}$ $" "=>" "$ ${((a_1)/(d_1)x -= (b_1)/(d_1) (mod (n_1)/(d_1))),(vdots),((a_m)/(d_m)x -= (b_m)/(d_m) (mod (n_m)/(d_m))):}$ $" "=" "$ ${(a'_1x -= b'_1 (mod n'_1)),(vdots),(a'_mx -= b'_m (mod n'_m)):}$
con $d_k=MCD(a_k,n_k)\qquad AAk=1..m$
4) Ora, ogni congruenza ammette un'unica soluzione. $AAk=1..m$, trovare la soluzione $c_k$ della k-esima congruenza usando la divisione euclidea e l'identità di bezout.
Trovate quindi tutte le $m$ soluzioni, il sistema viene nuovamente riscritto così:
${(x -= c_1 (mod n'_1)),(vdots),(x -= c_m (mod n'_m)):}$
!!! L'obiettivo delle prime 4 fasi è quindi quello di trasformare il sistema iniziale in un sistema in cui la $x$ abbia come coefficiente $1$, e ogni congruenza abbia un'unica soluzione (lo riscrivo per chiarezza cambiando qualche nomenclatura):
${(x -= c_1 (mod r_1)),(vdots),(x -= c_m (mod r_m)):}$
5) Siano:
$R:= r_1 * \quad cdots \quad* r_m$
$R_k := R / (r_k)\qquad AAk=1..m$
Consideriamo il seguente nuovo sistema:
$("*"){(R_1x -= c_1 (mod r_1)),(vdots),(R_mx -= c_m (mod r_m)):}$
Siano $bar x_k$ le soluzioni delle congruenze del sistema $("*")$.
Allora $bar x := R_1 * bar x_1 + cdots + R_m * bar x_m$ è L'UNICA SOLUZIONE DEL SISTEMA INIZIALE $ mod R$
----------------------------------------------------------------
Considerazioni: fare tutti questi calcoli è lungo! Se le congruenze del sistema sono poche, conviene molto di più risolvere il sistema con il metodo classico della sostituzione!
Tuttavia, tutta la procedura del teorema cinese del resto può essere semplificata:
PROCEDURA SEMPLIFICATA
Abbiamo il seguente sistema:
${(a_1x -= b_1 (mod n_1)),(vdots),(a_mx -= b_m (mod n_m)):}$
I primi tre punti 1) 2) e 3) sono identici.
Abbiamo quindi ottenuto il sistema equivalente:
${(a'_1x -= b'_1 (mod n'_1)),(vdots),(a'_mx -= b'_m (mod n'_m)):}$
che rinomino per semplicità: ${(a_1x -= b_1 (mod r_1)),(vdots),(a_mx -= b_m (mod r_m)):}$
4) Siano:
$R:= r_1 * \quad cdots \quad* r_m$
$R_k := R / (r_k)\qquad AAk=1..m$
Consideriamo il seguente nuovo sistema:
$("**"){(a_1R_1x -= c_1 (mod r_1)),(vdots),(a_mR_mx -= c_m (mod r_m)):}$
Siano $bar x_k$ le soluzioni delle congruenze del sistema $("**")$.
Allora $bar x := R_1 * bar x_1 + cdots + R_m * bar x_m$ è L'UNICA SOLUZIONE DEL SISTEMA INIZIALE $ mod R$
-------------------------------------------------------
Faccio un esempio tanto per chiarire le idee (usando la procedura semplificata):
Abbiamo: ${(x-=3 (mod 5)),(x-=5 (mod 6)):}$
1) $MCD(5,6)=1$ OK!
2) $MCD(1,5) | 3$ e $MCD(1,6) | 5$ OK!
3) Essendo già tutti gli MCD=1 non dobbiamo sostituire niente.
4)
$R:=5*6=30$
$R_1=30/5=6$ e $R_2=30/6=5$
Consideriamo il nuovo sistema:
${(1*6*x-=3 (mod 5)),(1*5*x-=5 (mod 6)):}$
Risolviamo la prima congruenza: $6x -=3 (mod 5) => x -=3 (mod 5)$ quindi $x_1=3$.
Risolviamo la seconda congruenza: $5x -=5 (mod 6) $ $1 = 6 - 5*1 $ $5= 6*5 - 5*5 $ $=> x =-5 (mod 6)$ quindi $x_2=1$.
Soluzione del sistema: $bar x = 6*3 + 5*1 = 23 mod 30$
Spero sia tutto chiaro! (sto morendo dalla fatica ho scritto troppo)
Ciao ciao
PROCEDURA COMPLETA
Abbiamo il seguente sistema:
${(a_1x -= b_1 (mod n_1)),(vdots),(a_mx -= b_m (mod n_m)):}$
1) Per applicare il teorema, è necessario che $MCD(n_i,n_k)=1\qquad AAi!=k$
2) Controllare che sia risolubile, cioè che $AAk=1..m\qquad MCD(a_k,n_k) | b_k$
3) $AAk=1..m$, se $d_k=MCD(a_k,n_k)!=1$, sostituire la k-esima congruenza, con una equivalente (nel senso che ha le stesse soluzioni) ottenuta dividendo ogni elemento per $d_k$.
In altre parole, $a_kx -= b_k (mod n_k)$ diventa $(a_k)/(d_k)x -= (b_1)/(d_k) (mod (n_1)/(d_k)) = a'_kx -= b'_k (mod n'_k)$
Quindi, tutto il sistema iniziale viene riscritto così:
${(a_1x -= b_1 (mod n_1)),(vdots),(a_mx -= b_m (mod n_m)):}$ $" "=>" "$ ${((a_1)/(d_1)x -= (b_1)/(d_1) (mod (n_1)/(d_1))),(vdots),((a_m)/(d_m)x -= (b_m)/(d_m) (mod (n_m)/(d_m))):}$ $" "=" "$ ${(a'_1x -= b'_1 (mod n'_1)),(vdots),(a'_mx -= b'_m (mod n'_m)):}$
con $d_k=MCD(a_k,n_k)\qquad AAk=1..m$
4) Ora, ogni congruenza ammette un'unica soluzione. $AAk=1..m$, trovare la soluzione $c_k$ della k-esima congruenza usando la divisione euclidea e l'identità di bezout.
Trovate quindi tutte le $m$ soluzioni, il sistema viene nuovamente riscritto così:
${(x -= c_1 (mod n'_1)),(vdots),(x -= c_m (mod n'_m)):}$
!!! L'obiettivo delle prime 4 fasi è quindi quello di trasformare il sistema iniziale in un sistema in cui la $x$ abbia come coefficiente $1$, e ogni congruenza abbia un'unica soluzione (lo riscrivo per chiarezza cambiando qualche nomenclatura):
${(x -= c_1 (mod r_1)),(vdots),(x -= c_m (mod r_m)):}$
5) Siano:
$R:= r_1 * \quad cdots \quad* r_m$
$R_k := R / (r_k)\qquad AAk=1..m$
Consideriamo il seguente nuovo sistema:
$("*"){(R_1x -= c_1 (mod r_1)),(vdots),(R_mx -= c_m (mod r_m)):}$
Siano $bar x_k$ le soluzioni delle congruenze del sistema $("*")$.
Allora $bar x := R_1 * bar x_1 + cdots + R_m * bar x_m$ è L'UNICA SOLUZIONE DEL SISTEMA INIZIALE $ mod R$
----------------------------------------------------------------
Considerazioni: fare tutti questi calcoli è lungo! Se le congruenze del sistema sono poche, conviene molto di più risolvere il sistema con il metodo classico della sostituzione!
Tuttavia, tutta la procedura del teorema cinese del resto può essere semplificata
:PROCEDURA SEMPLIFICATA
Abbiamo il seguente sistema:
${(a_1x -= b_1 (mod n_1)),(vdots),(a_mx -= b_m (mod n_m)):}$
I primi tre punti 1) 2) e 3) sono identici.
Abbiamo quindi ottenuto il sistema equivalente:
${(a'_1x -= b'_1 (mod n'_1)),(vdots),(a'_mx -= b'_m (mod n'_m)):}$
che rinomino per semplicità: ${(a_1x -= b_1 (mod r_1)),(vdots),(a_mx -= b_m (mod r_m)):}$
4) Siano:
$R:= r_1 * \quad cdots \quad* r_m$
$R_k := R / (r_k)\qquad AAk=1..m$
Consideriamo il seguente nuovo sistema:
$("**"){(a_1R_1x -= c_1 (mod r_1)),(vdots),(a_mR_mx -= c_m (mod r_m)):}$
Siano $bar x_k$ le soluzioni delle congruenze del sistema $("**")$.
Allora $bar x := R_1 * bar x_1 + cdots + R_m * bar x_m$ è L'UNICA SOLUZIONE DEL SISTEMA INIZIALE $ mod R$
-------------------------------------------------------
Faccio un esempio tanto per chiarire le idee (usando la procedura semplificata):
Abbiamo: ${(x-=3 (mod 5)),(x-=5 (mod 6)):}$
1) $MCD(5,6)=1$ OK!
2) $MCD(1,5) | 3$ e $MCD(1,6) | 5$ OK!
3) Essendo già tutti gli MCD=1 non dobbiamo sostituire niente.
4)
$R:=5*6=30$
$R_1=30/5=6$ e $R_2=30/6=5$
Consideriamo il nuovo sistema:
${(1*6*x-=3 (mod 5)),(1*5*x-=5 (mod 6)):}$
Risolviamo la prima congruenza: $6x -=3 (mod 5) => x -=3 (mod 5)$ quindi $x_1=3$.
Risolviamo la seconda congruenza: $5x -=5 (mod 6) $ $1 = 6 - 5*1 $ $5= 6*5 - 5*5 $ $=> x =-5 (mod 6)$ quindi $x_2=1$.
Soluzione del sistema: $bar x = 6*3 + 5*1 = 23 mod 30$
Spero sia tutto chiaro! (sto morendo dalla fatica ho scritto troppo
)Ciao ciao
GRAZIE!!avanzi una birra..
"kekko89":
GRAZIE!!avanzi una birra..
Magari!
salve a tutti. sfrutto questo post per un dubbio circa questa congruenza:
$6x=626824 (mod 22)$
osservando che è riducibile per due diventa: $3x=313412(mod 11)$
ma $313412$ dovrebbe potersi scrivere in una classe di resto equivalente. è corretto? e come si trova?
$6x=626824 (mod 22)$
osservando che è riducibile per due diventa: $3x=313412(mod 11)$
ma $313412$ dovrebbe potersi scrivere in una classe di resto equivalente. è corretto? e come si trova?
Trovi il resto della divisione per $11$ ^^
$313412= 28492*11+0$
quindi la tua congruenza risulta:
$3x\equiv 0 (11)$
$313412= 28492*11+0$
quindi la tua congruenza risulta:
$3x\equiv 0 (11)$
ah, ok. allora avevo capito bene.
a questo punto però, la congruenza trovata non è compatibile, xkè il MCD(3,11) non divide 0.
giusto?
a questo punto però, la congruenza trovata non è compatibile, xkè il MCD(3,11) non divide 0.
giusto?
Io dico che $MCD(3,11)=1|0$ visto che vale per tutti i numeri ^_^
Quindi la tua soluzione è:
$x\equiv 0(11)$
Quindi la tua soluzione è:
$x\equiv 0(11)$
si, hai ragione. grazie per la correzione.
con le congruenze dovrebbe avere a che fare anche quest'esercizio: trovare il periodo di $p^9$ e $p^10$ sapendo che il periodo di $p$ è $12$
Il periodo di $p^h$ è quel numero positivo a cui devo elevarlo per ottenere l'identità. Ma poichè il periodo di $p$ è 12, è come se fossimo in $Z_12$.
A questo punto possiamo utilizzare la formula : $n/(MCD(h,n))$
è corretto?
con le congruenze dovrebbe avere a che fare anche quest'esercizio: trovare il periodo di $p^9$ e $p^10$ sapendo che il periodo di $p$ è $12$
Il periodo di $p^h$ è quel numero positivo a cui devo elevarlo per ottenere l'identità. Ma poichè il periodo di $p$ è 12, è come se fossimo in $Z_12$.
A questo punto possiamo utilizzare la formula : $n/(MCD(h,n))$
è corretto?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo