Szukaj

narzędzia

W innych językach

Największy wspólny dzielnik

Spis treści

[edytuj] Definicja dla liczb naturalnych (i całkowitych)

Największym wspólnym dzielnikiem jednej lub więcej liczb naturalnych dodatnich $a_1, a_2, \dots, a_n$ nazywamy największą liczbę naturalną, która jest jednocześnie dzielnikiem każdej z liczb $a_1, a_2, \dots, a_n$ .

Koncepcyjnie lepiej mówić o największym wspólnym dzielniku w sensie praporządku podzielności: a | b. Otrzymuje się dla liczb naturalnych (gdy wykluczyć 0) równoważną definicję, która działa także w przypadku ogólnych monoidów przemiennych, a więc także dla pierścieni przemiennych (to znaczy dla monoidów multiplikatywnych tych pierścieni).
Podobną definicję do powyższej, ale istotnie ogólniejszą, można podać dla liczb całkowitych (dla dowolnych zbiorów, w tym dla pustego oraz dla nieskończonych):

Definicja Największym wspólnym dzielnikiem dowolnego zbioru A liczb całkowitych nazywamy nieujemną liczbę całkowitą a, taką że:

a | x dla każdego x ∈ A;

jeżeli całkowite b dzieli każde x ∈ A, to b | a.

Zatem największym wspólnym dzielnikiem zbioru pustego A := Ø jest 0.

Tego typu przypadki specjalne, jakby zdegenerowane, są ważne dla łatwości i elegancji dowodów, gdy w środku dowodu nie wiadomo czy pojawiający się zbiór A jest pusty, czy niepusty; dzięki ogólnej definicji, zawierającej przypadki specjalne, unika się uciążliwego rozbijania dowodów na przypadki: (i) A = Ø, (ii) A ≠ Ø.

Największy wspólny dzielnik oznacza się często symbolem $\operatorname{NWD}(a_1,\dots,a_n)$ , a w literaturze angielskiej $\operatorname{gcd}$ lub $\operatorname{GCD}$ (z ang. greatest common divisor).

[edytuj] Właściwości

Zmiana kolejności argumentów NWD nie zmienia jego wartości.
Zachodzi:

$1\le \operatorname{NWD}(a_1,\dots,a_n)\le \min(a_1,\dots,a_n)$

Zachodzi również zależność:

$\operatorname{NWD}(a_1,\dots,a_n, b_1,\dots,b_m)=\operatorname{NWD}\left(\operatorname{NWD}(a_1,\dots,a_n),\operatorname{NWD}(b_1,\dots,b_m)\right)$

Dla dwóch liczb zachodzi też zależność:

$\operatorname{NWD}(a,b)=\frac{ab}{\operatorname{NWW}(a,b)}$

gdzie NWW to najmniejsza wspólna wielokrotność. Dla więcej niż dwóch liczb zależność taka nie jest prawdziwa.

Jeśli $\operatorname{NWD}(a_1,\dots,a_n)=1,$ to liczby $a_1,\dots,a_n$ nazywamy względnie pierwszymi.

[edytuj] Prosty (szkolny) sposób obliczania

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.

42|2
21|7
 3|3
 1|

56|2
28|2
14|2
 7|7
 1|

NWD(42,56) = 1·(2)·(7) = 14
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ł jeden raz w pierwszym i drugim rozkładzie, więc w iloczynie występuje też raz.

NWD(192,348) = 1·(2·2)·(3) = 12

[edytuj] Ogólny sposób obliczania

Jeśli dokonamy rozkładu liczb na czynniki pierwsze:

$a_1=2^{w_{1,2}}\cdot 3^{w_{1,3}}\cdot \dots \cdot p_k^{w_{1,p_k}}$

$a_2=2^{w_{2,2}}\cdot 3^{w_{2,3}}\cdot \dots \cdot p_k^{w_{3,p_k}}$

$a_3=2^{w_{3,2}}\cdot 3^{w_{3,3}}\cdot \dots \cdot p_k^{w_{5,p_k}}$

$\dots$

$a_n=2^{w_{n,2}}\cdot 3^{w_{n,3}}\cdot \dots \cdot p_k^{w_{n,p_k}}$

to wówczas

$\operatorname{NWD}(a_1,a_2,\dots,a_n)=2^{\min(w_{1,2};w_{2,2};\dots;w_{n,2})}\ \cdot\ 3^{\min(w_{1,3};w_{2,3};\dots;w_{n,3})}\ \cdot\ \dots \cdot p_k^{\min(w_{1,p_k};w_{2,p_k};\dots;w_{n,p_k})}$

Efektywnym algorytmem znajdowania największego wspólnego dzielnika dwóch liczb jest starożytny algorytm Euklidesa, pochodzący z jego słynnych Elementów.

[edytuj] Przykłady

Obliczymy NWD liczb 140,60 i 50. Rozkład na czynniki pierwsze:

$\begin{matrix} 140 & =2\cdot 2\cdot 5\cdot 7= & 2^2\cdot 3^0\cdot 5^1\cdot 7^1 \\ 60 & =2\cdot 2\cdot 3\cdot 5= & 2^2\cdot 3^1\cdot 5^1\cdot 7^0 \\ 50 & =2\cdot 5\cdot 5= & 2^1\cdot 3^0\cdot 5^2\cdot 7^0 \end{matrix}$

Stąd

$\operatorname{NWD}(140,60,50)=2^1\cdot 3^0\cdot 5^1\cdot 7^0=10$

Przykłady wyników:

$\operatorname{NWD}(2,8)=2$

$\operatorname{NWD}(115,115)=115$

$\operatorname{NWD}(5,6)=1$

$\operatorname{NWD}(1,1)=1$

$\operatorname{NWD}(6,15)=3$

$\operatorname{NWD}(42,56)=14$

Przykład obliczania NWD za pomocą algorytmu Euklidesa znajduje się w artykule algorytm Euklidesa.

[edytuj] Uogólnienie na pierścień wielomianów

W pierścieniu wielomianów $K [X]$ , nad ciałem $K$ , przez największy wspólny dzielnik $\operatorname{NWD}(f(X),g(X))$ , wielomianów f, g, z których przynajmniej jeden nie jest 0, rozumie się wielomian unormowany najwyższego stopnia, który dzieli $\;f(X)$ oraz $\;g(X)$ . Gdy f = g = 0, to ich największy wspólny podzielnik jest 0.

Wielomiany nazywamy względnie pierwszymi, gdy

$\operatorname{NWD}(f(X),g(X))=1$

Dla dowolnych $f(X), g(X)\in K[X]-\{0\}$ istnieją dwa względnie pierwsze wielomiany $u(X), v(X)\in K[X]$ , dla których

$u(X)\cdot f(X)+v(X)\cdot g(X)=\operatorname{NWD}(f(X),g(X))$

Dla wielomianów (jednej zmiennej, jak wyżej) działa analog algorytmu Euklidesa, pozwalający efektywnie obliczać ich największy wspólny dzielnik. Dzięki temu pierścień liczb całkowitych i pierścień wielomianów jednej zmiennej, nad ustalonym ciałem, mają szereg wspólnych podstawowych własności, które można dowodzić pod wspólnym dachem pierścieni euklidesowych.

[edytuj] Uogólnienie na pierścienie całkowite

Ogólnie, jeśli $A$ jest pierścieniem całkowitym, to mówimy, że element $d\in A$ jest największym wspólnym dzielnikiem elementów $a,b\in A$ , gdy

$d | a$ oraz $d | b$
$c|a, c|b\Rightarrow c|d$ dla dowolnego $c\in A$ .

Elementy $a,b\in A$ nazywamy względnie pierwszymi jeśli ich największym wspólnym dzielnikiem jest $1$ .

[edytuj] Uwagi

Nie zawsze istnieje taki element. Jeśli istnieje, to fakt ten zapisujemy $d\sim \operatorname{NWD}(a,b)$ , co rozumiemy, że największy wspólny dzielnik jest wyznaczony z dokładnością do stowarzyszenia - tj. każdy element stowarzyszony z największym wspólnym dzielnikiem jest największym wspólnym dzielnikiem. Dwa elementy pierścienia całkowitego mogą mieć więcej niż jeden największy wspólny dzielnik. Np. w pierścieniu $\mathbb{Z}[\sqrt{2}]$ elementy $\sqrt{2}, -\sqrt{2}$ są największymi wspólnymi dzielnikami elementów $\sqrt{2}, 5\sqrt{2}$ , ale są istotnie różne.

Jeśli $A=\mathbb{Z}$ , to zapis $d=\operatorname{NWD}(a,b)$ jest równoważny z koniunkcją:

$d\sim \operatorname{NWD}(a,b)$ oraz $d\in\mathbb{N}\cup\{0\}$ .

Podobnie, jeśli $K$ jest ciałem i $A = K [X]$ , to zapis $h=\operatorname{NWD}(f,g)$ jest równoważny z koniunkcją:

$h\sim \operatorname{NWD}(f,g)$ oraz

h

jest wielomianem unormowanym lub

h = 0

[edytuj] Pierścienie z jednoznacznym rozkładem

Niech, w pierścieniu przemiennym z 1, P będzie zbiorem, mającym po jednym reprezentancie z każdej klasy stowarzyszonych elementów pierwszych. Pierścień jest pierścieniem jedoznacznego rozkładu, gdy każdy element a ma dokładnie jeden rozkład na skończony iloczyn elementów pierwszych:

a = u · Π _{p ∈ P} p ^α(p)

gdzie wszystkie nieujemne liczby całkowite α(p) = 0, poza skończonym podzbiorem liczb pierwszych p; oraz u jest jedną z jedności pierścienia.

Niech podobnie:

b = v · Π _{p ∈ P} p ^β(p)

dla innego elementu b. Wtedy:

NWD(a, b) = Π _{p ∈ P} p^{min(α(p), β(p))}

W skrótowej notacji:

NWD(u·P^α, v·P^β) = P ^min(α,β)

[edytuj] Pierścienie Euklidesa

Podstawowy dla teorii liczb jest twierdzenie Euklidesa, które przedstawia największy wspólny dzielnik liczb całkowitych $a_1,\ldots,a_n$ jako kombinację liniową (por. liniowe równanie diofantyczne):

$\operatorname{NWD}(a_1,\ldots,a_n) = k_1\cdot a_1 + \dots + k_n \cdot a_n$ dla pewnych $k_1,\ldots, k_n\in\mathbb{Z}$

Własność ta, w ramach (przemiennych) pierścieni noetherowskich charakteryzuje klasę pierścieni ideałów głównych. Gdy dopuścimy NWD dla zbiorów nieskończonych (co koniecznie należy czynić), to sytuacja się upraszcza i elegancko własność ta po prostu charakteryzuje przemienne pierścienie ideałów głównych. Należy wtedy twierdzenie Euklidesa formułować następująco:

w pierścieniu przemiennym ideałów głównych, dla dowolnego niepustego zbioru A istnieją jego elementy $a_1,\ldots,a_n$ oraz elementy elementy pierścienia $b_1,\ldots,b_n$ takie, że

$\operatorname{NWD}(a_1,\ldots,a_n) = b_1\cdot a_1 + \dots + b_n \cdot a_n$

I na odwrót, każdy pierścień, w którym zachodzi twierdzenie Euklidesa (lub raczej powyższa własność) jest peirścieniem ideałów głównych.

W szczególnościi twierdzenie Euklidesa jest prawdziwe dla pierścieni w których działa analog algorytmu Euklidesa. Nazywamy takie pierścienie euklidesowymi. Stanowią więc one podklasę pierścieni ideałów głównych. Każdy pierścień ideałów głównych jest pierścieniem z jednoznacznym rozkładem i pierścieniem noetherowskim.