Gcd va nocni topish va qo'llash

1.2 GCD ni hisoblash algoritmlari
1.2.1 Oddiy sanash algoritmi
Berilgan ikkita natural sonning eng katta umumiy boʻluvchisini topish uchun
siz taʼrif boʻyicha harakat qilishingiz mumkin: bu sonlarning barcha boʻluvchilarini yozing, ular orasidan umumiylarini tanlang va hammasidan eng kattasini tanlang. umumiy bo'luvchilar Misol. 54 va 36
sonlarning barcha bo‘luvchilarini toping. 54 1 ga bo‘linadi; 2; 3; 6; 9; 18; 27; 54.
36 soni 1 ga bo‘linadi; 2; 3; 4; 6; 9; 18; 36. Umumiy boʻluvchilar bu sonlar: 1, 2, 3, 6, 9, 18. Shunday qilib, GCD(54; 36)=18
1.2.2 Sonlarni tub
koʻrsatkichlarga ajratish orqali GCD ni
topish GCD ni topishning boshqa usulini koʻrib chiqing. Eng katta umumiy bo‘luvchini
sonlarni tub ko‘paytuvchilarga ajratish yo‘li bilan topish mumkin.Ko‘paytuvchilarga ajratish nima? Bu noqulay va murakkab misolni oddiy va chiroyli misolga aylantirishning bir usuli .
U har bir bosqichda va
6 ta
elementar matematikada va undan yuqori sinflarda uchraydi. Matematik tilda bunday o'zgarishlar
ifodalarning bir xil o'zgarishi deyiladi . Har qanday bir xil o'zgartirishning ma'nosi
ifodani uning mohiyatini saqlab qolgan holda
boshqa shaklda yozishdir .
Faktorizatsiyaning ma'nosi nihoyatda sodda va tushunarli. Sarlavhaning o'zidan
. Misol uchun, siz 12 raqamini ajratishingiz kerak. Siz xavfsiz yozishingiz mumkin: 12 = 3 4A siz 12 ni boshqa yo'l bilan parchalashingiz mumkin: 12 = 3 4 = 2 6 = 3 2 2 = 0,5 24 = ........ Parchalanish variantlari cheksiz miqdordir.
Qoidani shakllantiramiz: a va b ikkita musbat butun sonlarning GCD
a va b sonlarining tub omillarga kengayishidagi barcha umumiy tub omillarning mahsulotiga teng.
GCD ni topish qoidasini tushuntirish uchun misol keltiramiz.
220 va 600 sonlarining tub ko‘paytmalarga kengaytmalarini bilib olaylik, ular 220=2 2 5 11 va 600=2 2 2 3 5 5 ko‘rinishga ega. 220 va 600 sonlarining parchalanishida ishtirok etadigan umumiy tub omillar 2, 2 va 5 dir. Demak, gcd(220, 600)=2 2 5=20. Shunday qilib, a va b sonlarni tub koʻpaytmalarga ajratsak va ularning barcha umumiy omillarining ko‘paytmasini topsangiz, a va b sonlarning eng katta umumiy bo‘luvchisi topiladi.Misol. 72 va 96 sonlarining eng katta umumiy boʻluvchisini toping. Yechim. 72 va 96 sonlarini tub ko‘paytmalarga ajratamiz.72=2 2 2 3 3 va 96=2 2 2 2 2 3. Umumiy tub koeffitsientlar 2, 2,2 va 3. Shunday qilib, gcd(72, 96)=2 2 2 3=24. Javob: gcd(72, 96)=24. Ushbu bandni yakunlash uchun e’tibor bering: gcd ni topish uchun berilgan qoida gcd(m a, m b)=m gcd(a, b) ekanligini bildiruvchi eng katta umumiy bo‘luvchining xossasidan kelib chiqadi,