Cum de a rezolva o ecuație liniară diophantine

O ecuație diofantinică (sau diofantină) este o ecuație algebrică a cărei soluții sunt căutate pentru care variabilele iau în considerare valorile întregi. în general

Cu toate acestea, ecuațiile diofantine liniar de tipul ax + by = c pot fi rezolvate cu ușurință folosind algoritmul descris mai jos. Folosind această metodă, găsim (4,7) ca singure soluții pozitive întregi ale ecuației 31x + 8y = 180. Diviziile în aritmetica modulară pot fi exprimate și ca ecuații lineare diofante. De exemplu, 12/7 (mod 18) necesită soluția 7x = 12 (mod 18) și poate fi rescrisă ca 7x = 12 + 18y sau 7x - 18y = 12. Deși multe ecuații diofantine sunt greu de rezolvat, puteți încerca totuși.

2

aplica algoritmul euclidian la coeficienții a și b. Acest lucru servește din două motive. În primul rând, vrem să aflăm dacă a și b au un divizor comun. Dacă încercăm să rezolvăm 4x + 10y = 3, putem afirma imediat că, din moment ce partea stângă este întotdeauna uniformă și partea dreaptă este întotdeauna ciudată, nu există soluții complete pentru ecuație. În același mod, dacă avem 4x + 10y = 2, putem simplifica la 2x + 5y = 1. Cel de-al doilea motiv constă în faptul că, pentru a demonstra că există o soluție, putem construi unul din secvența de coeficienți obținuți prin algoritmul euclidian.

3

dacă la, b și c au un divizor comun, simplifică ecuația împărțind partea dreaptă și cea stângă de divizor. dacă la și b ei au un divizor comun între ei, dar acest lucru nu este un divizor al egalității c, apoi opriți. Nu există soluții complete.

4

Construiți o masă cu trei rânduri, așa cum se arată în imaginea de mai sus.

5

Scrieți în primul rând al tabelului coeficienții obținuți cu algoritmul euclidian. Imaginea de mai sus arată ceea ce ați obține prin rezolvarea ecuației 87x - 64y = 3.

6

Completați ultimele două linii de la stânga la dreapta urmând următoarea procedură: pentru fiecare celulă, se calculează produsul între prima celulă din partea de sus a coloanei respective și celula imediat în stânga celulei goale. Scrieți acest produs în celula goală plus valoarea a două celule din stânga.

7

Consultați ultimele două coloane ale tabelului completat. Ultima coloană trebuie să conțină la și b, coeficienții ecuației din pasul 3 (dacă nu, verificați din nou calculele). Penultima coloană va conține alte două numere. În exemplul cu la = 87 e b = 64, penultima coloană conține 34 și 25.

8

Rețineți că (87 * 25) - (64 * 34) = -1. Determinantul matricei 2x2 din dreapta jos va fi întotdeauna +1 sau -1. Dacă este negativă, se înmulțește ambele părți ale egalității cu -1 pentru a obține - (87 * 25) + (64 * 34) = 1. Această observație este punctul de plecare din care se construiește o soluție.

9

Reveniți la ecuația inițială. Rescrieți egalitatea pasajului anterior sau în formularul 87 * (- 25) + 64 * (34) = 1 sau 87 * (- 25) - 64 * (- 34) = 1, ecuația originală. În exemplu, a doua opțiune este preferabilă deoarece îndeplinește termenul -64y din ecuația inițială atunci când y = -34.

10

Doar acum trebuie să luăm în considerare acest termen c în partea dreaptă a ecuației. Deoarece ecuația precedentă demonstrează o soluție pentru ax + by = 1, multiplicați ambele părți cu c obținerea unui (cx) + b (cy) = c. Dacă (-25, -34) este o soluție de 87x - 64y = 1, atunci (-75, -102) este o soluție de 87x-64y = 3.

11

Dacă o ecuație liniară diofantină are o soluție, atunci are soluții infinite. Acest lucru se datorează faptului că ax + by = la (x+b) + b (y-a) = a (x+2b) + b (y-2a) și, în general, ax + by = la (x+kb) + b (y-ka) pentru fiecare număr întreg k. De aceea, deoarece (-75, -102) este o soluție de 87x-64y = 3, alte soluții sunt (-11, -15), (53.72), (117.159) etc. Soluția generală poate fi scrisă ca (53 + 64k, 72 + 87k) unde k este orice număr întreg.