Ecuația diofantină liniară

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

O ecuație diofantină liniară este o ecuație diofantină în care relațiile dintre variabile sunt liniare.

Ecuația diofantină liniară în două variabile

Criteriul de solvabilitate

Înainte de a examina câteva metode de rezolvare a ecuațiilor liniare diofantine, să vedem un criteriu pentru solvabilitatea lor.

Teorema

Lasa-i sa fie , , numere întregi.

Ecuația are soluții întregi dacă și numai dacă este divizibil cu cel mai mare divizor comun al Și , adică dacă și numai dacă .

Demonstrație

Este și ne amintim că identitatea lui Bézout afirmă că există două numere întregi Și astfel încât

.

să presupunem că acțiune . Înmulțim ambele părți ale ecuației cu numărul întreg și obținem

se concluzionează că cuplul este soluția ecuației diofantine.

Pe de altă parte, să presupunem că ecuația are o soluție dată de pereche . Expresia este o combinație liniară de numere întregi divizibile cu și, prin urmare, dă un număr întreg, egal cu , divizibil cu acest număr întreg. ( cvd )

Reductibilitate la coeficienții de coprimă

Fiecare ecuație diofantină solubilă o scriem , poate fi redus la o ecuație diofantină de formă având coeficienții de coprimă .

Avem de fapt că, dacă punem:

noi obținem

in care .

Rezoluție cu algoritmul lui Euclid

Să vedem acum o metodă de soluție bazată pe algoritmul lui Euclid pentru găsirea celui mai mare divizor comun între doi sau mai mulți numere întregi.

Să continuăm pas cu pas și înainte de a rezolva ecuația „redusă” cu , să ne ocupăm de rezolvarea ecuației „particulare” .

Putem presupune că este mai mare decât și implementăm algoritmul lui Euclid. Sa spunem Și :

cu
cu

cu
cu

.

Ultimul rest este în conformitate cu faptul că Și sunt primii printre ei. Acum trebuie să obținem o reprezentare a printr-un proces care derivă din algoritm. Să începem de jos și să scriem ca o combinație liniară de Și

.

Penultima ecuație este echivalent cu

,

și, înlocuind penultimul în ultimul, obținem

.

Am obținut astfel ca o combinație liniară de și de .

Din a treia ultima ecuație avem asta

și, similar cu ceea ce s-a făcut anterior, obținem ca o combinație liniară de și de .

Procesul continuă până când îl veți avea ca o combinație liniară de și de . Coeficienții combinației liniare, pe care îi denotăm Și , constituie o soluție a ecuației .

Să începem acum cu egalitatea pe care știm că este adevărată și înmulțiți ambele părți cu

.

Acest lucru echivalează cu a spune că cuplul este soluția ecuației .

Soluția găsită nu este singura soluție a ecuației . Într-adevăr, avem

.

Această egalitate arată că produsul este divizibil cu . De cand Și sunt primii dintre ei, putem concluziona că este divizibil cu , adică există un număr întreg astfel încât . Înlocuind această relație în cea precedentă, obținem:

adică .

În concluzie, soluțiile ecuației sunt date de

cu întreg.

Exemplu

Aplicăm metoda descrisă ecuației . Să luăm apoi în considerare ecuația și implementăm algoritmul lui Euclid în pereche Și :

Rescriem cele trei egalități prin evidențierea rămășițelor

Să începem cu ultima și să înlocuim valorile înapoi:

.

Deci avem Și .

Odată ce ați găsit o soluție la ecuație , pe care îl indicăm cu , pentru a obține o soluție a ecuației sunt suficiente trei multiplicări pentru același factor.

Înmulțind cu cei doi membri ai , obținem că o soluție a ecuației este dat de cuplu .

Soluția generală a ecuației este dat de

Rezoluție cu fracții continue

Acum arătăm cum pot fi utilizate fracțiile continuate pentru a rezolva ecuația diofantină . Abordarea noastră către acest obiectiv va avea loc treptat, prin pasaje ușoare, care vor culmina în cele din urmă cu metoda de rezolvare a fiecărei ecuații rezolvabile a formei .

Ecuația nedeterminată ax-by = ± 1

Să învățăm mai întâi cum să rezolvăm ecuația cu .

Teorema

Ecuația , unde este Și sunt numere întregi prime pozitive, are soluții întregi infinite .

Demonstrație

Să ne transformăm mai întâi într-o fracție continuă aritmetică limitată sau simplă

și calculăm reducerea .

Ultimii doi

ele sunt cheia soluției. Acestea, de fapt, satisfac relația fundamentală

și de atunci Și , da

.

De sine este par, adică dacă avem un număr par de coeficienți parțiali , iar ultima ecuație scrisă devine

.

Comparând acest lucru cu ecuația dată , vedem că o soluție în acest sens este

.

Cu toate acestea, aceasta este o soluție specială și nu soluția generală. Vom indica soluții speciale cu . Pe de altă parte dacă este ciudat așa că , putem schimba dezvoltarea

înlocuind

cu de sine

sau înlocuirea

cu de sine .

Adică, dacă dezvoltarea are un număr impar de coeficienți parțiali, se poate transforma în de sine sau în de sine ; în ambele cazuri numărul de coeficienți devine egal.

Folosind această fracție continuată, în ambele cazuri, recalculăm , și ecuația este din nou mulțumită.

După cum sa văzut deja în secțiunea anterioară, soluția generală este

( cvd )

Exemplu

Găsiți soluțiile întregi ale ecuației nedeterminate .

Aici numerele întregi Și sunt prime între ele și ecuația are soluții întregi. Fracția continuată corespunzătoare acesta este are un număr impar de coeficienți parțiali, dar poate fi înlocuit cu , dezvoltare echivalentă cu un număr par de coeficienți. Să le calculăm pe cele reduse.

Aici , , și, prin urmare, pentru

,

soluția generală a ecuației este

Observare

Metoda de rezolvare a ecuației cu este complet analog cu cel folosit pentru rezolvarea ecuației cu .

Doar transformă-te într-o fracție continuă aritmetică mărginită cu un număr impar de cele reduse.

Soluția generală a lui ax-by = c cu GCD (a, b) = 1

Am învățat să rezolv ecuația unde este Și sunt numere întregi prime, este ușor de rezolvat ecuația in care este întreg. După cum am văzut deja în paragrafele anterioare, soluția generală a Și

Soluția generală a lui ax + by = c cu GCD (a, b) = 1

Discuția acestei ecuații este similară, cu excepția unor modificări ușoare, cu cea a ecuației . Presupunând întotdeauna asta Și sunt numere întregi pozitive, mai întâi găsim o soluție specială a ecuației cu .

Pentru a face acest lucru, ne dezvoltăm în fracție continuată cu un număr par de coeficienți parțiali.

Din masa redusă luăm Și . Apoi contează , Ca înainte.

Trucul constă acum în scrierea ecuației date în formă

.

Schimbăm ordinea termenilor și obținem

.

Prin urmare împarte cantitatea afișată în stânga; dar prin urmare , care nu are divizori comuni cu (cu exceptia ), trebuie să împartă ceea ce echivalează cu a spune că există un număr întreg astfel încât

sau chiar asta

.

Se obține substituirea

care, rezolvat în variabilă , din

.

În schimb, oricare ar fi întregul , înlocuind da ai

și ecuația este satisfacut.

Deci soluția sa generală este

Exemplu

Rezolvăm acum ecuația diofantină cu fracții continue . Ne dezvoltăm în fracție continuă, obținând

Prin urmare . Fracția are un număr par de coeficienți parțiali, deci nu trebuie să o schimbăm. Reducerile fracției continue sunt: .

În concluzie, soluția generală a ecuației diofantine este dat de

.

Referințe

Elemente conexe

Matematica Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică