Gcd va nocni topish va qo'llash

1-bob. GCD va LCM ni hisoblash algoritmlari
1.1. Barcha algoritmlarning “katta bobosi” Evklid algoritmi
ikki butun sonning eng katta umumiy boʻluvchisini topishning samarali algoritmidir .
Algoritm yunon matematigi Evklid sharafiga nomlangan bo'lib, u uni birinchi marta elementlarning VII va X kitoblarida tasvirlab bergan.Eng oddiy holatda Evklid algoritmi musbat butun sonlar juftiga qo'llaniladi va kichikroq sondan iborat yangi juftlikni hosil qiladi. va katta va kichik son o'rtasidagi farq. Jarayon raqamlar teng bo'lguncha takrorlanadi. Topilgan son asl juftlikning eng katta umumiy boʻluvchisidir.Algoritmning birinchi taʼrifi “Evklid tamoyillari”da (taxminan miloddan avvalgi 300-yil) berilgan boʻlib, u bugungi kunda qoʻllanilayotgan eng qadimgi raqamli algoritmlardan biri hisoblanadi. Dastlabki algoritm faqat natural sonlar va geometrik uzunliklar (haqiqiy sonlar) uchun taklif qilingan. Keyinchalik Evklid algoritmi tugunlar va koʻp oʻlchovli koʻphadlar (bir necha oʻzgaruvchilardagi koʻphad) kabi boshqa matematik tuzilmalar uchun ham umumlashtirildi [2.2].Bu
algoritm uchun koʻplab nazariy va amaliy qoʻllanmalar mavjud. Xususan, u
elektron tijoratda keng qo'llaniladi. Shuningdek, algoritm Diofantin tenglamalarini echishda qo'llaniladi ( Butun sonlardagi tenglamalar ikki yoki undan ortiq noma'lum o'zgaruvchilar va butun son koeffitsientlari bo'lgan algebraik
tenglamalardir). Bunday tenglamaning echimlari
bu tenglamani qondiradigan noma'lum o'zgaruvchilarning butun 5
(ba'zan tabiiy yoki ratsional) qiymatlari to'plamidir .
Bunday tenglamalar
diofantin deb ham ataladi , qadimgi yunon matematigi Iskandariyalik Diofant sharafiga
, masalan: davomli kasrlarni qurishda x 2 - xy - 2y 2 \u003d
7) tenglamani butun sonlarda yeching. Evklid algoritmi
zamonaviy sonlar nazariyasida teoremalarni isbotlashning asosiy quroli hisoblanadi. [2.3]
Uzoq vaqt davomida Evklid algoritmi
eng katta umumiy boʻluvchini topishning eng samarali usuli boʻlgan boʻlsa, elektron hisoblash mashinalarining paydo boʻlishi bilan vaziyat oʻzgardi.Kompyuter yordamida arifmetik amallarni bajarishning oʻziga xos xususiyatlarini hisobga olish imkon yaratdi. Evklid algoritmining yanada samarali (dasturiy ta'minotni amalga oshirish uchun) versiyasini yaratish.