Najve~ta zajedni~cka mjera
D Neka su a i b cijeli brojevi koji nisu oba nula. Za prirodan broj d ka~zemo da je najve~ta zajedni~cka mjera (ili najve~ti zajedni~cki djelitelj) brojeva a i b , i pi~semo d=NZM(a,b) , ako d ima sljede~ta svojstva:
  1. d|a & d|b
  2. Za svaki prirodni c , c|a & c|b => c|d
(Svojstvo 1 ka~ze da je d zajedni~cki djelitelj od a i b . Svojstvo 2 ka~ze da je d djeljiv sa svim zajedni~ckim djeliteljima od a i b , pa je "najve~ti" u parcijalnom ure~daju "|". No budu~ti da na N djeljivost povla~ci standardni ure~daj po veli~cini, d je stvarno najve~ti i u uobi~cajenom smislu.)
S Da bismo opravdali gornju definiciju, koja o NZM(a,b) govori kao o potpuno odre~denom objektu, trebamo vidjeti da zaista za svaki par (a,b) (osim (0,0) ) postoji takav d , i da je on jedinstven. Kao i obi~cno u takvim dokazima, jedinstvenost je lak~se dokazati. Naime, pri tome nam poma~ze antisimetri~cnost 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~ti broj koji ima gornja dva svojstva. To izlazi iz sljede~teg:

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~zite da je d=NZM(a,b) .

Rj Trebamo dokazati da d ima gornja dva svojstva. Svojstvo 2. je lak~se -- 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~s 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~der 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~ta zajedni~cka mjera od a i b .

Dokaz nije gotov: primijetimo, koristili smo ve~t prije kori~steno svojstvo da ako prirodnih brojeva nekog oblika ima, onda postoji i najmanji takav. No ima li ih uop~te? 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~zite 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~cno sli~cno; ovdje ~tu pokazati samo jednu, ostale ostavljam kao DZ.

Ozna~cimo c:=NZM(a,b) i d:=NZM(b,a-b) . Doka~zimo c=d .
Prvo, iz c|a i c|b slijedi c|a-b . Iz c|b i c|a-b slijedi ( c je zajedni~cki djelitelj brojevia b i a-b , a d je najve~ti takav) c|d .
Prili~cno 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~zemo proizvoljno pribrajati jedan broj drugome, oduzimati, mijenjati predznake i redoslijed argumenata -- NZM ~te ostati isti. Iz toga se lako vide sljede~te 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). ~Sto 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~zemo oduzeti jednog od drugog: NZM(a,a)=NZM(a,a-a)=NZM(a,0) , a to je jednako a kako smo vidjeli gore.

Jo~s je samo preostao slu~caj a>b>0 . U tom slu~caju 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 ~te on upravo biti a mod b , i vidimo da vrijedi

NZM(a,b)=NZM(b,a mod b) ,
gdje je tako~der b>a mod b>=0 , pa mo~zemo nastaviti na isti na~cin: 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~s samo treba vidjeti da to staje nakon kona~cno mnogo koraka: pretpostavimo da nije tako, tj. da ostatak pri dijeljenju nikad nije 0 . Budu~ti da je a mod b uvijek strogo manje od b , dobivamo na drugom mjestu u NZM strogo padaju~ti niz prirodnih brojeva. Takav (beskona~cni) niz nije mogu~t (jo~s jedno bitno svojstvo skupa N -- primijetimo da npr. u Z i Q+ postoje strogo padaju~ti beskona~cni nizovi), pa je to kontradikcija -- postupak mora stati nakon kona~cno mnogo koraka. Drugim rije~cima, dobili smo algoritam za ra~cunanje 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~cunajmo gornjim algoritmom NZM brojeva 3094 i 19950 . (U uglatim zagradama su slu~cajevi 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~zemo rekonstruirati iz ovih dijeljenj~a u desnom dijelu -- i obi~cno se onda samo to pi~se 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~zena NZM.
S To je Euklidov algoritam, najefikasniji na~cin za op~tenito tra~zenje NZM. (U osnovnoj ~skoli se obi~cno radi algoritam koji se oslanja na rastavljanje oba broja na proste faktore, i mno~zenje zajedni~ckih faktor~a. To je strahovito lo~s algoritam -- dok vrijeme izvr~savanja Euklidovog algoritma raste u najgorem slu~caju kvadratno s brojem znamenaka danih brojeva, trenutno ~covje~canstvo ne zna za op~tenit algoritam rastavljanja na proste faktore koji nije sporiji od lagano subeksponencijalnog ecbrt(brojznamenaka). Konkretno, dok Euklidov algoritam s tipi~cnim 200znamenkastim brojevima na danas uobi~cajenom PCu tro~si manje od tisu~tinke sekunde, rastav tipi~cnih 200znamenkastih brojeva na proste faktore trenutno je izvan ljudskih mogu~tnost~i. Zapravo, me~du najbr~zim algoritmima dana~snjice za faktorizaciju broja n upravo su algoritmi koji (Euklidovim algoritmom) tra~ze NZM broja n s brojem koji je dobiven mno~zenjem ogromne hrpe prostih brojeva.)

No osim tra~zenja NZM, na njemu je mogu~te izgraditi i neke druge algoritme. Jedan od ~cesto kori~stenih je tzv. pro~sireni Euklidov algoritam, koji slu~zi za tra~zenje onih k0 i l0 -- cjelobrojnih koeficijenata pomo~cu kojih se NZM(a,b) mo~ze 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~zemo 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~cin mo~zemo prikazati sljede~ti ostatak, r2:=b mod r1 , kao linearnu kombinaciju b i r2 , _a time i_ kao linearnu kombinaciju a i b (uvrstimo r2 ). Sada mo~zemo prikazati i r3 (pomo~tu r1 i r2 , dakle i pomo~tu a i b ), i tako dalje, sve do pretposljednjeg ostatka koji je NZM. No zapravo je lak~se i~ti unatrag, od NZM prema sve ve~tim ostacima, sve do po~cetnih argumenata. Pogledajmo:

P Nastavljaju~ti 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~tnosti pogre~ske u ra~cunanju ovakvog tipa, dobro je provjeriti da je 96*19950+(-619)*3094 zaista jednako 14 .) Primijetimo da, po~sto je 14 relativno malen u odnosu na 19950 i 3094 , ~zelimo da 96*19950 i 619*3094 budu "pribli~zno jednaki", dakle da uz manji broj (3094) ide koeficijent koji je ve~ti po apsolutnoj vrijednosti (-619), i obrnuto. To je informacija koja mo~ze biti korisna kasnije. Tako~der primijetimo da koeficijenti (pogledajmo zadnji stupac jednakosti) ~cine "domino" lanac ure~denih parova (1,-3)->(-3,10)->(10,-43)->(-43,96)->(96,-619) , u kojem se novi brojevi dobivaju od prethodna dva, i odgovaraju~tih 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~ceni upotrijebljeni kvocijenti. Vidimo da se koriste obrnutim redom, da nam onaj zadnji (~ciji je ostatak 0 , u na~sem slu~caju 2=28:14 ) uop~te ne treba, te da su dva posljednja dobivena broja upravo koeficijenti koji nam trebaju. Tako~der vidimo da brojevi alterniraju u predznacima, a rastu po apsolutnoj vrijednosti. Na taj na~cin, posljednji dobiveni broj je najve~ti po apsolutnoj vrijednosti, dakle on je onaj koji mno~zi manji argument NZMa (u ovom slu~caju 3094 ).
O Gornji ra~cuni se mogu preglednije zapisati u obliku tablice 
	2	3	3	4	2	6     
0	1	-3	10	-43	96	-619 .