Gcd va nocni topish va qo'llash

bunda m har qanday musbat sondir.
1.2.3. Evklid algoritmi
7
Eng katta umumiy bo'luvchini topishning eng oddiy algoritmlaridan biri
Evklid algoritmidir. Bu ayirish va bo'linish yordamida ham amalga oshirilishi mumkin
. Keling, ushbu ikki usulning har birini ko'rib chiqaylik.
a) ayirish yo'li bilan GCD ni topish algoritmining tavsifi:
Katta sondan kichikni ayirish. Agar u 0 bo'lib chiqsa, demak, bu raqamlar
bir-biriga teng va GCD (siz tsikldan chiqishingiz kerak). Agar ayirish natijasi 0 bo'lmasa, katta sonni ayirish natijasi bilan almashtiramiz.1-bosqichga o'ting.Misol:
30 va 18 uchun GCD ni toping.30
- 18 = 1218 - 12 = 612 - 6 = 66 - 6 = 0 End: GCD kamayadi yoki chiqariladi. GCD (30, 18) = 6
b) GCD ni bo'lish yo'li bilan topish algoritmining tavsifi:
Kattaroq sonni kichikroqqa bo'ling. Agar u qoldiqsiz bo'lingan bo'lsa, unda kichikroq raqam
GCD (siz tsikldan chiqishingiz kerak). Agar qoldiq bo'lsa, katta raqam bo'linishning qolgan qismiga almashtiriladi. 1-bandga o'tamiz. Misol. GCD ni topish talab qilinsin (102; 84). Bir sonni ikkinchisiga bo'lib, qoldiqni topamiz =12*1+6 0 <6<12Endi - 12 va 6:12=6*2+0 uchun 0 qoldiq. Jarayon tugadi.
1.2.4. Binar Evklid algoritmi.
8
Ikkilik eng katta umumiy boʻluvchi algoritmi,
nomidan koʻrinib turibdiki, ikkita butun sonning eng katta umumiy boʻluvchisini topadi. Taniqli Evklid algoritmi bilan solishtirganda, bu amalda tezroq ishlaydi, lekin ayni paytda amalga oshirish qulayligi jihatidan birinchisidan bir oz pastroq. Algoritm 1-asrda Xitoyda ma'lum bo'lgan, lekin faqat 1967 yilda isroillik fizik va dasturchi Jozef Shtayn tomonidan nashr etilgan. U quyidagi GCD xususiyatlaridan foydalanishga asoslangan:1. gcd(2n, 2m) = 2 gcd(n, m) (masalan, gcd(8, 14)=2gcd(4,7)= 2*1=
2 ) , 2m+1) (masalan, gcd(10, 15)= gcd(5,15)=5)
3. gcd(-n, m) = gcd(n, m) (masalan, gcd(-6; 21)=gcd (6.21)=3)