Matematicamente.it

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?

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

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ì

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.

figurati. Da dove salta fuori quella formula?

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.