Najveća zajednička mjera

Najveća zajednička mjera (M) ili najveći zajednički djelitelj (D) dvaju ili više cijelih brojeva je najveći broj koji dijeli svaki od tih brojeva. Najveća zajednička mjera brojeva [math]\displaystyle{ x }[/math] i [math]\displaystyle{ y }[/math] obično se zapisuje [math]\displaystyle{ M(x, y), \text{nzd}(x, y) }[/math] ili pak [math]\displaystyle{ D(x, y). }[/math] U stranim tekstovima moguće je naići i na jednostavno [math]\displaystyle{ (x, y). }[/math]

Računanje i primjeri

Ako brojevi imaju zajedničke proste faktore, njihova najveća zajednička mjera je umnožak tih faktora.

Nađimo najveću zajedničku mjeru brojeva 12 i 30:

12 = 2 · 2 · 3

30 = 2 · 3 · 5

Primjećujemo su zajednički faktori oba broja 2 · 3 = 6, stoga vrijedi M(12, 30) = 6.

S druge strane, brojevi 10 i 63:

10 = 2 · 5

63 = 3 · 3 · 7

nemaju zajedničkih prostih faktora, pa je njihova mjera M(10, 63) = 1 (jer 1 dijeli svaki cijeli broj). Ako dva ili više brojeva imaju najveću zajedničku mjeru 1, tada su oni jedni u odnosu na druge relativno prosti.

Euklidov algoritam

Rastav na proste faktore kao metoda nalaženja najveće zajedničke mjere je nepraktičan za velike brojeve. U tu svrhu se za mjeru dva broja češće koristi Euklidov algoritam. Počevši s dijeljenjem većeg početnog broja manjim, lančano dijelimo tako da nakon svakog dijeljenja za sljedećeg djeljenika uzimamo djelitelja prijašnjeg dijeljenja, a za sljedećeg djelitelja ostatak. Taj postupak ponavljamo dok pri nekom dijeljenju ne dobijemo ostatak 0. Djelitelj pri tom dijeljenju (odnosno ostatak pri prethodnom dijeljenju) je onda najveća zajednička mjera tih brojeva. Primjerice, nađimo M(65, 45):

Počinjemo dijeljenjem 65 s 45:	65 = 1 · 45 + 20
Dijelimo djelitelj 45 s ostatkom 20:	45 = 2 · 20 + 5
Dijelimo 20 s novim ostatkom 5:	20 = 4 · 5 + 0

Budući da smo dosegli ostatak 0, mjera je posljednji djelitelj, 5.

Drugi algoritmi

Kod Euklidovog algoritma količnik pri dijeljenju je često malen broj, te je silazak do konačnog ostatka spor. Zbog toga je razvijen Lehmerov algoritam koji preskače mnoge operacije dijeljenja gdje bi količnik bio malen broj. Binarni Euklidov algoritam se za razliku od Euklidovog ne koristi dijeljenjem s ostatkom, nego su mu jedine operacije oduzimanje i dijeljenje s 2 (binarni pomak), zbog čega je znatno brži za računala.

Primjene

Najveća zajednička mjera može se koristiti za skraćivanje razlomaka. Na primjer:

[math]\displaystyle{ M(40, 60) = 20 }[/math]

[math]\displaystyle{ \frac{40}{60} = \frac{2 \cdot 20}{3 \cdot 20} = \frac{2}{3} }[/math]

Korisna je i za računanje najmanjeg zajedničkog višekratnika, jer vrijedi:

[math]\displaystyle{ M(x, y) \cdot V(x, y) = \left|x \cdot y \right| }[/math].

Svojstva

• Svaki broj koji dijeli (koji je djelitelj od) x i y, dijeli i M(x, y). Uz ovo, vrijedi da djelitelja oba x, y ima točno onoliko koliko ima djelitelja broja M(x, b), što se jasno vidi kada rastavimo brojeve na proste faktore, kao u osnovnom stavku aritmetike. (1)
• Bézoutova lema: Ako su a i b oba različiti od nule, M(a, b) može se definirati kao najmanji broj d koji se može zapisati u obliku d = ap + bq, gdje su p i q cijeli brojevi. p i q mogu se izračunati pomoću proširenog Euklidovog algoritma.
• M(x, 0) = |x|, za x različit od nule. Naime, svaki cijeli broj dijeli 0, a |x| je najveći djelitelj od x.
• M(0, 0) je obično nedefinirana, ali se može definirati da bude M(0, 0) = 0. Daljnja svojstva vrijede ako su sve navedene mjere definirane, tj. da uvrštavanjem varijabli ne dobijemo M(0, 0).
• Komutativnost: M(x, y) = M(y, x)
• Asocijativnost: M(x, y, z) = M(x, M(y, z)) = M(M(x, y), z)
• [math]\displaystyle{ M(a_1, a_2, \ldots, a_k) = M(M(a_1, a_2, \ldots, a_{k-1}), a_k) }[/math]
• [math]\displaystyle{ M(x, y) \cdot V(x, y) = \left|x \cdot y\right|. }[/math]

Naime, stavimo [math]\displaystyle{ c = M(x,y) }[/math] te neka je, bez smanjenja općenitosti [math]\displaystyle{ x, y \gt 0. }[/math] Tada je [math]\displaystyle{ x = ca }[/math] za neki [math]\displaystyle{ a }[/math] te [math]\displaystyle{ y = cb }[/math] za neki [math]\displaystyle{ b. }[/math] Uočimo da je [math]\displaystyle{ M(a, b) = 1 }[/math], tj. da su [math]\displaystyle{ a, b }[/math] relativno prosti. Po definiciji, [math]\displaystyle{ V(x,y) }[/math] je djeljiv s [math]\displaystyle{ x=ca }[/math] i [math]\displaystyle{ y=cb }[/math], dakle [math]\displaystyle{ V(x,y) = cab }[/math] (jer su [math]\displaystyle{ a,b }[/math] relativno prosti). Prema tome, [math]\displaystyle{ V(x,y)M(x,y) = cabc = (ca)(cb) = xy. }[/math]

Ovo se svojstvo može pokazati i direktno. Naime, uočimo da ako je [math]\displaystyle{ a = {p_1}^{\alpha_1} \cdot {p_2}^{\alpha_2} \cdot ... \cdot {p_k}^{\alpha_k} }[/math] i [math]\displaystyle{ b = {p_1}^{\beta_1} \cdot {p_2}^{\beta_2} \cdot ... \cdot {p_k}^{\beta_k} }[/math] za proste [math]\displaystyle{ p_i }[/math] te [math]\displaystyle{ \alpha_i, \beta_i \in \{0, 1, 2, ...\} }[/math] onda je [math]\displaystyle{ M(a, b) = p_1^{\text{min}(\alpha_1, \beta_1)} \cdot p_2^{\text{min}(\alpha_2, \beta_2)} \cdot ... \cdot p_k^{\text{min}(\alpha_k, \beta_k)} }[/math] i slično [math]\displaystyle{ V(a, b) = p_1^{\text{max}(\alpha_1, \beta_1)} \cdot p_2^{\text{max}(\alpha_k, \beta_k)} \cdot ... \cdot p_k^{\text{max}(\alpha_k, \beta_2)} }[/math] iz čega je očito da vrijedi [math]\displaystyle{ M(a, b) \cdot V(a, b) = ab }[/math].

• Distributivnost mjere po višekratniku i obratno:

[math]\displaystyle{ M(x, V(y, z)) = V(M(x, y), M(x, z)) }[/math]

[math]\displaystyle{ V(x, M(y, z)) = M(V(x, y), V(x, z)) }[/math]

• Neka dva broja imaju rastav na proste faktore [math]\displaystyle{ x = p_1^{e_1} p_2^{e_2} \ldots p_k^{e_k} }[/math] i [math]\displaystyle{ y = p_1^{f_1} p_2^{f_2} \ldots p_k^{f_k} }[/math] gdje svaki eksponent [math]\displaystyle{ e_i, f_i \geq 0 }[/math]. Tada:

[math]\displaystyle{ M(x, y) = p_1^{min\{e_1, f_1\}} p_2^{min\{e_2, f_2\}} \ldots p_k^{min\{e_k, f_k\}} }[/math]

• U pravokutnom koordinatnom sustavu dužina koja povezuje ishodište i točku (x, y) prolazi kroz M(x, y) točaka s cjelobrojnim koordinatama.

