Farg‘ona davlat universiteti matematika-informatika fakulteti matematika yo‘nalishi guruh talabasi ning “Analitik geometriya” fanidan «Evklidga qadar bo‘lgan geometriya. Evklidning “Negizlar” asari»

3-§ 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 bo‘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. Evklid algoritmi qadimdan ma’lum. Uning yoshi 2 ming yildan ortiq. U Evklidning “Negizlar” ida ta’riflangan. Evklid bu algoritmdan foydalanib tub sonlar, eng kichik umumiy bo‘linuvchi va boshqa xossalarni keltirib chiqargan. Evklid 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 Evklid algoritmi bir o‘zgaruvchili ko‘phadlarga ham tatbiq etildi. Keyinchalik Evklid algoritmini ba’zi bir boshqa obyektlar uchun ham aniqlashga muvaffaq bo‘lindi.
Eng katta umumiy bo‘luvchi (EKUB)
Ta`rif: sonlarning umumiy bo‘luvchisi deb, berilgan sonlarning har biri bo‘linadigan 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 kabi belgilanadi.
Eng katta umumiy bo‘luvchining ta’rifidan ushbu muhim xossa kelib chiqadi:

1. 
   • agar bo‘lsa, sonlarning barcha umumiy bo‘luvchilari to‘plami d sonining barcha bo‘luvchilaridan iborat bo‘ladi.
   
2. 
   • agar bo‘lsa, u holda bo‘ladi. Aksincha, agar bo‘lsa, bo‘ladi.
   

Agar bo‘lsa, sonlar “o‘zaro tub sonlar” deyiladi.
Endi berilgan sonlarning eng katta bo‘luvchisini qanday toppish mumkinligi haqida fikr yuritamiz.
sonlar uchun: ketma-ketlikni quyidagi tuzamiz:
deb olamiz. Agar bo‘lsa, bo‘ladi. Aks holda ni ga bo‘lishda hosil bo‘lgan qoldiqni deb olamiz, ni ga bo‘lishdagi qoldiqni deb olamiz va hokazo.
Bunday qoldiqli bo‘lishlar ketma-ketligini qulaylik uchun tengliklar zanjiri ko‘rinishida bunday yozamiz:

qoldiqli bo‘lish natijasida qoldiqlar uchun munosabat o‘rinli bo‘ladi, bundan tashqari qoldiqlar nomanfiy sonlardir. Shu sababli bu qoldiqlar orasida nolga teng bo‘ladigani albatta uchraydi. uchun noldan farqli oxirgi qoldiqni olamiz. Bu holda soni ga bo‘linishi ravshan.
Hosil qilingan ketma-ketlik a va b sonlari uchun Evklid ketma-ketligi deyiladi.
Ketma-ket qoldiqli bo‘lish yordamida bunday ketma-ketlikni hosil qilish usuli Evklid algoritmi deb ataladi.