Podstawowe pojęcia | Informatyka MIMUW

Dowolną liczbę wymierną $a$ można wydzielić przez dowolną niezerową liczbę wymierną $b$ i wynik tego działania jest liczbą wymierną. Ograniczając sie jednak zbioru $\mathbb{Z}$ liczb całkowitych, nie każde dzielenie jest wykonalne: $15:3=5$ , $-22:2=-11$ ale $31:3=$ ?. Rozważamy więc dzielenie liczb całkowitych z resztą.

Dzielenie liczb całkowitych z resztą.

Niech $b>0$ , wtedy dla każdej liczby całkowitej $a$ istnieją jednoznacznie wyznaczone: iloraz $q$ i reszta $r$ spełniające:

$a=bq+r\qquad\textrm{i}\qquad 0\leq r < b.$

Resztę $r$ z dzielenia $a$ przez $b$ zapisujemy też jako: $a \ {\sf mod}\ b$ .

Przykład

$47 \ {\sf mod}\ 9 =2$ , $1823 \ {\sf mod}\ 2 =1$ , $32 \ {\sf mod}\ 43 =32$ , $111 \ {\sf mod}\ 13 =7$ , $-3 \ {\sf mod}\ 7 =4$ . W pewnych sytuacjach reszta równa jest $0$ , np. $-22=-2\cdot 11+0$ .

