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

Чөлөөт нэвтэрхий толь, Википедиагаас
Харайх: Удирдах, Хайлт

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

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

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

Жишээ[засварлах]

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

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

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