Licenca
To delo je na voljo pod pogoji slovenske licence Creative Commons 2.5:

priznanje avtorstva - nekomercialno - deljenje pod enakimi pogoji.

Celotna licenca je na voljo na spletu na naslovu http://creativecommons.org/licenses/by-nc-sa/2.5/si/. V skladu s to licenco je dovoljeno vsakemu uporabniku delo razmnoževati, distribuirati, javno priobčevati, dajati v najem in tudi predelovati, vendar samo v nekomercialne namene in ob pogoju, da navede avtorja oziroma avtorje in izdajatelja tega dela. Če uporabnik delo predela, kar pomeni, da ga spremeni, preoblikuje, prevede ali uporabi to delo v svojem delu, lahko predelavo dela ponudi na voljo le pod pogoji, ki so enaki pogojem iz te licence oziroma pod enako licenco.

Povzetek

Algoritem je zaporedje korakov, ki nas privedejo do cilja. Algoritmi morajo biti hitri, končni in enolični. Uporabljamo jih v vsakdanjem življenju, računalništvu in sodobni tehnologiji.

Evklidov algoritem je končen računski postopek, s katerim izračunamo največji skupni delitelj dveh naravnih števil. Običajno se zanj odločimo takrat, ko:

  • ne znamo narediti praštevilskega razcepa,
  • so vpletena števila zelo velika.

Na sliki je prikazan potek Evklidovega algoritma.

Najmanjši skupni večkratnik lahko izračunamo z zvezo $$a\cdot b=D(a,b)\cdot v(a,b).$$

Koraki Evklidovega algoritma

  1. Večje število delimo z manjšim. 
  2. Rezultat deljenja zapišemo po osnovnem izreku o deljenju.
  3. Zamenjamo vlogi: delitelj postane novi deljenec, ostanek postane novi delitelj.

Te korake ponavljamo toliko časa, da dobimo ostanek enak $0$. Največji skupni delitelj začetnih dveh števil je tedaj enak zadnjemu neničelnemu ostanku oziroma zadnjemu delitelju v postopku.

Zgled: Izračunaj največji skupni delitelj števil $3861$ in $1430$. Pomožne račune piši v zvezek, vmesne rezultate pa v prazna polja.

$3861=$ 2 $\cdot$ $1430+$ 1001

$1430=$ 1 $\cdot$ 1001 $+$ 429

1001 $=$ 2 $\cdot$ 429 $+$ 143

429 $=$ 3 $\cdot$ 143 $+0$ 

Največji skupni delitelj števil $3861$ in $1430$ je število 143 .

<NAZAJ
>NAPREJ199/661