Equazione diofantea AIUTO

[enrico9991]

Potete aiutarmi per favore a risolvere tale esercizio che non son proprio capace?? se qualcuno può scrivermi anche i passaggi per capire...

determirare il più piccolo k>100
per cui equazione diofantea 6x + 7y = k ammette soluzioni e determinare tali soluzioni


GRAZIE A TUTTI!

[g.schgor1]

Io, difronte ad un problema di questo genere, non trovo di meglio
che incaricare della ricerca un piccolo computer.
Ed ecco qui i risultati:

.k .....x......y
100.....5.....10
100....12......4
101.....4.....11
101....11......5
102.....3.....12
102....10......6
................

(se t’interessa, il programma in Basic e’:

For k=100 To 110
.....For x=1 To 20
..........For y=1 To 20
...............If 6*x + 7*y = k Then
...................Print x,y,k
...............End if
..........Next y
......Next x
Next k

e puoi continuare fin che vuoi,
ma forse Diofanto avrebbe da ridire...
Nota pero' le sequenze dei risultati).

[Mistral2]

quote:

---

Originally posted by enrico999

Potete aiutarmi per favore a risolvere tale esercizio che non son proprio capace?? se qualcuno può scrivermi anche i passaggi per capire...

determirare il più piccolo k>100
per cui equazione diofantea 6x + 7y = k ammette soluzioni e determinare tali soluzioni


GRAZIE A TUTTI!

---

Prima cosa l'equazione ammette soluzioni per ogni valore di k, infatti equivale alla soluzione della congruenza:

6x==k (mod7) equivalente a dire che 7 divide 6x-k

per capire questo basta tenere presente che il massimo comun divisore tra 6 e 7 è 1, quindi esistono u,v tali che 6u+7v=1, nel nostro caso u=-1 e v=1 cioè basta osservare che -6+7=1 !. Se ora moltiplichi questa equazione per un k qualsiasi hai una soluzione, cioè (-6+7)k=k. Quindi il valore minimo di k è 101, una soluzione è x0=-101,y0=101. Per ottenere tutte le soluzioni devi osservare che se x1,y1 è una altra soluzione allora hai che:

6(x1-x0)+7(y1-y0)=0 da cui segue che 7 divide x1-x0, cioè
x1=x0+7h con h intero qualsiasi, da questo segue y1=y0-6h.

Per ottenere soluzioni positive basta scegliere un adeguato h positivo. Ad esempio per h=15 ottieni la soluzione determinata da g.schgor:

x1=-101+15*7=4, y1=101-15*6=12


Saluti

Mistral