ЕВКЛИД АЛГОРИТМИ

ЕВКЛИ́Д АЛГОРИТМИ – эки бүтүн сандын эӊ чоӊ жалпы бөлүүчүсүн, ошондой эле эки кесиндинин жалпы ченин табуу ыкмасы. Бул ыкманы оӊ бүтүн a_³b сандары үчүн төмөнкүчө сүрөттөсө бо­лот. a санын b санына бөлгөн учурда a=tb+b₁ туюнтмасы алынат, мында t – оӊ бүтүн сан, b₁ саны b санынан кичине болгон калдык, б. а. 0≤b <b. Удаалаш бөлүүлөрдү жүргүзсөк: а = tb + b1, ⎫ ⎪ Евклиддин «Башталыш» деген философиялык эмгегин­де берилген. Е. г. үч түрдүү объектилердин көп­түгү катары сүрөттөлөт. Алар: «чекиттер», «түз b = t1b1 + b2, ⎪ b = t b + b , ^⎬...................^⎪ (*) сызыктар», «тегиздиктер». Бул объектилердин арасында тиешелүүлүк, иреттүүлүк, конкурент­түүлүк ж-а үзгүлтүксүздүк катыштары бар. Е. г-нын акыркы эӊ так аксиоматикасын Д. Гиль­берт сунуштаган. Е. г. айлана-чөйрөдөгү көзгө көрүнгөн элестерден (түз сызыктар, керилген жип, жарык нуру ж. б.) улам келип чыккан. мында t_i – оӊ бүтүн сандар, 0≤b_i<b_i+1. Бул бөлүү­лөрдү калдыгы нөл болгончо улантса, барабар­дыктардын (*) катар b_k–1 = t_k–1b_k–1+b_k, b_{k– 1} = t_kb_k туюнтмалары м-н аяктайт. Бул учурда алын­ган b_k саны берилген а жана b сандарынын эӊ чоӊ жалпы бөлүүчүсү болот.

С. С. Токсонбаев.