Evklidov algoritem

Evklidov algoritem

Avtor: E-um (vsebinsko), Skupina NAUK (tehnično)

Več o projektu...

Uvod


Spoznali bomo "recept" za določanje največjega skupnega delitelja dveh števil.



Razlaga osnovnih pojmov


ALGORITEM - po korakih določen postopek, kako se nekaj dela; recept

EVKLID - eden največjih grških matematikov (325 pr.n.št. - 265 pr.n.št.)

EVKLIDOV ALGORITEM - postopek za določanje največjega skupnega delitelja dveh števil



Evklidov algoritem

Najprej si oglejmo, kakšen je Evklidov recept za določanje največjega skupnega delitelja. Ko bomo algoritem obvladali, bomo poskušali o njem povedati še kaj več.



Več o Evklidovem algoritmu


Evklidov algoritem:

  • osnovni izrek o deljenju za večje število in manjše število
  • osnovni izrek o deljenju za manjše število in 1. ostanek
  • osnovni izrek o deljenju za 1. ostanek in 2. ostanek
  • osnovni izrek o deljenju za 2. ostanek in 3. ostanek
  • osnovni izrek o deljenju za 3. ostanek in 4. ostanek
  • ...

Postopek nadaljujemo, dokler ne dobimo ostanka 0.

Največji skupni delitelj je zadnji od 0 različen ostanek.



1. primer

Z Evklidovim algoritmom določimo največji skupni delitelj števil 60 in 52. Dopolni. Pomagaš si lahko s prejšnjo animacijo.

Klikni sem za animacijo

osnovni izrek o deljenju za števili 60 in 5260 = 1 · 52 +
osnovni izrek o deljenju za števili 52 in 852 = · 8 + 4
osnovni izrek o deljenju za števili 8 in 48 = · 4 + 0



Ko dobimo ostanek 0, končamo z Evklidovim algoritmom.

Zadnji od 0 različen ostanek je 4, zato je največji skupni delitelj števil 60 in 52 enak 4.

Preveri

Pravilno Naprej

Žal si v vsaj eno polje vpisal(-a) napačno število. Poskusi ponovno! Ponovno Rešitev Naprej

[--! animacija --]

1. 8
2. 6
3. 2

2. primer

Z Evklidovim algoritmom določimo največji skupni delitelj števil 88 in 121. Dopolni.

osnovni izrek o deljenju za števili 121 in 88121 = · 88 +
osnovni izrek o deljenju za števili 88 in 3388 = · 33 +
osnovni izrek o deljenju za števili 33 in 2233 = · 22 +
osnovni izrek o deljenju za števili 22 in 1122 = · 11 +



Ko dobimo ostanek 0, končamo z Evklidovim algoritmom.

Zadnji od 0 različen ostanek je , zato je največji skupni delitelj števil 121 in 88 enak .

Preveri

Pravilno Naprej

Žal si v vsaj eno polje vpisal(-a) napačno število. Poskusi ponovno! Ponovno Rešitev Naprej

1. 1
2. 33
3. 2
4. 22
5. 1
6. 11
7. 2
8. 0
9. 11
10. 11

3. primer

Z Evklidovim algoritmom določimo še največji skupni delitelj števil 208 in 124. Dopolni.

osnovni izrek o deljenju za števili 208 in 124208 = 1 · 124 + 84
osnovni izrek o deljenju za števili in = 1 · + 40
osnovni izrek o deljenju za števili in = 2 · + 4
osnovni izrek o deljenju za števili in = 10 · + 0



Zadnji od 0 različen ostanek je , zato je največji skupni delitelj števil 208 in 124 enak .

Preveri

Pravilno Naprej

Žal si v vsaj eno polje vpisal(-a) napačno število. Poskusi ponovno! Ponovno Rešitev Naprej

1. 124
2. 84
3. 124
4. 84
5. 84
6. 40
7. 84
8. 40
9. 40
10. 4
11. 40
12. 4
13. 4
14. 4

4. primer

Zdaj poskusimo z Evkildovim algoritmom določiti največji skupni delitelj števil 96 in 37. Pišimo le še račune. Dopolni.

96= 2 · 37+ 22
= · +
= · +
= · +
= · +



Največji skupni delitelj števil 96 in 37 je , torej sta števili 96 in 37 tuji.

Preveri

Pravilno Naprej

Žal si v vsaj eno polje vpisal(-a) napačno število. Poskusi ponovno! Ponovno Rešitev Naprej

1. 37
2. 1
3. 22
4. 15
5. 22
6. 1
7. 15
8. 7
9. 15
10. 2
11. 7
12. 1
13. 7
14. 7
15. 1
16. 0
17. 1

1. naloga

Z Evklidovim algoritmom poišči največje skupne delitelje naslednjih parov števil in poveži stolpca:

D(300, 245)=
D(775, 279)=
D(299, 323)=
5
31
1



Preveri

Pravilno Naprej

Žal je odgovor napačen. Poskusi ponovno! Ponovno Rešitev Naprej

(resitev_popravljena.jpg)

2. naloga

S pomočjo Evklidovega algoritma določi največji skupni delitelj in najmanjši skupni večkratnik števil 992 in 1768.

(992, 1768)=

(992, 1768)=



Preveri

Namig

Pravilno Naprej

Žal je odgovor napačen. Poskusi ponovno! Ponovno Rešitev Naprej

Največji skupni delitelj dobimo kot zadnji neničelni ostanek v Evklidovem algoritmu.

Kako pa dobimo najmanjši skupni večkratnik?

Spomni se zveze a·b=D(a,b)·v(a,b).

  • Določimo najprej največji skupni delitelj.

    Evklidov algoritem:

    1768 = 1 · 992 + 776
    992= 1 · 776+ 216
    776= 3 · 216+ 128
    216= 1 · 128+ 88
    128= 1 · 88+ 40
    88= 2 · 40+ 8
    40= 5 · 8+ 0



Največji skupni delitelj števil 992 in 1768 je enak 8.

  • Določimo še najmanjši skupni večkratnik teh dveh števil:

    Uporabimo zvezo .

    1768·992=8·v(a,b)

    v(a,b)=219232

3. naloga

Na dva načina določi največji skupni delitelj in najmanjši skupni večkratnik števil 4331 in 5183:

  • Najprej s pomočjo praštevilskega razcepa obeh števil,
  • nato z Evklidovim algoritmom.

Največji skupni delitelj:

1. Praštevilski razcep

4331=61·

5183=71·

2. Evklidov algoritem

5183= 1 · + 852
4331= 5 · 852+
852= 12 · + 0




Najmanjši skupni večkratnik:

4331·5183=·




Preveri Nauk te naloge

Pravilno Naprej

Žal je odgovor napačen. Poskusi ponovno! Ponovno Rešitev Naprej

Morda se pa le splača poznati Evklidov algoritem...

1. 71
2. 73
3. 71
4. 4431
5. 71
6. 71
7. 71
8. 316163

4. naloga

Kolikor se le da okrajšaj ulomek



Preveri

Namig

Pravilno Naprej

Žal je odgovor napačen. Poskusi ponovno! Ponovno Naprej

krajšati ulomek = števec in imenovalec deliti z istim številom

kolikor se le da okrajšati ulomek = števec in imenovalec deliti z istim največjim možnim številom

Kako pa rečemo številu, ki deli dve števili in je največje možno? Izračunajmo ga.

Še več o Evklidovem algoritmu

Zdaj, ko obvladamo Evklidov algoritem, poskušajmo odgovoriti na naslednja vprašanja:

  • Kdaj uporabiti Evklidov algoritem? Odgovor

  • Ali lahko z Evklidovim algoritmom določimo največji skupni delitelj treh števil? Odgovor

  • Ali se Evklidov algoritem vedno konča? Odgovor

  • Zakaj Evklidov algoritem sploh deluje? Odgovor


Ko imamo veliki števili in je težko uganiti delitelje ali narediti praštevilski razcep. Lahko pa ga uporabimo kar tako.

Ker osnovni izrek o deljenju vključuje le dve števili, lahko Evklidov algoritem uporabljamo le za dve števili.

Lahko pa si pomagamo takole:

  • Z Evklidovim algoritmom izračunamo največji skupni delitelj prvega in drugega števila.
  • Z Evklidovim algoritmom izračunamo največji skupni delitelj tretjega števila in števila, ki smo ga dobili kot največji skupni delitelj prvega in drugega števila.

Tako dobimo največji skupni delitelj treh števil.

(razlaga.jpg)



Pozorno opazuj sliko.

Prva vrstica:

  • Evklidov izrek vedno začnemo z večjim izmed števil: a je večje od b
  • Ker je pri osnovnem izreku o deljenju ostanek vedno manjši od delitelja, je je manjši od b

    Druga vrstica:
  • Ker je pri osnovnem izreku o deljenju ostanek manjši od delitelja, je še manjši od

    Tretja vrstica:
  • Ker je pri osnovnem izreku o deljenju ostanek manjši od delitelja, je še manjši od

In tako naprej...

Kaj se dogaja z ostanki? So vedno manjši. Tako moramo zagotovo priti do najmanjšega možnega ostanka 0. Takrat se Evklidov algoritem zaključi. Torej se Evklidov algoritem vedno mora končati po določenem številu vrstic.

(zadnja.jpg)