$b$ dzieli $a$ (lub $a$ jest podzielne przez $b$ , co zapisujemy $b|a$ , jeśli istnieje $q$ takie, że $b=aq$ . W takim wypadku mówimy też, że $b$ jest dzielnikiem $a$ lub, że $a$ jest wielokrotnością $b$ . Innymi słowy, jeśli $b$ dzieli $a$ to reszta z dzielenia $a$ przez $b$ równa jest $0$ tzn. $a\ {\sf mod} \ b =0$ .

Obserwacja 10.1

Dla dowolnych $a,b,c$ zachodzi:

jeśli $a|b$ to $a|bc$ ,

jeśli $a|b$ i $b|c$ to $a|c$ ,

jeśli $a|b$ , $a|c$ to $a|(b+c)$ .

Dowód

Z założenia pierwszego punktu wiemy, iż istnieje $d$ takie, że $ad=b$ . Mnożąc obie strony równości przez $c$ dostajemy $adc=bc$ . A więc istnieje $d'=dc$ takie, że $ad'=bc$ , co z kolei oznacza, że $a|bc$ .

Z założenia drugiego punktu wiemy, iż istnieją $d,e\in\mathbb{Z}$ takie, że $ad=b$ i $be=c$ . Łatwo zauważamy, że dla $d'=de$ mamy $ad'=c$ , czyli $a|c$ .

Z założenia trzeciego punktu istnieją $d,e$ takie, że $ad=b$ i $ae=c$ . Dodając stronami ostatnie równości otrzymujemy $a(d+e)=b+c$ , czyli $a|b+c$ .

Największy wspólny dzielnik liczb $a$ i $b$ (zapisywany przez ${\sf NWD}\ (a,b)$ , gdzie chociaż jedna z liczb $a,b$ jest różna od $0$ , to największa liczba $d$ taka, że $d|a$ i $d|b$ . Oczywiście, $1 \leq\ {\sf NWD}\ (a,b) \leq \min (|,|)$ .

Przykład

${\sf NWD}\ (30,75)=15$ , ${\sf NWD}\ (10,3)=1$ , ${\sf NWD}\ (2,8)=2$ .

Algorytm Euklidesa

Algorytm Euklidesa to algorytm wyznaczania największego wspólnego dzielnika dwu dodatnich liczb całkowitych. Warto tu wspomnieć, iż jest to jeden z najstarszych znanych algorytmów. Euklides zamieścił go ok. 300 roku p.n.e. w Elementach - jednym z najsłynniejszych dzieł naukowych ludzkości. Jednak sam algorytm prawie na pewno znał już Eudoksos z Knidos ok. 50 lat wcześniej.

Wczytaj liczby $a,b>0$ .
Oblicz $r$ jako resztę z dzielenia $a$ przez $b$ .
Zastąp $a$ przez $b$ , zaś $b$ przez $r$ .
Jeżeli $b=0$ to zwróć $a$ w przeciwnym wypadku przejdź do (2).

Przykład

Przebieg obliczenia ${\sf NWD}\ (1029,1071)$ :

$\begin{array} {llll} a=1029 & b=1071 & 1029=0\cdot 1071+1029 & r=1029 \\ a=1071 & b=1029 & 1071=1\cdot 1029+42 & r=42 \\ a=1029 & b=42 & 1029=24\cdot 42+21 & r=21 \\ a=42 & b=21 & 42=2\cdot 21+0 & r=0 \\ a=21 & b=0 & & \end{array}$

Zgodnie z instrukcją (4) algorytm zwraca $a=21$ .

Dowód

Dla dowódu poprawności algorytmu Euklidesa ustalmy dwie liczy naturalne $a,b>0$ . Jeśli $a < b$ to podany algorytm odwróci ich porządek przy pierwszym wykonaniu kroku (3), gdyż w tym przypadku $a \ {\sf mod} \ b =a$ . Zauważmy, że w każdym następnym kroku $a>b>r$ , ponieważ reszta z dzielenia $a$ przez $b$ leży w zbiorze ${\{ {0,\ldots,b-1} \} }$ . A zatem kolejne reszty będą tworzyć ciąg ściśle malejący, który w końcu osiągnie $0$ , czyli algorytm Euklidesa po pewnej skończonej ilości kroków się zatrzyma.

Pozostaje sprawdzić, czy algorytm Euklidesa zwraca właściwą odpowiedź. Niech $r=a \ {\sf mod} \ b$ tzn. $r=a-bq$ dla pewnego $q$ . Wszystkie dzielniki $a$ i $b$ dzielą prawą stronę ostatniej równości, a więc dzielą też $r$ , co implikuje ${\sf NWD}\ (a,b)={\sf NWD}\ (b,r)$ . Dowodzi to, iż wszystkie pary rozważane przez algorytm mają te same dzielniki, a więc ten sam ${\sf NWD }$ .

Rozszerzenie algorytmu Euklidesa.

Poza znajdowaniem NWD dwóch podanych liczb $a,b>0$ algorytm Euklidesa można zastosować do wskazania dwu dodatkowych liczb $x,y\in\mathbb{Z}$ takich, że

$ax+by={\sf NWD}\ (a,b).$

Już sam fakt, że istnieją takie liczby $x,y$ to obserwacja, która leży u podstaw wielu kolejnych twierdzeń. Ponadto rozszerzony algorytm Euklidesa jest intensywnie stosowany do rozwiązywania równań, w przekształceniach kryptograficznych.

Dowód

Załóżmy, że $a>b$ . Niech $r_0=a$ , $r_1=b$ , natomiast $r_2\ldots,r_n,r_{n+1}$ będą kolejnymi resztami wygenerowanymi przez algorytm Euklidesa, przy czym $r_{n+1}=0$ . Wtedy wiemy, że $r_n={\sf NWD}\ (a,b)$ oraz

$\begin{align*} {} r_{n-1} & =q_{n-1}\cdot r_n, \\ r_{n-2} & =q_{n-2}\cdot r_{n-1} + r_n, \\ r_{n-3} & =q_{n-3}\cdot r_{n-2} + r_{n-1}, \\ & \vdots & \\ r_1 & =q_1\cdot r_2+r_3, \\ r_0 & =q_0\cdot r_1+r_2, \end{align*}$

dla pewnych $q_0,q_1,\ldots,q_{n-1}$ . Mamy zatem $r_{n-2}-q_{n-2}\cdot r_{n-1}={\sf NWD}\ (a,b)$ . Załóżmy indukcyjnie, dla $0 < i\leq n-2$ , że istnieją $x,y\in\mathbb{Z}$ takie, że $r_{i}\cdot x+r_{i+1}\cdot y={\sf NWD}\ (a,b)$ . Ponieważ $r_{i+1}=r_{i-1}+q_{i-1}\cdot r_i$ otrzymujemy:

$\begin{align*} {\sf NWD}\ (a,b) & =r_{i}\cdot x+r_{i+1}\cdot y \\ & =r_{i}\cdot x + (r_{i-1}+q_{i-1}\cdot r_i)\cdot y \\ & =r_{i-1}\cdot y+r_{i}\cdot(x+q_{i-1}\cdot y). \end{align*}$

A więc możemy zejść z liczbą $i$ do $i=0$ , co daje pożądane przedstawienie ${\sf NWD}\ (a,b)$ jako $r_0\cdot x + r_1\cdot y =ax+by$ .

Czas działania.

Niech $r_0,r_1,\ldots,r_{n+1}$ będą zdefiniowane, jak w dowodzie powyżej. Załóżmy dodatkowo, iż $a>b$ (jeśli nie, to zaczynamy analizować po pierwszym kroku algorytmu). Pokażemy, że

$r_{j+2} < \frac{1}{2}r_j.$

Jeśli $r_{j+1}\leq \frac{1}{2}r_j$ , to natychmiast mamy $r_{j+2} < r_{j+1}\leq\frac{1}{2} r_j$ . Załóżmy więc, że $r_{j+1}>\frac{1}{2}r_j$ . W tym przypadku podczas dzielenia $r_j$ przez $r_{j+1}$ zachodzi $r_j=1\cdot r_{j+1}+r_{j+2}$ , czyli $r_{j+2}=r_j-r_{j+1} < \frac{1}{2}r_j$ .

Ponieważ po każdych, kolejnych dwu krokach rozmiar $r_j$ spada co najmniej dwukrotnie, kroków jest $O(\lg{a})$ . W każdym kroku przeprowadzane jest dzielenie liczb długości $O(\lg{a})$ , a więc $O(\lg^2{a})$ operacji bitowych. To oznacza, iż do policzenia ${\sf NWD}\ (a,b)$ ( $a\geq b$ ) algorytmem Euklidesa wystarcza $O(\lg^3{a})$ operacji bitowych.

Aby policzyć współczynniki $x$ , $y$ takie, że $ax+by={\sf NWD}\ (a,b)$ , zgodnie z przedstawionym dowodem, należy przedstawić ${\sf NWD}\ (a,b)$ jako kombinację $r_{n-1}$ i $r_{n-2}$ , a później pozbyć się kolejnych $r_i$ (poczynając od $r_{n-1}$ ) wprowadzając $r_{i-2}$ . Mamy więc $O(\lg{a})$ kroków i w każdym kroku przeprowadzamy mnożenie i dodawanie lub odejmowanie liczb o długości co najwyżej $O(\lg{a})$ .

Przykład

Działanie rozszerzonego algorytmu Euklidesa dla $a=1547$ i $b=560$ .

$\begin{align*} 1547 & =2\cdot560+427 \\ 560 & =1\cdot427+133 \\ 427 & =3\cdot133+28 \\ 133 & =4\cdot28+21 \\ 28 & =1\cdot21+7 \\ 21 & =3\cdot7+0. \end{align*}$

A więc ${\sf NWD}\ (1547,560)=7$ . Aby wyrazić $7$ jako kombinację danych wejściowych liczymy:

$\begin{align*} 7 & =\textbf{28}-1\cdot\textbf{21}=28-1\cdot(133-4\cdot28) \\ & =-1\cdot\textbf{133}+5\cdot\textbf{28}=-1\cdot133+5\cdot(427-3\cdot133) \\ & =5\cdot\textbf{427}-16\cdot\textbf{133}=5\cdot427-16\cdot(560-1\cdot427) \\ & =-16\cdot\textbf{560}+21\cdot\textbf{427}=-16\cdot560+21\cdot(1547-2\cdot560) \\ & =21\cdot\textbf{1547}-58\cdot\textbf{560}. \end{align*}$