Евклидийн алгоритм

Евклидийн алгоритм гэдэг нь 2 натурал тооны хамгийн их ерөнхий хуваагчийг олох аргуудын нэг юм.

2 бодит тоо a, b (a ≧ b)-гийн хувьд a-г b-д хуваахад гарах үлдэгдлийг r гэвэл a ба b-гийн хамгийн их ерөнхий хуваагч нь b ба r-ийн хамгийн их ерөнхий хуваагчтай тэнцүү байдаг. Энэхүү шинж чанарыг ашиглан цааш b-г r-д хуваахад гарах үлдэгдлийг олох гэх мэтээр явсаар үлдэгдэл нь 0 болох хүртэл үргэлжлүүлэн a ба b-гийн хамгийн их ерөнхий хуваагчийг олдог.

Энэ нь МЭӨ 300 оны орчимд бичигдсэн, Евклидийн "Эхлэл" зохиолын 7-р бүлгийн 1-3-т бичигдсэн байдаг.

Жишээ

(Бодлого) 1071 ба 1029-ийн хамгийн их ерөнхий хуваагчийг ол.

• 1071-г 1029-д хуваахад гарах үлдэгдэл 42
• 1029-г 42-т хуваахад гарах үлдэгдэл 21
• 42-г 21-т хуваахад гарах үлдэгдэл 0

Иймд 1071 ба 1029-ийн хамгийн их ерөнхий хуваагч нь 21 болно.