Največji skupni delitelj (D)
S katerimi največjimi kvadratnimi ploščicami lahko tlakuješ pod sobe 14x16 m^2, ne da bi odrezal niti ene ploščice?
V pomoč ti priskoči največji skupni delitelj (D).
Kaj je D in kako ga grafično prikažemo?
Lahko prikažeš največji skupni delitelj (D) dveh števil a in b tako, da narišeš pravokotnik s stranicama a in b (naj bo a>b).
- V pravokotnik včrtaj vse kvadrate z osnovnico b (manjša od dveh stranic).
- Ostane ti pravokotnik z osnovnicama b in r (r<b). Ponovi prejšnji postopek dokler ne prekriješ začetni pravokotnik samo s kvadrati.
Največji skupni delitelj (D) je osnovnica najmanjšega kvadrata.
Opisani postopek je Evklidov algoritem D(a,b):
1) deli a z b in označi z r ostanek;
2) če je ostanek 0 potem je D=b : STOP;
3) drugače zamenjaj a z b in b z r in vrni se k točki 1).
In če je število a večkratnik števila b?