Skozi naslednje razmišljanje si pomagajmo z zgornjo sliko. Od spodaj navzgor:

  • 4. vrstica: Ker je ostanek 0, je leva stran deljiva z zadnjim od 0 različnim ostankom (24 je deljivo z 8).
  • 3. vrstica: Ker je desna stran deljiva z zadnjim od 0 različnim ostankom (8 in 24 deljivi z 8), je tudi leva stran deljiva z zadnjim od 0 različnim ostankom (32 je deljivo z 8).
  • 2. vrstica: Ker je desna stran deljiva z zadnjim od 0 različnim ostankom (24 in 32 deljivi z 8), je tudi leva stran deljiva z zadnjim od 0 različnim ostankom (88 je deljivo z 8).
  • 1. vrstica: Ker je desna stran deljiva z zadnjim od 0 različnim ostankom (32 in 88 deljivi z 8), je tudi leva stran deljiva z 8 (120 je deljivo z 8).

Torej sta obe začetni števili deljivi z zadnjim od 0 različnim ostankom (120 in 88 sta deljivi z 8).

Ugotovili smo: ZADNJI OD 0 RAZLIČEN OSTANEK DELI NAJVEČJI SKUPNI DELITELJ.

To pa še ne pomeni, da sta enaka. Nadaljujmo z razmišljanjem.

Od zgoraj navzdol

  • 1. vrstica: Ker največji skupni delitelj deli obe števili (120 in 88), mora deliti tudi 1. ostanek (32)
  • 2. vrstica: Ker največji skupni delitelj deli število in 1. ostanek (88 in 32), mora deliti tudi 2. ostanek (24)
  • 3. vrstica: Ker največji skupni delitelj deli 1. ostanek in 2. ostanek (32 in 24), mora deliti tudi zadnji od 0 različen ostanek (8)


Ugotovili smo:NAJVEČJI SKUPNI DELITELJ DELI ZADNJI OD 0 RAZLIČEN OSTANEK.

Sklep:

Števili, ki se vzajemno delita, sta enaki. Torej je zadnji od 0 različen ostanek ravno največji skupni delitelj.

Preveri svoje znanje 1

Določi največji skupni delitelj števil 1589 in 3983.



Preveri

Pravilno Naprej

Žal je odgovor napačen. Poskusi ponovno! Ponovno Naprej

Preveri svoje znanje 2

Števili 905 in 92129 sta tuji.



Nazaj Preveri Naprej

Pravilno Naprej

Žal je odgovor napačen. Poskusi ponovno! Ponovno Naprej

Preveri svoje znanje 3

Ulomka ne moremo okrajšati.



Preveri

Pravilno Naprej

Žal je odgovor napačen. Poskusi ponovno! Ponovno Naprej

1. dodatna naloga

Z Evklidovim algoritmom določi največji skupni delitelj naslednjih števil. Poveži stolpca.

D(120, 68)=
D(300, 255)=
D(1452, 389)=
D(1300, 1030)=
D(1891, 1647)=
D(4061, 3799)=
4

15

1

10

61

131



Preveri

Pravilno Naprej

Žal je odgovor napačen. Poskusi ponovno! Ponovno Naprej

2. dodatna naloga

Števili 1385 in 2979 sta tuji.



Preveri

Namig

Pravilno Naprej

Žal je odgovor napačen. Poskusi ponovno! Ponovno Naprej

Števili sta tuji, ko je njun največji skupni delitelj enak 1. S pomočjo Evklidovega logaritma preveri, ali trditev drži.

3. dodatna naloga

Določi največji skupni delitelj in najmanjši skupni večkratnik naslednjih števil. Poveži stolpca.

=2, =27132
=116, =5220
=283, =38205
=673, =117775
x=266, y=204

x=1044, y=580

x=7641, y=1415

x=4711, y=16825



Preveri

Pravilno Naprej

Žal je odgovor napačen. Poskusi ponovno! Ponovno Naprej

4. dodatna naloga

Naslednje ulomke okrajšaj kolikor se da. Poveži stolpca.





Ulomka se ne da okrajšati.



Preveri

Pravilno Naprej

Žal je odgovor napačen. Poskusi ponovno! Ponovno Naprej

5. dodatna naloga

Bazen je dolg 25,25 m in širok 17,57 m. Ali lahko popolnoma prekrijemo njegovo dno z enako velikimi kvadratnimi ploščicami (stranica večja od 1 cm), če ploščic ne smemo rezati?



Preveri

Namig

Pravilno Končaj

Žal je odgovor napačen. Poskusi ponovno! Ponovno Končaj

Ker ploščic ne smemo rezati, mora stranica kvadrata hkrati deliti višino in širino bazena. Torej iščemo skupne delitelje dolžine in širine. Poiščimo najprej največji skupni delitelj. Da lahko to storimo, dolžino in širino spremenimo iz decimalnih števil v naravni.

0%
0%