da 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