Equzioni Diofantee, Algoritmo di Euclide
Ho un problema con la risoluzione delle equazioni diofantee, precisamente dopo avere apllicato l'algoritmo di euclide.
ad esempio ho un equazione 86x + 16y = 8
per controllare che tale equazione abbia solozioni verifico l'identità di beazout(cioè l'MCD dei coefficenti deve dividere c)
determino l'MCD con l'algoritmo euclideo
86=16*5+6
16=6*2+4
6=4*1+2
4=2*2+0
arrivati al resto pari a 0 l'MCD è il resto precedente.
dunque riparto dal MCD e risalgo per determinare i termini
2=6-4
determino 4 dalla seconda riga
2=6-16*2
6 dalla prima riga
2=86-16*5-16*2
arrivati qui non riesco a preseguire, dovrei trovare l'uguaglianza scritta in una certa maniera ovvero 2=?*?-?*?
help me!
ad esempio ho un equazione 86x + 16y = 8
per controllare che tale equazione abbia solozioni verifico l'identità di beazout(cioè l'MCD dei coefficenti deve dividere c)
determino l'MCD con l'algoritmo euclideo
86=16*5+6
16=6*2+4
6=4*1+2
4=2*2+0
arrivati al resto pari a 0 l'MCD è il resto precedente.
dunque riparto dal MCD e risalgo per determinare i termini
2=6-4
determino 4 dalla seconda riga
2=6-16*2
6 dalla prima riga
2=86-16*5-16*2
arrivati qui non riesco a preseguire, dovrei trovare l'uguaglianza scritta in una certa maniera ovvero 2=?*?-?*?
help me!
Risposte
Devi determinare $x$ e $y$ tale che $86x + 16y = 8$
Per controllare se esistono soluzioni devi vedere se $MCD(86,16)$ divide 8.
E questo lo fai prima di usare l'algoritmo di Euclide!!!
Per trovare l'MCD di 2 numeri basta scomporli in fattori primi.
Si ha che $16=2^4$ mentre $86=2*43$ e quindi l'MCD è 2 che divide 8 e perciò esistono $x,y$ che verificano l'uguaglianza.
Ora per trovarli usi l'algoritmo di Euclide.
Tu hai scritto:
86=16*5+6
16=6*2+4
6=4*1+2
4=2*2+0
dunque riparto dal MCD e risalgo per determinare i termini
e fin qui va bene.
Dunque $2=6-4$
Ora determini 4 dalla 2° riga e hai $4=16-6*2$ e quindi $2=6-4=6-(16-6*2)=6*3-16$
Ora determini 6 dalla prima riga e hai $6=86-16*5$ e quindi $2=6*3-16=(86-16*5)*3-16=3*86-15*16-16=3*86-16*16$
Hai quindi $2=3*86-16*16$
Ora $8=2*4$ e quindi moltiplichi la relazione che hai ottenuto per 4 e hai
$8=12*86-64*16$
Quindi $x=12$ e $y=-64$
Per controllare se esistono soluzioni devi vedere se $MCD(86,16)$ divide 8.
E questo lo fai prima di usare l'algoritmo di Euclide!!!
Per trovare l'MCD di 2 numeri basta scomporli in fattori primi.
Si ha che $16=2^4$ mentre $86=2*43$ e quindi l'MCD è 2 che divide 8 e perciò esistono $x,y$ che verificano l'uguaglianza.
Ora per trovarli usi l'algoritmo di Euclide.
Tu hai scritto:
86=16*5+6
16=6*2+4
6=4*1+2
4=2*2+0
dunque riparto dal MCD e risalgo per determinare i termini
e fin qui va bene.
Dunque $2=6-4$
Ora determini 4 dalla 2° riga e hai $4=16-6*2$ e quindi $2=6-4=6-(16-6*2)=6*3-16$
Ora determini 6 dalla prima riga e hai $6=86-16*5$ e quindi $2=6*3-16=(86-16*5)*3-16=3*86-15*16-16=3*86-16*16$
Hai quindi $2=3*86-16*16$
Ora $8=2*4$ e quindi moltiplichi la relazione che hai ottenuto per 4 e hai
$8=12*86-64*16$
Quindi $x=12$ e $y=-64$
ecco non riesco a capire come fai a passare da
2=6-(16-6*2)
a 2=6*3-16
2=6-(16-6*2)
a 2=6*3-16
"BHK":
ecco non riesco a capire come fai a passare da
2=6-(16-6*2)
a 2=6*3-16
E' come se tu mi stessi chiedendo come faccio a passare da $3=12-(15-6)$ a $3=12-9$!!!!
Comunque:
$2=6-(16-6*2)$ quindi togliendo la parentesi e cambiando il segno perchè c'è davanti il meno $2=6-16+6*2$ cioè $2=6+6*2-16$ e quindi dato che $6+6*2$ fa $6*3$ ho $2=6*3-16$
"BHK":
ecco non riesco a capire come fai a passare da
2=6-(16-6*2)
a 2=6*3-16
Considera che avevi l'altro $6$ prima e quindi da $6*2$ passi a $6*3$.....
P.S: ti conviene scrivere le formule tra \$ così almeno sono più leggibili
ok, $2=6*3-16$
$2=(86-16*5)*3-16$
risolvo
$2=86*3-16*15-16$
porto -16 alla sinistra dell'uguale
$18=86*3-16*15$
quindi $x=3$ e $y=15$?
$2=(86-16*5)*3-16$
risolvo
$2=86*3-16*15-16$
porto -16 alla sinistra dell'uguale
$18=86*3-16*15$
quindi $x=3$ e $y=15$?
a me vengono questi valori $x=3$ e $y=-16$
Con l'algoritmo di divisione ho trovato che il $MCD(86,16)=2$ che divide $8$
$86= 5*16 + 6$
$16= 2*6 + 4$
$6=4+2$
adesso trovo $x$ e $y$ procedendo al contrario, cioè
$2=6-4=6-(16-2*6)=-16+3*6=-16 + 3(86-5*16)=3*86-16*16$
Spero di non aver fatto dei calcoli sbagliati
Con l'algoritmo di divisione ho trovato che il $MCD(86,16)=2$ che divide $8$
$86= 5*16 + 6$
$16= 2*6 + 4$
$6=4+2$
adesso trovo $x$ e $y$ procedendo al contrario, cioè
$2=6-4=6-(16-2*6)=-16+3*6=-16 + 3(86-5*16)=3*86-16*16$
Spero di non aver fatto dei calcoli sbagliati
i calcoli sono giusti ma anche i miei dovrebbero esserlo
io ho
$18=86*3-16*15$
l'equzione all'inizio era $86x+16y=8$
quindi ho fatto male spostare il -16 oppure ho trovato un altra soluzioni fra quelle dell'equazione.
io ho
$18=86*3-16*15$
l'equzione all'inizio era $86x+16y=8$
quindi ho fatto male spostare il -16 oppure ho trovato un altra soluzioni fra quelle dell'equazione.
"Samy21":
a me vengono questi valori $x=3$ e $y=-16$
Con l'algoritmo di divisione ho trovato che il $MCD(86,16)=2$ che divide $8$
$86= 5*16 + 6$
$16= 2*6 + 4$
$6=4+2$
adesso trovo $x$ e $y$ procedendo al contrario, cioè
$2=6-4=6-(16-2*6)=-16+3*6=-16 + 3(86-5*16)=3*86-16*16$
Spero di non aver fatto dei calcoli sbagliati
Questa non è la soluzione finale, ma solo quella parziale!!!!
Infatti devi trovare x e y tali che $8==86x+16y$
Per passare dall'equazione trovata (che finora è giusta) a quella definitiva si deve fare come ho scritto nel post precedente (rileggetelo!)
"BHK":
i calcoli sono giusti ma anche i miei dovrebbero esserlo
io ho
$18=86*3-16*15$
l'equzione all'inizio era $86x+16y=8$
quindi ho fatto male spostare il -16 oppure ho trovato un altra soluzioni fra quelle dell'equazione.
Certo, i tuoi calcoli sono giusti. Ma a cosa ti servono?!?!
Se per quello invece che $18=86*3-16*15$ puoi anche dire $18=86*3-16*14-16$ e quindi $34=86*3-16*14$. E allora?!
Tu devi arrivare a scrivere $8=86x+16y$ e non $18=....$.
Anche per te rileggi il mio post precedente e trovi spiegato tutto
Si giustissimo, avevo dimenticato il $2$ all'inizio...
ok ricapitolando,
l'equazione iniziale era 86x+16y=8
abbiamo
$2=3*86-16*16$
ma dobbiamo scriverla con il termine noto pari a 8 quindi moltiplichiamo i coefficenti per 4
$8=12*86-64*16$
$x=12; y=-64$ che è una soluzione particolare
è possibile scrivere la soluzione generale?
l'equazione iniziale era 86x+16y=8
abbiamo
$2=3*86-16*16$
ma dobbiamo scriverla con il termine noto pari a 8 quindi moltiplichiamo i coefficenti per 4
$8=12*86-64*16$
$x=12; y=-64$ che è una soluzione particolare
è possibile scrivere la soluzione generale?
"BHK":
ok ricapitolando,
l'equazione iniziale era 86x+16y=8
abbiamo
$2=3*86-16*16$
ma dobbiamo scriverla con il termine noto pari a 8 quindi moltiplichiamo i coefficenti per 4
$8=12*86-64*16$
$x=12; y=-64$ che è una soluzione particolare
è possibile scrivere la soluzione generale?
Bene.
Riguardo alla soluzione generale non hai proprio nessuna idea?
Io azzarderei una risposta, ma penso sia meglio far pensare BHK
allora per determinare la soluzione generale parto dall'equzione omogenea associata
ovvero $86x+16y=0$
$x=12$
$y=-64$
la soluzione particolare era $12*86-64$
quindi
$(12*86+12t,64*16-64t)$
risolvendo
$(1032-12t,1024-64t)$
è corretto?
ovvero $86x+16y=0$
$x=12$
$y=-64$
la soluzione particolare era $12*86-64$
quindi
$(12*86+12t,64*16-64t)$
risolvendo
$(1032-12t,1024-64t)$
è corretto?
Io penso sia invece $x=12-16h$ e $y=-64+86h$
Facendo i calcoli (poni per esempio h=1) noti che l'uguaglianza della diofantea è rispettata
Facendo i calcoli (poni per esempio h=1) noti che l'uguaglianza della diofantea è rispettata
Samy21 ha fatto un buon ragionamento, ma la soluzione non è totalmente corretta in quanto eclude alcune soluzioni.
La soluzione è la seguente:
data l'equazione $ax+by=c$ con $d=MCD(a,b)$ e detta $(x_0,y_0)$ una soluzione particolare , allora tutte le soluzioni sono della forma:
$x=x_0+b/dh$
$y=y_0-a/dh$
Perciò nel nostro caso abbiamo:
$86x+16y=8$ e $x_0=12$, $y_0=-64$.
Poi $d=MCD(a,b)=MCD(86,16)=2$
Allora tutte le soluzioni sono della forma:
$x=12+8h$
$y=-64-43h$
(ovviamente posso scrivere indifferentemente che le soluzioni sono:
$x=12-8h$
$y=-64+43h$)
Non è difficile dimostrare che questa è la soluzione generale.
Se vuoi provare a farlo basta che supponi di avere 2 soluzioni e vedi cosa succede
La soluzione è la seguente:
data l'equazione $ax+by=c$ con $d=MCD(a,b)$ e detta $(x_0,y_0)$ una soluzione particolare , allora tutte le soluzioni sono della forma:
$x=x_0+b/dh$
$y=y_0-a/dh$
Perciò nel nostro caso abbiamo:
$86x+16y=8$ e $x_0=12$, $y_0=-64$.
Poi $d=MCD(a,b)=MCD(86,16)=2$
Allora tutte le soluzioni sono della forma:
$x=12+8h$
$y=-64-43h$
(ovviamente posso scrivere indifferentemente che le soluzioni sono:
$x=12-8h$
$y=-64+43h$)
Non è difficile dimostrare che questa è la soluzione generale.
Se vuoi provare a farlo basta che supponi di avere 2 soluzioni e vedi cosa succede
Ahn ecco, mi sa che hai corretto perchè non capivo come mai dividevi l' $86$ e non il $16$.. 
COmunque grazie, adesso ho chiare le diofantee...Prima mi perdevo nella soluzione finale
COmunque grazie, adesso ho chiare le diofantee...Prima mi perdevo nella soluzione finale
allora vediamo se ho capito il precedimento
vi posto direttamente l'esericizio
$693x+187y=44$
1)Identità di Bezout = $MCD(a,b)|c$ e Algoritmo Euclideo
$693=187*3+132$
$187=132*1+55$
$132=55*2+22$
$55=22*2+11$
$22=11*2+0$
$MCD(693,187)=11$
$44/11=4$
dunque ha soluzioni
2)Ricerca della soluzione particolare
$11=55-22*2
$11=187-132-22*2$
$11=187-132-(132-55*2)*2$
$11=187-(693-187*3)-((693-187*3)-55*2)*2$
$11=187-693+187-(693-187*3)*2+(187-132)*4$
$11=187-693+187-693*2+187*6+187*4-132*4$
$11=187*14-693*3-132*4$
$11=187*14-693*3-(693-187*3)*4$
$11=187*14-693*3-693-4+187*12$
$11=-693*7+187*26$
$11=693*(-7)+187*26$
con c =44 abbiamo $693*(-28)+187*104$
qundi $x=-28; y=104$
3)soluzione generale
$X=-28-(187/4)t$
$Y=104-(693/4)t$
ai posteri larga sentenza
vi posto direttamente l'esericizio
$693x+187y=44$
1)Identità di Bezout = $MCD(a,b)|c$ e Algoritmo Euclideo
$693=187*3+132$
$187=132*1+55$
$132=55*2+22$
$55=22*2+11$
$22=11*2+0$
$MCD(693,187)=11$
$44/11=4$
dunque ha soluzioni
2)Ricerca della soluzione particolare
$11=55-22*2
$11=187-132-22*2$
$11=187-132-(132-55*2)*2$
$11=187-(693-187*3)-((693-187*3)-55*2)*2$
$11=187-693+187-(693-187*3)*2+(187-132)*4$
$11=187-693+187-693*2+187*6+187*4-132*4$
$11=187*14-693*3-132*4$
$11=187*14-693*3-(693-187*3)*4$
$11=187*14-693*3-693-4+187*12$
$11=-693*7+187*26$
$11=693*(-7)+187*26$
con c =44 abbiamo $693*(-28)+187*104$
qundi $x=-28; y=104$
3)soluzione generale
$X=-28-(187/4)t$
$Y=104-(693/4)t$
ai posteri larga sentenza
"BHK":
$X=-28-(187/4)t$
$Y=104-(693/4)t$
E quindi puoi scrivere alla fine che $x= -28 - 17t$ e $y=104 + 63t$. Provando per $t=1$ (per esempio), noti che si verifica l'identità
In virtù di quello he abbiamo detto fin'ora è così.
Ti sono chiari tutti i passaggi?
"BHK":
3)soluzione generale
$X=-28-(187/4)t$
$Y=104-(693/4)t$
ai posteri larga sentenza
Attento che c'è un errore in questo ultimo passaggio.Perchè dividi per 4?
Vai a vedere per cosa ho detto di dividere nel post che ho scritto in precedenza io
"BHK":
ai posteri larga sentenza
"Ai posteri l'ardua sentenza" (da Il Cinque Maggio).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo