Największy wspólny dzielnik

Największy wspólny dzielnik, największy wspólny podzielnik – dla danych dwóch (lub więcej) liczb całkowitych największa liczba naturalna dzieląca każdą z nich[1]. Pojęcie to ma wiele uogólnień, które przedstawiono w dalszej części artykułu.

Największy wspólny dzielnik liczb i zapisuje się zwykle lub czasem po prostu Np. oraz

Dwie liczby nazywa się względnie pierwszymi, jeżeli ich największym wspólnym dzielnikiem jest – na przykład względnie pierwsze są i

Pojęcie największego wspólnego dzielnika wykorzystuje się podczas redukcji ułamków do postaci nieskracalnej (to znaczy takiej, w której licznik i mianownik są względnie pierwsze). Przykładowo największym wspólnym dzielnikiem liczb oraz jest stąd

Definicje

Jeśli nie zaznaczono inaczej, słowo „liczba” będzie oznaczać dalej liczbę całkowitą. Przedstawiona we wstępie definicja wymaga formalizacji: w szczególności należy wytłumaczyć, czym jest dzielnik liczby, co oznacza, że jest on wspólny dla danych liczb, i w jaki sposób wskazać największy z nich[a].

Otóż liczba jest dzielnikiem liczby jeśli istnieje taka liczba dla której zachodzi fakt ten zapisuje się [b]. Liczbę nazywa się wspólnym dzielnikiem liczb oraz jeśli dzieli ona obie z nich[c].

Największym wspólnym dzielnikiem liczb nazywa się taką nieujemną liczbę oznaczaną która jest wspólnym dzielnikiem oraz a przy tym każdy wspólny dzielnik i dzieli Symbolicznie można to wyrazić następująco: gdy

  • i oraz
  • jeśli i to dla dowolnej liczby

Największy wspólny dzielnik liczb i może być równoważnie zdefiniowany jako najmniejsza nieujemna liczba którą można przedstawić w postaci tożsamości Bézouta:

dla pewnych liczb całkowitych i – liczby te można wyznaczyć za pomocą rozszerzonego algorytmu Euklidesa.

Definicję największego wspólnego dzielnika można rozszerzyć na dowolną, skończoną liczbę argumentów za pomocą indukcji matematycznej; można go traktować jako przypadek szczególny rozszerzenia tego pojęcia na nieskończoną liczbę argumentów: największym wspólnym dzielnikiem dowolnego zbioru liczb całkowitych nazywa się taką nieujemną liczbę dla której spełnione są warunki

  • dla każdego
  • jeżeli dla każdego to dla każdej liczby

Wówczas jeżeli jest zbiorem skończonym składającym się z elementów to największy wspólny dzielnik zbioru oznacza się symbolem

Przykłady

  • Największym wspólnym dzielnikiem zbioru wszystkich liczb pierwszych jest 1.
  • Największy wspólny dzielnik zbioru liczb całkowitych nie istnieje.
  • Największym wspólnym dzielnikiem zbioru wszystkich tych liczb całkowitych, które w zapisie w systemie dziesiętnym jako ostatnią mają cyfrę 0, jest 10.
  • Największym wspólnym dzielnikiem zbioru pustego jest Ten przypadek szczególny bywa istotny ze względu na przejrzystość dowodów, w których unika się osobnego rozważania przypadków, gdy dany zbiór elementów jest pusty albo nie.

Obliczanie

Poprzez rozkład na czynniki pierwsze

Największe wspólne dzielniki można z zasady obliczać poprzez wyznaczenie rozkładu na czynniki pierwsze dwóch liczb i porównanie ich czynników, jak ma to miejsce w następującym przykładzie: aby obliczyć szuka się rozkładu na czynniki pierwsze liczb oraz i wyodrębnia „pokrywające się” części dwóch wyrażeń, stąd W praktyce metoda ta jest użyteczna dla małych liczb (np. za pomocą stosowanego w szkole zapisu „w słupku”), gdyż wyznaczanie rozkładu na czynniki pierwsze jest bardzo czasochłonne.

W następującym przykładzie, w którym poszukuje się największego wspólnego dzielnika liczb oraz do zobrazowania istoty problemu wykorzystany zostanie diagram Venna. Rozkładami tych liczb na czynniki pierwsze są:

Wspólną częścią rozkładu są dwie i

Least common multiple.svg
Najmniejsza wspólna wielokrotność =
Największy wspólny dzielnik =

Metoda szkolna

Dokonujemy w słupku rozkładu liczb, dla których szukamy NWD, na czynniki pierwsze rozpoczynając od czynnika 2 przez sprawdzenie, czy dana liczba dzieli się na konkretny czynnik bez reszty. Jeśli dzieli się, to pod daną liczbą wpisujemy iloraz, jeśli nie, to sprawdzamy kolejne czynniki pierwsze jako dzielniki. Dalej postępujemy analogicznie dopóki nie otrzymamy ilorazu równego 1. Następnie wyliczamy iloczyn liczby 1 i tych czynników, które występują w obu rozkładach, ale tak, że dany czynnik pierwszy w iloczynie występuje tyle razy ile razy występował w rozkładzie, w którym pojawił się mniejszą liczbę razy. Wynika z tego, że NWD dwóch liczb pierwszych jest liczba 1.

Wyznaczenie NWD liczb 42 i 56

Czynnik 2 wystąpił w obu rozkładach (raz w pierwszym rozkładzie i trzy razy w drugim), więc w iloczynie występuje tylko raz, czynnik 3 wystąpił raz w pierwszym rozkładzie i zero razy w drugim, więc w iloczynie nie występuje, natomiast czynnik 7 wystąpił również w obu rozkładach (po jednym razie w pierwszym i drugim), więc w iloczynie występuje też raz.

Wyznaczenie NWD liczb 192 i 348

Za pomocą algorytmu Euklidesa

Znacznie bardziej efektywnym sposobem jest pochodzący ze słynnych Elementów algorytm Euklidesa, który opiera się na twierdzeniu o dzieleniu z resztą oraz obserwacji, iż dwóch liczb dzieli również ich różnicę. Przykładowo dzielenie przez daje iloraz równy i resztę Podzielenie przez daje iloraz i resztę równą Ostatecznie podzielenie przez daje zerową resztę, co oznacza, że jest Formalnie można to opisać w następujący sposób:

Ciąg ilorazów powstały podczas algorytmu Euklidesa tworzy ułamek łańcuchowy.

Inne metody

Jeśli są niezerowe, to największy wspólny dzielnik i można obliczyć za pomocą najmniejszej wspólnej wielokrotności tych liczb:

Keith Slavin pokazał, że dla nieparzystych równość

definiuje funkcję zmiennej zespolonej [2] zaś Wolfgang Schramm udowodnił, że

jest funkcją całkowitą zmiennej dla wszystkich dodatnich liczb całkowitych gdzie oznacza sumę Ramanujana[3]. Z kolei Marcelo Polezzi wykazał, iż

dla dodatnich liczb całkowitych [4] Donald Knuth dowiódł następującej redukcji:

dla nieujemnych liczb całkowitych z których co najwyżej jedna może być zerem[5].

Własności

  • Z definicji zmiana kolejności argumentów nie zmienia jego wartości.
  • Każdy wspólny dzielnik liczb i jest dzielnikiem
  • Dla dowolnego zachodzi ponieważ każda liczba dzieli zero (jest dzielnikiem zera), zaś największym dzielnikiem jest Własność ta jest punktem wyjścia dla algorytmu Euklidesa.
  • Jeżeli oraz to
  • Jeżeli jest nieujemną liczbą całkowitą, to
  • Jeżeli jest dowolną liczbą całkowitą, to
  • Jeżeli jest niezerowym wspólnym dzielnikiem oraz to
  • Jako funkcja, jest
    • multiplikatywna w następującym sensie: jeżeli i są względnie pierwsze, to
    • przemienna:
    • łączna:
  • Największy wspólny dzielnik trzech liczb może być obliczony jako lub w inny sposób na mocy przemienności i łączności. Definicję tę można rozszerzyć na dowolną, skończoną liczbę argumentów.
  • Liczba jest blisko związana z najmniejszą wspólną wielokrotnością otóż
