Pojęcia największego wspólnego dzielnika i najmniejszej wspólnej wielokrotności liczb całkowitych są fundamentalne w teorii liczb. Ich podstawowa definicja jest ściśle związana z istnieniem porządku w zbiorze liczb całkowitych. Należy jednak zaznaczyć, że istnieje definicja tych pojęć w ogólniejszych strukturach algebraicznych, w których na ogół nie możemy mówić o pojęciu „najmniejszy” czy „największy”. Wspomnianą defincję przdstawimy dalszej części naszyh rozważań ( odnośnik).
Definicja 2.2.1 ( NWD, NWW, względna pierwszość).
(1) Największym wspólnym dzielnikiem liczb \(a_1,\dots ,a_r\in \Z \), (zakładamy, że przynajmniej jedna z liczb jest niezerowa) nazywamy największą liczbę całkowitą, która dzieli wszystkie \(a_1, \ldots , a_r\). 1
\(\underline {Oznaczenie:}\) \(\nwd (a_1,\dots ,a_r)\) (w literaturze również: \((a_1,\ldots , a_r)\))
(2) Najmniejszą wspólną wielokrotnością niezerowych liczb całkowitych \(a_1,\dots ,a_r\) nazywamy najmniejszą liczbę całkowitą dodatnią, która jest podzielna przez każdą z liczb \(a_1,\ldots , a_r\).
\(\underline { Oznaczenie:}\) \(\nww (a_1,\dots ,a_r)\) (w literaturze również: \([a_1,\ldots , a_r]\))
(3) (liczby względnie pierwsze) Liczby \(a_1, \ldots , a_r\in \Z \), \(a_1\ne 0\) nazywamy względnie pierwszymi, gdy \(\nwd (a_1,\ldots , a_r)=1\).
Przedstawimy teraz metodę wyznaczania największego wspólnego dzielnika dwóch liczb całkowitych \(a\) i \(b\), która nosi nazwę algorytmu Euklidesa 2. Oczywiście, jeśli \(a\in \Z ^\star \), \(b=0\), to \(\nwd (a,b)=|a|\). W dalszej części naszych rozważań zakładamy, że obie liczby są niezerowe.
Algorytm Euklidesa 3
Ustalmy dwie liczby całkowite \(a,b\in \Z ^\star \). Przyjmijmy: \(r_{-1}:=a\), \(r_0:=|b|\).
Krok 1: Zgodnie z algorytmem dzielenia z resztą (1.3.(B) (\(\bullet \))) istnieją liczby całkowite \(q_1,r_1\in \Z \) takie, że:
(1) \(a=r_{-1}=q_1|b|+r_1\),
(2) \(0\leqslant r_1<|r_0|=|b|\).
Jeśli \(r_1=0\), to kończymy algorytm. Jeśli \(r_1\ne 0\), to wykonujemy Krok 2.
Krok 2: Istnieją liczby całkowite \(q_2,r_2\in \Z :\)
(1) \(r_0=q_2r_1+r_2\),
(2) \(0\leqslant r_2<r_1<|r_0|=|b|\).
Jeśli \(r_2=0\), to kończymy algorytm. Jeśli \(r_2\ne 0\), to kontynuujemy analogicznie.
Ogólnie, mając \(r_{i-2}, r_{i-1}\) takie, że \(r_{i-1}\ne 0\), wykonujemy kolejny krok:
Krok (i\(>\)1): Istnieją liczby całkowite \(q_i,r_i\in \Z \):
(1) \(r_{i-2}=q_ir_{i-1}+r_i\),
(2) \(0\leqslant r_i<r_{i-1}\).
Ze względu na nierówności: \(0\leqslant r_i<r_{i-1}\) istnieje \(N(a,b)\in \N \) takie, że \(r_{N(a,b)+1}=0\) ale \(r_{N(a,b)}\ne 0\).
Liczbę \(N(a,b)\in \N \) będziemy nazywać dalej długością algorytmu Euklidesa dla liczb \(a\) i \(b\), (długość może być równa zero, gdy \(b|a\)), zaś \(r(a,b):=r_{N(a,b)}\) wynikiem tego algorytmu.
Zanim przedstawimy związek algorytmu Euklidesa z wyznaczaniem największego wspólnego dzielniak liczb \(a, b\in \Z ^{\star }\) potrzebny nam będzie jeszcze jeden wynik.
Dowód. Niech \(d:=\nwd (a,b)\) i \(d’:=\nwd (b,r)\). Wykażemy, że \(d=d’\). Ponieważ \(d|a\) i \(d|b\), więc istnieją takie liczby \(k_{1}, k_{2}\in \Z \), że \(a=dk_{1}, b=dk_{2}\). Z założenia otrzymujemy równość \(r=a-qb=d(k_{1}-qk_{2})\). Oznacza to, że \(d|r\) i w konsekwencji \(d|d’\) (bo \(d’=\nwd (b,r)\)). W szczególności \(d\leq d’\). Niech teraz \(k_{3}, k_{4}\in \Z \) będą takie, że \(b=d’k_{3}, r=d’k_{4}\). Stąd \(a=qb+r=d’(qk_{3}+k_{4})\) i dostajemy, że \(d’|a\). Oznacza to, że \(d’\) jest wspólnym dzielnikiem \(a, r\) i prawdziwa jest nierówność \(d’\leq d\) (bo \(d=\nwd (a,b)\)). Otrzymujemy zatem \(d=d’\), co daje tezę. □
Wykażemy teraz, że prawdziwe jest następujące
Dowód. Dla \(a, b\in \Z ^\star \) oznaczmy \(n:=N(a,b)\). By dowieść naszego twierdzenia wykażemy równość \(\nwd (a,b)=r_{n}\). Z opisu algorytmu Euklidesa wynika, że istnieją takie ciągi liczb całkowitych \(r_{i}, i=1,\ldots , n, q_{i}, i=1, \ldots , n+1\), że spełnione są równości
\[ a=q_{1}|b|+r_{1},\; |b|=q_{2}r_{1}+r_{2},\ldots ,r_{n-2}=q_{n}r_{n-1}+r_{n},\;r_{n-1}=q_{n+1}r_{n}, \]
gdzie \(0<r_{n}<r_{n-1}<\ldots < r_{2}<r_{1}\). W konsekwencji, z lematu 2.2.3, otrzymujemy ciąg równości
\( \seteqsection {2} \)\begin{align*} \nwd (a,b)&=\nwd (|b|,r_{1})=\nwd (r_{1},r_{2})=\ldots =\nwd (r_{n-2},r_{n-1})\\ &=\nwd (r_{n-1},r_{n})=\nwd (q_{n+1}r_{n},r_{n})=r_{n}, \end{align*} co dowodzi tezy. □
Gdy już wiemy, że dla danej pary liczb \(a, b\in \Z ^{\star }\) można łatwo wyznaczyć ich największy wspólny dzielnik pojawia się naturalne pytanie: jak duża jest liczba kroków konieczna do wyznaczenia \(\nwd (a,b)\)? Innymi słowy interesuje nas wielkość liczby \(N(a,b)\). Odpowiedź na tak sformułowane pytanie daje rezultat otrzymany przez G. Lamégo. Zanim go sformułujemy przypomnijmy pojęcie liczby Fibonacciego. Dokładniej, jeśli \(F_{0}=0, F_{1}=1\), oraz dla \(n\geq 2\) położymy \(F_{n}=F_{n-1}+F_{n}\), to liczbę \(F_{n}\) nazywamy \(n\)-tą liczbą Fibonacciego. Jeśli oznaczymy teraz \(\phi \) dodatni pierwiastek równania \(x^2-x-1=0\), tzn. \(\phi =\frac {1}{2}(1+\sqrt {5})\), to można wykazać, że \(n\)-ta iczba Fibonacciego wyraża się tzw. wzorem Bineta postaci:
\[ F_{n}=\frac {1}{\sqrt {5}}\left (\phi ^{n}-\frac {1}{(-\phi )^{n}}\right ). \]
Stosując indukcję ze względu na \(n\) oraz rekurencję \(F_{n}=F_{n-1}+F_{n-2}\) bez trudu można wykazać, że \(F_{n}>\phi ^{n-2}\).
Dowód. Dla \(a, b\in \N , b<a,\) oznaczmy \(n:=N(a,b)\). Z twierdzenia 2.2.4 wiemy, że \(\nwd (a,b)=r_{n}\). Z opisu algorytmu Euklidesa wynika, że istnieją takie ciągi liczb całkowitych \(r_{i}, i=1,\ldots , n, q_{i}, i=1, \ldots , n+1\), że spełnione są równości
\[ a=q_{1}|b|+r_{1},\; |b|=q_{2}r_{1}+r_{2},\ldots ,r_{n-2}=q_{n}r_{n-1}+r_{n},\;r_{n-1}=q_{n+1}r_{n}, \]
\(0<r_{n}<r_{n-1}<\ldots < r_{2}<r_{1}\). Ponadto, dla \(i=1,\ldots , n,\) mamy, że \(q_{i}\geq 1\) oraz \(q_{n+1}\geq 2\). Otrzymujemy zatem, że
\( \seteqsection {2} \)\begin{align*} r_{n}&\geq 1=F_{1},\\ r_{n-1}&\geq 2r_{n}\geq 2F_{1}=F_{2},\\ r_{n-2}&\geq r_{n-1}+r_{n}\geq F_{2}+F_{1}=F_{3},\\ r_{n-3}&\geq r_{n-2}+r_{n-1}\geq F_{3}+F_{2}=F_{4},\\ \vdots & \\ r_{2} & \geq r_{3}+ r_{2}\geq F_{n-2}+F_{n-3}=F_{n-1},\\ r_{1} & \geq r_{2}+ r_{1} \geq F_{n-1}+F_{n-2}=F_{n},\\ r_{0}=b & \geq r_{1}+r_{0} \geq F_{n}+F_{n-1}=F_{n+1}. \end{align*} W szczególności prawdziwa jest nierówność \(b\geq F_{n+1}\) i jeśli \(n\geq 2\), to otrzymujemy \(b \geq \phi ^{n-1}\). Ponieważ \(\log _{10}\phi =0.208988\ldots >\frac {1}{5}\), więc \(\log _{10}b>\frac {1}{5}(n-1)\) lub równoważnie
\[ n\leq 5\log _{10}b+1. \]
Zauważmy teraz, że jeśli \(b\) ma \(m\) cyfr w zapisie dziesiętnym, to \(b\leq 10^{m}\) i stąd \(\log _{10}b<m\). W konsekwencji \(n<5m+1\) i ostatecznie \(n\leq 5m\). Ponieważ prawdziwa jest równość \(m=\lfloor \log _{10}b\rfloor +1\), więc dostajemy tezę. □
Uwaga 2.2.6. Należy zauważyć, że teza w powyższym twierdzeniu nie może być wzmocniona. Istotnie, z dowodu wynika, jeśli \(a=F_{n+1}, b=F_{n}\), to w nierównościach wiążących reszty \(r_{n-i}\) z liczbami Fibonacciego \(F_{i+1}\) dla \(i=0,\ldots , n\), mamy tak naprawdę równości, co jest konsekwencją rekurencji spełnianej przez liczby Fibonacciego.
Przejdziemy teraz do dowodu tzw. identyczności Bacheta-Bezouta, która dla ustalonych liczb całkowitych \(a_{1},\ldots ,a_{n}\), umożliwia przedstawienie \(\nwd (a_{1},\ldots ,a_{n})\) jako kombinacji liniowej o współczynnikach całkowitych liczb \(a_{1},\ldots ,a_{n}\).
Dowód. Najpierw udowodnimy tezę dla dwóch liczb \(a\), \(b\) z których co najmniej jedna jest niezerowa. W tym celu rozważmy zbiór \(T=\{ax+by: \ ax+by>0, x, y\in \Z \}\). Oczywiście, jedna z liczb \(\pm a\), \(\pm b\) należy do naszego zbioru bo któraś z liczb \(a\), \(b\) jest niezerowa. Wobec tego zbiór ten jest niepusty. Ponieważ zawiera wyłącznie liczby naturalne, to posiada element najmniejszy, powiedzmy \(d\). Istnieją więc takie liczby \(x_0\), \(y_0\in \Z \), że \(d=ax_0+by_0\). 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 \(a=dq+r\) i \(0\leqslant r<d\). Wobec tego
\[r=a-dq=a(1-qx_0)-bqy_0.\]
Jeśli \(r>0\), to \(r\in T\) i jest to element mniejszy od \(d\), sprzeczność. W takim razie \(r=0\) i w konsekwencji dostajemy \(d|a\). W analogiczny sposób dowodzimy, że \(d|b\).
Załóżmy teraz, że \(0<t\) jest taką liczbą całkowitą, która dzieli i \(a\) i \(b\). To oznacza, że \(a=tm\), \(b=tn\), skąd \(d=ax_0+by_0=t(mx_0+ny_0)\) czyli \(t|d\), wobec czego \(t\leqslant d\). Oznacza to, że każdy wspólny dzielnik liczb \(a\) i \(b\) jest dzielnikiem \(d\), co oznacza, że \(d=\nwd (a,b)\).
Przypuśćmy teraz, że \(n>2\) i nasze twierdzenie jest prawdziwe dla mniej niż \(n\) liczb.
Wprowadźmy następujące oznaczenia:
\[d_0:=\nwd (a_1,\ldots , a_{n-1})>0, \ \ \ \ d:=\nwd (\nwd (a_1,\ldots , a_{n-1}),a_n)>0.\]
Zgodnie z założeniem indukcyjnym wiemy, że istnieją takie liczby \(l_1,\ldots , l_{n-1}, k, l\in \Z \), że
\[ (\star )\ \ \ d_0=l_1a_1+\ldots +l_{n-1}a_{n-1}, \ \ \ \ \ d=kd_0+la_n. \]
Udowodnimy, że \(d\) jest największym wspólnym dzielnikiem liczb \(a_1,\ldots , a_n\), (a przy okazji udowodnimy własność rekurencyjnego obliczania \(\nwd \)).
Z definicji wynika, że \(d\) dzieli \(d_0\) oraz \(a_n\). Ponieważ \(d_0\) dzieli każde \(a_i\) dla \(i=1,\ldots , n-1\), z przechodniości relacji podzielności \(d\) jest wspólnym dzielnikiem wszystkich liczb \(a_1,\ldots , a_n\).
Z drugiej strony jeśli \(\tilde d\in \N \) jest wspólnym dzielnikiem \(a_1,\ldots , a_n\), to z \((\star )\) mamy, że \(\tilde d|d_0\), a tym samym liczba \(\tilde d\) dzieli \(d\). Oznacza to, że \(\tilde d\leqslant d\) i wobec tego \(d=\)NWD\((a_1,\ldots , a_n)\).
Jednocześnie, ponownie dzięki \((\star )\), wiemy, że \(d=kd_0+la_n=k(l_1a_1+\ldots +l_{n-1}a_{n-1})+la_n\) i przyjmując \(k_i:=kl_i\) dla \(i=1,\ldots , n-1\) i \(k_n:=l\) mamy tezę.
□
Z twierdzenia 2.2.7 i jego dowodu otrzymujemy następujące wnioski.
Wniosek 2.2.8 ( wnioski z BB). Z: \(a_1,\dots ,a_r\in \Z \), \(\exists \ i=1,\ldots ,r: a_i\ne 0\).
T: (1) Liczby \(a_1,\ldots ,a_r\) są względnie pierwsze wtedy i tylko wtedy, gdy istnieją takie liczby całkowite \(k_1,\ldots ,k_r\), że:
\[(\star )\ \ \ \ \ \ 1=k_1a_1+\ldots +k_ra_r.\]
(2) Jeśli \(r>2\), to \(\nwd (\nwd (a_1,\ldots , a_{r-1}),a_r)=\nwd (a_1,\ldots , a_r)\).
(3) Jeśli \((a,b)=1\) i \(a|bc\), to \(a|c\).
Odnotujmy jeszcze w tym miejscu, że znajomość rozkładu liczb całkowitych \(a, b\) na czynniki pierwsze umożliwia szybkie wyznaczenie \(\nwd (a,b)\). Istotnie, jeśli
\[ a=\text {sgn}(a)p_1^{k_1}\cdot \ldots \cdot p_s^{k_s},\;b=\text {sgn}(b)p_1^{l_1}\cdot \ldots \cdot p_s^{l_s},\]
(zakładamy, że \(p_i\ne p_j\) dla \(i\ne j\), \(k_i\geqslant 0\) oraz \(t_i=\)min\((k_i,l_i)>0\) dla każdego \(i\)), to \(\nwd (a,b)=p_1^{t_1}\cdot \ldots \cdot p_s^{t_s}\). Nie wspominamy dokładniej o tej metodzie, gdyż odwołuje się ona do zasadniczego twierdzenia arytmetyki, o którym opowiemy w dalszej części naszych rozważań. Należy jednak zwrócić uwagę, że ta metoda wyznaczania \(\nwd (a,b)\) ma istotną słabość, gdyż wymaga znajomości rozkładu liczb \(a, b\). Dla małych wartości \(a, b\) nie jest to problem, ale gdy liczby \(a, b\) są duże, powiedzmy \(>10^{100}\), i wybrane w sposób losowy, to problem ich rozkładu jest trudny.
Z podstawowych informacji odnotujmy na zakończenie zależność łaczącą \(\nwd (a,b)\) i \(\nww (a,b)\).
Przedstawimy teraz metodę, która umożliwia rozwiązywanie liniowych równań diofantycznych. Dokładniej, przez liniowe równanie diofantyczne będziemy rozumieć równanie postaci:
\[ax+by=c,\]
gdzie \(a, b, c\) są ustalonymi liczbami całkowitymi, zaś rozwiązań \(x, y\) poszukujemy w liczbach całkowitych.
Twierdzenie 2.2.10 ( istnienie i postać rozwiązań liniowego równania diofantycznego). Z: Niech \(a, b, c\in \Z \) i załóżmy, że \(ab\neq 0\).
T:
(1) Liniowe równanie diofantyczne \(ax+by=c\) posiada rozwiązanie w liczbach całkowitych \(x, y\), wtedy i tylko wtedy, gdy \(d=\)NWD\((a,b)|c\).
(2) Jeśli \((x_{0}, y_{0})\) jest dowolnym rozwiązaniem równania \(ax+by=c\), to każde inne rozwiązanie jest postaci
\[ x=x_{0}+\frac {b}{d}t,\quad y=y_{0}-\frac {a}{d}t, \]
dla pewnego \(t\in \Z \).
Dowód. Pierwsza część naszego twierdzenia jest natychmistowym wnioskiem z twierdzenia 2.2.7.
By dowieść drugiej części na początek zauważmy, że dla dowolnej liczby całkowitej \(t\) mamy
\[ a\left (x_{0}+\frac {b}{d}t\right )+b\left (y_{0}-\frac {a}{d}t\right )=ax_{0}+by_{0}=c. \]
Oznacza to, że para \(\left (x_{0}+\frac {b}{d}t,y_{0}-\frac {a}{d}t\right )\) również jest rozwiązaniem naszego równania.
Niech teraz \((X,Y)\) będzie całkowitym rozwiązaniem równania \(ax+by=c\), tzn. \(aX+bY=c\). Mamy zatem, że \(aX+bY=c=ax_{0}+by_{0}\) i w konsekwencji
\[ a(X-x_{0})=b(y_{0}-Y)\;\mbox {lub rÃşwnowaÅijnie}\;\frac {a}{d}(X-x_{0})=\frac {b}{d}(y_{0}-Y). \]
Ponieważ \(\nwd (a/d,b/d)=1\), więc \(\frac {a}{d}|y_{0}-Y\) oraz \(\frac {b}{d}|X-x_{0}\). Onzacza to, że istnieje taka liczba całkowita \(t\), że spełnione są równości
\[ t=\frac {y_{0}-Y}{\frac {a}{d}}=\frac {X-x_{0}}{\frac {b}{d}}. \]
Innymi słowy \(X=x_{0}+\frac {b}{d}t, Y=y_{0}-\frac {a}{d}t\), co kończy dowód naszego twierdzenia.
□
Przykład 2.2.11. By pokazać teraz działanie (rozszerzonej wersji) algorytmu Euklidesa w akcji rozwiążemy liniowe równanie diofantyczne
\[ 720x+546y=12. \]
By rowiązać powyższe równanie wyznaczymy najpierw \(\nwd (720,546)\), a dokładniej takie liczby całkowite \(x_{0}, y_{0}\), że \(\nwd (720,546)= 720x_{0}+546y_{0}\). Zanim jednak to zrobimy zauważmy, że przedstawienie \(\nwd \) dwóch liczb za pomocą kombinacji liczb wyjściowych można oczywiście uzyskać „wracając” krok po kroku drogą wykonywanego algorytmu Euklidesa. Jest to jednak czasochłonne, gdyż wymaga wielu operacji arytmetycznych. Procedurę tę można uprościć wyrażając w każdym kroku powstałą resztę jako kombinację liniową (o współczynnikach całkowitych) liczb \(720\) i \(546\).
Chcemy wyliczyć \(\nwd (720, 546)\) oraz przedstawić tę liczbę w postaci Bezouta (tak nazywać będziemy poszukiwaną kombinację).
Wypiszmy, dla przejrzystości kolejne kroki w tabeli
| 720 | 546 | |
| 720 | 1 | 0 |
| 546 | 0 | 1 |
.
Wiemy teraz, że \(720=1\cdot 546+174\). Mnożąc drugi wiersz przez \(1\) i odejmujemy od pierwszego dostajemy
| 720 | 546 | |
| 546 | 0 | 1 |
| 174 | 1 | -1 |
.
Otrzymaliśmy zatem przedstawienie reszty: \(174=1\cdot 720+(-1)\cdot 546\) w postaci kombinacji wyjściowych liczb. Dalej powtarzamy procedurę zgodnie z algorytmem Euklidesa i otrzymujemy równość \(546=3\cdot 174+24\). Ponownie więc mnożymy drugi wiersz ostatniej tabeli przez \(3\) i odejmujemy od pierwszego otrzymując
| 720 | 546 | |
| 174 | 1 | -1 |
| 24 | -3 | 4 |
,
i w konsekwencji dostajemy równość \(24=(-13)\cdot 720+4\cdot 546\). Kontynuujemy nasze rozumowanie wykorzystując równość \(174=7\cdot 24+6\) i otrzymujemy
| 720 | 546 | |
| 24 | -3 | 4 |
| 6 | 22 | -29 |
.
Po wydzieleniu \(24\) przez \(6\) jako resztę otrzymamy zero, wobec tego \(\nwd (720,546)=6\) i otrzymaliśmy też przedstawienie \(6=22\cdot 720+(-29)\cdot 546\). Mamy zatem, że para \((X_{0},Y_{0})=(22, 29)\) jest rozwiązaniem równania \(720X+546Y=6\). W konsekwencji, para \((x_{0},y_{0})=(44,-58)\) jest szczególnym rozwiązaniem naszego wyjściowego równania, zaś ogólne rozwiązanie ma postać
\[ x=44+91t,\quad y=-58-120t. \]
1 Zauważmy, że stwierdzenie największa liczba ma tutaj sens: rozważamy naturalny porządek w zbiorze liczb całkowitych, zaś potencjalne dzielniki są ograniczone z góry przez \(|a_i|\)
2 Euklides: matematyk grecki, głównie działający w Aleksandrii, (ok.364-300 p.n.e. dokładne daty nie są znane), autor jednego z najbardziej znanych dzieł matematycznych: Elementy
3 Nazwa algorytm pochodzi od brzmienia fragmentu nazwiska arabskiego matematyka Muhammada ibn Musa al.-Chorezmiego, którego uznaje się za prekursora metod obliczeniowych w matematyce. Żył on na przełomie VIII i IX wieku, przyczynił się do upowszechnienia systemu dziesiętnego oraz wprowadził stosowanie zera jako symbolu oznaczającego ”nic”