Risoluzione sistemi di congruenze per sostituzione
Mi ritrovo ad affrontare la risoluzione dei sistemi di congruenze lineari tramite il metodo della sostituzione, ed essendo che secondo i miei calcoli il sistema sembra incompatibile, e non riuscendo a dimostrare "che la mia soluzione sia realmente vera", ho pensato di riportarla qui sul forum per chiedere se a voi il procedimento sembra corretto.
$\{(x -= 2 (mod 3)),(x -= 1 (mod 4)),(x -= 1 (mod 5)):}$
Qui l'unica cosa che possiamo dire è che non essendo i moduli a due a due coprimi non possiamo usare il teorema del resto cinese.
Per la compatibilità di ogni singola congruenza, sono tutte compatibili perchè tutti i primi termini delle congruenze sono pari ad $1$ e l'mcd che otteniamo è sempre 1 che divide sia $2$ che $1$ ? oppure ho sbagliato il ragionamento?
Vediamo come risolvere il sistema iniziando da $x -= 2 (mod 3)$ dico che questa si può scrivere come:
$3|x-2$ ovvero $x-2 = 3*h$ con $h in ZZ$
Riscrivendola come congruenza abbiamo che:
$3*h -=2 (mod 3)$
Quindi $x = 3*h$ è la soluzione della prima congruenza del nostro sistema, sostituiamola nella seconda congruenza ed abbiamo:
$3*h -= 1 (mod 4)$
Qui diciamo subito che $mcd(3,4)=1|1$ ovvero la congruenza è compatibile ed ammette una ed una sola soluzione (dato che l'mcd è 1);
La sviluppiamo dicendo che quindi $4| 3*h -1$
Possiamo sostituire $3$ ad h ed abbiamo che $4|4$ ergo possiamo dire che $3*h-1 = 4*k$ con $k in ZZ$
Riscrivendocela sotto forma di congruenza otteniamo che $3*h -= 1 (mod 4)$ che è appunto la congruenza di prima.
Ovvero $x=3*h=4*k+1$ con $k in ZZ$ è soluzione sia del primo che del secondo elemento del sistema, andiamo a sostituire nella terza congruenza ed otteniamo che:
$4*k+1 -= 1 (mod 5)$ ma $5$ non divide $4k+1 -1$
In conclusione la terza congruenza rende il sistema incompatibile.
Ho fatto bene i calcoli?
$\{(x -= 2 (mod 3)),(x -= 1 (mod 4)),(x -= 1 (mod 5)):}$
Qui l'unica cosa che possiamo dire è che non essendo i moduli a due a due coprimi non possiamo usare il teorema del resto cinese.
Per la compatibilità di ogni singola congruenza, sono tutte compatibili perchè tutti i primi termini delle congruenze sono pari ad $1$ e l'mcd che otteniamo è sempre 1 che divide sia $2$ che $1$ ? oppure ho sbagliato il ragionamento?
Vediamo come risolvere il sistema iniziando da $x -= 2 (mod 3)$ dico che questa si può scrivere come:
$3|x-2$ ovvero $x-2 = 3*h$ con $h in ZZ$
Riscrivendola come congruenza abbiamo che:
$3*h -=2 (mod 3)$
Quindi $x = 3*h$ è la soluzione della prima congruenza del nostro sistema, sostituiamola nella seconda congruenza ed abbiamo:
$3*h -= 1 (mod 4)$
Qui diciamo subito che $mcd(3,4)=1|1$ ovvero la congruenza è compatibile ed ammette una ed una sola soluzione (dato che l'mcd è 1);
La sviluppiamo dicendo che quindi $4| 3*h -1$
Possiamo sostituire $3$ ad h ed abbiamo che $4|4$ ergo possiamo dire che $3*h-1 = 4*k$ con $k in ZZ$
Riscrivendocela sotto forma di congruenza otteniamo che $3*h -= 1 (mod 4)$ che è appunto la congruenza di prima.
Ovvero $x=3*h=4*k+1$ con $k in ZZ$ è soluzione sia del primo che del secondo elemento del sistema, andiamo a sostituire nella terza congruenza ed otteniamo che:
$4*k+1 -= 1 (mod 5)$ ma $5$ non divide $4k+1 -1$
In conclusione la terza congruenza rende il sistema incompatibile.
Ho fatto bene i calcoli?
Risposte
Ciao, due cose:
1) Perché dici che moduli non sono a due a due coprimi?
2)
Questo ragionamento è purtroppo errato.
Giusto fino a $x-2=3h$
Poi non capisco come agisci quando dici: riscriviamola come congruenza.
In ogni caso, sarebbe inutile anche se stessi riscrivendo bene la congruenza: infatti sei passato dalla congruenza alla diofantea, ripassando alla congruenza non otterrai nulla di nuovo o utile.
Inoltre $x=3h$ vedi subito che non è sol della prima congruenza, perché $3h\equiv2(mod3)$ è assurda, perché $3h$ è multiplo di 3 e praticamente per definizione deve valere $0$ modulo 3.
Il modo giusto è questo: arrivi a $x=3h+2$, e sostituisci nella seconda:
$3h+2\equiv1(mod4)$ cioè $h\equiv1(mod4)$, come ti lascio verificare.
Continua tu sostituendo anche nell'ultima.
Ciao!
1) Perché dici che moduli non sono a due a due coprimi?
2)
"Neptune":
Vediamo come risolvere il sistema iniziando da $x -= 2 (mod 3)$ dico che questa si può scrivere come:
$3|x-2$ ovvero $x-2 = 3*h$ con $h in ZZ$
Riscrivendola come congruenza abbiamo che:
$3*h -=2 (mod 3)$
Quindi $x = 3*h$ è la soluzione della prima congruenza del nostro sistema
Questo ragionamento è purtroppo errato.
Giusto fino a $x-2=3h$
Poi non capisco come agisci quando dici: riscriviamola come congruenza.
In ogni caso, sarebbe inutile anche se stessi riscrivendo bene la congruenza: infatti sei passato dalla congruenza alla diofantea, ripassando alla congruenza non otterrai nulla di nuovo o utile.
Inoltre $x=3h$ vedi subito che non è sol della prima congruenza, perché $3h\equiv2(mod3)$ è assurda, perché $3h$ è multiplo di 3 e praticamente per definizione deve valere $0$ modulo 3.
Il modo giusto è questo: arrivi a $x=3h+2$, e sostituisci nella seconda:
$3h+2\equiv1(mod4)$ cioè $h\equiv1(mod4)$, come ti lascio verificare.
Continua tu sostituendo anche nell'ultima.
Ciao!
Ho proseguito in questo modo:
Abbiamo detto che $h=1$
Quindi se la seconda doveva essere del tipo $x=3*h+2 -= 1(mod4)$ sostituendo l'h trovata avremo che:
$x = 3*1+2 = 5$
Ovvero dalla seconda congruenza abbiamo che $x=5$
Sostituendolo nella terza però ci accorgiamo subito che $5$ non è una soluzione perchè $5 -= 0 (mod 5)$ mentre noi avremmo che $5 -= 1 (mod 5)$ che è sbagliata.
E' giusta così?
Abbiamo detto che $h=1$
Quindi se la seconda doveva essere del tipo $x=3*h+2 -= 1(mod4)$ sostituendo l'h trovata avremo che:
$x = 3*1+2 = 5$
Ovvero dalla seconda congruenza abbiamo che $x=5$
Sostituendolo nella terza però ci accorgiamo subito che $5$ non è una soluzione perchè $5 -= 0 (mod 5)$ mentre noi avremmo che $5 -= 1 (mod 5)$ che è sbagliata.
E' giusta così?
Ho provato a farla con il teorema cinese del resto e denominando con $C$ la soluzione del sistema mi esce:
$C = 20*2*2+15*1*1+12*1*3 = 131$
Ovvero applicando la formula: $C = r1*N1*x1+...+r_k*N_k*x_k$
Mentre la più piccola soluzione positiva mi esce $ 131 -= 11 (mod 60)$
Ma andando a sostituire $11$ alle $x$ del sistema mi accorgo che non va bene per la seconda perchè $11 -= 3 (mod 4)$
Ergo il sistema mi risulta non compatibile anche con il teorema cinese dei resti.
$C = 20*2*2+15*1*1+12*1*3 = 131$
Ovvero applicando la formula: $C = r1*N1*x1+...+r_k*N_k*x_k$
Mentre la più piccola soluzione positiva mi esce $ 131 -= 11 (mod 60)$
Ma andando a sostituire $11$ alle $x$ del sistema mi accorgo che non va bene per la seconda perchè $11 -= 3 (mod 4)$
Ergo il sistema mi risulta non compatibile anche con il teorema cinese dei resti.
Ti posto tutti i passaggi cosi ti rendi conto
$\{(x-=2(mod 3)),(x-=1(mod 4)),(x-=1(mod5)):}
Prendiamole prime due congruenze
$\{(x-=2(mod 3)),(x-=1(mod 4)):}
MCD(3,4)=1 $rArr$ $(3,4)|2-1$ cioè $(2-1)/(MCD)=1/1=1
$4=3*1+1
$3=1$*3+0$
Il sistema ammette soluzione
Adesso scriviamo il sistema nel seguente modo
$\{(x-=2+3h),(x-=1+4k):}
$2+3h=1+4k$ $rArr$ $1=3(-h)+4k
Identità Di Bezout
$(3,4)=1=4-3*1
Confrontanto quest'ultima uguaglianza con $1=3(-h)+4k
Otteniamo che $(-h=-1=1)$, $(k=1)$
Infatti se vai a sostituire questi valori al sistema ottieni che
$\{(x=2+3(1)=5),(x=1+4(1)=5):}
Tutte le soluzioni sono date da $x=5+12p$ equivalentemente $x-=5(mod 12)$
Adesso prendi la soluzione del sistema che hai svolto e lo metti con l'equazione che rimane del sistema iniziale
$\{(x-=5(mod 12)),(x-=1(mod5)):}
MCD (12,5)=1 $(5-1)/(MCD)=4/1=4
$12=5*2+2
$5=2*2+1
$2=1$*2+0$
Il sistema ammette soluzione
Adesso scriviamo il sistema nel seguente modo
$\{(x-=5+12h),(x-=1+5k):}
$5+12h=1+5k$ $rArr$ $4=12(-h)+5K
Identità di Bezout
$2=12-5*2
$1=5-2*2
(12,5)$=1=5-2*2=5-(12-5*2)*2=12(-2)+5(5)
Quindi abbiamo
$1=12(-2)+5(5)$ moltiplichiamo tutto per $4$ otteniamo $4=12(-8)+5(20)$quindi $(-h=-8=8),(k=20)
Sostituisco e ottengo
$\{(x-=5+12(8)=101),(x-=1+5(20)=101):}
Tutte le soluzioni sono date da:
$x=101+60p$ equivalente $x-=101(mod 60)
semplifichi ed ottieni
$x-=41(mod 60)
Spero di esserti stato di aiuto
$\{(x-=2(mod 3)),(x-=1(mod 4)),(x-=1(mod5)):}
Prendiamole prime due congruenze
$\{(x-=2(mod 3)),(x-=1(mod 4)):}
MCD(3,4)=1 $rArr$ $(3,4)|2-1$ cioè $(2-1)/(MCD)=1/1=1
$4=3*1+1
$3=1$*3+0$
Il sistema ammette soluzione
Adesso scriviamo il sistema nel seguente modo
$\{(x-=2+3h),(x-=1+4k):}
$2+3h=1+4k$ $rArr$ $1=3(-h)+4k
Identità Di Bezout
$(3,4)=1=4-3*1
Confrontanto quest'ultima uguaglianza con $1=3(-h)+4k
Otteniamo che $(-h=-1=1)$, $(k=1)$
Infatti se vai a sostituire questi valori al sistema ottieni che
$\{(x=2+3(1)=5),(x=1+4(1)=5):}
Tutte le soluzioni sono date da $x=5+12p$ equivalentemente $x-=5(mod 12)$
Adesso prendi la soluzione del sistema che hai svolto e lo metti con l'equazione che rimane del sistema iniziale
$\{(x-=5(mod 12)),(x-=1(mod5)):}
MCD (12,5)=1 $(5-1)/(MCD)=4/1=4
$12=5*2+2
$5=2*2+1
$2=1$*2+0$
Il sistema ammette soluzione
Adesso scriviamo il sistema nel seguente modo
$\{(x-=5+12h),(x-=1+5k):}
$5+12h=1+5k$ $rArr$ $4=12(-h)+5K
Identità di Bezout
$2=12-5*2
$1=5-2*2
(12,5)$=1=5-2*2=5-(12-5*2)*2=12(-2)+5(5)
Quindi abbiamo
$1=12(-2)+5(5)$ moltiplichiamo tutto per $4$ otteniamo $4=12(-8)+5(20)$quindi $(-h=-8=8),(k=20)
Sostituisco e ottengo
$\{(x-=5+12(8)=101),(x-=1+5(20)=101):}
Tutte le soluzioni sono date da:
$x=101+60p$ equivalente $x-=101(mod 60)
semplifichi ed ottieni
$x-=41(mod 60)
Spero di esserti stato di aiuto
Altro aggiornamento, facendo il tutto per bene sono arrivato a dire che la soluzione dell'ultima congruenza del sistema è in forma:
$5z+6$, e leggendo il risultato dato dalla professoressa dell'intero sistema, ovvero 41, mi ci posso ricondurre facendo $5*7+6$
Però adesso sorgono i dubbi, io avrei dovuto provare a mettere $Z$ per tentativi finchè non mi usciva un numero buono per tutti o c'è un metodo piu veloce che mi sfugge?
Ed anche, come mai tramite il teorema cinese del resto mi usciva $11$, che è sempre nella forma $5z+6$ ma non è la soluzione di tutti, invece di uscirmi 41? ovvero a voi esce 41 con il teorema cinese del resto?
$5z+6$, e leggendo il risultato dato dalla professoressa dell'intero sistema, ovvero 41, mi ci posso ricondurre facendo $5*7+6$
Però adesso sorgono i dubbi, io avrei dovuto provare a mettere $Z$ per tentativi finchè non mi usciva un numero buono per tutti o c'è un metodo piu veloce che mi sfugge?
Ed anche, come mai tramite il teorema cinese del resto mi usciva $11$, che è sempre nella forma $5z+6$ ma non è la soluzione di tutti, invece di uscirmi 41? ovvero a voi esce 41 con il teorema cinese del resto?
"Neptune":Ho postato la soluzione dell'eserizio è risulta X=41, controlla tutti i relativi passaggi.
Altro aggiornamento, facendo il tutto per bene sono arrivato a dire che la soluzione dell'ultima congruenza del sistema è in forma:
$5z+6$, e leggendo il risultato dato dalla professoressa dell'intero sistema, ovvero 41, mi ci posso ricondurre facendo $5*7+6$
Però adesso sorgono i dubbi, io avrei dovuto provare a mettere $Z$ per tentativi finchè non mi usciva un numero buono per tutti o c'è un metodo piu veloce che mi sfugge?
Ed anche, come mai tramite il teorema cinese del resto mi usciva $11$, che è sempre nella forma $5z+6$ ma non è la soluzione di tutti, invece di uscirmi 41? ovvero a voi esce 41 con il teorema cinese del resto?
"Gladior":
Ti posto tutti i passaggi cosi ti rendi conto
$\{(x-=2(mod 3)),(x-=1(mod 4)),(x-=1(mod5)):}
Prendiamole prime due congruenze
$\{(x-=2(mod 3)),(x-=1(mod 4)):}
MCD(3,4)=1 $rArr$ $(3,4)|2-1$ cioè $(2-1)/(MCD)=1/1=1
$4=3*1+1
$3=1$*3+0$
Il sistema ammette soluzione
Adesso scriviamo il sistema nel seguente modo
$\{(x-=2+3h),(x-=1+4k):}
$2+3h=1+4k$ $rArr$ $1=3(-h)+4k
Identità Di Bezout
$(3,4)=1=4-3*1
Confrontanto quest'ultima uguaglianza con $1=3(-h)+4k
Otteniamo che $(-h=-1=1)$, $(k=1)$
Infatti se vai a sostituire questi valori al sistema ottieni che
$\{(x=2+3(1)=5),(x=1+4(1)=5):}
Tutte le soluzioni sono date da $x=5+12p$ equivalentemente $x-=5(mod 12)$
Adesso prendi la soluzione del sistema che hai svolto e lo metti con l'equazione che rimane del sistema iniziale
$\{(x-=5(mod 12)),(x-=1(mod5)):}
MCD (12,5)=1 $(5-1)/(MCD)=4/1=4
$12=5*2+2
$5=2*2+1
$2=1$*2+0$
Il sistema ammette soluzione
Adesso scriviamo il sistema nel seguente modo
$\{(x-=5+12h),(x-=1+5k):}
$5+12h=1+5k$ $rArr$ $4=12(-h)+5K
Identità di Bezout
$2=12-5*2
$1=5-2*2
(12,5)$=1=5-2*2=5-(12-5*2)*2=12(-2)+5(5)
Quindi abbiamo
$1=12(-2)+5(5)$ moltiplichiamo tutto per $4$ otteniamo $4=12(-8)+5(20)$quindi $(-h=-8=8),(k=20)
Sostituisco e ottengo
$\{(x-=5+12(8)=101),(x-=1+5(20)=101):}
Tutte le soluzioni sono date da:
$x=101+60p$ equivalente $x-=101(mod 60)
semplifichi ed ottieni
$x-=41(mod 60)
Spero di esserti stato di aiuto
Questa me la devo rivedere per bene, perchè non utilizzo questi passaggi e quindi mi sfugge qualcosa. Ora me lo stampo, lo pastrocchio e vedo e se riesco a capirlo
Se c dovessero essere problemi fammi sapere 
"Gladior":Ho postato la soluzione dell'eserizio è risulta X=41, controlla tutti i relativi passaggi.[/quote]
[quote="Neptune"]Altro aggiornamento, facendo il tutto per bene sono arrivato a dire che la soluzione dell'ultima congruenza del sistema è in forma:
$5z+6$, e leggendo il risultato dato dalla professoressa dell'intero sistema, ovvero 41, mi ci posso ricondurre facendo $5*7+6$
Però adesso sorgono i dubbi, io avrei dovuto provare a mettere $Z$ per tentativi finchè non mi usciva un numero buono per tutti o c'è un metodo piu veloce che mi sfugge?
Ed anche, come mai tramite il teorema cinese del resto mi usciva $11$, che è sempre nella forma $5z+6$ ma non è la soluzione di tutti, invece di uscirmi 41? ovvero a voi esce 41 con il teorema cinese del resto?
Non vorrei approfittare troppo di te, ma se hai tempo e voglia ti andrebbe di scrivermi la soluzione anche tramite il teorema cinese del resto?
Grazie comunque per la pazienza, suppongo ce ne voglia tanta per vedere i miei calcoli
"Neptune":Ho postato la soluzione dell'eserizio è risulta X=41, controlla tutti i relativi passaggi.[/quote]
[quote="Gladior"][quote="Neptune"]Altro aggiornamento, facendo il tutto per bene sono arrivato a dire che la soluzione dell'ultima congruenza del sistema è in forma:
$5z+6$, e leggendo il risultato dato dalla professoressa dell'intero sistema, ovvero 41, mi ci posso ricondurre facendo $5*7+6$
Però adesso sorgono i dubbi, io avrei dovuto provare a mettere $Z$ per tentativi finchè non mi usciva un numero buono per tutti o c'è un metodo piu veloce che mi sfugge?
Ed anche, come mai tramite il teorema cinese del resto mi usciva $11$, che è sempre nella forma $5z+6$ ma non è la soluzione di tutti, invece di uscirmi 41? ovvero a voi esce 41 con il teorema cinese del resto?
Non vorrei approfittare troppo di te, ma se hai tempo e voglia ti andrebbe di scrivermi la soluzione anche tramite il teorema cinese del resto?
Grazie comunque per la pazienza, suppongo ce ne voglia tanta per vedere i miei calcoli
[/quote]Magari non subito , in tarda serata credo troverai quello che ti serve
"Gladior":
Se c dovessero essere problemi fammi sapere
Il punto è che non ci è stato fatto vedere in questi termini, quindi per questo mi sembrava strano benchè la capisco, vorrei però riuscire a risolverla con i metodi dati dalla professoressa.
Ora ti riscrivo, tramite metodo di sostituzione, dove sono arrivato io (così grossomodo ti mostro anche il mio modo di operare):
Per completezza riscrivo il sistema
$\{(x -= 2 (mod 3)),(x -= 1 (mod 4)),(x -= 1 (mod 5)):}$
Prendo la prima, ovvero $x -= 2 (mod 3)$
La posso scrivere come:
$3| x-2$ ovvero $x = 3*h+2$ con $h in ZZ$ è la soluzione della prima congruenza, la sostituisco nella seconda ed ottengo:
$3*h+2 -= 1 (mod 4)$
$3*h -= -1 (mod 4)$
$-1 -= 3 (mod 4)$
quindi per transitività:
$3*h -= 3 (mod 4)$
$mcd (3,4) = 1$ quindi posso dividere per tre ottenendo:
$h -= 1 (mod 4)$
ovvero $4| h-1$ e quindi $h = 4*k+1$ con $k in ZZ$
quindi $x = 3h+2 = 3*(4*k+1)+2 = 12*k +5$
Questa la vado a sostituire nella terza congruenza ed ottengo che:
$12k+5 -= 1 (mod 5)$
$12k -= -4 (mod 5)$
$-4 -= 1 (mod 5)$
Per transitività:
$12k -= 1 (mod 5)$
$5 | 12k -1$ ovvero $12k-1 = 5 * z$ con $z in ZZ$
$12k = 5*z+1$
$12k+5 = 5 * z + 6$
Quindi in conclusione:
$x = 3h+2 = 3*(4*k+1)+2 = 12*k +5 = 5 * z + 6$
Ed infatti abbiamo che per $x = 5*7+6=41$ il sistema è risolto.
Il punto è che io sapendo che il risultato è $41$ mi sono trovato subito qual'e il $k$ che soddisfa tutto il sistema. Ma altrimenti come lo dovevo trovare $k$? per tentativi la vedo molto lunga e dispersiva la cosa.
Sistema di partenza
$\{(x = 2 mod 3),(x = 1 mod 4),(x = 1 mod 5):}
Sistema 1
$\{(x = 1 mod 3),(x = 0 mod 4),(x = 0 mod 5):}
$k1 = 20$$................$ $n1 = 3$
$3r + 20s = 1$
$r = 7$............ $s = -1$
$x1 = -20$
Sistema 2
$\{(x =0 mod 3),(x = 1 mod 4),(x = 0 mod 5):}
$k2 = 15$............... $n2 = 4$
$4r + 15s = 1
$r = 4$........$ s = -1
$x2 = -15
Sistema 3
$\{(x = 0 mod 3),(x = 0 mod 4),(x = 1 mod 5):}
$k3 = 12$..................$ n3 = 5$
$5r + 12s = 1
$r = 5$.............$ s = -2
$x3 = -24
Una soluzione è: $x= (-20*2)-(15*1)-(24*1)=-79$
Ogni altra soluzione è del tipo $x = -79 + 60h$ da questa ti ricavi $x=-79+60(2)=-79+120=41$
La più piccola soluzione positiva è $x = 41$ equivalente $x-=41(mod60)$
Fammi sapere se sono stato chiaro................
$\{(x = 2 mod 3),(x = 1 mod 4),(x = 1 mod 5):}
Sistema 1
$\{(x = 1 mod 3),(x = 0 mod 4),(x = 0 mod 5):}
$k1 = 20$$................$ $n1 = 3$
$3r + 20s = 1$
$r = 7$............ $s = -1$
$x1 = -20$
Sistema 2
$\{(x =0 mod 3),(x = 1 mod 4),(x = 0 mod 5):}
$k2 = 15$............... $n2 = 4$
$4r + 15s = 1
$r = 4$........$ s = -1
$x2 = -15
Sistema 3
$\{(x = 0 mod 3),(x = 0 mod 4),(x = 1 mod 5):}
$k3 = 12$..................$ n3 = 5$
$5r + 12s = 1
$r = 5$.............$ s = -2
$x3 = -24
Una soluzione è: $x= (-20*2)-(15*1)-(24*1)=-79$
Ogni altra soluzione è del tipo $x = -79 + 60h$ da questa ti ricavi $x=-79+60(2)=-79+120=41$
La più piccola soluzione positiva è $x = 41$ equivalente $x-=41(mod60)$
Fammi sapere se sono stato chiaro................
"Gladior":
Sistema di partenza
$\{(x = 2 mod 3),(x = 1 mod 4),(x = 1 mod 5):}
Sistema 1
$\{(x = 1 mod 3),(x = 0 mod 4),(x = 0 mod 5):}
$k1 = 20$$................$ $n1 = 3$
$3r + 20s = 1$
$r = 7$............ $s = -1$
$x1 = -20$
Sistema 2
$\{(x =0 mod 3),(x = 1 mod 4),(x = 0 mod 5):}
$k2 = 15$............... $n2 = 4$
$4r + 15s = 1
$r = 4$........$ s = -1
$x2 = -15
Sistema 3
$\{(x = 0 mod 3),(x = 0 mod 4),(x = 1 mod 5):}
$k3 = 12$..................$ n3 = 5$
$5r + 12s = 1
$r = 5$.............$ s = -2
$x3 = -24
Una soluzione è: $x= (-20*2)-(15*1)-(24*1)=-79$
Ogni altra soluzione è del tipo $x = -79 + 60h$ da questa ti ricavi $x=-79+60(2)=-79+120=41$
La più piccola soluzione positiva è $x = 41$ equivalente $x-=41(mod60)$
Fammi sapere se sono stato chiaro................
Riguardo il teorema del resto ho riguardato i miei conti ed era solo un errore di calcolo, così mi imparo a scrivere un esercizio su "post-it"
Benchè comunque hai un metodo di sviluppo molto diverso dal mio.
Però con il metodo della sostituzione mi manca ancora "il passaggio finale", ovvero se rivedi il mio svolgimento che ti ho postato prima mi ritrovo a sapere che la soluzione è del tipo $5*z+6$ ma riesco a calcolarmi $z=7$ solo perchè so già il risultato, altrimenti dovrei andare a tentativi ovvero "metterze z=1" e vedere "soddisfa tutte le congruenze?" e cosi finchè non mi trovo appunto $z=7$ ma è troppo dispersiva come cosa, esisterà un procedimento per evitare di andare a tentativi, o no?
"Neptune":
[quote="Gladior"]Se c dovessero essere problemi fammi sapere
Il punto è che non ci è stato fatto vedere in questi termini, quindi per questo mi sembrava strano benchè la capisco, vorrei però riuscire a risolverla con i metodi dati dalla professoressa.
Ora ti riscrivo, tramite metodo di sostituzione, dove sono arrivato io (così grossomodo ti mostro anche il mio modo di operare):
Per completezza riscrivo il sistema
$\{(x -= 2 (mod 3)),(x -= 1 (mod 4)),(x -= 1 (mod 5)):}$
Prendo la prima, ovvero $x -= 2 (mod 3)$
La posso scrivere come:
$3| x-2$ ovvero $x = 3*h+2$ con $h in ZZ$ è la soluzione della prima congruenza, la sostituisco nella seconda ed ottengo:
$3*h+2 -= 1 (mod 4)$
$3*h -= -1 (mod 4)$
$-1 -= 3 (mod 4)$
quindi per transitività:
$3*h -= 3 (mod 4)$
$mcd (3,4) = 1$ quindi posso dividere per tre ottenendo:
$h -= 1 (mod 4)$
ovvero $4| h-1$ e quindi $h = 4*k+1$ con $k in ZZ$
quindi $x = 3h+2 = 3*(4*k+1)+2 = 12*k +5$
Questa la vado a sostituire nella terza congruenza ed ottengo che:
$12k+5 -= 1 (mod 5)$
$12k -= -4 (mod 5)$
$-4 -= 1 (mod 5)$
Per transitività:
$12k -= 1 (mod 5)$
$5 | 12k -1$ ovvero $12k-1 = 5 * z$ con $z in ZZ$
$12k = 5*z+1$
$12k+5 = 5 * z + 6$
Quindi in conclusione:
$x = 3h+2 = 3*(4*k+1)+2 = 12*k +5 = 5 * z + 6$
Ed infatti abbiamo che per $x = 5*7+6=41$ il sistema è risolto.
Il punto è che io sapendo che il risultato è $41$ mi sono trovato subito qual'e il $k$ che soddisfa tutto il sistema. Ma altrimenti come lo dovevo trovare $k$? per tentativi la vedo molto lunga e dispersiva la cosa.[/quote]
Forse quello che ti manca è il teorema della divisione successiva di euclide , e l'identità di Bezout, conoscendo questi argomenti, arrivi facilmente a comprendere i passaggi della tua professoressa. Anche perchè alcune volte i professori omettono dei passaggi stupidi ma che sono indispensabili per la comprensione.
In bocca a lupo
Nono, lo conosco bezout e quello delle divisioni successive pure, quei passaggi che ti ho scritto gli ho scritti io (intendevo che la professoressa fa passaggi diversi dai tuoi).
Quello che mi manca è, arrivato alla formula $x= 5z+6$ come faccio a dire "in maniera algoritmica" o comunque tramite formula qual'è la $z$ che sostituita nella formula mi soddisfa tutto il sistema?
Perchè ripeto per tenativi, o sapendo il risultato finale, sai che $z=7$ e risolto il problema. Ma se non sai il risultato finale? mica posso calcolarmi l'identità di bezout qui, perchè non mi interessa "trovare un generico z tc..." mi serve trovare "l'unizo z t.c sia soddisfatto l'intero sistema".
Quello che mi manca è, arrivato alla formula $x= 5z+6$ come faccio a dire "in maniera algoritmica" o comunque tramite formula qual'è la $z$ che sostituita nella formula mi soddisfa tutto il sistema?
Perchè ripeto per tenativi, o sapendo il risultato finale, sai che $z=7$ e risolto il problema. Ma se non sai il risultato finale? mica posso calcolarmi l'identità di bezout qui, perchè non mi interessa "trovare un generico z tc..." mi serve trovare "l'unizo z t.c sia soddisfatto l'intero sistema".
Scusami se ti faccio questa domanda
Sai riconoscere quando un sistema ammette soluzioni? Mostrami questo procedimento come lo esegui.
Sai riconoscere quando un sistema ammette soluzioni? Mostrami questo procedimento come lo esegui.
Se possiamo applicare il teorema cinese del resto possiamo dire che il sistema ammette soluzioni se i moduli sono a due a due coprimi e se le singole congruenze sono compatibili. Per vedere se le singole congruenze sono compatibili facciamo l'mcd del primo termine della congruenza e del modulo e tale mcd deve risultare divisore del secondo termine della congruenza, ovvero:
$ax -= b (mod n)$ è compatibile se $mcd(a,n)|b$
Nel nostro caso gli esponenti di $a$ sono tutti uno quindi sono tutte compatibili, inoltre stiamo applicando il metodo di risoluzione per sostituzione quindi l'unico modo per vedere se il sistema è compatibile e trovare man mano le $x$ che soddisfano le varie congruenze.
Da quel che so il sistema è compatibile se esiste almeno 1 soluzione.
Se sbaglio in qualche cosa correggimi perfavore. Purtroppo sto studiando da poco il metodo per sostituzione e difatti sono qui perchè non mi è del tutto chiaro.
$ax -= b (mod n)$ è compatibile se $mcd(a,n)|b$
Nel nostro caso gli esponenti di $a$ sono tutti uno quindi sono tutte compatibili, inoltre stiamo applicando il metodo di risoluzione per sostituzione quindi l'unico modo per vedere se il sistema è compatibile e trovare man mano le $x$ che soddisfano le varie congruenze.
Da quel che so il sistema è compatibile se esiste almeno 1 soluzione.
Se sbaglio in qualche cosa correggimi perfavore. Purtroppo sto studiando da poco il metodo per sostituzione e difatti sono qui perchè non mi è del tutto chiaro.
"Neptune":Cosa intendi per compatibili? che ammette soluzione?
Se possiamo applicare il teorema cinese del resto possiamo dire che il sistema ammette soluzioni se i moduli sono a due a due coprimi e se le singole congruenze sono compatibili. Per vedere se le singole congruenze sono compatibili facciamo l'mcd del primo termine della congruenza e del modulo e tale mcd deve risultare divisore del secondo termine della congruenza, ovvero:
$ax -= b (mod n)$ è compatibile se $mcd(a,n)|b$
Nel nostro caso gli esponenti di $a$ sono tutti uno quindi sono tutte compatibili, inoltre stiamo applicando il metodo di risoluzione per sostituzione quindi l'unico modo per vedere se il sistema è compatibile e trovare man mano le $x$ che soddisfano le varie congruenze.
Da quel che so il sistema è compatibile se esiste almeno 1 soluzione.
Se sbaglio in qualche cosa correggimi perfavore. Purtroppo sto studiando da poco il metodo per sostituzione e difatti sono qui perchè non mi è del tutto chiaro.
Perchè un qualsiasi sistema è verificato cioè ha soluzione se le singole (equazioni,Congruenze, etc ) sono verificate cioè ammettono soluzioni. Se una (equazioni,Congruenze, etc ) è impossibile tutto il sistema è impossibile. Il sistema svolge la funzione di unificare le soluzioni delle singole (equazioni,Congruenze, etc ).Che io sappia, speriamo che qualcuno possa unirsi per confermare.
"Gladior":Cosa intendi per compatibili? che ammette soluzione?
[quote="Neptune"]Se possiamo applicare il teorema cinese del resto possiamo dire che il sistema ammette soluzioni se i moduli sono a due a due coprimi e se le singole congruenze sono compatibili. Per vedere se le singole congruenze sono compatibili facciamo l'mcd del primo termine della congruenza e del modulo e tale mcd deve risultare divisore del secondo termine della congruenza, ovvero:
$ax -= b (mod n)$ è compatibile se $mcd(a,n)|b$
Nel nostro caso gli esponenti di $a$ sono tutti uno quindi sono tutte compatibili, inoltre stiamo applicando il metodo di risoluzione per sostituzione quindi l'unico modo per vedere se il sistema è compatibile e trovare man mano le $x$ che soddisfano le varie congruenze.
Da quel che so il sistema è compatibile se esiste almeno 1 soluzione.
Se sbaglio in qualche cosa correggimi perfavore. Purtroppo sto studiando da poco il metodo per sostituzione e difatti sono qui perchè non mi è del tutto chiaro.
Perchè un qualsiasi sistema è verificato cioè ha soluzione se le singole (equazioni,Congruenze, etc ) sono verificate cioè ammettono soluzioni. Se una (equazioni,Congruenze, etc ) è impossibile tutto il sistema è impossibile. Il sistema svolge la funzione di unificare le soluzioni delle singole (equazioni,Congruenze, etc ).Che io sappia, speriamo che qualcuno possa unirsi per confermare.[/quote]
Esatto, ma può anche essere che tutte le congruenze siano compatibili ma non abbiamo una soluzione in comune.
Io, nel mio svolgimento, ho visto come siano compatibili ed ho anche scritto "in che forma sarà la soluzione" fino ad arrivare a dire che la soluzione del sistema sarà in forma $5*z+6$ con $z in ZZ$. La questione è che non è verifato per ogni $z$, ed il problema è trovare per quale $z$ lo è.
Non so e sono chiaro in quel che dico.
Direi di tagliare la testa al toro, non è che qualcuno mi saprebbe citare una guida che spiega come risolvere i sistemi di congruenze lineari tramite sostituzione?
Perchè un mio collega di università mi ha fatto vedere come sviluppare questa, provo a farne un'altra io e sempre non mi riesce (ovvero trovo una soluzione che è valida per 2 congruenze lineari su tre del sistema). Quindi forse è meglio che mi rileggo bene come si fa, invece di perdere tempo ad andare a tenativi.
Perchè un mio collega di università mi ha fatto vedere come sviluppare questa, provo a farne un'altra io e sempre non mi riesce (ovvero trovo una soluzione che è valida per 2 congruenze lineari su tre del sistema). Quindi forse è meglio che mi rileggo bene come si fa, invece di perdere tempo ad andare a tenativi.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo