jedro
EVKLIDOV ALGORITEM / EUKLIDESZI ALGORITMUS
Največji skupni delitelj dveh števil lahko izračunamo tudi s postopkom, ki ga imenujemo Evklidov algoritem, s spodaj navedeno formulo pa tudi njun najmanjši skupni večkratnik: / Két szám legnagyobb közös osztóját meghatározhatjuk az ún. euklideszi algoritmussal is, az alábbi képlet segítségével pedig kiszámíthatjuk a legkisebb közös többszörösüket:
| D(a,b)$\cdot$v(a,b)=a$\cdot$b |
Zgled / Példa
Z Evklidovim algoritmom izračunajmo D(60,52) in v(60,52). / Euklideszi algoritmussal számítsuk ki a D(60,52)-t és v(60,52)-t!
|
osnovni izrek o deljenju za števili 60 in 52 /
maradékos osztás tétele a 60 és az 52 esetében |
60=1$\cdot$52+ |
|
osnovni izrek o deljenju za števili 52 in 8 / maradékos osztás tétele az 52 és a 8 esetében |
52= $\cdot$8+4 |
|
osnovni izrek o deljenju za števili 8 in 4 / maradékos osztás tétele a 8 és a 4 esetében |
8= $\cdot$4+ 0 |
Zgled / Példa
Z Evklidovim algoritmom izračunaj D(451,123). / Euklideszi algoritmussal számítsd ki a D(451,123)-t!
451=
$\cdot$123+
123= $\cdot$82+
82= $\cdot$41+