3582469008

Równania diofantyczne liniowe - równania rozwiązywane w zbiorze liczb całkowitych Z. Są to równania postaci:

ax + by = c

Do ich rozwiązywania wykorzystuje się algorytm Euklidesa służący do wyznaczania najmniejszego wspólnego dzielnika

Równanie diofantyczne liniowe można rozwiązać, gdy NWD(a, b) dzieli c. W przeciwnym wypadku jest ono sprzeczne.

Przykłady i metoda rozwiązywania :

A) Rozwiąż w zbiorze liczb całkowitych:

1)    504* + 462y = 42

2)    504% + 462y = 126

3)    504% + 462y = 13

Dla każdego z powyższych równań współczynniki a i b są równe, więc sprawdzenie, czy są one rozwiązywalne sprowadza się do jednej czynności

NWD(a, b)=?

Wykorzystuję rozszerzony algorytm Euklidesa, którego kolejne kroki będą potrzebne w dalszej części zadania:

1.    Biorę większą z licz a, b i przedstawiam ją jako wielokrotność tej drugiej plus reszta:

504 = 1 * 462 + 42

2.    W kolejnych krokach robię to samo, ale za większą liczbę biorę tą mniejszą, a za mniejszą - resztę (i tak dopóki reszta nie wyniesie 0):

462 = 11*42 + 0

3.    Gdy reszta jest równa zero, wynikiem jest mniejsza liczba, w tym wypadku 42.

WD(504,462) = 42

Teraz sprawdzam, czy równania są rozwiązywalne w zbiorze liczb całkowitych:

1)    42/42 e Z, więc równanie ma rozwiązania

2)    126/42 e Z, więc równanie ma rozwiązania

3)    13142 £ Z, więc równanie nie ma rozwiązania

Wyznaczam rozwiązania szczególne %₀, y₀ przedstawiając NWD(a, b) za pomocą kroków alg. Euklidesa sumę wielokrotności a i b :

42 = 504* 1-462*1 *o = i,yo = -i

Korzystając z wzorów na rozwiązania ogólne można wyznaczyć ostateczne rozwiązania: