Prijeđi na sadržaj

Najveća zajednička mjera

Izvor: Wikipedija

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.[1] Najveća zajednička mjera brojeva i obično se zapisuje ili pak U stranim tekstovima moguće je naići i na jednostavno

Računanje i primjeri

[uredi | uredi kôd]

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

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

12 = 2 · 2 · 3
30 = 2 · 3 · 5.

Primjećujemo da su zajednički djelitelji 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

[uredi | uredi kôd]

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.[1] 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.[2] 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

[uredi | uredi kôd]

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.[3] 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.[4]

Primjene

[uredi | uredi kôd]

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

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

.

Svojstva

[uredi | uredi kôd]
  • 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)

Naime, stavimo te neka je, bez smanjenja općenitosti Tada je za neki te za neki Uočimo da je , tj. da su relativno prosti. Po definiciji, je djeljiv s i , dakle (jer su relativno prosti). Prema tome,

Ovo se svojstvo može pokazati i izravno. Naime, uočimo da ako je i za proste te onda je i slično iz čega je očito da vrijedi .

  • Distributivnost mjere po višekratniku i obratno:
  • Neka dva broja imaju rastav na proste faktore i gdje svaki eksponent . Tada:

Ovo se svojstvo može pokazati na sljedeći način. Neka imamo dva cijela broja, takva da je . Tada je jednadžba tog pravca . Sada je . No, iz ovoga slijedi pa mora biti . Analogno mora biti . Prema tome, ovu jednadžbu u skupu prirodnih brojeva zadovoljava samo jedan par i to točka . Sada je jasno da će pravac za neka dva broja imati cjelobrojnih točaka, točku i redom točke nastale generiranjem početne točke : jer će y-vrijednosti prijašnjih točaka za cijeli x ostati necijeli brojevi, i tako za svaki koji nije višekratnik od . Ovo činimo za bilo koja dva cijela broja takva da je čime je tvrdnja dokazana.

  • Za koji nisu oba nule te pozitivni broj n:

Koristimo svojstvo (1). Sada direktnim korištenjem Gaussove leme o Eulerovoj funkciji slijedi pravilo.

Komutativni prstenovi

[uredi | uredi kôd]

Analogon 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, bP. Tada element dP zovemo zajedničkim djeliteljem a i b ako dijeli i a, i b; tj. ako postoje elementi x, yP 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 :

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, qP. 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 dP, 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 pokušaju rješavanja Posljednjeg Fermatovog poučka, nazivajući ga skupom višekratnika nekog zamišljenog, "idealnog" elementa d. Otuda dolazi i naziv za ideal.

Izvori

[uredi | uredi kôd]
  1. a b najveća zajednička mjera. Hrvatska enciklopedija, mrežno izdanje. Leksikografski zavod Miroslav Krleža, 2020. Pristupljeno 26. 12. 2020.
  2. Euklidov algoritam. Hrvatska enciklopedija, mrežno izdanje. Leksikografski zavod Miroslav Krleža, 2020. Pristupljeno 26. 12. 2020.
  3. Lehmer's Algorithm. Kapil Hari Paranjape, imsc.res.in. Pristupljeno 26. prosinca 2020. (engl.)
  4. Binary Euclid's Algorithm. Alexander Bogomolny, Cut The Knot. Pristupljeno 26. prosinca 2020. (engl.)