Dokaz Evklidovega algoritma in rekurzivna funkcija

Če nas kdo vpraša, kakšen je največji skupni delitelj a in b, lahko razmišljamo takole. Najprej predpostavimo, da je a večji od b. S primerom, ko ni, se bomo ukvarjali kasneje.

Kdor nima veselja do matematike, naj brez škode za znanje račualništva (a z morebitno škodo za znanje matematike) preskoči naslednja dva odstavka in se nam spet pridruži za njima.

Zdaj ugotovimo, da imata števili a-b in b enak največji skupni delitelj kot a in b. To hitro uvidimo: recimo, da je največji skupni delitelj a in b neko (še neznano) število d. Tedaj lahko napišemo a = a₁d in b = b₁d. Potem je a - b = a₁d - a₁d = (a₁ - a₁)d. Očitno je a - b še vedno deljivo z d, torej je d gotovo skupni delitelj a - b in b, strah nas je lahko le, da ni največji. Vendar je takšen strah neupravičen: če imata a - b in b kakšen skupen faktor, se, na podoben način kot zgoraj, hitro prepričamo, da mora ta faktor nastopati tudi v a-ju, potemtakem pa d sploh ni bil največji skupni delitelj a in b, temveč je obstajal še večji.)

Ne glede na to, ali ste dokaz preskočili ali ne: vemo, da bi lahko namesto največjega skupnega delitelja a in b računali tudi največji skupni delitelj a - b in b, saj bi dobili isto. Po isti logiki bi lahko računali tudi največji skupni delitelj a - 2b in b, ali pa a - 15b in b - če je le a dovolj velik. Se pravi - b smemo poljubnokrat odšteti od a; odšteti ga smemo tolikokrat, da od a ostane samo še ostanek po deljenju a z b.

Vemo torej: največji skupni delitelj a in b je enak kot največji skupni delitelj a % b in b.

Tako imamo strategijo za računanje največjega skupnega delitelja. Če je a slučajno deljiv z b, je največji skupni delitelj kar b. Sicer pa se bom delal neumnega: rekel bom, da ne vem, kakšen je največji skupni delitelj a in b, zato bom raje računal največji skupni delitelj b in a % b (vrstni red sem spremenil zato, ker si želim, da bi bila prva številka večja).

Kaj pa, če je a manjši od b. Nič hudega. Na predavanjih smo dodali še nek if in tako naprej - a ni potreben. Stvari se uredijo same od sebe. Če je a manjši od b, je a % b enako a. Torej bo r = a in funkcija bo v prvem koraku poklicala sebe z obrnjenimi argumenti. Od tam naprej pa vse steče, kot mora.