Eng katta umumiy bo'luvchi (GCD): ta'rif, misollar va xususiyatlar. Evklid algoritmi va asosiy faktorizatsiya yordamida GCD ni topish
Eng katta umumiy boʻluvchi
Ta'rif 2
Agar natural a soni $b$ natural soniga boʻlinadigan boʻlsa, $b$ $a$ ning boʻluvchisi, $a$ soni esa $b$ ning karrali deb ataladi.
$a$ va $b$ natural sonlar boʻlsin. $c$ soni $a$ va $b$ uchun umumiy boʻluvchi deyiladi.
$a$ va $b$ sonlarining umumiy boʻluvchilari toʻplami cheklangan, chunki bu boʻluvchilarning hech biri $a$ dan katta boʻla olmaydi. Bu shuni anglatadiki, bu bo'linuvchilar orasida eng kattasi mavjud bo'lib, u $a$ va $b$ sonlarining eng katta umumiy bo'luvchisi deb ataladi va uni belgilash uchun yozuv ishlatiladi:
$gcd \ (a;b) \ yoki \ D \ (a;b)$
Ikki sonning eng katta umumiy boʻluvchisini topish uchun:
- 2-bosqichda topilgan raqamlarning ko'paytmasini toping. Olingan son kerakli eng katta umumiy bo'luvchi bo'ladi.
1-misol
$121$ va $132.$ sonlarining gcd ni toping
$242=2\cdot 11\cdot 11$
$132=2\cdot 2\cdot 3\cdot 11$
Ushbu raqamlarni kengaytirishga kiritilgan raqamlarni tanlang
$242=2\cdot 11\cdot 11$
$132=2\cdot 2\cdot 3\cdot 11$
2-bosqichda topilgan raqamlarning ko'paytmasini toping. Olingan son kerakli eng katta umumiy bo'luvchi bo'ladi.
$gcd=2\cdot 11=22$
2-misol
$63$ va $81$ monomiallarning GCD ni toping.
Taqdim etilgan algoritmga muvofiq topamiz. Buning uchun:
Keling, sonlarni tub omillarga ajratamiz
$63=3\cdot 3\cdot 7$
$81=3\cdot 3\cdot 3\cdot 3$
Biz bu raqamlarni kengaytirishga kiritilgan raqamlarni tanlaymiz
$63=3\cdot 3\cdot 7$
$81=3\cdot 3\cdot 3\cdot 3$
2-bosqichda topilgan sonlarning ko'paytmasini topamiz. Olingan son kerakli eng katta umumiy bo'luvchi bo'ladi.
$gcd=3\cdot 3=9$
Ikki raqamning GCD ni raqamlarning bo'linuvchilari to'plamidan foydalanib, boshqa yo'l bilan topishingiz mumkin.
3-misol
$48$ va $60$ raqamlarining gcd ni toping.
Yechim:
$48$ boʻluvchilar toʻplamini toping: $\left\((\rm 1,2,3.4.6,8,12,16,24,48)\right\)$
Endi $60$ ning boʻluvchilar toʻplamini topamiz:$\ \left\((\rm 1,2,3,4,5,6,10,12,15,20,30,60)\right\)$
Ushbu to‘plamlarning kesishishini topamiz: $\left\((\rm 1,2,3,4,6,12)\right\)$ - bu to‘plam $48$ va $60 sonlarining umumiy bo‘luvchilari to‘plamini aniqlaydi. $. Ushbu to'plamdagi eng katta element $12$ bo'ladi. Demak, $48$ va $60$ ning eng katta umumiy boʻluvchisi $12$.
MOK ta'rifi
Ta'rif 3
natural sonlarning umumiy karrali$a$ va $b$ - bu $a$ va $b$ ning koʻpaytmasi boʻlgan natural son.
Raqamlarning umumiy karralilari asliyatiga qoldiqsiz boʻlinadigan sonlardir.Masalan, $25$ va $50$ raqamlari uchun umumiy koʻpaytmalar $50.100.150.200$ va boshqalar boʻladi.
Eng kichik umumiy karrali eng kichik umumiy karra deb ataladi va LCM$(a;b)$ yoki K$(a;b) bilan belgilanadi.
Ikki raqamning LCM ni topish uchun sizga kerak bo'ladi:
- Raqamlarni tub omillarga ajrating
- Birinchi raqamning bir qismi bo'lgan omillarni yozing va ularga ikkinchisining bir qismi bo'lgan va birinchisiga kirmaydigan omillarni qo'shing.
4-misol
$99$ va $77$ raqamlarining LCM ni toping.
Taqdim etilgan algoritmga muvofiq topamiz. Buning uchun
Raqamlarni tub omillarga ajrating
$99=3\cdot 3\cdot 11$
Birinchisiga kiritilgan omillarni yozing
ularga ikkinchisining bir qismi bo'lgan va birinchisiga bormaydigan omillarni qo'shing
2-bosqichda topilgan raqamlarning ko'paytmasini toping. Olingan son kerakli eng kichik umumiy karrali bo'ladi
$LCC=3\cdot 3\cdot 11\cdot 7=693$
Raqamlarga bo'linuvchilar ro'yxatini tuzish ko'pincha juda ko'p vaqt talab etadi. GCD ni topishning Evklid algoritmi deb ataladigan usuli mavjud.
Evklid algoritmi asoslangan bayonotlar:
Agar $a$ va $b$ natural sonlar va $a\vdots b$ boʻlsa, $D(a;b)=b$
Agar $a$ va $b$ natural sonlar boʻlsa, $b
$D(a;b)= D(a-b;b)$ dan foydalanib, biz ko'rib chiqilayotgan sonlarni, ulardan biri ikkinchisiga bo'linadigan juft songa yetguncha ketma-ket kamaytirishimiz mumkin. Shunda bu sonlarning kichigi $a$ va $b$ raqamlari uchun kerakli eng katta umumiy boʻluvchi boʻladi.
GCD va LCM xususiyatlari
- $a$ va $b$ ning har qanday umumiy karrali K$(a;b)$ ga boʻlinadi
- Agar $a\vdots b$ bo'lsa, K$(a;b)=a$
Agar K$(a;b)=k$ va $m$- natural son boʻlsa, K$(am;bm)=km$
Agar $d$ $a$ va $b$ uchun umumiy boʻluvchi boʻlsa, K($\frac(a)(d);\frac(b)(d)$)=$\ \frac(k)(d) ) $
Agar $a\vdots c$ va $b\vdots c$ boʻlsa, $\frac(ab)(c)$ $a$ va $b$ ning umumiy karrali boʻladi.
Har qanday natural sonlar uchun $a$ va $b$ tenglik
$D(a;b)\cdot K(a;b)=ab$
$a$ va $b$ ning har qanday umumiy boʻluvchisi $D(a;b)$ ning boʻluvchisidir.
Lekin ko'pgina natural sonlar boshqa natural sonlarga teng bo'linadi.
Masalan:
12 soni 1 ga, 2 ga, 3 ga, 4 ga, 6 ga, 12 ga bo‘linadi;
36 soni 1 ga, 2 ga, 3 ga, 4 ga, 6 ga, 12 ga, 18 ga, 36 ga bo‘linadi.
Raqam bo'linadigan raqamlar (12 uchun 1, 2, 3, 4, 6 va 12) deyiladi. son bo'luvchilar. Natural sonning bo'luvchisi a berilgan sonni ajratuvchi natural son a izsiz. Ikki dan ortiq koeffitsientga ega natural son deyiladi kompozitsion. E'tibor bering, 12 va 36 raqamlari umumiy bo'luvchilarga ega. Bu raqamlar: 1, 2, 3, 4, 6, 12. Bu raqamlarning eng katta bo'luvchisi 12 ga teng.
Berilgan ikkita sonning umumiy boʻluvchisi a va b berilgan ikkala sonning qoldiqsiz bo‘linadigan soni a va b. Ko'p sonlarning umumiy bo'luvchisi (GCD) ularning har biri uchun bo'luvchi vazifasini bajaradigan son.
Qisqacha raqamlarning eng katta umumiy bo'luvchisi a va b quyidagicha yoziladi:
Misol: gcd (12; 36) = 12.
Yechimning yozuvidagi sonlarning bo'luvchilari Bosh harf"D".
Misol:
gcd (7; 9) = 1
7 va 9 raqamlari faqat bitta umumiy bo'luvchiga ega - 1 raqami. Bunday raqamlar chaqiriladi ko'paytmachi slam.
Koʻpaytirish raqamlari faqat bitta umumiy bo'luvchiga ega bo'lgan natural sonlar - 1 soni. Ularning gcd si 1 ga teng.
Eng katta umumiy bo'luvchi (GCD), xususiyatlar.
- Asosiy xususiyat: eng katta umumiy bo'luvchi m va n bu sonlarning har qanday umumiy boʻluvchisiga boʻlinadi. Misol: 12 va 18 sonlar uchun eng katta umumiy boʻluvchi 6 ga teng; u bu raqamlarning barcha umumiy bo'luvchilariga bo'linadi: 1, 2, 3, 6.
- Xulosa 1: umumiy bo‘luvchilar to‘plami m va n gcd bo'luvchilar to'plamiga to'g'ri keladi ( m, n).
- Xulosa 2: umumiy ko'paytmalar to'plami m va n bir nechta LCM to'plamiga to'g'ri keladi ( m, n).
Bu, xususan, kasrni kamaytirilmaydigan ko'rinishga keltirish uchun uning soni va maxrajini ularning gcd ga bo'lish zarurligini bildiradi.
- Raqamlarning eng katta umumiy boʻluvchisi m va n ularning barcha chiziqli birikmalari to'plamining eng kichik ijobiy elementi sifatida aniqlanishi mumkin:
va shuning uchun raqamlarning chiziqli birikmasi sifatida ifodalanadi m va n:
Bu nisbat deyiladi Bezout nisbati, va koeffitsientlar u va v — bezout koeffitsientlari. Bezout koeffitsientlari kengaytirilgan Evklid algoritmi bilan samarali hisoblanadi. Ushbu bayonot natural sonlar to'plamlari uchun umumlashtiriladi - uning ma'nosi shundaki, to'plam tomonidan yaratilgan guruhning kichik guruhi siklikdir va bitta element tomonidan hosil qilinadi: gcd ( a 1 , a 2 , … , a n).
Eng katta umumiy bo'luvchini hisoblash (gcd).
Ikki raqamning gcd ni hisoblashning samarali usullari Evklid algoritmi va ikkilikalgoritm. Bundan tashqari, GCD qiymati ( m,n) agar raqamlarning kanonik kengayishi ma'lum bo'lsa, osongina hisoblash mumkin m va n asosiy omillar uchun:
bu erda alohida tub sonlar va va manfiy bo'lmagan butun sonlar (agar mos tub son kengaytmada bo'lmasa, ular nolga teng bo'lishi mumkin). Keyin gcd ( m,n) va LCM ( m,n) formulalar bilan ifodalanadi:
Agar ikkitadan ortiq raqam bo'lsa: , ularning GCD quyidagi algoritm bo'yicha topiladi:
- bu kerakli GCD.
Bundan tashqari, topish uchun eng katta umumiy bo'luvchi, berilgan sonlarning har birini tub omillarga ajratishingiz mumkin. Keyin barcha berilgan raqamlarga kiritilgan omillarni alohida yozing. Keyin biz bir-biriga yozilgan raqamlarni ko'paytiramiz - ko'paytirish natijasi eng katta umumiy bo'linuvchidir .
Keling, eng katta umumiy bo'luvchining hisobini bosqichma-bosqich tahlil qilaylik:
1. Sonlarning bo‘luvchilarini tub ko‘paytuvchilarga ajrating:
Hisob-kitoblar vertikal chiziq yordamida qulay tarzda yoziladi. Qatorning chap tomonida birinchi navbatda dividendni, o'ngda - bo'luvchini yozing. Keyinchalik chap ustunda biz shaxsiy qiymatlarni yozamiz. Keling, darhol misol bilan tushuntiramiz. Keling, 28 va 64 sonlarini tub ko'paytmalarga ajratamiz.
2. Ikkala sonda ham bir xil tub omillarni ta’kidlaymiz:
28 = 2 . 2 . 7
64 = 2 . 2 . 2 . 2 . 2 . 2
3. Bir xil tub omillarning mahsulotini topamiz va javobni yozamiz:
GCD (28; 64) = 2. 2 = 4
Javob: GCD (28; 64) = 4
GCD ning joylashishini ikkita usulda tartibga solishingiz mumkin: ustunda (yuqorida qilinganidek) yoki "qatorda".
GCD yozishning birinchi usuli:
GCD 48 va 36 ni toping.
GCD (48; 36) = 2 . 2. 3 = 12
GCD yozishning ikkinchi usuli:
Endi GCD qidiruv yechimini qatorga yozamiz. GCD 10 va 15 ni toping.
D(10) = (1, 2, 5, 10)
D(15) = (1, 3, 5, 15)
D(10, 15) = (1, 5)
Ushbu maqola haqida eng katta umumiy bo'luvchini topish (gcd) ikki va Ko'proq raqamlar. Birinchidan, Evklid algoritmini ko'rib chiqing, bu sizga ikkita raqamning GCD ni topishga imkon beradi. Shundan so'ng, biz raqamlarning GCD ni ularning umumiy tub omillarining mahsuloti sifatida hisoblash imkonini beruvchi usulga to'xtalamiz. Keyinchalik, biz uch yoki undan ortiq sonlarning eng katta umumiy bo'luvchisini topish bilan shug'ullanamiz, shuningdek, manfiy sonlarning GCD ni hisoblash misollarini keltiramiz.
Sahifani navigatsiya qilish.
GCD ni topish uchun Evklid algoritmi
E'tibor bering, agar biz eng boshidan tub sonlar jadvaliga murojaat qilgan bo'lsak, 661 va 113 raqamlari tub ekanligini bilib olgan bo'lardik, ulardan darhol ularning eng katta umumiy bo'luvchisi 1 ekanligini aytishimiz mumkin edi.
Javob:
gcd(661, 113)=1 .
Raqamlarni asosiy omillarga ajratish orqali GCDni topish
GCD ni topishning boshqa usulini ko'rib chiqing. Eng katta umumiy bo‘luvchini sonlarni tub ko‘paytmalarga ajratish yo‘li bilan topish mumkin. Keling, qoidani tuzamiz: Ikki musbat butun a va b sonlarning gcd qiymati a va b ni tub omillarga ajratishda barcha umumiy tub omillarning mahsulotiga teng..
Keling, 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 kengayishida ishtirok etadigan umumiy tub omillar 2, 2 va 5 dir. Shuning uchun gcd(220, 600)=2 2 5=20 .
Shunday qilib, agar a va b sonlarni tub omillarga ajratsak va ularning barcha umumiy ko'paytmalari ko'paytmasini topsak, u holda a va b sonlarining eng katta umumiy bo'luvchisi topiladi.
E'lon qilingan qoida bo'yicha GCD ni topish misolini ko'rib chiqing.
Misol.
72 va 96 ning eng katta umumiy boʻluvchisini toping.
Yechim.
72 va 96 sonlarini koeffitsientlarga ajratamiz: 
Ya'ni, 72=2 2 2 3 3 va 96=2 2 2 2 2 3. Umumiy tub omillar 2 , 2 , 2 va 3 dir. Demak, gcd(72, 96)=2 2 2 3=24 .
Javob:
gcd(72, 96)=24 .
Ushbu bo'limni yakunlab, shuni ta'kidlaymizki, gcd ni topish uchun yuqoridagi qoidaning to'g'riligi eng katta umumiy bo'luvchining xususiyatidan kelib chiqadi. GCD(m a 1 , m b 1)=m GCD(a 1 , b 1), bu yerda m har qanday musbat butun son.
Uch yoki undan ortiq raqamlarning GCD ni topish
Uch yoki undan ortiq sonning eng katta umumiy boʻluvchisini topish ikki sonning gcd ni ketma-ket topishga qisqartirilishi mumkin. GCD xususiyatlarini o'rganishda biz buni eslatib o'tdik. U erda biz teoremani tuzdik va isbotladik: a 1 , a 2 , …, a k sonlarning eng katta umumiy boʻluvchisi. soniga teng d k, u ketma-ket hisob 1da topiladi, a k)=d k.
Keling, misol yechimini ko'rib chiqish orqali bir nechta raqamlarning GCD ni topish jarayoni qanday ko'rinishini ko'rib chiqaylik.
Misol.
78 , 294 , 570 va 36 toʻrtta sonning eng katta umumiy boʻluvchisini toping.
Yechim.
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 tengliklarni olamiz; 78=60 1+18 ; 60=18 3+6 va 18=6 3 . Shunday qilib, d 2 =GCD(78, 294)=6 .
Endi hisoblaylik d 3 \u003d GCD (d 2, a 3) \u003d GCD (6, 570). Yana Evklid algoritmini qo'llaymiz: 570=6·95 , demak, d 3 =GCD(6, 570)=6 .
Hisoblash uchun qoladi d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36). 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 =6 , ya'ni gcd(78, 294, 570, 36)=6 ga teng.
Javob:
gcd(78, 294, 570, 36)=6 .
Raqamlarni tub omillarga ajratish, shuningdek, uch yoki undan ortiq raqamlarning GCD ni hisoblash imkonini beradi. Bunday holda, eng katta umumiy bo'luvchi berilgan sonlarning barcha umumiy tub omillarining ko'paytmasi sifatida topiladi.
Misol.
Oldingi misoldagi raqamlarning GCD ni ularning asosiy faktorizatsiyalaridan foydalanib hisoblang.
Yechim.
78 , 294 , 570 va 36 sonlarini tub koʻpaytmalarga ajratamiz, 78=2 3 13 , 294=2 3 7 7 , 570=2 3 5 19 , 36=2 2 3 ni olamiz. Barcha berilgan to'rtta sonning umumiy tub omillari 2 va 3 raqamlaridir. Binobarin, GCD(78, 294, 570, 36)=2 3=6.
Keling, muammoni hal qilaylik. Bizda ikki turdagi cookie-fayllar mavjud. Ba'zilari shokoladli, ba'zilari esa oddiy. 48 ta shokolad bo'lagi bor va oddiy 36. Bu kukilardan maksimal darajada sovg'a qilish kerak va ularning barchasi ishlatilishi kerak.
Birinchidan, keling, ushbu ikki raqamning har birining barcha bo'luvchilarini yozamiz, chunki bu raqamlarning ikkalasi ham sovg'alar soniga bo'linishi kerak.
olamiz
- 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48.
- 36: 1, 2, 3, 4, 6, 9, 12, 18, 36.
Keling, bo'luvchilar orasida birinchi va ikkinchi songa ega bo'lgan umumiy sonlarni topamiz.
Umumiy bo'luvchilar: 1, 2, 3, 4, 6, 12.
Hammaning eng katta umumiy boʻluvchisi 12. Bu son 36 va 48 ning eng katta umumiy boʻluvchisi deyiladi.
Natijaga asoslanib, biz barcha kukilardan 12 ta sovg'a qilish mumkin degan xulosaga kelishimiz mumkin. Bunday sovg'alardan biri 4 ta shokoladli pechene va 3 ta oddiy pechene bo'ladi.
Eng katta umumiy bo'luvchini topish
- Ikki a va b sonlar qoldiqsiz boʻlinadigan eng katta natural son bu sonlarning eng katta umumiy boʻluvchisi deyiladi.
Ba'zan GCD qisqartmasi yozuvni qisqartirish uchun ishlatiladi.
Ba'zi juft raqamlarning eng katta umumiy bo'luvchisi bittaga ega. Bunday raqamlar chaqiriladi umumiy sonlar. Masalan, 24 va 35 raqamlari. GCD =1 bo'lsin.
Eng katta umumiy bo'luvchini qanday topish mumkin
Eng katta umumiy bo'luvchini topish uchun bu sonlarning barcha bo'luvchilarini yozish shart emas.
Siz boshqacha qilishingiz mumkin. Birinchidan, ikkala raqamni tub omillarga aylantiring.
- 48 = 2*2*2*2*3,
- 36 = 2*2*3*3.
Endi birinchi raqamni kengaytirishga kiritilgan omillardan biz ikkinchi raqamni kengaytirishga kirmaydigan barcha narsalarni o'chirib tashlaymiz. Bizning holatlarimizda bu ikkita ikkilikdir.
- 48 = 2*2*2*2*3 ,
- 36 = 2*2*3 *3.
2, 2 va 3 koeffitsientlari qoladi.Ularning ko'paytmasi 12. Bu raqam 48 va 36 sonlarining eng katta umumiy bo'luvchisi bo'ladi.
Bu qoida uch, to'rt va hokazo holatlarga kengaytirilishi mumkin. raqamlar.
Eng katta umumiy bo'luvchini topishning umumiy sxemasi
- 1. Sonlarni tub ko‘paytuvchilarga ajrating.
- 2. Bu raqamlardan birining kengayishiga kiritilgan omillardan boshqa raqamlarning kengayishiga kirmaydiganlarini kesib tashlang.
- 3. Qolgan omillarning mahsulotini hisoblang.