Najveća zajednička mjera
D Neka su a i b cijeli brojevi koji nisu oba nula. Za prirodan broj d kažemo da je najveća zajednička mjera (ili najveći zajednički djelitelj) brojeva a i b , i pišemo d=NZM(a,b) , ako d ima sljedeća svojstva:
  1. d|a & d|b
  2. Za svaki prirodni c , c|a & c|b => c|d
(Svojstvo 1 kaže da je d zajednički djelitelj od a i b . Svojstvo 2 kaže da je d djeljiv sa svim zajedničkim djeliteljima od a i b , pa je "najveći" u parcijalnom uređaju "|". No budući da na N djeljivost povlači standardni uređaj po veličini, d je stvarno najveći i u uobičajenom smislu.)
S Da bismo opravdali gornju definiciju, koja o NZM(a,b) govori kao o potpuno određenom objektu, trebamo vidjeti da zaista za svaki par (a,b) (osim (0,0) ) postoji takav d , i da je on jedinstven. Kao i obično u takvim dokazima, jedinstvenost je lakše dokazati. Naime, pri tome nam pomaže antisimetričnost relacije "|" na N (zato smo i propisali d@N u definiciji). Ako postoje dva takva, recimo c i d , lako se vidi da c|d , i analogno d|c , pa moraju biti jednaki.
Za egzistenciju, bilo bi dobro efektivnije naći broj koji ima gornja dva svojstva. To izlazi iz sljedećeg:

8Z Neka su a i b cijeli brojevi takvi da !(a=b=0) , i neka je d najmanji prirodni broj oblika ka+lb (najmanja prirodna linearna kombinacija a i b s cjelobrojnim koeficijentima). Dokažite da je d=NZM(a,b) .

Rj Trebamo dokazati da d ima gornja dva svojstva. Svojstvo 2. je lakše -- d je neka linearna kombinacija a i b , pa svaki c koji dijeli a i b , dijeli i d . (Neka je d=k0*a+l0*b . Ako c dijeli a , tada dijeli i k0*a . Ako c dijeli b , dijeli i l0*b . Ako dijeli oba, dijeli i njihov zbroj.)

Još treba dokazati svojstvo 1., odnosno da d zaista dijeli oba broja a i b . Naravno, zbog simetrije zadatka a<->b , dovoljno je dokazati d|a -- tada d|b ide potpuno analogno.
Pa pretpostavimo da d ne dijeli a . Po Teoremu o dijeljenju s ostatkom, postoje brojevi q i r takvi da je a=d*q+r , i 0<=r<d . Po pretpostavci r nije 0 , pa je r prirodan broj strogo manji od d . No sjetimo se, d=k0*a+l0*b . Odnosno, r=a-d*q=a-(k0*a+l0*b)*q=a-k0*q*a-l0*q*b=(1-k0*q)*a+(-l0)*b -- 1-k0*q i -l0 su cijeli brojevi, pa je r također prirodna linearna kombinacija a i b s cjelobrojnim koeficijentima. d je najmanja takva, no to je u kontradikciji s r<d. So, pretpostavka je bila kriva, te vrijedi d|a . Odnosno, d je zaista najveća zajednička mjera od a i b .

Dokaz nije gotov: primijetimo, koristili smo već prije korišteno svojstvo da ako prirodnih brojeva nekog oblika ima, onda postoji i najmanji takav. No ima li ih uopće? Kako znamo da postoji linearna kombinacija a i b koja je prirodan broj? Lako... ako nisu oba nula, bar jedan (BSOMP a ) nije 0 . No tada je |a|=sgn(a)*a+0*b prirodan broj.

9L Dokažite NZM(a,b)=NZM(b,a)=NZM(a,-b)=NZM(a,a+b)=NZM(a,a-b)=NZM(b,a-b) .

Rj Sve ove jednakosti dokazuju se prilično slično; ovdje ću pokazati samo jednu, ostale ostavljam kao DZ.

Označimo c:=NZM(a,b) i d:=NZM(b,a-b) . Dokažimo c=d .
Prvo, iz c|a i c|b slijedi c|a-b . Iz c|b i c|a-b slijedi ( c je zajednički djelitelj brojevia b i a-b , a d je najveći takav) c|d .
Prilično analogno, iz d|b i d|a-b slijedi i da dijeli njihov zbroj, d|b+(a-b)=a . Sad iz d|a i d|b slijedi d|c .
Iz c|d i d|c ( c i d su prirodni) slijedi c=d .

S Gornja propozicija nam pokazuje da možemo proizvoljno pribrajati jedan broj drugome, oduzimati, mijenjati predznake i redoslijed argumenata -- NZM će ostati isti. Iz toga se lako vide sljedeće stvari:

BSOMP da su a i b nenegativni. Naime, promjena predznaka je ok, pa vrijedi NZM(a,b)=NZM(|a|,|b|) .
Nadalje, BSOMP da je a>=b . Naravno, ako nije, zamijenimo ih.
Sad imamo a>=b>=0 , s tim da ne mogu vrijediti obje jednakosti (nisu oba nula, preciznije a sigurno nije nula). Što ako vrijedi jedna od njih?

Ako je b=0 , lako je vidjeti da je upravo a=NZM(a,0) . Naime a|a & a|0 , te bilo koji drugi broj koji dijeli a i 0 , naravno dijeli a .
Ako je a=b , možemo oduzeti jednog od drugog: NZM(a,a)=NZM(a,a-a)=NZM(a,0) , a to je jednako a kako smo vidjeli gore.

Još je samo preostao slučaj a>b>0 . U tom slučaju vrijedi NZM(a,b)=NZM(b,a-b)=NZM(b,(a-b)-b)=NZM(b,a-2b)=NZM(b,a-3b)= ... , i tako dovoljno mnogo puta, dok ne oduzmemo dovoljno b-ova da a-q*b postane manji od b . Tada će on upravo biti a mod b , i vidimo da vrijedi

NZM(a,b)=NZM(b,a mod b) ,
gdje je također b>a mod b>=0 , pa možemo nastaviti na isti način: ako je a mod b=0 , NZM je jednak b , a ako nije, ponovimo postupak i dobijemo NZM(b,a mod b)=NZM(a mod b,b mod(a mod b)) , i tako dalje.

Još samo treba vidjeti da to staje nakon konačno mnogo koraka: pretpostavimo da nije tako, tj. da ostatak pri dijeljenju nikad nije 0 . Budući da je a mod b uvijek strogo manje od b , dobivamo na drugom mjestu u NZM strogo padajući niz prirodnih brojeva. Takav (beskonačni) niz nije moguć (još jedno bitno svojstvo skupa N -- primijetimo da npr. u Z i Q+ postoje strogo padajući beskonačni nizovi), pa je to kontradikcija -- postupak mora stati nakon konačno mnogo koraka. Drugim riječima, dobili smo algoritam za računanje NZM , poznat pod imenom Euklidov algoritam:

Al Neka su dani cijeli brojevi a i b , koji nisu oba 0 . Treba odrediti NZM(a,b) .
  1. Ako je a<b , NZM(a,b)=NZM(b,a) .
  2. Ako je b<0 , NZM(a,b)=NZM(a,-b) .
  3. Ako je b=0 , NZM(a,b)=a .
  4. Ako je a>=b>0 , NZM(a,b)=NZM(b,a mod b) .

P Izračunajmo gornjim algoritmom NZM brojeva 3094 i 19950 . (U uglatim zagradama su slučajevi 1..4 .) 

NZM(3094,19950)=[1]
NZM(19950,3094)=[4]	|	19950 : 3094 = 6 i ost. 1386
NZM(3094,1386)=[4]	|	 3094 : 1386 = 2 i ost.  322
NZM(1386,322)=[4]	|	 1386 :  322 = 4 i ost.   98
NZM(322,98)=[4]		|	  322 :   98 = 3 i ost.   28
NZM(98,28)=[4]		|	   98 :   28 = 3 i ost.   14 <--
NZM(28,14)=[4]		|	   28 :   14 = 2 i ost.    0
NZM(14,0)=[3] 14
Vidimo da zapravo sve možemo rekonstruirati iz ovih dijeljenjā u desnom dijelu -- i obično se onda samo to piše kao Euklidov algoritam. Zadnji stupac, ostaci pri dijeljenju, strogo pada (jer u svakom koraku dijelimo prethodnim ostatkom) prema nuli, i onaj pretposljednji ostatak (prije nule) upravo je tražena NZM.
S To je Euklidov algoritam, najefikasniji način za općenito traženje NZM. (U osnovnoj školi se obično radi algoritam koji se oslanja na rastavljanje oba broja na proste faktore, i množenje zajedničkih faktorā. To je strahovito loš algoritam -- dok vrijeme izvršavanja Euklidovog algoritma raste u najgorem slučaju kvadratno s brojem znamenaka danih brojeva, trenutno čovječanstvo ne zna za općenit algoritam rastavljanja na proste faktore koji nije sporiji od lagano subeksponencijalnog ecbrt(brojznamenaka). Konkretno, dok Euklidov algoritam s tipičnim 200znamenkastim brojevima na danas uobičajenom PCu troši manje od tisućinke sekunde, rastav tipičnih 200znamenkastih brojeva na proste faktore trenutno je izvan ljudskih mogućnostī. Zapravo, među najbržim algoritmima današnjice za faktorizaciju broja n upravo su algoritmi koji (Euklidovim algoritmom) traže NZM broja n s brojem koji je dobiven množenjem ogromne hrpe prostih brojeva.)

No osim traženja NZM, na njemu je moguće izgraditi i neke druge algoritme. Jedan od često korištenih je tzv. prošireni Euklidov algoritam, koji služi za traženje onih k0 i l0 -- cjelobrojnih koeficijenata pomoču kojih se NZM(a,b) može prikazati kao linearna kombinacija brojeva a i b .
Da vidimo kako se to radi, primijetimo da onaj prvi ostatak, r1:=a mod b , sigurno možemo prikazati kao linearnu kombinaciju a i b : to je jednostavno a-q*b=1*a+(-q)*b , gdje je q:=a div b . Na isti način možemo prikazati sljedeći ostatak, r2:=b mod r1 , kao linearnu kombinaciju b i r2 , _a time i_ kao linearnu kombinaciju a i b (uvrstimo r2 ). Sada možemo prikazati i r3 (pomoću r1 i r2 , dakle i pomoću a i b ), i tako dalje, sve do pretposljednjeg ostatka koji je NZM. No zapravo je lakše ići unatrag, od NZM prema sve većim ostacima, sve do početnih argumenata. Pogledajmo:

P Nastavljajući gornji primjer, 

14=NZM(19950,3094)=98mod28  =    98         -3*28     =1*98+(-3)*28=
=1*98+(-3)*(322-3*98)       =-3*322+(1-3*(-3))*98     =-3*322+10*98=
=-3*322+10*(1386-4*322)     =10*1386+(-3-4*10)*322    =10*1386+(-43)*322=
=10*1386+(-43)*(3094-2*1386)=-43*3094+(10-2*(-43))*1386=-43*3094+96*1386=
=-43*3094+96*(19950-6*3094)=96*19950+(-43-6*96)*3094=96*19950+(-619)*3094
, dobivamo da su koeficijenti redom 96 i -619 uz 19950 i 3094 . (Naravno, zbog velike mogućnosti pogreške u računanju ovakvog tipa, dobro je provjeriti da je 96*19950+(-619)*3094 zaista jednako 14 .) Primijetimo da, pošto je 14 relativno malen u odnosu na 19950 i 3094 , želimo da 96*19950 i 619*3094 budu "približno jednaki", dakle da uz manji broj (3094) ide koeficijent koji je veći po apsolutnoj vrijednosti (-619), i obrnuto. To je informacija koja može biti korisna kasnije. Također primijetimo da koeficijenti (pogledajmo zadnji stupac jednakosti) čine "domino" lanac uređenih parova (1,-3)->(-3,10)->(10,-43)->(-43,96)->(96,-619) , u kojem se novi brojevi dobivaju od prethodna dva, i odgovarajućih kvocijenata u Euklidovom algoritmu. Konkretno, -3=0-3*1 ; 10=1-3*(-3) ; -43=-3-4*10 ; 96=10-2*(-43) ; -619=-43-6*96 , gdje su podvučeni upotrijebljeni kvocijenti. Vidimo da se koriste obrnutim redom, da nam onaj zadnji (čiji je ostatak 0 , u našem slučaju 2=28:14 ) uopće ne treba, te da su dva posljednja dobivena broja upravo koeficijenti koji nam trebaju. Također vidimo da brojevi alterniraju u predznacima, a rastu po apsolutnoj vrijednosti. Na taj način, posljednji dobiveni broj je najveći po apsolutnoj vrijednosti, dakle on je onaj koji množi manji argument NZMa (u ovom slučaju 3094 ).
O Gornji računi se mogu preglednije zapisati u obliku tablice 
	2	3	3	4	2	6     
0	1	-3	10	-43	96	-619 .