276061995

4 Podstawy teorii liczb

Dowód. C.l    □

Przejdziemy teraz do wspomnianej identyczności Bezouta, (zob. C.2)

Twierdzenie 1.2.4 (identyczność Bacheta-Bezouta). Z: a\,... ,a_n E Z, (co najmniej jedna z nich jest niezerowa)

T: Istnieją liczby ki,..., k_n E Z:

NWD(ai,..., a_n) = k\a\ + ... + k_na_n.

Dowód. Najpierw udowodnimy naszą własność dla dwóch liczb a, b z których co najmniej jedna jest niezerowa. Rozważmy zbiór T — {ax + by : ax + by > 0, x, y E Z}. Oczywiście, jedna z liczb ±a, ±b należy do naszego zbioru bo któraś z liczb a, b jest niezerowa. Wobec tego zbiór ten jest niepusty, zawiera wyłącznie liczby naturalne, posiada w takim razie element najmniejszy, ?? powiedzmy d. Istnieją więc liczby xq, yo E Z takie, że d — axo+byo. Udowodnimy, że d jest poszukiwanym największym wspólnym dzielnikiem a i b.

Udowodnimy najpierw, że d\a. Z algorytmu dzielenia z resztą wiemy, że istnieją q, r takie, że 0 ^ r < d, że a — dq + r. Wobec tego

r = a - dq = a(l - qx₀) - bqy₀.

Jeśli r > 0, to r E T i jest to element mniejszy od d, sprzeczność. W takim razie r — 0 i oznacza to, że d\a. Analogicznie dowodzimy, że d\b.

Załóżmy teraz, że 0 < i jest taką liczbą całkowitą, która dzieli i a i b. To oznacza, że a = tm, b = tn, skąd d = axo +by₀ = t(mxo + ny₀) czyli t\d, wobec czego t ^ d.

Przypuśćmy teraz, że n > 2 i twierdzenie mamy udowodnione dla mniej niż n liczb. Wprowadźmy następujące oznaczenia:

do := NWD(a!,..., o_n_i) >0,    d:= KWD(NWD(a_lt..., a„_i), aj > 0.

Zgodnie z założeniem indukcyjnym wiemy, że istnieją Zi,..., l_n~i, k,l E Z takie, że

(★) do = l\a\ + ... + /_n_io_n_i, d = kdo + lan-

Udowodnimy, że d jest największym wspólnym dzielnikiem liczb a\,... ,a_n. (przy okazji udowodnimy własność rekurencyjnego obliczania NWD).

Z definicji wynika, że d dzieli do oraz a_n. Ponieważ do dzieli każde a* dla i = 1,..., n—1, z przechodniości relacji podzielności d jest wspólnym dzielnikiem wszystkich liczb ai,... ,a_n.

Z drugiej strony jeśli d E N jest wspólnym dzielnikiem aj,..., a_n, to z (*) mamy, że d\do a tym samym dzieli d. Oznacza to, że d ^ d i wobec tego d =NWD(ai,..., a_n).

Jednocześnie ponownie dzięki (*) wiemy, że d = kdo+lcin = k(l\ai + .. . + /_n_ia_n_i) + Za„ i przyjmując fcj := kii dla i = 1,..., n — 1 i k_n := l mamy tezę.

□

Bezpośrednio, z dowodu i twierdzenia otrzymujemy kolejne wnioski.