Hogy kell ezt euklideszi algoritmussal megoldani?

Ez gyakorlatilag csak első lépésben azonos az euklideszi algoritmussal.

Van egy nagyobb érméd és egy kisebb, 20 és 10.

A nagyobbal elkezded az osztást:

150/20=7,5

Az egészrész a szükséges 20 forintosaid száma. Most jön a kisebb érme. Megnézed, mennyi a maradék:

20X7=140

150-140=10

És most ezt osztod a következő érmével:

10/10=1

7 db 20-as és 1 db 10-es.

Vegyünk egy jobb példát:

50, 20, 10 és 5 forintos, az összeg mondjuk 245.

245/50=4,9

4 db 50-es

50X4=200

245-200=45

45/20=2,25

2 db 20-as

2X20=40

45-40=5

5/10=0,5

0 db 10-es

5/5=1

1 db 5-ös.

> „Nem tudom egyébként, hogy a legnagyobb közös osztó meghatározása ehhez a kérdéshez hogyan jön.”

Nem csak a legnagyobb közös osztó meghatározását hívják Euklideszi algoritmusnak, hanem a két ismeretlenes lineáris diofantoszi egyenlet megoldóalgoritmusát is.

Ez talán segít:

[link]