Equazioni diofantee e ricerca della minima soluzione

[Neptune]

Salve a tutti,
credo sia noto a tutti il metodo di risoluzione delle equazioni
diofantee, ovvero si vede se sono compatibili, nel caso si trova
almeno una soluzione tramite l'identità di bezout e successivamente si
passa a calcolare tutte le solzuioni ammesse tramite una formula nota.

Mettiamo caso che ho una generica equazione diofantea che ammette
infinite soluzioni, mi posso calcolare la più piccola soluzione intera
positiva? se si come?

[g***@iit.cnr.it]

Post by Neptune
Salve a tutti,
credo sia noto a tutti il metodo di risoluzione delle equazioni
diofantee, ovvero si vede se sono compatibili, nel caso si trova
almeno una soluzione tramite l'identità di bezout e successivamente si
passa a calcolare tutte le solzuioni ammesse tramite una formula nota.

Scusa, ma esattamente a quale sottoclasse di equazioni diofantee ti
stai riferendo?

Perche' parli di "generica equazione diofantea", ma immagino che tu
stia
riferendoti a quelle lineari (e in tal caso, in quante variabili?)
perche' se hai una equazione diofantea tipo x^y * y^(2^z)+z^77=w^4+1
non credo
che con Bezout vai molto avanti...

E poi, per soluzione "piu' piccola" (nel caso di equazioni con piu'
variabili)
cosa intendi esattamente ?

ciao,
g.
--
http://www.iread.it : anagrammi, criptaritmi, polimini, ...

[Neptune]

Post by g***@iit.cnr.it

Post by Neptune
Salve a tutti,
credo sia noto a tutti il metodo di risoluzione delle equazioni
diofantee, ovvero si vede se sono compatibili, nel caso si trova
almeno una soluzione tramite l'identità di bezout e successivamente si
passa a calcolare tutte le solzuioni ammesse tramite una formula nota.

Scusa, ma esattamente a quale sottoclasse di equazioni diofantee ti
stai riferendo?
Perche' parli di "generica equazione diofantea", ma immagino che tu
stia
riferendoti a quelle lineari (e in tal caso, in quante variabili?)
perche' se hai una equazione diofantea tipo  x^y * y^(2^z)+z^77=w^4+1
non credo
che con Bezout vai molto avanti...
E poi, per soluzione "piu' piccola" (nel caso di equazioni con piu'
variabili)
cosa intendi esattamente ?
ciao,
g.
--http://www.iread.it: anagrammi, criptaritmi, polimini, ...

...

Ho un equazione diofantea in forma:
ax+by= c

Dove a,b e c sono i termini noti;
x ed y sono le variabili;

Stiamo parlando dell'insieme Z dei numeri interi.

Per soluzione soluzione di una equazione diofantea intendo la coppia
di interi (x,y) che soddisfa la nostra equazione.

Sappia che se l'mcd(a,b) divide c allora è compatibile;

Per bezout, o se siamo bravi anche ad occhio possiamo trovarci una
coppia ordinata di valore (x,y) che soddisfa la nostra equazione e poi
c'è la formula per trovarci tutte le possibili coppie ordinate che
saranno del tipo:

(x+b/d*h; y-a/d*h) al variare di h in Z

