"diofantilistele" - 1 õppematerjal

ITT0030 Diskreetne matemaatika II - eksamikonspekt

Algoritmil kulub tulemuse saamiseks aega ülimalt 1 sammu. *Sõnades võib algoritmi tööd esitada järgmiselt: a). Valime b ossa suurema kahest arvust gcd(a,b). b). Jagame b'd a'ga, saame jäägi r ning asendame b selle jäägiga r. c). Pöördume tagasi silmuse algusesse või kui a on 0, siis väljastame b gcd'na. *Lisaks: Eukleidese algoritm on äärmiselt laia kasutust leidnud ka arvuteooria erinvates rakendustes, kuna ta võimaldab näiteks leida lineaarsetele diofantilistele võrranditele täisarvulisi lahendeid või siis lahendada kongruentseid võrrandeid moodulil m. [27].Lineaarsed diofantilised võrrandid. *Lineaarsed diofantilised võrrandid e. Diophantose võrrandid on mitme tundmatuga ning täisarvuliste kordajatega algebralised võrrandid, millele otsitakse täisarvulisi lahendeid. *Lineaarsele diofantilisele võrrandile leiduvad täisarvulised lahendid parajasti siis, kui gcd(a,b)|c