Równość ta nie jest prawdziwa dla większej liczby argumentów. Wzór ten wykorzystuje się często do obliczania najmniejszych wspólnych wielokrotności: najpierw wyznacza się z algorytmu Euklidesa, a następnie dzieli się iloczyn danych liczb przez ich Zachodzi następująca wersja rozdzielności:
  • Zdefiniowanie oraz czyni z liczb naturalnych kratę zupełną rozdzielną z oraz odpowiednio jako supremum i infimum. To rozszerzenie definicji jest zgodne z uogólnieniem na pierścienie przemienne opisanym niżej.
  • W kartezjańskim układzie współrzędnych można interpretować jako liczbę punktów o współrzędnych całkowitych leżących na odcinku łączącym punkty oraz z wyłączeniem końca

Niech litery oraz oznaczają dowolne podzbiory liczb całkowitych. Prawdziwe są zależności:

Uogólnienia

Prawdziwy jest następujący diagram zawierania się klas pierścieni z jedynką:

pierścienie przemiennedziedziny całkowitościdziedziny z jednoznacznością rozkładudziedziny ideałów głównychdziedziny euklidesoweciała

W kontekście uogólnień największego wspólnego dzielnika poglądowo można go podsumować w następujący sposób:

  • pierścień przemienny to zbiór elementów, które można dodawać, odejmować i mnożyć według znanych reguł arytmetyki (nie zawsze istnieje iloraz dwóch elementów); w każdym pierścieniu przemiennym możliwe jest zdefiniowanie podzielności oraz
  • dziedzina całkowitości to pierścień przemienny, w którym brak właściwych dzielników zera sprawia, iż struktury te są naturalnym środowiskiem do badania podzielności, a jest wyznaczony z dokładnością do stowarzyszenia (tzn. z dokładnością do elementu odwracalnego).
  • dziedzina z jednoznacznością rozkładu to dziedzina całkowitości, w której zachodzi uogólnienie podstawowego twierdzenia arytmetyki, co sprawia, że dla dowolnych dwóch elementów istnieje ich przy czym można go wyznaczyć za pomocą rozkładu elementu na elementy nierozkładalne (pierwsze);
  • dziedzina ideałów głównych to dziedzina z jednoznacznością rozkładu, w której dla każdych dwóch elementów i spełniona jest tzw. tożsamość Bézouta, tzn. istnieją takie elementy i że
  • dziedzina euklidesowa to dziedzina ideałów głównych, w której poprawne zdefiniowane jest dzielenie z resztą, a można znaleźć za pomocą uogólnienia algorytmu Euklidesa.

W szczególności dziedzinami euklidesowymi są pierścień liczb całkowitych (którego największy wspólny dzielnik został opisany w zasadniczej części artykułu) oraz pierścienie wielomianów o współczynnikach z ciała, w których największym wspólnym dzielnikiem wielomianów oraz nazywa się wielomian unormowany (o ile jest on różny od wielomianu zerowego; powód wyjaśniono dalej) najwyższego stopnia, który dzieli (bez reszty) oraz

W ciałach pojęcie największego wspólnego dzielnika (jak i największej wspólnej wielokrotności) traci sens: ponieważ każdy niezerowy element jest odwracalny, to największym wspólnym dzielnikiem dwóch niezerowych elementów jest jedynka, zatem są one względnie pierwsze; jeżeli choć jedna z nich jest zerem, to ich największym wspólnym dzielnikiem również jest zero.

