Ion Nanu

Ecuaii diofantice liniare cu dou necunoscute
Aici ne vom referi la ecuaiile diofantice de forma:ax + by = c a,b,c Z i (a,b,c)=1 Aadar, presupunem c a, b, c snt numere ntregi prime ntre ele i a, b nenule. Dac n-ar fi aa, atunci ecuaia s-a simplifica prin cel mai mare divizor comun al numerelor a, b, c.

Problemele care se pun n legtur cu aceste ecuaii snt: dac au soluii ntregi i, n caz afirmativ, cum se determin soluiile.

Dac c=0 atunci avem ecuaiaax + by = 0, deci ax = -by, adic x = -by/a. Punnd y=t*a, rezult x = -t*b, oricare ar fi t ntreg.

n continuare, vom presupune, deci, c i c este nenul.

1)Dac (a,b) 1 atunci ecuaia nu are soluii.
ntr-adevr, dac exist k > 1 astfel nct a = a1*k i b = b1*k, atunci ax + by = k(a1x + b1y), rezult k divide pe c, ceea ce contrazice ipoteza (a,b,c) = 1.

2)Dac (x0,y0) este o soluie particular, atunci x = x0+ b*k, y = y0- a*k este soluia general, k Z.
ntr-adevr, ax + by = a(x0+b*k) + b(y0- b*k) = a*x0+ b*y0= c.

3)Dac (x0,y0) este o soluie a ecuaiei ax + by = c, atunci (-x0,y0) este soluie a ecuaiei -ax + by = c iar (x0,-y0) este soluie a ecuaiei ax - by = c.
ntr-adevr:
-a*(-x0) + b*y0= a*x0+ b*y0= c
a*x0- b*(-y0) = a*x0+ b*y0= c

4) Determinarea unei soluii particulare n cazul (a,b,c)=1 i (a,b)=1, a, b nenule.
Dac b = 1, atunci obinem soluia x = t, y = c - a*t, t Z iar dac b = -1, obinem soluia x = t, y = -c + a*t, t Z.
Presupunem, deci, |a|>|b|>1. Mai mult, innd seama de punctul 3, putem presupune c a > b > 1.
Fr a restrnge generalitatea, ecuaia se poate scrie sub forma:
a0*x0+ b0*y0= ci presupunem c a0> b0> 1
Exist k0i r0ntregi, astfel ca:
a0= k0*b0+ r0i r0{1,2,...,b0-1}
S observm c r0> 0, deoarece (a0,b0)=1. De asemenea, (b0,r0) = 1.
nlocuind, obinem (k0*b0+ r0)*x + b0*y0= c, adic b0*(k0*x0+ y0) + r0*x0= c
Notm: a1= b0, b1= r0, x1= k0*x0+ y0i y1= x0, rezultnd ecuaia:
a1*x1+ b1*y1= c i a1> b1, (a1,b1)=1.
Dac b1= 1, procesul se oprete, altfel se continu, n acelai fel. Astfel, dac la pasul n-1 avem ecuaia
an-1*xn-1+ bn-1*yn-1= ci (an-1,bn-1)=1
atunci, la pasul n avem ecuaia
an*xn+ bn*yn= ci (an,bn)=1
n care
xn= kn-1*xn-1+ yn-1
yn= xn-1
Procesul continu pn cnd bn= 1. Acest lucru este asigurat de faptul c irul (bn) este strict descresctor:
1 = bn< bn-1< ... < b1< b0
Aadar, dac bn= 1, avem ecuaia: an*xn+ yn= c
Ecuaia de mai sus, n necunoscutele xni yn, are soluia particular (xn= 1 , yn= c - an).
n continuare, folosind formulele de recuren: xn-1= yn, yn-1= xn- kn-1*yn determinm soluia particular(x0,y0) a ecuaiei iniiale.

Exemplu:
S se rezolve ecuaia diofantic 8x - 5y = 2.

Rezolvare 1:
Rezolvm, mai nti, ecuaia: 8x + 5y =2.
Scriem ecuaia astfel: 8*x0+ 5*y0= 2
Avem: 8 = 1*5 + 3 , deci
8*x0+ 5*y0= (5 + 3)*x0+ 5*y0= 5*(x0+ y0) + 3*x0= 2
Notm: x1= x0+ y0, y1=x0i obinem ecuaia 5*x1+ 3*y1= 2.
Avem: 5 = 1*3 + 2, deci
5*x1+ 3*y1= (3 + 2)*x1+ 3*y1= 3*(x1+ y1) + 2*x1= 2
Notm: x2= x1+ y1, y2=x1i ecuaia 3*x2+ 2*y2= 2.
Avem: 3 = 1*2 + 1, deci
3*x2+ 2*y2= (2 + 1)*x2+ 2*y2= 2*(x2+ y2) + x2= 2
Notm: x3= x2+ y2, y3=x2i ecuaia 2*x3+ y3= 2.
Ultima ecuaie are soluia particular: x3= 1, y3= 0
Deducem: x2= y3, y2= x3- 1*y3, adic x2= 0, y2= 1
Apoi:x1= y2, y1= x2- 1*y2, adic x1= 1, y1= -1
n fine, x0= y1, y0= x1- 1*y1, adic x0= -1, y0= 2
Astfel, soluia general a ecuaiei 8x + 5y = 2 este:
x = -1 + 5*k, y = 2 - 8*k
Conform 3, soluia particular a ecuaiei 8x - 5y = 2 este x = -1, y = -2, deci soluia general este:
x = 5*k - 1, y =8*k - 2.

Rezolvare 2:
Se poate proceda, mai practic, astfel: 8x - 5y = 2 -> 5y = 8x - 2 -> y = (8x - 2)/5
y = x +(3x - 2)/5
Trebuie ca 3x - 2 = 5u -> 3x = 5u + 2 -> x = (5u + 2)/3
x = u + (2u + 2)/3
Trebuie ca 2u + 2 = 3v -> 2u = 3v - 2 -> u = (3v - 2)/2
u = v + (v - 2)/2
Trebuie ca v - 2 = 2t - > v = 2t + 2
Deci: u = v + (v - 2)/2 = 2t + 2 + (2t + 2 -2)/2 = 2t + 2 + t = 3t + 2
Apoi: x = u + (2u + 2)/3 = 3t + 2 + (6t + 4 + 2)/3 = 3t + 2 + 2t + 2 = 5t + 4
Deci: y = x + (3x - 2)/5 = 5t + 4 + (15t + 12 - 2)/5 =5t + 4 + 3t + 2 = 8t + 6
Aadar, soluia general este: x = 5t + 4, y = 8t +6
Soluia de aici, se obine din cea de la rezolvarea nr.1, lund k=t+1.Top

Trafic.ro - clasamente si statistici pentru site-urile romanesti