Największy wspólny dzielnik
przykład funkcji wielu zmiennych całkowitych / Z Wikipedii, wolnej encyclopedia
Drogi AI, mówmy krótko, odpowiadając po prostu na te kluczowe pytania:
Czy możesz wymienić najważniejsze fakty i statystyki dotyczące Największy wspólny dzielnik?
Podsumuj ten artykuł dla 10-latka
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
- Zobacz też: dzielnik.
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[uwaga 1].
Otóż liczba jest dzielnikiem liczby jeśli istnieje taka liczba dla której zachodzi fakt ten zapisuje się [uwaga 2]. Liczbę nazywa się wspólnym dzielnikiem liczb oraz jeśli dzieli ona obie z nich[uwaga 3].
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
- 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.
Poprzez rozkład na czynniki pierwsze
- Osobny artykuł: 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
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
- Osobny artykuł: algorytm 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].