Z kolei w pierścieniach nieprzemiennych sytuacja jest bardziej złożona: dla danego elementu można wyróżnić jego dzielniki lewo- i prawostronne. Można więc zdefiniować największy wspólny dzielnik lewo- i prawostronny, przy czym istnienie jednego nie pociąga za sobą istnienia drugiego, czy też ich równości w przypadku istnienia obu.

Pierścienie przemienne

Definicja korzystająca z podzielności (jak również i rozszerzona), podana w sekcji Definicje, przenosi się wprost na pierścienie przemienne. Niech będzie pierścieniem przemiennym oraz Element nazywa się największym wspólnym dzielnikiem elementów jeżeli

  • oraz oraz
  • jeśli oraz to dla dowolnej liczby

Jedyną różnicą jest fakt, iż nie ma gwarancji istnienia największego wspólnego dzielnika oraz tego, że jeśli nawet istnieje, to jest on wyznaczony jednoznacznie (dla danych elementów może być ich kilka; w szczególności nie zakłada się jego „nieujemności”).

Dziedziny całkowitości

W dziedzinie całkowitości największy wspólny dzielnik dwóch elementów również może nie istnieć, lecz jeśli istnieje ich kilka, to muszą być one ze sobą stowarzyszone: jeśli jest dla to jest nim dowolny inny element stowarzyszony z fakt ten zapisuje się symbolicznie Przykładowo w pierścieniu największymi wspólnymi dzielnikami liczb są tzn.

To właśnie stowarzyszenie jest powodem, dla którego największy wspólny dzielnik liczb całkowitych definiowany jest jako liczba nieujemna (w dziedzinie liczb całkowitych liczby przeciwne są ze sobą stowarzyszone, gdyż jedynymi elementami odwracalnymi są jedynka i minus jedynka), co przy tej definicji pozwala stosować znak równości zamiast znaku relacji stowarzyszenia. Podobnie ma się rzecz z wielomianami, gdzie jednoznaczność gwarantuje unormowanie największego wspólnego dzielnika (w pierścieniu wielomianów odwracalne są wyłącznie niezerowe elementy z ciała).

Oto przykład dziedziny całkowitości, w której dwa elementy nie mają

Elementy oraz są dwoma „maksymalnymi wspólnymi dzielnikami” (tzn. żaden wspólny dzielnik będący wielokrotnością nie jest stowarzyszony z ), podobnie ma się rzecz z lecz nie są one stowarzyszone, a więc największy wspólny dzielnik oraz nie istnieje.

Dziedziny z jednoznacznością rozkładu

Niech będzie dziedziną z jednoznacznością rozkładu, zaś oznacza zbiór zawierający wyłącznie elementy pierwsze – lub równoważnie: elementy nierozkładalne – tego pierścienia. Wówczas dowolne dwa elementy można zapisać w postaci skończonych iloczynów

oraz

gdzie oraz pewnymi ciągami liczb całkowitych, przy czym iloczyny w przedstawieniu są wyznaczone jednoznacznie z dokładnością do permutacji czynników, zaś symbol tyldy oznacza relację stowarzyszenia.

Wówczas największy wspólny dzielnik elementów można zdefiniować wzorem

co odpowiada metodzie rozkładu na czynniki proste. Skrótowo można to zapisać:

Najogólniejszą strukturą, w której dowolne dwa elementy mają największy wspólny dzielnik jest dziedzina z największym wspólnym dzielnikiem (ang. greatest common divisor domain) będąca dziedziną z jednoznacznością rozkładu.

Dziedziny ideałów głównych