Ora, sappiamo per bezout una generica soluzione (dove per soluzione
ordinata ripeto, ci riferiamo alla coppia ordinata (x,y);
Sappiamo come calcolarci le altro soluzioni al variare di h in Z;
Se volessimo trovarci la coppia ordina (x,y) più piccola in Z+ che sia
soluzione dell'equazione, come psoso fare?

[g***@iit.cnr.it]

Post by Neptune
(x+b/d*h; y-a/d*h) al variare di h in Z
Sappiamo come calcolarci le altro soluzioni al variare di h in Z;
Se volessimo trovarci la coppia ordina (x,y) più piccola in Z+ che sia
soluzione dell'equazione, come psoso fare?

Beh, ancora non sono sicuro di aver capito cosa significa soluzione
"piu' piccola"
visto che stiamo parlando di una coppia di numeri.
Cosa vuoi minimizzare? il valore assoluto del piu' piccolo, il valore
assoluto
del piu' grande, la somma dei valori assoluti, la media geometrica dei
numeri?

Comunque, se le soluzioni sono del tipo x = x' + p*h e y = y' - q*h al
variare di h, per x,y,p,q interi,
e se sei interessato alle soluzioni positive potresti provare a vedere
dove
ti portano le disequazioni x'+p*h>0 e y'-q*h>0. A seconda dei segni
ti puo' venire
fuori qualcosa tipo t<h<z e quindi sai che prendendo h il piu'
piccolo possibile magari
minimizzi la x mentre prendendo il valore di h all'altro estremo
minimizzi la y (chiaramente
i vari casi probabilmente dipendono dai segni dei coeffcienti nella
equazione di partenza).
Insomma dipende un po' dal tuo concetto di "soluzione piu' piccola"...

Esempio: 7x+4y = 111
Soluzione x = 1+4*h y=26-7*h
Impongo x>0 e y>0 e ottengo 0 <= h<=3.
per h=0 ho x=1 y=26 (minimizzo la x)
per h=3 ho x=13 y=5 (minimizzo la y)

ciao,
giovanni
--
http://www.iread.it : anagrammi, criptaritmi, ...

[Neptune]

Post by g***@iit.cnr.it

Post by Neptune
(x+b/d*h; y-a/d*h) al variare di h in Z
Sappiamo come calcolarci le altro soluzioni al variare di h in Z;
Se volessimo trovarci la coppia ordina (x,y) più piccola in Z+ che sia
soluzione dell'equazione, come psoso fare?

Beh, ancora non sono sicuro di aver capito cosa significa soluzione
"piu' piccola"
visto che stiamo parlando di una coppia di numeri.
Cosa vuoi minimizzare? il valore assoluto del piu' piccolo, il valore
assoluto
del piu' grande, la somma dei valori assoluti, la media geometrica dei
numeri?
Comunque, se le soluzioni sono del tipo x = x' + p*h e y = y' - q*h al
variare  di h, per x,y,p,q interi,
e se sei interessato alle soluzioni positive potresti provare a vedere
dove
ti portano le disequazioni x'+p*h>0 e y'-q*h>0.  A seconda dei segni
ti puo' venire
fuori qualcosa tipo   t<h<z  e quindi sai che prendendo h il piu'
piccolo possibile magari
minimizzi la x mentre prendendo il valore di h all'altro estremo
minimizzi la y (chiaramente
i vari casi probabilmente dipendono dai segni dei coeffcienti nella
equazione di partenza).
Insomma dipende un po' dal tuo concetto di "soluzione piu' piccola"...
Esempio:  7x+4y = 111
Soluzione  x = 1+4*h  y=26-7*h
Impongo x>0 e y>0 e ottengo   0 <= h<=3.
per h=0 ho x=1 y=26 (minimizzo la x)
per h=3 ho x=13 y=5 (minimizzo la y)
ciao,
giovanni
--http://www.iread.it: anagrammi, criptaritmi, ...

...

Ho una coppia di termini (x,y) che è soluzione della mia equazione
diofantea. Ho un modo per stabilire se ci sono numeri interi positivi
piu piccoli della coppia (x,y) trovata? Ovvero mi possono chiedere di
trovare "la coppia ordinata di numeri, soluzione della mia equazione
diofantea, che sia il più piccolo possibile?"

[Giovanni Resta]

Post by Neptune
Ho una coppia di termini (x,y) che è soluzione della mia equazione
diofantea. Ho un modo per stabilire se ci sono numeri interi positivi
piu piccoli della coppia (x,y) trovata? Ovvero mi possono chiedere di
trovare "la coppia ordinata di numeri, soluzione della mia equazione
diofantea, che sia il più piccolo possibile?"

E io ti chiedo (per la 3a volta!) cosa vuol dire che una coppia
di numeri (x',y') e' "piu' piccola" di una coppia di numeri (x,y) ???

Fino a che non chiarisci cosa intendi per "piu' piccola" non si va
avanti. Non esiste un modo univoco di ordinare le coppie.
Immagina di avere due soluzioni (7, 12) e (8,10).
Secondo te, quale e' piu "piccola"? La (7,12) perche' contiene il
numero minore (7) oppure la (8,10) perche' 8+10 < 7+12 ?

g.