Evklid algoritmi yordamida tugunlarni topish va asosiy faktorizatsiyadan foydalanish. Raqamlarni tub omillarga ajratish orqali nokni topish Evklidning gcd ni topish algoritmi
Eng katta umumiy bo'luvchini topishning ikkita usulini ko'rib chiqing.
Faktoring orqali topish
Birinchi usul - berilgan sonlarni qismlarga ajratish orqali eng katta umumiy bo'luvchini topishdir asosiy omillar.
Bir nechta sonlarning GCD ni topish uchun ularni tub omillarga ajratish va ularning barcha berilgan raqamlar uchun umumiy bo'lganlarini bir-biriga ko'paytirish kifoya.
1-misol Keling, GCD ni topamiz (84, 90).
Biz 84 va 90 raqamlarini tub omillarga ajratamiz:
Shunday qilib, biz barcha umumiy tub omillarni ta'kidladik, ularni bir-biriga ko'paytirish qoladi: 1 2 3 = 6.
Shunday qilib, gcd (84, 90) = 6.
2-misol Keling, GCD ni topamiz (15, 28).
Biz 15 va 28 ni tub omillarga ajratamiz:
15 va 28 raqamlari koʻpaytiriladi, chunki ularning eng katta umumiy boʻluvchisi bittadir.
gcd (15, 28) = 1.
Evklid algoritmi
Ikkinchi usul (boshqacha Evklid usuli deb ataladi) ketma-ket bo'linish orqali GCD ni topishdir.
Birinchidan, biz ushbu usulni faqat ikkita berilgan raqamga qanday qo'llashni ko'rib chiqamiz, so'ngra uni uch yoki undan ortiq raqamlarga qanday qo'llashni aniqlaymiz.
Agar berilgan ikkita sondan kattasi kichigiga boʻlinadigan boʻlsa, kichikroq son ularning eng katta umumiy boʻluvchisi boʻladi.
1-misol Keling, ikkita 27 va 9 sonini olaylik. 27 9 ga va 9 ga boʻlinadigan boʻlgani uchun 9 soni 27 va 9 sonlarining umumiy boʻluvchisi boʻladi. Bu boʻluvchi ham eng katta, chunki 9 hech qanday songa boʻlinmaydi, 9 dan katta. Demak, gcd (27, 9) = 9.
Boshqa hollarda, ikkita sonning eng katta umumiy bo'luvchisini topish uchun ishlatiladi keyingi buyurtma harakatlar:
- Berilgan ikkita sondan katta son kichikga bo'linadi.
- Keyin kichikroq raqam bo'linish natijasida hosil bo'lgan qoldiqqa bo'linadi Ko'proq kamroq uchun.
- Bundan tashqari, birinchi qoldiq ikkinchi qoldiqga bo'linadi, bu kichik sonni birinchi qoldiqqa bo'lish orqali olinadi.
- Ikkinchi qoldiq uchinchiga bo'linadi, birinchi qoldiqni ikkinchisiga bo'lish natijasida olinadi va hokazo.
- Shunday qilib, bo'linish qolgan nolga teng bo'lguncha davom etadi. Oxirgi bo'luvchi eng katta umumiy bo'luvchi bo'ladi.
2-misol 140 va 96 sonlarining eng katta umumiy bo‘luvchisini topamiz:
1) 140: 96 = 1 (qolgan 44)
2) 96: 44 = 2 (qolgan 8)
3) 44: 8 = 5 (qolgan 4)
Oxirgi bo'luvchi 4, ya'ni gcd(140, 96) = 4.
Ketma-ket bo'linish ustunga ham yozilishi mumkin:
Uch yoki undan ortiq berilgan sonlarning eng katta umumiy boʻluvchisini topish uchun quyidagi tartibdan foydalaning:
- Birinchidan, bir nechta ma'lumotlar to'plamidan har qanday ikkita raqamning eng katta umumiy bo'luvchisini toping.
- Keyin topilgan bo'linuvchining GCD ni va uchinchi berilgan sonni topamiz.
- Keyin biz oxirgi topilgan bo'luvchi va to'rtinchi berilgan sonning GCD ni topamiz va hokazo.
3-misol 140, 96 va 48 sonlarining eng katta umumiy boʻluvchisini topamiz. Biz oldingi misolda 140 va 96 sonlarining GCD ni topdik (bu 4 raqami). 4 va uchinchi berilgan sonning eng katta umumiy bo'luvchisini topish qoladi - 48:
48 4 ga qoldiqsiz bo'linadi. Shunday qilib, gcd (140, 96, 48) = 4.
Sonni tub sonlarning ko'paytmasi sifatida ifodalash deyiladi bu sonni tub omillarga ajratish.
Masalan, 110 = 2 5 11 yozuvi 110 soni 2, 5 va 11 tub omillarga ajralishini ko'rsatadi.
Umuman olganda, hamma narsani asosiy omillarga ajratish mumkin kompozit raqam bundan tashqari, har qanday usul bilan, agar omillarning tartibi hisobga olinmasa, bitta va bir xil parchalanish olinadi. Demak, 110 raqamini 2 · 5 · 11 yoki 5 · 2 · 11 koʻpaytmasi sifatida koʻrsatish, mohiyatan, 110 sonining tub koʻpaytuvchilarga bir xil parchalanishidir.
Sonlarni tub ko‘paytuvchilarga ajratishda, 2, 3, 5 va hokazolarga bo‘linish belgilaridan foydalangan holda, sonning tub ko‘paytuvchilarga parchalanishini yozish usulini eslaylik. Masalan, 720 sonini tub koʻpaytmalarga ajratamiz.720 soni 2 ga boʻlinadi. Demak, 2 soni 720 sonining yemirilishida tub koʻrsatkichlardan biri hisoblanadi. 720 ni 2 ga boʻling. 2 raqami quyidagicha yoziladi. tenglik belgisining o'ng tomoni, va 360 qismi 720 raqami ostida yoziladi. 360 sonini 2 ga bo'lsak, biz 180 ni olamiz. 180 ni 2 ga bo'lamiz, biz 90 ga, 90 ni 2 ga bo'lamiz, 45 ga, 45 ga bo'linadi. 3, 15 ni olamiz, 15 ni 3 ga bo'lamiz, 5 ni olamiz. 5 soni tub, 5 ga bo'linganda 1 bo'ladi. Ko'paytmalar bo'linishi tugallandi.
720 = 2 2 2 2 3 3 5
Bir xil omillar mahsulotini quvvat bilan almashtirish odatiy holdir: 720 = 5. 720 raqamining bunday ko'rinishi deyiladi. kanonik ko'rinish bu raqam.
Sonni tub omillarga ko‘paytirish ularning eng katta umumiy bo‘luvchisini va eng kichik umumiy karralini topish uchun ishlatiladi.
Masalan, 3600 va 288 sonlarining eng katta umumiy boʻluvchisini va eng kichik umumiy karralini toping.
Keling, ushbu raqamlarning har birini ifodalaylik kanonik shakl.
3600 = 2 2 2 2 3 3 5 5 =; 288 = 2 2 2 2 2 3 3 =
3600 va 288 sonlarining eng katta umumiy boʻluvchisini tub koʻpaytirgichlarga ajratishda hammasi umumiy oddiy ko'paytirish, berilgan raqamlarning kengaytmalarida mavjud bo'lgan va ularning har biridan olinishi kerak eng past ko'rsatkich bu bilan u ikkala kengaytmaga kiradi. Shuning uchun, 3600 va 288 sonlarining eng katta umumiy bo'linmasining kengayishi omillarni va ni o'z ichiga oladi. Shunday qilib, D (3600? 288) = · = 144.
3600 va 288 ning eng kichik umumiy koʻpaytmasini tub omillarga ajratish tarkibidagi barcha tub omillarni oʻz ichiga olishi kerak. kamida bittasida 3600 va 288 raqamlarining kengayishlaridan va ularning har biri olinishi kerak eng yuqori ball bilan, bu raqamlarning ikkala kengaytmasiga kiritilgan. Demak, 3600 va 288 ning eng kichik umumiy karrali kengayishi , , 5 omillarini o'z ichiga oladi. Demak,
K (3600, 288) = 5 = 7200.
Umuman olganda, berilgan sonlarning eng katta umumiy boʻluvchisini topish uchun:
2) Biz barcha berilgan sonlar uchun umumiy tub omillar ko'paytmasini hosil qilamiz va ularning har biri bu sonlarning barcha kengayishlariga kiradigan eng kichik ko'rsatkich bilan olinadi;
3) Biz ushbu mahsulotning qiymatini topamiz - bu raqamlarning eng katta umumiy bo'luvchisi bo'ladi.
Berilgan sonlarning eng kichik umumiy karralini topish uchun:
1) Biz har bir berilgan sonni kanonik shaklda ifodalaymiz;
2) Biz bu sonlarning kengayishlarida bo'lgan barcha tub omillardan hosila hosil qilamiz va har biri bu sonlarning barcha kengayishlariga kiradigan eng katta ko'rsatkich bilan olinadi;
3) Biz ushbu mahsulotning qiymatini topamiz - bu raqamlarning eng kichik umumiy soni bo'ladi.
Chipta raqami 45. Raqamlarning eng kichik umumiy karrali. Uning xossalari va topish usullari. Misollar.
Gcd (eng kichik umumiy bo'luvchi) orqali eng kichik umumiy ko'plikni (LCM) hisoblash
Eng kichik umumiy ko'paytmani topishning bir usuli LCM va GCD o'rtasidagi munosabatlarga asoslanadi. LCM va GCD o'rtasidagi mavjud munosabat sizga ma'lum bo'lgan eng katta umumiy bo'luvchi orqali ikkita musbat sonning eng kichik umumiy ko'paytmasini hisoblash imkonini beradi. Tegishli formulada shakl mavjud LCM(a, b)=a b: GCD(a, b) . Yuqoridagi formula bo'yicha LCMni topish misollarini ko'rib chiqing.
Misol.
Ikki sonning eng kichik umumiy karralini toping 126 va 70 .
Yechim.
Ushbu misolda a=126, b=70. Keling, formula bilan ifodalangan LCM va GCD o'rtasidagi munosabatdan foydalanaylik LCM(a, b)=a b: GCD(a, b). Ya'ni, avval raqamlarning eng katta umumiy bo'luvchisini topishimiz kerak 70 va 126 , shundan so'ng biz yozma formula bo'yicha ushbu raqamlarning LCM ni hisoblashimiz mumkin.
Keling, topamiz GCD(126, 70), Evklid algoritmidan foydalangan holda: 126=70 1+56, 70=56 1+14, 56=14 4, Binobarin, gcd(126, 70)=14.
Endi biz kerakli eng kichik umumiy ko'paytmani topamiz: LCM(126, 70)=126 70: GCM(126, 70)=126 70:14=630.
Javob:
LCM(126, 70)=630.
Misol.
Nimaga teng MOQ(68, 34)?
Yechim.
Chunki 68 butunlay boʻlinadi 34 , keyin GCD(68, 34)=34. Endi biz eng kichik umumiy ko'paytmani hisoblaymiz: LCM(68, 34)=68 34:GCM(68, 34)=68 34:34=68.
Javob:
LCM(68, 34)=68.
E'tibor bering, oldingi misol musbat butun sonlar uchun LCMni topish uchun quyidagi qoidaga mos keladi a va b: agar raqam a tomonidan bo'linadi b, u holda bu sonlarning eng kichik umumiy karrali a.
Raqamlarni asosiy omillarga ajratish orqali LCMni topish
Eng kichik umumiy ko'paytmani topishning yana bir usuli raqamlarni tub omillarga ajratishga asoslangan. Agar biz ushbu sonlarning barcha tub omillaridan hosil bo'ladigan bo'lsak, shundan so'ng biz ushbu ko'paytmadan ushbu sonlarning kengayishlarida mavjud bo'lgan barcha umumiy tub omillarni chiqarib tashlasak, natijada hosil bo'lgan mahsulot ushbu sonlarning eng kichik umumiy ko'paytmasiga teng bo'ladi.
LCMni topish uchun e'lon qilingan qoida tenglikdan kelib chiqadi LCM(a, b)=a b: GCD(a, b). Darhaqiqat, raqamlar mahsuloti a va b sonlarning kengayishlarida ishtirok etuvchi barcha omillarning mahsulotiga teng a va b. O'z navbatida gcd(a, b) sonlarning kengayishlarida bir vaqtning o'zida mavjud bo'lgan barcha tub omillarning ko'paytmasiga teng a va b(bu raqamlarni tub omillarga ajratish orqali GCDni topish bo'limida tasvirlangan).
Keling, bir misol keltiraylik. Buni bizga xabar bering 75=3 5 5 va 210=2 3 5 7. Ushbu kengayishlarning barcha omillarining mahsulotini tuzing: 2 3 3 5 5 5 7. Endi biz ushbu mahsulotdan raqamni kengaytirishda ham mavjud bo'lgan barcha omillarni istisno qilamiz 75 va sonning kengayishida 210 (bunday omillar 3 va 5 ), keyin mahsulot shaklni oladi 2 3 5 5 7. Ushbu mahsulotning qiymati raqamlarning eng kichik umumiy ko'paytmasiga teng 75 va 210 , ya'ni, LCM(75, 210)= 2 3 5 5 7=1 050.
Misol.
Raqamlarni kengaytirish 441 va 700 tub omillarga aylantirib, bu sonlarning eng kichik umumiy karrasini toping.
Yechim.
Keling, raqamlarni ajratamiz 441 va 700 asosiy omillar uchun:
olamiz 441=3 3 7 7 va 700=2 2 5 5 7.
Keling, ushbu raqamlarning kengayishiga ta'sir qiluvchi barcha omillarning mahsulotini yarataylik: 2 2 3 3 5 5 7 7 7. Keling, ushbu mahsulotdan ikkala kengayishda bir vaqtning o'zida mavjud bo'lgan barcha omillarni istisno qilaylik (faqat bitta bunday omil mavjud - bu raqam 7 ): 2 2 3 3 5 5 7 7. Shunday qilib, LCM(441, 700)=2 2 3 3 5 5 7 7=44 100.
Javob:
LCM (441, 700) = 44 100.
Raqamlarni tub omillarga ajratish yordamida LCMni topish qoidasi biroz boshqacha shakllantirilishi mumkin. Agar sonning kengayishidan omillarga a raqamni kengaytirishdan etishmayotgan omillarni qo'shing b, keyin hosil bo'lgan mahsulotning qiymati raqamlarning eng kichik umumiy ko'paytmasiga teng bo'ladi a va b .
Misol uchun, barcha bir xil raqamlarni olaylik 75 va 210 , ularning faktorizatsiyasi quyidagicha: 75=3 5 5 va 210=2 3 5 7. Ko'paytiruvchilarga 3 , 5 va 5 sonning parchalanishidan 75 2 va 7 sonning parchalanishidan 210 , biz mahsulotni olamiz 2 3 5 5 7, kimning qiymati MOQ(75, 210).
Misol.
Sonlarning eng kichik umumiy karralisini toping 84 va 648 .
Yechim.
Biz birinchi navbatda raqamlarning parchalanishini olamiz 84 va 648 asosiy omillarga. Ular o'xshaydi 84=2 2 3 7 va 648=2 2 2 3 3 3 3. Ko'paytiruvchilarga 2 , 2 , 3 va 7 sonning parchalanishidan 84 etishmayotgan omillarni qo'shish 2 , 3 , 3 va 3 sonning parchalanishidan 648 , biz mahsulotni olamiz 2 2 2 3 3 3 3 7 ga teng 4 536 . Shunday qilib, raqamlarning istalgan eng kichik umumiy karrali 84 va 648 teng 4 536 .
Javob:
LCM(84, 648)=4536.
Keling, GCD ni ikkita asosiy usulda topishning ikkita asosiy usulini ko'rib chiqaylik: Evklid algoritmidan foydalanish va faktoring. Keling, ikkita, uch va undan ko'p sonlar uchun ikkala usulni ham qo'llaymiz.
Yandex.RTB R-A-339285-1
GCD ni topish uchun Evklid algoritmi
Evklid algoritmi ikkita musbat sonning eng katta umumiy boʻluvchisini hisoblashni osonlashtiradi. Biz Evklid algoritmining formulalari va isbotini eng katta umumiy boʻluvchi: aniqlovchi, misollar boʻlimida keltirdik.
Algoritmning mohiyati qoldiq bilan bo'linishni izchil amalga oshirishdir, bunda shaklning bir qator tengliklari olinadi:
a = b q 1 + r 1 , 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1
Biz bo'linishni qachon tugatishimiz mumkin rk + 1 = 0, unda r k = gcd (a , b).
1-misol
64 va 48 .
Yechim
Belgilashni kiritamiz: a = 64 , b = 48 .
Evklid algoritmiga asoslanib, biz bo'linishni amalga oshiramiz 64 ustida 48 .
Biz 1 ni, qolganini esa 16 ni olamiz. Ma’lum bo‘lishicha, q 1 = 1, r 1 = 16.
Ikkinchi qadam - bo'linish 48 16 ga kelib, biz 3 ni olamiz. Ya'ni q2 = 3, a r 2 = 0. Shunday qilib, 16 raqami shartdagi raqamlar uchun eng katta umumiy bo'luvchidir.
Javob: gcd(64, 48) = 16.
2-misol
Raqamlar GCD nima 111 va 432 ?
Yechim
Bo'lmoq 432 ustida 111 . Evklid algoritmiga ko'ra, 432 = 111 3 + 99, 111 = 99 1 + 12, 99 = 12 8 + 3, 12 = 3 4 tenglik zanjirini olamiz.
Shunday qilib, raqamlarning eng katta umumiy bo'luvchisi 111 va 432 3 bo'ladi.
Javob: gcd(111, 432) = 3.
3-misol
661 va 113 sonlarining eng katta umumiy boʻluvchisini toping.
Yechim
Biz raqamlarni ketma-ket ajratamiz va GCD ni olamiz (661 , 113) = 1 . Demak, 661 va 113 nisbatan tub sonlardir. Agar biz tub sonlar jadvaliga qarasak, hisob-kitoblarni boshlashdan oldin buni aniqlab olishimiz mumkin.
Javob: gcd(661, 113) = 1.
Raqamlarni asosiy omillarga ajratish orqali GCDni topish
Ikki sonning eng katta umumiy boʻluvchisini faktoring usulida topish uchun bu ikki sonni parchalash natijasida olingan va ular uchun umumiy boʻlgan barcha tub koʻpaytuvchilarni koʻpaytirish kerak.
4-misol
Agar biz 220 va 600 sonlarini tub omillarga ajratsak, 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 NOD 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
Ikkita son uchun umumiy tub omillar: 2, 2, 2 va 3. Bu NOD 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 (m a 1, m b 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 bir xil algoritmga amal qilamiz, bu ketma-ket ikkita raqamning GCD ni topishdan iborat. Bu algoritm quyidagi teoremani qo'llashga asoslangan: bir nechta sonlarning GCD a 1 , a 2 , … , a k soniga teng dk, bu gcd ni ketma-ket hisoblashda 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 boʻluvchisini 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: d2= GCD (78 , 294) = 6 .
Endi topishni boshlaylik d 3 \u003d GCD (d 2, a 3) \u003d GCD (6, 570) . Evklid algoritmiga ko'ra 570 = 6 95. Bu shuni anglatadiki d 3 = GCD (6 , 570) = 6 .
d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36) ni toping. 36 6 ga qoldiqsiz bo'linadi. Bu bizga olish imkonini beradi d4= GCD (6 , 36) = 6 .
d4 = 6, ya'ni GCD (78 , 294 , 570 , 36) = 6 .
Javob:
Keling, ushbu va boshqa raqamlar uchun GCDni hisoblashning boshqa usulini ko'rib chiqaylik. Biz 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 raqamlari bo'ladi.
Ma'lum bo'lishicha, NOD (78, 294, 570, 36) = 2 3 = 6.
Javob: gcd(78 , 294 , 570 , 36 ) = 6 .
Manfiy sonlarning gcd ni topish
Agar biz manfiy sonlar bilan shug'ullanishimiz kerak bo'lsa, unda biz eng katta umumiy bo'luvchini topish uchun ushbu raqamlarning modullaridan foydalanishimiz mumkin. Qarama-qarshi belgilarga ega bo'lgan raqamlarning xususiyatini bilib, buni qila olamiz: raqamlar n va -n bir xil bo'luvchilarga ega.
8-misol
Manfiy butun sonlarning gcd ni toping − 231 va − 140 .
Yechim
Hisoblashlarni bajarish uchun shartda berilgan sonlarning modullarini olaylik. Bular 231 va 140 raqamlari bo'ladi. Keling, qisqacha aytaylik: GCD (− 231 , − 140) = GCD (231, 140). Endi Evklid algoritmidan foydalanib, ikkita sonning tub omillarini topamiz: 231 = 140 1 + 91 ; 140 = 91 1 + 49; 91 = 49 1 + 42; 49 = 42 1 + 7 va 42 = 7 6. Biz gcd (231, 140) = 7 ni olamiz .
Va NODdan beri (− 231 , − 140) = GCD (231 , 140) , keyin raqamlarning gcd − 231 va − 140 teng 7 .
Javob: gcd (- 231 , - 140) = 7 .
9-misol
Uchta sonning gcd ni aniqlang - 585, 81 va − 189 .
Yechim
Yuqoridagi ro'yxatdagi manfiy raqamlarni ularning bilan almashtiramiz mutlaq qiymatlar, biz GCD olamiz (− 585 , 81 , − 189) = GCD (585 , 81 , 189) . Keyin barcha berilgan raqamlarni tub omillarga ajratamiz: 585 = 3 3 5 13, 81 = 3 3 3 3 va 189 = 3 3 3 7. 3 va 3 bosh omillari uchta raqam uchun umumiydir. Ma'lum bo'lishicha, gcd (585 , 81 , 189) = gcd (- 585 , 81 , - 189) = 9 .
Javob: GCD (- 585, 81, - 189) = 9.
Agar siz matnda xatolikni sezsangiz, uni belgilab, Ctrl+Enter tugmalarini bosing