Ovo se svojstvo može pokazati na sljedeći način. Neka imamo dva cijela broja, [math]\displaystyle{ x_1, y_1 }[/math] takva da je [math]\displaystyle{ M(x_1, y_1) = 1 }[/math]. Tada je jednadžba tog pravca [math]\displaystyle{ y = \frac{y_1}{x_1}x }[/math]. Sada je [math]\displaystyle{ yy_1 = xx_1 }[/math]. No, iz ovoga slijedi [math]\displaystyle{ y \vert x_1, x_1 \vert y }[/math] pa mora biti [math]\displaystyle{ y = x_1 }[/math]. Analogno mora biti [math]\displaystyle{ x = y_1 }[/math]. Prema tome, ovu jednadžbu u skupu prirodnih brojeva zadovoljava samo jedan par i to točka [math]\displaystyle{ (x_1, y_1) }[/math]. Sada je jasno da će pravac za neka dva broja [math]\displaystyle{ dx_1, dy_1, d \gt 1 }[/math] imati [math]\displaystyle{ d }[/math] cjelobrojnih točaka, točku [math]\displaystyle{ A_1(x_1, y_1) }[/math] i redom točke nastale generiranjem početne točke [math]\displaystyle{ A_1 }[/math]: [math]\displaystyle{ A_2(2x, 2y), ..., A_d(dx, dy) }[/math] jer će y-vrijednosti prijašnjih točaka [math]\displaystyle{ \{\frac{y_1}{x_1}x : x \in \{1, 2, ..., x_1 - 1\} }[/math] za cijeli x ostati necijeli brojevi, i tako za svaki [math]\displaystyle{ x \lt dx_1 }[/math] koji nije višekratnik od [math]\displaystyle{ x_1 }[/math]. Ovo činimo za bilo koja dva cijela broja [math]\displaystyle{ x_1, y_1 }[/math] takva da je [math]\displaystyle{ (x_1, y_1) = 1 }[/math] čime je tvrdnja dokazana.

• Za [math]\displaystyle{ x, y \geq 0 }[/math] koji nisu oba nule te pozitivni broj n:

[math]\displaystyle{ M(n^x - 1, n^y - 1) = n^{M(x, y)} - 1 }[/math]

• Veza s Eulerovom funkcijom:

[math]\displaystyle{ M(x, y) = \sum_{k|x\text{ i }k|y}{\varphi(k)} }[/math]

Koristimo svojstvo (1). Sada direktnim korištenjem Gaussove leme za Eulerovu funkciju slijedi pravilo.

Komutativni prstenovi

Pandan najvećoj zajedničkoj mjeri može se definirati na bilo kojem komutativnom prstenu, kao što je primjerice prsten polinoma. Za razliku od operacije na cijelim brojevima, rezultat ne mora biti definiran za svaki par elemanata prstena, a moguće je i da isti par elemenata ima više različitih najvećih zajedničkih djelitelja.

Neka je P komutativni prsten, te a, b ∈ P. Tada element d ∈ P zovemo zajedničkim djeliteljem a i b ako dijeli i a, i b; tj. ako postoje elementi x, y ∈ P takvi da d · x = a i d · y = b. Ako je d zajednički djelitelj a i b i ako svaki drugi zajednički djelitelj od a i b dijeli i d, onda je d najveći zajednički djelitelj a i b.

Dva elementa komutativnog prstena mogu imati zajedničke djelitelje, a da istovremeno nemaju najveći zajednički djelitelj. Primjer u prstenu [math]\displaystyle{ \mathbb{Z}\left[\sqrt{-3}\right] }[/math]:

[math]\displaystyle{ \begin{array}{lcl} a & = & 4 & = & 2\cdot 2 & = \left(1+\sqrt{-3}\right)\left(1-\sqrt{-3}\right) \\ b & = & 2 + 2\sqrt{-3} & = & \left(1+\sqrt{-3}\right)\cdot 2 & \\ \end{array} }[/math]

Brojevi 2 ili 1 + √−3 su tzv. maksimalni zajednički djelitelji od a i b, tj. svaki zajednički djelitelj koji je višekratnik od 2 je asociran s 2, i isto vrijedi za 1 + √−3. Međutim, 2 i 1 + √−3 nisu međusobno asocirani, pa nijedan od njih ne možemo zvati najvećim zajedničkim djeliteljem a i b.

Inspirirani Bézoutovom lemom možemo proučiti skup elemenata oblika pa + qb, za svaki mogući p, q ∈ P. Taj skup nazivamo idealom koji generiraju a i b i označavamo (a, b). U prstenu u kojem su svi ideali glavni (prsten glavnih ideala), taj ideal bit će identičan skupu višekratnika nekog elementa d ∈ P, te je d najveći zajednički djelitelj a i b. Ideal (a, b) može biti koristan i kad ne postoji odgovarajući najveći zajednički djelitelj. Njemački matematičar Ernst Kummer koristio je takav ideal umjesto najvećeg zajedničkog djelitelja u svom napadu na Posljednji Fermatov teorem, nazivajući ga skupom višekratnika nekog zamišljenog, "idealnog" elementa d. Otuda dolazi i naziv za ideal.