276061996

1.3. Rozszerzenie algorytmu Euklidesa 5

Wniosek 1.2.5 (wnioski z BB). Z: a,\,... ,a_r e Z, 3 i = 1,...,r : Oi ^ 0.

T: (1) Liczby a\,... ,a_r są względnie pierwsze wtedy i tylko wtedy, gdy istnieją liczby całkowite ki,...,k_r takie, że:

(*)    1 — k\a\ + ... + k_ra_r.

(2)    Jeśli r > 2, to NWD(NWD(a_u..., a_r-i),a_r)=NWD{a₁,..., a_r),

(3)    Jeśli (a, b) = 1 i a\bc, to a|c.

Odnotujmy jeszcze w tym miejscu, że wyznaczanie NWD liczb całkowitych można też przeprowadzić za pomocą ich rozkładu na liczby pierwsze, jeśli a — sgn(a)pj' ■ ... • p^^s zaś b = sgn(6)pi‘ ■... - p^ls^s, (zakładamy, że p, Pj dla i ^ j, k_t ^ 0 oraz U =min(A:_i, li) > 0 dla każdego i) to NWD (a, b) = pf •• pi". Nie wspominamy dokładniej o tej metodzie, gdyż odwołuje się ona do zasadniczego twierdzenia arytmetyki, o którym opowiemy za chwilę. Z podstawowych informacji odnotujmy na zakończenie wniosek o zależności NWD(a, b) i NWW(a, 6).

Wniosek 1.2.6 (zależność między NWW i NWD). Dla liczb a, b E N zachodzi równość: NWD(a, b)-NWW(a, b) = ab.

Dowód. C.2    □

Zastosowania tożsamości Bezouta: liniowe równania diofantyczne.

Nazwą liniowe równanie diofantyczne określamy równanie postaci: ax + by = c

gdzie a, b, c są liczbami całkowitymi, zaś poszukiwane rozwiązania też należą do TL.

Bezpośrednio z identyczności Bezouta łatwo wynika wniosek dotyczący istnienia rozwiązań liniowych równań diofantycznych, (zob. C.3).

Wniosek 1.2.7 (istnienie rozwiązania równania diofantycznego). Liniowe równanie diofantyczne ax + by = c posiada rozwiązanie wtedy i tylko wtedy, gdy d —NWD(a, b)\c.

Oczywiście równanie takie, jeśli posiada rozwiązanie, to ma ich nieskończenie wiele -znając jedno szczególne (Xo,yo) otrzymujemy postać ogólną: (xq + ^,yo — ^f), k E Z.

1.3 Rozszerzenie algorytmu Euklidesa

Pod pojęciem rozszerzenia algorytmu Euklidesa kryje się bądź to wzbogacanie algorytmu o dodatkowe informacje jakie przy jego wykonywaniu otrzymamy, bądź też jego modyfikacje prowadzące do wniosków algebraicznych w szerszych strukturach.

W tej wstępnej części omówimy najprostsze rozszerzenie: pozwalające wyliczać jednocześnie przedstawienie Bezouta liczb a i 6 i tym samym też często wykorzystywaną, zwłaszcza w kryptografii odwrotność modulo zadanej liczby, (o ile oczywiście taka istnieje).