Cum se rezolvă ecuațiile liniare diophantine

O ecuație diofantină este o ecuație algebrică, cu restricția suplimentară că ne referim doar la soluții în care variabilele sunt numere întregi. În "general", există mai multe abordări pentru rezolvarea acestui tip de ecuație (Ultima teoremă a lui Fermat este o ecuație eminentă diophantină care a rămas nerezolvată de peste 350 de ani.)

conținut

Pași
Sfaturi
Materiale necesare

Cu toate acestea, ecuațiile diofantine "lineare" sub forma unui "x" + b "y" = c pot fi rezolvate într-un mod relativ ușor folosind algoritmul descris aici. Folosind această metodă, putem găsi (4,7) ca singura soluție în întregi pozitivi pentru 31x + 8y = 180. Diviziunea în aritmetica modulară poate fi exprimată și ca o ecuație liniară diofantină. De exemplu, 12/7 (mod 18) solicită soluția pentru 7x = 12 (mod 18) și poate fi rescrisă ca 7x = 12 + 18y sau 7x - 18y = 12. În timp ce unele dintre aceste ecuații sunt extrem de greu de rezolvat, este posibil să experimentați acest lucru.

pași

Imaginea intitulată Rezolvați o ecuație liniară diofantină Pasul 1

Dacă nu este încă, puneți ecuația în forma ax + by = c.

Imaginea intitulată Rezolvați o ecuație liniară diofantină Pasul 2

Aplicați algoritmul euclidian asupra coeficienților a și b. Aceasta are două scopuri. În primul rând, vrem să știm dacă a și b au un factor comun. Dacă încercați să rezolvați 4x + 10y = 3, putem spune rapid că dacă partea stângă este întotdeauna uniformă și dreapta este întotdeauna ciudată, nu există o soluție întreagă. De asemenea, dacă am avea 4x + 10y = 2, am putea simplifica problema pentru 2x + 5y = 1. Al doilea motiv este: stabilit că există o soluție, putem construi unul din secvența de coeficienți obținuți din algoritmul euclidian.

Imaginea intitulată Rezolva o ecuație liniară diofantină Pasul 3

Dacă "a", "b" și "c" au un factor comun, atunci simplificați prin împărțirea părților stângi și drepte ale ecuației cu acest factor. Dacă "a" și "b" au un factor comun care nu este împărțit cu "c", opriți. Nu există soluții întregi.

Imaginea intitulată Rezolva o ecuație liniară diofantină Pasul 4

Efectuați o foaie de calcul cu trei linii, așa cum se arată în figură.

Imaginea intitulată Rezolvați o ecuație liniară diofantină Pasul 5

Puneți în rândul superior coeficienții algoritmului lui Euclid. În această imagine, se arată cum rezoluția de la 87x - 64y = 3.

Imaginea intitulată Rezolvați o ecuație liniară diofantină Pasul 6

În cele două linii de fund, de la stânga la dreapta, procedați în felul următor: Pentru fiecare celulă, plasați produsul celular deasupra coloanei respective și în partea stângă a celulei goale. Completați această celulă cu produsul adăugând valoarea celor două celule din stânga.

Imaginea intitulată Rezolvați o ecuație liniară diofantină Pasul 7

Uită-te la ultimele două coloane ale tabelului complet. Coloana finală ar trebui să numere "a" și "b", plus coeficienții ecuației în pasul 3 (Dacă nu, revedeți calculele). Ultima coloană va conține alte două numere. De exemplu, cu = 87 și b = 64, alături de ultima coloană conține 34 și 25.

Imaginea intitulată Rezolvați o ecuație liniară diofantină Pasul 8

Rețineți că 87 * 25-64 * 34 = -1. Factorul determinant al matricei 2x2 din dreapta jos va fi întotdeauna mai mult sau mai puțin 1. Dacă este negativ, multiplicați ambele părți ale identității cu -1 pentru a avea 87 * 25 + 64 * 34 = 1. Această observație este punctul de plecare pentru construirea soluție.

Imaginea intitulată Rezolvați o ecuație liniară diofantină Pasul 9

Reveniți la ecuația inițială. Rescrieți identitatea pasului anterior, fie ca 87 * (- 25) + 64 * (34) = 1 sau ca 87 * (- 25) - 64 * (- 34) = 1. Utilizați tot ce vă aminteste cel mai bine despre ecuația inițială. De exemplu, a doua opțiune este preferabilă deoarece se potrivește cu termenul de -64y în original, unde y = -34.

Imaginea intitulată Rezolvați o ecuație liniară diofantină Pasul 10

Acum trebuie să ne uităm la termenul constant "c" în partea dreaptă a ecuației. Deoarece ecuația de mai sus demonstrează o soluție pentrux + by = 1, prin înmulțirea ambelor părți cu "c" pentru a obține o (cx) + b (cy) = c. Dacă (-25, -34) vom avea o soluție pentru 87x - 64y = 1. Astfel, (-75, -102) este o soluție pentru 87x-64y = 3.

Imaginea intitulată Rezolvați o ecuație liniară diofantină Pasul 11

Dacă o ecuație diofantină are vreo soluție, atunci are o infinitate de alții. Acest lucru se datorează faptuluix + by = a (x+b) + b (y-a) = a (x+2b) + b (y-2a) și, în general,x + by = a (x+kb) + b (y-ka) pentru orice număr întreg k. De aceea, deoarece (-75, -102) este o soluție pentru 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.

sfaturi

Ar trebui să puteți rezolva acest lucru cu creion și hârtie. Calculatoarele și foile de calcul vă vor ajuta dacă trebuie să efectuați conturi mai mari.
Verificați răspunsul. Instrucțiunile de la pasul 8 ar trebui să vă ajute să surprindeți orice greșeală făcută în algoritmul lui Euclid sau în completarea tabelului. Compararea răspunsului final cu ecuația inițială ar trebui să fie, de asemenea, utilă în identificarea erorilor.

Cum se rezolvă ecuațiile liniare diophantine

pași

sfaturi

Materiale necesare