Opierając się na tożsamości Bézouta w dowolnym pierścieniu przemiennym można rozważać zbiory elementów postaci gdzie przebiegają cały pierścień. Zbiór ten jest ideałem generowanym przez oraz który oznacza się W pierścieniu, w którym wszystkie ideały są główne (tzn. pierścieniu ideałów głównych), ideał ten pokrywałby się ze zbiorem wielokrotności pewnego elementu pierścienia[d]; ten właśnie element nazywa się największym wspólnym dzielnikiem oraz Tożsamość Bézouta charakteryzuje dziedziny ideałów głównych wśród klasy pierścieni noetherowskich.

Ideały

Ideał może być jednak przydatny nawet wtedy, gdy największy wspólny dzielnik i nie istnieje (rzeczywiście, Ernst Kummer wykorzystał ten ideał zamiast podczas swoich badań nad wielkim twierdzeniem Fermata, choć widział go raczej jako zbiór pewnych hipotetycznych, czy też idealnych, elementów pierścienia, skąd właśnie nazwę wziął powyższy termin teorii pierścieni) – można go traktować jako najszersze uogólnienie pojęcia największego wspólnego dzielnika.

W związku z powyższym największy wspólny dzielnik ideałów pierścienia definiuje się jako ideał

zaś ich najmniejszą wspólną wielokrotność jako ideał

Uwagi

  1. Wskazanie największego wspólnego dzielnika nie przedstawia trudności w zbiorze liczb naturalnych, jednak już w zbiorze liczb całkowitych można wyróżnić dwa największe wspólne dzielniki (w sensie ich wartości bezwzględnej – zwyczajowo wybiera się większy z nich, co odpowiada potocznemu znaczeniu wyrazu „największy”); niżej przedstawiona definicja unika korzystania z uporządkowania, czy też unormowania zbioru, wykorzystując jedynie własności podzielności, co umożliwia dość naturalne przeniesienie definicji na ogólniejsze obiekty niewyposażone we wspomniane struktury (zob. Uogólnienia).
  2. Ponieważ każda liczba dzieli zero (jest dzielnikiem zera; wystarczy wyżej przyjąć ), często rozważa się wyłącznie dzielniki liczb różnych od zera i, co za tym idzie, definiuje się największy wspólny dzielnik wyłącznie dla liczb różnych od zera.
  3. Fakt, iż jeśli jest wspólnym dzielnikiem liczb oraz to jest nim również jest powodem, dla którego czasem podaje się definicję wyłącznie dla liczb naturalnych – ma to na celu zapewnienie jednoznaczności wspólnego dzielnika. W podanej niżej definicji największego wspólnego dzielnika jego jednoznaczność zagwarantowana jest założeniem, że musi on być nieujemny. W ogólniejszych strukturach rezygnuje się z tego ograniczenia (zob. Uogólnienia).
  4. Najogólniejszą dziedziną całkowitości, w której zachodzi tożsamość Bézouta, jest dziedzina Bézouta.

Przypisy

  1. największy wspólny dzielnik, [w:] Encyklopedia PWN [online] [dostęp 2021-10-02].
  2. Keith R. Slavin. Q-Binomials and the Greatest Common Divisor. „Integers Electronic Journal of Combinatorial Number Theory”. 8, s. A5, 2008. University of West Georgia, Uniwersytet Karola w Pradze. [dostęp 2008-05-26]. 
  3. Wolfgang Schramm. The Fourier transform of functions of the greatest common divisor. „Integers Electronic Journal of Combinatorial Number Theory”. 8, s. A50, 2008. University of West Georgia, Uniwersytet Karola w Pradze. [dostęp 2008-11-25]. 
  4. Marcelo Polezzi. A Geometrical Method for Finding an Explicit Formula for the Greatest Common Divisor. „Am Math Mon”. 104 (5), s. 445 i 446, 1997. Mathematical Association of America. DOI: 10.2307/2974739. JSTOR: 10.2307/2974739. 
  5. Donald E. Knuth, R. L. Graham, O. Patashnik: Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley, marzec 1994. ISBN 0-201-55802-5.

Media użyte na tej stronie

Least common multiple.svg
Autor: Morn, Licencja: GFDL
Least common multiple