83702 Str018 (2)

32 I. Kilka mgarfnieA clprncnlnmcj I fot ii lioah

(c) Korzystając z punktów (a) i (h). znajdź ograniczenie górne liczby k, zależne tylko od a. Porównaj je z oszacowań i cm wynikającym z dowo* du twierdzenia 1.2.1.

11.    Celem tego ćwiczenia jest znalezienie ogólnego oszacowania czasu potrzeb* nego do znalezienia AW7)(o, h), gdzie a > h, lepszego niż podane w twierdzeniu 1.2.1

(a)    Wykaż, że liczba operacji na bitach potrzebnych do wykonania dzielenia a - bq + r wynosi 0((logó)(l + logq)).

(b)    Stosując szacowanie z punktu (a) do wszystkich 0(loga) dzieleń postaci r_t-₁ = q_lĄ i r, -|- r_ł4. wyprowadź następujące oszacowanie czasu: O ((log b) (logo)).

12.    Zajmijmy się wielomianami o współczynnikach rzeczywistych. (To zadanie ma zastosowanie również w przypadku wielomianów o współczynnikach z dowolnego ciała.) Jeśli f i g są wielomianami, to mówimy, że f\g_t jeśli istnieje wielomian h taki, że g = fh. Definiujemy NWD(f g) w zasadzie w taki sam sposób jak w przypadku liczb całkowitych, mianowicie jako wielomian najwyższego stopnia dzielący zarówno f jak i g. Wielomian NWD(f g) zdefiniowany w ten sposób, nic jest wyznaczony jednoznacznie, ponieważ możemy otrzymać inny wielomian tego samego stopnia, o tej samej własności, mnożąc go przez dowolną stałą różną od zera. Jednakże możemy wybrać go w jednoznaczny sposób wymagając, by wielomian będący największym wspólnym dzielnikiem był unormowany, tzn. miał współczynnik przy najwyższej potędze zmiennej równy 1. Mówimy, że wielomiany fig są względnie pierwsze, jeśli ich największy wspólny dzielnik jest „wielomianem stałym" równym 1. Obmyśl sposób znajdowania największego wspólnego dzielnika wielomianów - tzn. algorytm Euklidesa dla wielomianów - analogiczny do algorytmu Euklidesa dla liczb całkowitych, a następnie zastosuj ten algorytm do znalezienia (a) NWD(xf + x² + \, x² + \) oraz (b) NWD{x⁴ - 4x³ + 6x² — 4x + 1, x³ - x² + x - 1). W obu przypadkach znajdź wielomiany u(x) i v(x) takie, że największy wspólny dzielnik jest postaci u(x)f(x) + v(x)g(x).

13.    Wiadomo z algebry, że wielomian ma pierwiastki wielokrotne wtedy i tylko wtedy, gdy ma wspólny dzielnik różny od 1 ze swoją pochodną; w tym przypadku pierwiastki wielokrotne wielomianu f(x) są pierwiastkami NWD(f /'). Znajdź pierwiastki wielokrotne wielomianu ** — 2jc³ — x² + + 2x + 1.

14.    (Przed wykonaniem tego ćwiczenia przypomnij sobie, jak wykonuje się działania na liczbach zespolonych. Pamiętaj, że ponieważ (a + bi)(a — bi) jest liczbą rzeczywistą a² 4- ó², możemy dzielić liczby zespolone, pisząc (c + di)l(a -f bi) = (c + di)(a — bi)l(a² + b²).)

Liczby całkowite Gaussa są to liczby zespolone, których części rzeczywista i urojona są liczbami całkowitymi. Na płaszczyźnie zespolonej są one wierzchołkami kwadratów siatki kwadratowej utworzonej przez

proste przecinające osie w punktach o współrzędnych całkowitych**. Jeśli ot i /i są liczbami całkowitymi Gaussa, to mówimy, że st|/f, jeśli istnieje liczba całkowita Gaussa y taka, że fi — Tf. Definiujemy NWD(i, P) jako liczbę całkowitą Gaussa b o największej wartości bezwzględnej, dzielącą obie liczby a i [i (dla przypomnienia: wartość bezwzględna |£| to odległość liczby ó od 0, czyli pierwiastek kwadratowy z sumy kwadratów części rzeczywistej i urojonej liczby 5). Tak określony największy wspólny dzielnik nie jest wyznaczony jednoznacznie, ponieważ możemy pomnożyć go przez ±1 lub ± i, by otrzymać inną liczbę b o tej samej wartości bezwzględnej, dzielącą obie liczby ot i /?. To daje cztery możliwości. W dalszym ciągu każdą z tych czterech możliwych liczb będziemy traktować jako największy wspólny dzielnik.

Zauważmy, że każdą liczbę zespoloną można zapisać w postaci sumy liczby całkowitej Gaussa i liczby zespolonej, której części rzeczywista

1. 1

i urojona są zawarte między — i--

Wykaź, że to oznacza, iż liczbę

całkowitą Gaussa <x możemy podzielić przez inną liczbę całkowitą Gaussa P i otrzymać iloraz i resztę będące liczbami całkowitymi Gaussa, przy czym wartość bezwzględna reszty jest mniejsza od wartości bezwzględnej p. Zastosuj to do zaprojektowania algorytmu Euklidesa, za pomocą którego znajduje się największy wspólny dzielnik dwóch Hczb całkowitych Gaussa. Wykorzystaj ten algorytm Euklidesa do znalezienia (a) NWD{5 + 6/, 3-20 oraz (b) NWD{7 - lii, 8 - 190- W obu przypadkach przedstaw największy wspólny dzielnik jako kombinację liniową postaci ua + vP, gdzie u i o są liczbami całkowitymi Gaussa.

1S. Ostatnie ćwiczenie może być wykorzystane do znalezienia efektywnego sposobu zapisywania pewnych liczb pierwszych jako sum dwóch kwadratów. Przypuśćmy na przykład, że liczba pierwsza p dzieli pewną liczbę postaci b⁶ + 1. Chcemy zapisać p w postaci p = c² + d¹ dla pewnych liczb całkowitych c i d. Jest to równoważne znalezieniu nietrywialnego dzielnika liczby p w zbiorze liczb całkowitych Gaussa, ponieważ c² 4- d² = = (c + di)(c — di). Możemy postępować w następujący sposób. Zauważmy, że

ó⁶ + 1 = (ó² + l)(ó* -b² + \) oraz b* - b² + 1 = (b² - l)² 4 b².

Na mocy własności 4 relacji podzielności liczba p musi dzielić jeden z czynników po prawej stronie pierwszej równości. Jeśli p\b² +1 = = (b 4- i)(b — /), to zauważamy, że NWD(p, b + i) daje żądaną liczbę c -f di. Jeśli p\b* — b² + 1 = ((b² -1)4- bi)((b² - 1) - bi), to NWD(p, (b² — 1) 4- bi) daje nam szukaną liczbę c 4- di.

^f) To punkty często nazywa się punktami kratowymi (przyp. tłum.).