Evklid algoritmi

Evklid algoritmi

Evklid algoritmi — ikkita butun sonning eng katta umumiy bo`luvchisini topish, shuningdek ikkita o`lchovdosh kesmaning umumiy o`lchovini topish usuli. Ikkita musbat butun sonning eng katta umumiy b o`luvchisini topish uchun avvalo katta sonni kichik songa bo`lish, so`ngra kichik sonni katta sonning qoldig`iga, keyin esa birinchi qoldiqni ikkinchi qoldiqqa va hokazo bo`lish lozim. Bu jarayondagi noldan farqli oxirgi qoldiq berilgan sonlar­ning eng katta umumiy bo`luvchisi bo`ladi.

Ikki kesmaning eng katta umumiy o`lchovini topish uchun ham ana shunday yo`l tutiladi. Bunda qoldiqli bo`lish amali uning geometrik analogi bilan almashtiriladi: kichik kesma katta kesmaga necha marta joylashsa, o`shancha marta qo`yiladi, katta kesmaning qolgan qismi (“bo`lishdan qolgan qoldiq” sifatida qabul qilinadigan) kichik kesmaga qo`yiladi va h. k. Agar a va b kesmalar o`lchovdosh bo`lsa, u holda oxirgi noldan farqli qoldiq bu kesmalarning eng katta umumiy o`lchovini beradi. Kesmalar umumiy o`lchovga ega bo`lmagan holda noldan farqli qoldiqlar ketma-ketligi cheksiz davom etadi.
Yevklid algoritmi qadimdan ma`lum. Uning yoshi 2 ming yildan ortiq. U Yevklidning «Negizlar» ida ta`riflangan. Yevklid bu algoritmdan foydalanib tub sonlar, eng kichik umumiy bo`linuvchi va boshqa xossalarni keltirib chiqargan. Yevklid algoritmi ikkita kesmaning eng katta umumiy o`lchovini topish usuli sifatida (ba`zan u navbatma-navbat ayirish ham deb ataladi) pifagorchilarga ham ma`lum edi. XVI asr o`rtalarida Yevklid algo­ritmi bir o`zgaruvchili ko`phadlarga ham tatbiq etildi. Keyinchalik Yev­klid algoritmini ba`zi bir boshqa algebraik ob`ektlar uchun ham aniqlashga muvaffaq bo`lindi.
Yevklid algoritmi ko`p tatbiqlarga ega. Uni aniqlovchi tengliklar a va b sonlarning eng katta umumiy bo`luvchisi bo`lgan d sonini d=ax+by ko`rinishida ifodalash imkonini beradi (x; y — butun sonlar), bu formu­la esa ikki noma`lumli birinchi darajali Diofant tenglamalari yechimlarini topishga asos bo`ladi. Yevklid algoritmi ratsional sonni uzluksiz kasr sifatida tasvirlash vositasi hamdir. U ko`pincha elektron hisoblash mashinalari dasturlarida qo`llaniladi, son­lar nazariyasida ham ahamiyati kattadir.