Jak wyznaczyć liczby całkowite x i y takie, że ax + by = c?

Rozwiązywanie równania nieoznaczonego (albo: równania diofantycznego) ax + by = c polega na wyznaczeniu wszystkich par (x, y) liczb całkowitych, spełniających to równanie.

Twierdzenie: Równanie diofantyczne ax + by = c ma rozwiązanie wtedy i tylko wtedy, gdy NWD(a, b) jest dzielnikiem liczby c.

Dowód: Oznaczmy d = NWD(a, b) i załóżmy, że istnieje choć jedno rozwiązanie (x, y). Skoro d jest wspólnym dzielnikiem liczb a, b, to jest również wspólnym dzielnikiem liczb ax, by, a zatem jest też dzielnikiem ich sumy c = ax + by.

Odwrotnie, załóżmy, że d = NWD(a, b) jest dzielnikiem liczby c. Oznaczmy symbolem (a, b) = {ax + by : x, y całkowite} zbiór wszystkich wartości wyrażenia ax + by. Jest to niepusty zbiór liczb calkowitych ( a = a ^. 1 + b ^. 0 $\in$ (a, b)). Jeśli liczba ax + by jest elementem tego zbioru, ax + by $\in$ (a, b), to należy i liczba przeciwna: - (ax + by) = a(- x) + b(- y) $\in$ (a, b). Zatem do zbioru (a, b) należą liczby naturalne. Inaczej: zbiór A liczb naturalnych postaci ax + by jest niepusty. Każdy niepusty zbiór liczb naturalnych ma element najmniejszy. Niech p = aq + bs będzie najmniejszą liczbą naturalną postaci ax + by. Podzielmy a przez p z resztą:

a = i ^. p + r i 0 $$\leq$$ r < p

skąd:

r = a ^. 1 - i ^. p = a ^. 1 - a ^. q - b ^. s =

$$\in$$ =

Ale p jest najmniejszą liczbą naturalną postaci ax + by, więc nierówność r < p oznacza, że r nie może być liczba naturalna, musi być zerem. Czyli p jest dzielnikiem liczby a. Podobnie sprawdzamy, że p jest dzielnikiem liczby b. W takim razie p jest dzielnikiem największego wspólnego dzielnika d. Ale wiemy już, że d jest dzielnikiem każdej liczby postaci ax + by, w tym liczby p. Ostatecznie p = d. To z kolei oznacza, ze d = aq + bs $\in$ (a, b). Zatem każda wielokrotnosc dt = a(qt) + b(st) liczby d jest postaci ax + by - między innymi liczba c. To kończy dowód.

Twierdzenie: Jeśli para liczb całkowitych (x₀, y₀) jest rozwiązaniem równania diofantycznego ax + by = c i jeśli d = NWD(a, b), gdzie a = a'd, b = b'd, c = c'd, to każde rozwiązanie dane jest wzorem

$$\left\{\vphantom{ \begin{array}{l} x = x_0 + t \cdot b' y = y_0 - t \cdot a' \end{array} }\right.$$$$\begin{array}{l} x = x_0 + t \cdot b' y = y_0 - t \cdot a' \end{array}$$

dla pewnej liczby całkowitej t.

Dowód: Z jednej strony każda taka para (x, y) jest rozwiązaniem:

ax + by = a(x₀ + tb') + b(y₀ - ta') =

= ax₀ + by₀ + (ab' - ba')t =

= c + d (a'b' - b'a')t = c.

Z drugiej strony jeśli ax + by = c i ax₀ + by₀ = c, to

ax + by = ax₀ + by₀

a(x - x₀) = b(y₀ - y)

a'(x - x₀) = b'(y₀ - y).

Liczby a', b' są względnie pierwsze, więc jedyną możliwościa jest

x - x₀ = b't,    y₀ - y = a' > t

dla pewnej liczby całkowitej t, co kończy dowód.

Pozostaje wskazać sposób znajdowania jednego rozwiązania (x₀, y₀). W tym celu szukamy rozwiązania równowaznego równania a'x + b'y = c'. Najpierw rozwiązujemy pomocnicze równanie a'u + b'v = 1. Rozwiązaniem interesującego nas równania będzie para (c'u, c'v).

Żeby wyznaczyć u i v stosujemy algorytm Euklidesa do liczb a' i b':

a' = i₁b' + r₁ i 0 $$\leq$$ r₁ < b';

b' = i₂r₁ + r₂ i 0 $$\leq$$ r₂ < r₁;

r₁ = i₃r₂ + r₃ i 0 $$\leq$$ r₃ < r₂;

...

r_m-4 = i_m-2r_m-3 + r_m-2 i 0 $$\leq$$ r_m-2 < r_m-3

r_m-3 = i_m-1r_m-2 +1 i 0 $$\leq$$ 1 < r_m-2.

Teraz obliczamy kolejno od końca:

1 = r_m-3 - i_m-1r_m-2 =

= r_m-3 - i_m-1(r_m-4 - i_m-2r_m-3) =

= (1 + i_m-1i_m-2)r_m-3 - i_m-1r_m-4

itd. Jeśli już udało się znaleźć przedstawienie

1 = $$\alpha$$r_k + $$\beta$$r_k+1

to z równości

r_k-1 = i_k-3r_k + r_k+1

wyznaczamy resztę o największym numerze (najmniejszą z tych trzech reszt):

r_k+1 = r_k-1 - i_k-3r_k

i podstawiamy do 1 = $\alpha$r_k + $\beta$r_k+1 :

$$\alpha \beta$$ 1 =

$$\beta \alpha \beta$$ =

Po takim wykorzystaniu równości a' = i₁b' + r₁ otrzymujemy w wyniku szukane rozwiązanie.

Przykład: wyznaczyć jedno rozwiązanie równania diofantycznego

1119x - 6778y = 1.

Najpierw algorytm Euklidesa:

-6778 = - 7 ^. 1119 + 1055

1119 = 1 ^. 1055 + 64

1055 = 16 ^. 64 + 31

64 = 2 ^. 31 + 2

31 = 15 ^. 2 + 1

potem podstawienia:

1 = 31 - 15 ^. 2

2 = 64 - 2 ^. 31

1 = 31 - 15 ^. (64 - 2 ^. 31) = 31 ^. 31 - 15 ^. 64

31 = 1055 - 16 ^. 64

1 = 31 ^. 31 - 15 ^. 64 = 31 ^. (1055 - 16 ^. 64) - 15 ^. 64 = 31 ^. 1055 - (15 + 31 ^. 16) ^. 64 = 31 ^. 1055 - 511 ^. 64

64 = 1119 - 1 ^. 1055

1 = 31 ^. 1055 - 511 ^. 64 = 31 ^. 1055 - 511 ^. (1119 - 1 ^. 1055) = (31 + 511) ^. 1055 - 511 ^. 1119 = 542 ^. 1055 - 511 ^. 1119

1055 = - 6778 + 7×1119

1 = 542 ^. 1055 - 511 ^. 1119 = 542 ^. (- 6778 + 7 ^. 1119) - 511 ^. 1119 = 542 ^. (- 6778) - (511 - 542 ^. 7) ^. 1119 = 1119 ^. 3283 - 6778 ^. 542.

Tak więc ostatecznie otrzymaliśmy:

1 = 1119 ^. 3283 - 6778 ^. 542.