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ą.
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:
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 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.
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 } \).
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 \).
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*} \)