"diophantose" - 1 õppematerjal

ITT0030 Diskreetne matemaatika II - eksamikonspekt

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. Kui viimane tingimus pole täidetud, siis täisarvulisi lahendeid võrrandil ei leidu. *Lahendamiseks kasutatakse harilikult laiendatud Eukleidese algoritmi iteratiivset meetodit