Amaliy mashg‘ulotlarni bajarish buyicha uslubiy ko’rsatmalar. Amaliy mashg’ulot. Mavzu

Raqamlarni tub omillarga ajratish orqali gcd ni topish

Ikki sonning eng katta umumiy bo’luvchisini koeffitsientlarga ajratish usulida topish uchun bu ikki sonning parchalanishidan olingan va ular uchun umumiy bo’lgan barcha tub ko’paytuvchilarni ko’paytirish kerak bo’ladi.
4-misol
Agar 220 va 600 sonlarini tub ko‘paytiruvchilarga ko‘paytirsak, ikkita mahsulot hosil bo‘ladi: 220 = 2 2 5 11 va 600 = 2 2 2 3 5 5... Ushbu ikki mahsulotdagi umumiy omillar 2, 2 va 5 bo'ladi. Bu GCD degan ma'noni anglatadi (220, 600) = 2 2 5 = 20
5-misol
Sonlarning eng katta umumiy bo‘luvchisini toping 72 va 96 .
Yechim
Sonlarning barcha tub omillarini toping 72 va 96 :
72 36 18 9 3 1 2 2 2 3 3
96 48 24 12 6 3 1 2 2 2 2 2 3
Ikki son uchun umumiy bo'lgan tub omillar 2, 2, 2 va 3 dir. Bu GCD degan ma'noni anglatadi (72, 96) = 2 2 2 3 = 24.
Javob: GCD (72, 96) = 24.
Ikki sonning eng katta umumiy boʻluvchisini topish qoidasi eng katta umumiy boʻluvchining xossalariga asoslanadi, unga koʻra GCD (ma 1, mb 1) = m GCD (a 1, b 1), bu erda m har qanday musbat butun sondir.

Uch yoki undan ortiq raqamlarning GCD ni topish

GCD ni topishimiz kerak bo'lgan raqamlar sonidan qat'i nazar, biz ikkita raqamning GCD ni ketma-ket topishdan iborat bo'lgan bir xil algoritmga muvofiq harakat qilamiz. Ushbu algoritm quyidagi teoremani qo'llashga asoslangan: bir nechta sonlarning GCD a 1, a 2,…, a k soniga teng d k, bu GCD ning ketma-ket hisob-kitobida topiladi (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.
6-misol
78, 294, 570 va to'rtta sonning eng katta umumiy ko'rsatkichini toping 36 .
Yechim
Belgilanishni kiritamiz: a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.
78 va 294 raqamlarining GCD ni topishdan boshlaylik: d 2 = Gcd (78 , 294) = 6 .
Endi d 3 = gcd (d 2, a 3) = gcd (6, 570) ni topishni boshlaylik. Evklid algoritmiga ko'ra 570 = 6 · 95. Bu shuni anglatadiki d 3 = Gcd (6 , 570) = 6 .
d 4 = gcd (d 3, a 4) = gcd (6, 36) ni toping. 36 6 ga qoldiqsiz bo'linadi. Bu bizga qabul qilish imkonini beradi d 4 = Gcd (6 , 36) = 6 .
d 4 = 6, ya'ni gcd (78 , 294 , 570 , 36) = 6 .
Javob:
Keling, ushbu va boshqa raqamlar uchun GCDni hisoblashning boshqa usulini ko'rib chiqaylik. GCD ni raqamlarning barcha umumiy tub omillarini ko'paytirish orqali topishimiz mumkin.
7-misol
78, 294, 570 va raqamlarining gcd ni hisoblang 36 .
Yechim
Keling, bu sonlarni tub ko‘paytmalarga ajratamiz: 78 = 2 · 3 · 13, 294 = 2 · 3 · 7 · 7, 570 = 2 · 3 · 5 · 19, 36 = 2 · 2 · 3 · 3.
Barcha to'rtta raqam uchun umumiy tub omillar 2 va 3 dir.
Ma'lum bo'lishicha, GCD (78, 294, 570, 36) = 2 3 = 6.