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 sonlarning 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 algoritmi bir o'zgaruvchili ko'phadlarga ham tatbiq etildi. Keyinchalik Yevklid algoritmini ba'zi bir boshqa algebraik obyektlar 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 formula 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, sonlar nazariyasida ham ahamiyati kattadir. 2. Eng katta umumiy bo'luvchi (EKUB) Ta'rif: a1,a2,a3,…,anZ sonlarning umumiy bo'luvchisi deb, berilgan sonlarning har biri bo'linadigan dZ songa aytiladi. Berilgan sonlarning umumiy bo'luvchi shu sonlarning barcha umumiy bo'luvchilariga bo'linsa, bu umumiy bo'luvchi berilgan sonlarning eng katta umumiy bo'luvchi deyiladi. Berilgan sonlarning eng katta umumiy bo'luvchisi EKUB(a1,a2,a3,…,an) kabi belgilanadi. Eng katta umumiy bo'luvchining ta'rifidan ushbu muhim xossa kelib chiqadi: agar d=EKUB(a1,a2,a3,…,an) bo'lsa, a1, a2, a3, … , an sonlarning barcha umumiy bo'luvchilari to'plami d sonining barcha bo'luvchilaridan iborat bo'ladi. agar d=EKUB(a1,a2,a3,…,an) bo'lsa, u holda d=EKUB(a1,a2,a3,…,an,0) bo'ladi. Aksincha, agar d=EKUB(a1,a2,a3,…,an,0) bo'lsa, d=EKUB(a1,a2,a3,…,an) bo'ladi. Agar EKUB(a1,a2,a3,…,an)=1 bo'lsa, a1, a2, a3, … , an sonlar o'zaro tub sonlar deyiladi. Endi berilgan sonlarning eng ...