| Index | Texte | Muzică | Radio-TV | Mesaje | Imagini | Sport | Contact | Forum |  |
| Saitul Ion Nanu |
|
Ecuații diofantice liniare cu două necunoscute Aici ne vom referi la ecuațiile diofantice de forma: Problemele care se pun în legătură cu aceste ecuații sînt: dacă au soluții întregi și, în caz afirmativ, cum se determină soluțiile. Dacă c=0 atunci avem ecuația ax + by = 0, deci ax = -by, adică x = -by/a. Punînd 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 ecuația nu are soluții. Într-adevăr, dacă există k > 1 astfel încît 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 soluție particulară, atunci x = x0 + b*k, y = y0 - a*k este soluția generală, k∈ Z. Într-adevăr, ax + by = a(x0 +b*k) + b(y0 - b*k) = a*x0 + b*y0 = c. 3) Dacă (x0,y0) este o soluție a ecuației ax + by = c, atunci (-x0,y0) este soluție a ecuației -ax + by = c iar (x0,-y0) este soluție a ecuației ax - by = c. Într-adevăr: -a*(-x0) + b*y0 = a*x0 + b*y0 = c a*x0 - b*(-y0) = a*x0 + b*y0 = c 4) Determinarea unei soluții particulare în cazul (a,b,c)=1 și (a,b)=1, a, b nenule. Dacă b = 1, atunci obținem soluția x = t, y = c - a*t, t∈ Z iar dacă b = -1, obținem soluția x = t, y = -c + a*t, t∈ Z. Presupunem, deci, |a|>|b|>1. Mai mult, ținînd seama de punctul 3, putem presupune că a > b > 1. Fără a restrînge generalitatea, ecuația se poate scrie sub forma: a0*x0 + b0*y0 = c și presupunem că a0 > b0 > 1 Există k0 și r0 întregi, astfel ca: a0 = k0*b0 + r0 și r0∈{1,2,...,b0-1} Să observăm că r0 > 0, deoarece (a0,b0)=1. De asemenea, (b0,r0) = 1. Înlocuind, obținem (k0*b0 + r0)*x + b0*y0 = c, adică b0*(k0*x0 + y0) + r0*x0 = c Notăm: a1 = b0 , b1 = r0, x1 = k0*x0 + y0 și y1 = x0, rezultînd ecuația: a1*x1 + b1*y1 = c și a1 > b1, (a1,b1)=1. Dacă b1 = 1, procesul se oprește, altfel se continuă, în același fel. Astfel, dacă la pasul n-1 avem ecuația an-1*xn-1 + bn-1*yn-1 = c și (an-1,bn-1)=1 atunci, la pasul n avem ecuația an*xn + bn*yn = c și (an,bn)=1 în care xn = kn-1*xn-1 + yn-1 yn = xn-1 Procesul continuă pînă cînd bn = 1. Acest lucru este asigurat de faptul că șirul (bn) este strict descrescător: 1 = bn < bn-1 < ... < b1 < b0 Așadar, dacă bn = 1, avem ecuația: an*xn + yn = c Ecuația de mai sus, în necunoscutele xn și yn, are soluția particulară (xn = 1 , yn = c - an). În continuare, folosind formulele de recurență: xn-1 = yn , yn-1 = xn - kn-1*yn determinăm soluția particular(x0,y0) a ecuației inițiale. Exemplu: Să se rezolve ecuația diofantică 8x - 5y = 2. Rezolvare 1: Rezolvăm, mai întîi, ecuația: 8x + 5y =2. Scriem ecuația 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 Notăm: x1 = x0 + y0, y1=x0 și obținem ecuația 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 Notăm: x2 = x1 + y1, y2=x1 și ecuația 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 Notăm: x3 = x2 + y2, y3=x2 și ecuația 2*x3 + y3 = 2. Ultima ecuație are soluția 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, soluția generală a ecuației 8x + 5y = 2 este: x = -1 + 5*k, y = 2 - 8*k Conform 3, soluția particulară a ecuației 8x - 5y = 2 este x = -1, y = -2, deci soluția 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 Așadar, soluția generală este: x = 5t + 4, y = 8t +6 Soluția de aici, se obține din cea de la rezolvarea nr.1, luînd k=t+1. |