equazioni diofantee

Messaggioda Legolas87 » 25/04/2004, 16:35

considerando l'equazione diofantea di I grado
ax+by=c
qualcuno sa dirmi se esiste un algoritmo generale risolutivo per questo tipo di equazioni che non usi l'ingombrante algoritmo di euclide?
Legolas87
Junior Member
Junior Member
 
Messaggio: 41 di 113
Iscritto il: 30/01/2004, 19:27
Località: Italy

Messaggioda karl » 25/04/2004, 18:48

Un approccio puo' essere questo.
Sia ax+by=c l'equazione diofantina.
Essa si puo' risolvere in Z solo e solo se il termine
noto c e'divisibile per il M.C.D. di a e b;
da cio' segue (una volta soddisfatta questa
condizione)che a e b si possono sempre supporre
primi tra loro.
Se poi (A,B) e' una soluzione particolare ,la soluzione
generale si ottiene con le formule:
[x=A+k*b, y=B-k*a] con k in Z.
La soluzione x=A si puo' ottenere con la formula:
A=a^(phi(b)-1)*c,essendo phi(b) il cosiddetto
"indicatore di Gauss" di b ,che e' il numero dei
numeri primi con b e non maggiori di b .
Com' e' noto phi(b) si puo' calcolare con la
formula phi(b)=b*(1-1/p1)*(1-1/p2)*...*(1-1/pk)
dove p1,p2,...,pk sono i divisori primi di b.
Se b=1 allora phi(b)=1,se b e' primo allora phi(b)=b-1.
Faccio qualche esempio.
2x+6y=5--->non e' risolubile in Z perche' M.C.D.(2,6)=2
e 2 non divide il termine noto 5.
2x+5y=7----> e' risolubile in Z perche' M.C.D.(2,5)=1
ed 1 divide (ovviamente) il termine noto 7.
La soluzione A e' data da:
A=2^(phi(5)-1)*7=2^(4-1)*7=56
(phi(5)=5-1=4,perche' 5 e' primo)
Sostituendo questo valore di x nell'equazione ,si ricava B:
B=-21
In conclusione la soluzione e':
<b>[x=56+5k,y=-21-2k]</b>.
karl.





Modificato da - karl il 25/04/2004 21:37:35
karl
 

Messaggioda Legolas87 » 26/04/2004, 17:55

grazie karl

P.S. <BLOCKQUOTE id=quote><font size=1 face="Verdana, Arial, Helvetica" id=quote>citazione:<hr height=1 noshade id=quote>essendo phi(b) il cosiddetto
"indicatore di Gauss" di b ,che e' il numero dei
numeri primi con b e non maggiori di b .
<hr height=1 noshade id=quote></BLOCKQUOTE id=quote></font id=quote><font face="Verdana, Arial, Helvetica" size=2 id=quote>
ma non è la funzione phi di eulero? io l'ho sempre sentita chiamare così
Legolas87
Junior Member
Junior Member
 
Messaggio: 43 di 113
Iscritto il: 30/01/2004, 19:27
Località: Italy

Messaggioda karl » 26/04/2004, 20:08

Grazie per il...grazie.
Quanto all'indicatore di Gauss,effettivamente
altri lo chiamano "funzione di Eulero" (basta
consultare internet per leggere la doppia denominazione).
Alla fine non credo che la cosa abbia tanta importanza.
karl.
karl
 

Messaggioda Legolas87 » 27/04/2004, 17:41

figurati. Da dove salta fuori quella formula?
Legolas87
Junior Member
Junior Member
 
Messaggio: 45 di 113
Iscritto il: 30/01/2004, 19:27
Località: Italy

Messaggioda karl » 27/04/2004, 18:14

Per Legolas87.
Partiamo da ax+by=c,da cui:
ax-c=-by
Cio significa che ax e c sono tra loro congruenti
rispetto al modulo b:
ax==c (mod b) ( il doppio uguale sta per congruente))
Ora,poiche' possiamo supporre a e b primi tra loro,si
puo' applicare il teorema di Eulero:
a^(phi(b))==1 (mod b),da cui :
c*a^(phi(b)==c (mod b)
Pertanto una soluzione si ha quando:
ax=c*a^(phi(b))---->x=c*a^(phi(b)-1).
karl.
karl
 


Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: hydro e 1 ospite