Gcd va nocni topish va qo'llash

1.2.5. Uch yoki undan ortiq sonning
gcd ni topish Uch yoki undan ortiq sonning eng katta umumiy boʻluvchisini
topish
GCD ( a 1 , a 2 )=d 2 ,
GCD( d 2 , a 3 )=d 3 ,
GCD(d 3 , a 4 )=d 4 , …, GCD(d k-1 , a k )=d k .
Misol. 78, 294, 570 va 36
to‘rt sonning eng katta umumiy bo‘luvchisini toping . Bu misolda a 1 =78, a 2 =294, a 3 =570, a 4 =36. Birinchidan, Evklid algoritmidan foydalanib,
birinchi ikkita 78 va 294 sonlarning eng katta umumiy bo'luvchisi d
2 ni aniqlaymiz . Bo'lishda 294=78 3+60;78=60 1+18; 60=18 3+6 va 18=6 3. Shunday qilib, d 2 =GCD(78, 294)=6. Endi d
3 =gcd(d 2 , a 3 )=gcd(6, 570) ni hisoblaymiz . Yana Evklid algoritmini qo'llaymiz
: 570=6·95, demak, d 3 =GCD(6, 570)=6. D
4 \u003d GCD (d 3 , a 4 ) \u003d GCD (6, 36) ni hisoblash qoladi . 36 6 ga bo'linishi sababli,
d 4 \u003d GCD (6, 36) \u003d 6.
Shunday qilib, berilgan to'rtta sonning eng katta umumiy bo'luvchisi d 4 \u003d 6,
ya'ni GCD (78, 294, 570, 36) \u003d 6. Javob: GCD (78, 294, 570, 36) \u003d 6 .
9 Raqamlarni tub omillarga ajratish, shuningdek
, uch yoki undan ortiq sonlarning GCD ni hisoblash imkonini beradi .
Bunda eng katta umumiy bo‘luvchi shu sonlarning barcha umumiy tub ko‘paytmalari ko‘paytmasi sifatida topiladi.Misol. Oldingi misoldagi sonlarning GCD ni ularning tub koeffitsientlari yordamida hisoblang Yechish.78, 294, 570 va 36 sonlarini tub ko‘paytmalarga ajratsak, 78=2 3 13.294=2 3 7 7, 570=2 3 5 19 hosil bo‘ladi. , 36=2 2 3 3. Bu toʻrt sonning umumiy tub koʻpaytuvchilari 2 va 3. Demak, GCD(78, 294, 570.36)=2 3=6. Javob: GCD(78, 294, 570, 36)=6.
Xulosa. Uch yoki undan ortiq sonli GCD ni hisoblash eng yaxshi
asosiy faktorizatsiya yordamida amalga oshiriladi1.2.6. Manfiy sonlarning gcd ni topish
Agar eng katta bo'luvchisi topilishi kerak bo'lgan sonlarning bittasi, bir nechtasi yoki hammasi
manfiy sonlar bo'lsa, ularning gcd si bu sonlar modullarining eng katta umumiy bo'luvchisiga teng bo'ladi. Buning sababi, qarama-qarshi a va -a sonlari bir xil bo'luvchilarga ega.Misol. -231 va -140 manfiy butun sonlarning gcd ni toping Yechish.-231 ning moduli 231 va -140 ning moduli 140, gcd(-231,-140) = gcd(231, 140). Evklid algoritmi bizga quyidagi tenglikni beradi: 231=140 1+91; 140=91 1+49; 91=49 1+42; 49=42 1+7 va 42=7 6. Demak, gcd(231, 140)=7. U holda -231 va -140
manfiy sonlarning
kerakli eng katta umumiy bo'luvchisi 7 ga teng. Javob: GCD(-231, -140)=7. 1.3. LCMni hisoblash algoritmlari
1.3.1. 10