Matek

Igazából az első kettő állítás triviális, egyszerűen az lnko definíciójából következik.

A harmadiknak a bizonyításához már valóban lehet, hogy érdemes felhasználni az euklideszi algoritmust, de szerintem még azt is be lehetne bizonyítani anélkül.

Serbia is like Nokia: each year a new model, and it's getting smaller.

Köszi, nem ezek azok, de közben megtaláltam.

A tanár "logikus módon" a jegyzetben meghatározta a következményeket és csak utána mutatta be magát az algoritmust.



Amúgy ezekre gondoltam:
Ha m osztója n-nek, akkor lnko(n, m) = m

lnko(n, m) = lnko(n-m, m)

Tekintsük az n és m (>0) egészeket és legyen n-nek m-mel való osztási hányadosa q, maradéka rvagyis
n = m*q+r , ahol 0

Következményei? Hát, az, hogy véges sok lépésben megkapod vele két egész szám legnagyobb közös osztóját. Esetleg van még ilyen kiterjesztett változata is. Valamint működik absztrakt algebrai terekben is. Egyébként gyakorlati alkalmazás szempontjából pedig felhasználó például diofantikus egyenletek és egyenletrendszerek megoldására. Hú, de régen tanultam már ezeket, volt vagy négy-öt éve!

Serbia is like Nokia: each year a new model, and it's getting smaller.

Mik az Euklideszi algoritmus következményei?