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.[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 primjeriUredi

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 algoritamUredi

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 algoritmiUredi

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]

PrimjeneUredi

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:

 .

SvojstvaUredi

  • 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 direktno. 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 za Eulerovu funkciju slijedi pravilo.

Komutativni prstenoviUredi

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, 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 napadu na Posljednji Fermatov teorem, nazivajući ga skupom višekratnika nekog zamišljenog, "idealnog" elementa d. Otuda dolazi i naziv za ideal.

IzvoriUredi

  1. 1,0 1,1 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. 12. 2020. (engl.)
  4. Binary Euclid's Algorithm. Alexander Bogomolny, Cut The Knot. Pristupljeno 26. 12. 2020. (engl.)