Евклидийн алгоритм
Чөлөөт нэвтэрхий толь — Википедиагаас
Евклидийн алгоритм гэдэг нь 2 натурал тооны хамгийн их ерөнхий хуваагчийг олох аргуудын нэг юм.
2 бодит тоо a, b (a ≧ b)-гийн хувьд a-г b-д хуваахад гарах үлдэгдлийг r гэвэл a ба b-гийн хамгийн их ерөнхий хуваагч нь b ба r-ийн хамгийн их ерөнхий хуваагчтай тэнцүү байдаг. Энэхүү шинж чанарыг ашиглан цааш b-г r-д хуваахад гарах үлдэгдлийг олох гэх мэтээр явсаар үлдэгдэл нь 0 болох хүртэл үргэлжлүүлэн a ба b-гийн хамгийн их ерөнхий хуваагчийг олдог.
Энэ нь МЭӨ 300 оны орчимд бичигдсэн, Евклидийн "Эхлэл" зохиолын 7-р бүлгийн 1-3-т бичигдсэн байдаг.
Жишээ[засварлах | edit source]
(Бодлого) 1071 ба 1029-ийн хамгийн их ерөнхий хуваагчийг ол.
- 1071-г 1029-д хуваахад гарах үлдэгдэл 42
- 1029-г 42-т хуваахад гарах үлдэгдэл 21
- 42-г 21-т хуваахад гарах үлдэгдэл 0
Иймд 1071 ба 1029-ийн хамгийн их ерөнхий хуваагч нь 21 болно.
