Sistemi Congruenze
ciao a tutti ragazzi! devo risolvere un sistema di congruenze, ma non mi è ben chiaro il metodo:
$x -= 8 (mod9)$
$x -= 2(mod4)$
queste due congruenze sono ovviamente a sistema. Io ho pensato così:
Poiché esistono N = n1n2n3....nk diverse scelte di sequenze(a1a2a3....ak) , è naturale cercare le soluzioni del sistema nel modulo N: in questo caso n1n2 = 36
quindi devo risolvere quelle congruenze rispetto a mod36
o meglio:
$x + 36y = 8$
e
$x + 36y = 2$
il problema è che mi si annullano sia la X che le Y. o meglio, quando risolvo il sistema, mi esce ad esempio sostituendo $y = (8 - x)/36$ nella seconda equazione 288 = 72 che è ovviamente sbagliato...dove può essere l'errore??
grazie mille!!!
$x -= 8 (mod9)$
$x -= 2(mod4)$
queste due congruenze sono ovviamente a sistema. Io ho pensato così:
Poiché esistono N = n1n2n3....nk diverse scelte di sequenze(a1a2a3....ak) , è naturale cercare le soluzioni del sistema nel modulo N: in questo caso n1n2 = 36
quindi devo risolvere quelle congruenze rispetto a mod36
o meglio:
$x + 36y = 8$
e
$x + 36y = 2$
il problema è che mi si annullano sia la X che le Y. o meglio, quando risolvo il sistema, mi esce ad esempio sostituendo $y = (8 - x)/36$ nella seconda equazione 288 = 72 che è ovviamente sbagliato...dove può essere l'errore??
grazie mille!!!
Risposte
Hai studiato il teorema cinese dei resti?
"Paolo90":
Hai studiato il teorema cinese dei resti?
si ma non ci capisco niente sul libro, difatti volevo provare questo metodo che mi sembrava più semplice
non funziona vero??
Forse funzionerà anche ma è mooooolto più comodo usare il th cinese, visto che puoi.
Per prima cosa scrivi un'identità di Bézout per i moduli, vale a dire 9 e 4 (dai che questo non è difficile!)
Per prima cosa scrivi un'identità di Bézout per i moduli, vale a dire 9 e 4 (dai che questo non è difficile!)
"Paolo90":
Forse funzionerà anche ma è mooooolto più comodo usare il th cinese, visto che puoi.
Per prima cosa scrivi un'identità di Bézout per i moduli, vale a dire 9 e 4 (dai che questo non è difficile!)
uhm allora l'identità di bezout mi dice che è possibile trovare due interi u,v tale che:
au + bv = d
dove d è il massimo comune divisore tra a e b
quindi dovrebbe essere:
u + 8v = 1
u +2v = 1
giusto?:P
No, si vede che non mi sono spiegato bene.
Devi trovare l'MCD tra 9 e 4 e scrivere un'identità di Bézout.
Qual è l'MCD tra 9 e 4?
E' .... e quindi proprio per questo possiamo applicare il th cinese.
Adesso devi trovarmi un'identità di Bezout per 9 e 4.
Devi trovare l'MCD tra 9 e 4 e scrivere un'identità di Bézout.
Qual è l'MCD tra 9 e 4?
E' .... e quindi proprio per questo possiamo applicare il th cinese.
Adesso devi trovarmi un'identità di Bezout per 9 e 4.
"Paolo90":
No, si vede che non mi sono spiegato bene.
Devi trovare l'MCD tra 9 e 4 e scrivere un'identità di Bézout.
Qual è l'MCD tra 9 e 4?
E' .... e quindi proprio per questo possiamo applicare il th cinese.
Adesso devi trovarmi un'identità di Bezout per 9 e 4.
ops mi sa che avevo capito male io, scusa...
beh l'MCD(9,4) = 1
quindi l'identità di Bezout per 9 e 4 è:
9u + 4v = 1?
quindi u = 1 v = -2
corretto?
edit: per curiosità, ma non c'entra con questo esercizio, se avessi avuto ad esempio i numeri 30 e 40 anzichè 9 e 4, avrei potuto applicare sempre 9u + 4v = MCD(30,40) oppure era sbagliato?
"Lordofnazgul":
beh l'MCD(9,4) = 1
quindi l'identità di Bezout per 9 e 4 è:
9u + 4v = 1?
quindi u = 1 v = -2
corretto?
Sì, corretto. L'identità è $9*1+4*(-2)=1$.
Ora fai attenzione, facciamo una magia.
Moltiplichiamo ambo i membri per $8-2$ (che è la differenza degli altri due numeri del sistema: i resti, cioè 8 e 2).Sei d'accordo con me che $1=9*1+4*(-2)$ diventa $(8-2)=(8-2)(9*1+4*(-2))$ e ancora $(8-2)=6(9*1+4*(-2))$.
Applichiamo la proprietà distributiva: $(8-2)=6*(9*1)+6*(4*(-2))$.
Ancora un ultimo trucchetto e abbiamo finito: portiamo a primo membro il primo termine:
$(8-2)-6*(9*1)=+6*(4*(-2))$
e adesso portiamo a secondo membro il 2 della prima parentesi:
$8-6*(9*1)=+6*(4*(-2))+2$
Se fai i conti resta $-46=-46$.
E direi che puoi farla finita qui. Scommettiamo che quella lì è la tua soluzione? Ovviamente modulo 36, quindi se vuoi quella positiva aggiungi qualche multiplo di 36: $-46+36*2=26$.
Adesso ti chiedo: hai capito? Se hai capito mi spieghi perchè ciò che ho fatto funziona? Come mai quella lì è proprio la soluzione? Perchè lo affermo con certezza?
P.S. Spero sia tutto chiaro. Ovviamente, se ci sono dubbi, sono qui.
edit: per curiosità, ma non c'entra con questo esercizio, se avessi avuto ad esempio i numeri 30 e 40 anzichè 9 e 4, avrei potuto applicare sempre 9u + 4v = MCD(30,40) oppure era sbagliato?
Non ho capito bene che cosa intendi. Se al posto di 9 e 4 avevi altri due numeri $x$ e $y$ dovevi cercare l'identità di Bézout tra $x$ e $y$...
Ok?
"Paolo90":
[quote="Lordofnazgul"]
beh l'MCD(9,4) = 1
quindi l'identità di Bezout per 9 e 4 è:
9u + 4v = 1?
quindi u = 1 v = -2
corretto?
Sì, corretto. L'identità è $9*1+4*(-2)=1$.
Ora fai attenzione, facciamo una magia.
Moltiplichiamo ambo i membri per $8-2$ (che è la differenza degli altri due numeri del sistema: i resti, cioè 8 e 2).Sei d'accordo con me che $1=9*1+4*(-2)$ diventa $(8-2)=(8-2)(9*1+4*(-2))$ e ancora $(8-2)=6(9*1+4*(-2))$.
Applichiamo la proprietà distributiva: $(8-2)=6*(9*1)+6*(4*(-2))$.
Ancora un ultimo trucchetto e abbiamo finito: portiamo a primo membro il primo termine:
$(8-2)-6*(9*1)=+6*(4*(-2))$
e adesso portiamo a secondo membro il 2 della prima parentesi:
$8-6*(9*1)=+6*(4*(-2))+2$
Se fai i conti resta $-46=-46$.
E direi che puoi farla finita qui. Scommettiamo che quella lì è la tua soluzione? Ovviamente modulo 36, quindi se vuoi quella positiva aggiungi qualche multiplo di 36: $-46+36*2=26$.
Adesso ti chiedo: hai capito? Se hai capito mi spieghi perchè ciò che ho fatto funziona? Come mai quella lì è proprio la soluzione? Perchè lo affermo con certezza?
P.S. Spero sia tutto chiaro. Ovviamente, se ci sono dubbi, sono qui.
edit: per curiosità, ma non c'entra con questo esercizio, se avessi avuto ad esempio i numeri 30 e 40 anzichè 9 e 4, avrei potuto applicare sempre 9u + 4v = MCD(30,40) oppure era sbagliato?
Non ho capito bene che cosa intendi. Se al posto di 9 e 4 avevi altri due numeri $x$ e $y$ dovevi cercare l'identità di Bézout tra $x$ e $y$...
Ok?
[/quote]beh se devo essere sincero, ho capito il procedimento, però il perchè hai fatto così sto ancora cercando di capirlo :p
Stavo pensando, hai sostanzialmente spostato i membri in modo tale che ne uscisse un'identità, in modo tale che uscendo un'identità, l'equazione era verificata e quella era la soluzione.
Giusto?
Se invece avessi avuto un sistema a 3 congruenze, come mi sarei dovuto comportare?
grazie mille ancora! scusa per il disturbo!
edit: se al posto di 9 e 4 avessi avuto x e y tali che x = 30 e y = 40, avrei dovuto fare mcd(30,40) = 10 e dovevo scrivere 30u + 40v = 10 giusto?
Qualche precisazione doverosa.
1. il modo di procedere che ti ho fatto vedere è una procedura standard (e costituisce anche una dimostrazione - costruttiva- del CRT). La sostanza del ragionamento è: prendi Bezout con i tuoi moduli e moltiplica ambo i membri per la differenza dei resti; quella che hai ottenuto è ancora un'identità. Il trucco sta nello spostare "di qui e di là" i termini in modo da ottenere quello che ti serve: nel tuo caso, avevi bisogno di un numero che si potesse scrivere come $8+9k$ e contemporaneamente come $2+4k$. E l'abbiamo trovato.
2. Ricordo che quanto fatto è applicabile solo se moduli sono coprimi; se avessi avuto $mod4$ e $mod2$ andava a farsi benedire tutto.
3. Se hai un sistema con tre o più equazioni ne risolvi due alla volta, per ridurti a un sistema più piccolo.
Ok?
1. il modo di procedere che ti ho fatto vedere è una procedura standard (e costituisce anche una dimostrazione - costruttiva- del CRT). La sostanza del ragionamento è: prendi Bezout con i tuoi moduli e moltiplica ambo i membri per la differenza dei resti; quella che hai ottenuto è ancora un'identità. Il trucco sta nello spostare "di qui e di là" i termini in modo da ottenere quello che ti serve: nel tuo caso, avevi bisogno di un numero che si potesse scrivere come $8+9k$ e contemporaneamente come $2+4k$. E l'abbiamo trovato.
2. Ricordo che quanto fatto è applicabile solo se moduli sono coprimi; se avessi avuto $mod4$ e $mod2$ andava a farsi benedire tutto.
3. Se hai un sistema con tre o più equazioni ne risolvi due alla volta, per ridurti a un sistema più piccolo.
Ok?
"Paolo90":
Qualche precisazione doverosa.
1. il modo di procedere che ti ho fatto vedere è una procedura standard (e costituisce anche una dimostrazione - costruttiva- del CRT). La sostanza del ragionamento è: prendi Bezout con i tuoi moduli e moltiplica ambo i membri per la differenza dei resti; quella che hai ottenuto è ancora un'identità. Il trucco sta nello spostare "di qui e di là" i termini in modo da ottenere quello che ti serve: nel tuo caso, avevi bisogno di un numero che si potesse scrivere come $8+9k$ e contemporaneamente come $2+4k$. E l'abbiamo trovato.
2. Ricordo che quanto fatto è applicabile solo se moduli sono coprimi; se avessi avuto $mod4$ e $mod2$ andava a farsi benedire tutto.
3. Se hai un sistema con tre o più equazioni ne risolvi due alla volta, per ridurti a un sistema più piccolo.
Ok?
ok ci sono grazie mille! ho aggiunto questo metodo ai miei appunti, sei stato gentilissimo eheh!
ti rubo ancora un attimo:
io ho provato a risolvere questo sistema di congruenze:
$x -=36(mod99)$
e $x -= -36(mod171)$
in quest'altro modo visto che 99 e 171 non sono coprimi:
$36 + k99 = -36 +h171$
$72 = h171 - k99$
così h = k = 1 e quindi avrei $ x = 36 + 99 = 135$ come soluzione particolare.
il procedimento secondo te è corretto? lo posso estendere come soluzione generalizzata del sistema? se sì, come?:p
scusa ancora per il disturbo..
ultimissima cosa: questo metodo se corretto, può essere applicato anche a un sistema di 3 o più congruenze?? grazie mille!
Sì, diciamo che nel caso di no coprimalità le cose si fanno più delicate.
Ad occhio direi che va bene.
Puoi giungere come a quella soluzione intersecando gli insiemi delle soluzioni della prima e della seconda equazione. In altri termini, la prima equazione ha come insieme delle soluzioni $sigma_1={z in ZZ " tali che " z=99k+36, " " k in ZZ}={...-63, 36,135... }$; la seconda $sigma_2={z in ZZ " tali che " z=171h-36, " " h in ZZ}={...-36, 135... }$.
Vedi subito che 135 sta nell'intersezione, quindi è soluzione comune. Se ne becchi una, le becchi tutte aggiungendoci multipli del mcm dei moduli: la soluzione generale del tuo sistemino è quindi $135+k*"m.c.m."(99,171)$ al variare di $k$ in $ZZ$.
Anche qui tutto ok? Capito? Non ti far problemi, mi raccomando
Ad occhio direi che va bene.
Puoi giungere come a quella soluzione intersecando gli insiemi delle soluzioni della prima e della seconda equazione. In altri termini, la prima equazione ha come insieme delle soluzioni $sigma_1={z in ZZ " tali che " z=99k+36, " " k in ZZ}={...-63, 36,135... }$; la seconda $sigma_2={z in ZZ " tali che " z=171h-36, " " h in ZZ}={...-36, 135... }$.
Vedi subito che 135 sta nell'intersezione, quindi è soluzione comune. Se ne becchi una, le becchi tutte aggiungendoci multipli del mcm dei moduli: la soluzione generale del tuo sistemino è quindi $135+k*"m.c.m."(99,171)$ al variare di $k$ in $ZZ$.
Anche qui tutto ok? Capito? Non ti far problemi, mi raccomando
"Paolo90":
Sì, diciamo che nel caso di no coprimalità le cose si fanno più delicate.
Ad occhio direi che va bene.
Puoi giungere come a quella soluzione intersecando gli insiemi delle soluzioni della prima e della seconda equazione. In altri termini, la prima equazione ha come insieme delle soluzioni $sigma_1={z in ZZ " tali che " z=99k+36, " " k in ZZ}={...-63, 36,135... }$; la seconda $sigma_2={z in ZZ " tali che " z=171h-36, " " h in ZZ}={...-36, 135... }$.
Vedi subito che 135 sta nell'intersezione, quindi è soluzione comune. Se ne becchi una, le becchi tutte aggiungendoci multipli del mcm dei moduli: la soluzione generale del tuo sistemino è quindi $135+k*"m.c.m."(99,171)$ al variare di $k$ in $ZZ$.
Anche qui tutto ok? Capito? Non ti far problemi, mi raccomando
ok, direi decisamente che ho capito! grazie mille sei stato gentilissimo! sai, l'esame di matematica discreta incombe e per lo meno questi esercizi base volevo essere in grado di farli tranquillamente (sono uno studente del corso di Scienze e tecnologie dell'informazione ma non pensavo che in informatica ci fosse così tanta matematica eheh)...grazie mille ancora! se dovessi avere qualche problema al massimo inserisco un altro post, ma direi decisamente che mi hai schiarito le idee! grazie mille ancora!
Figurati, è un piacere. In bocca al lupo per i tuoi esami, anche io questa settimana ho algebra I, speriamo bene.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo