Nod va nok raqamlari - bir nechta sonlarning eng katta umumiy bo'luvchisi va eng kichik umumiy karrali. Nod va nok uch yoki undan ortiq sonlar Nod ta'rifiga misollar

Ta'rif. a va b sonlari qoldiqsiz bo'linadigan eng katta natural son deyiladi eng katta umumiy bo'luvchi (gcd) bu raqamlar.

24 va 35 sonlarining eng katta umumiy bo‘luvchisini topamiz.
24 ning bo‘luvchilari 1, 2, 3, 4, 6, 8, 12, 24 sonlari, 35 ning bo‘luvchilari esa 1, 5, 7, 35 sonlari bo‘ladi.
Biz 24 va 35 raqamlarining faqat bitta umumiy bo'luvchiga ega ekanligini ko'ramiz - 1 raqami. Bunday raqamlar deyiladi. ko'paytma.

Ta'rif. Natural sonlar deyiladi ko'paytma agar ularning eng katta umumiy boʻluvchisi (gcd) 1 boʻlsa.

Eng katta umumiy bo'luvchi (GCD) berilgan sonlarning barcha bo‘luvchilarini yozmasdan ham topish mumkin.

48 va 36 raqamlarini koeffitsientga olib, biz quyidagilarni olamiz:
48 = 2 * 2 * 2 * 2 * 3, 36 = 2 * 2 * 3 * 3.
Ushbu raqamlarning birinchisini kengaytirishga kiritilgan omillardan biz ikkinchi raqamni kengaytirishga kiritilmaganlarni o'chirib tashlaymiz (ya'ni, ikkita ikkilik).
2 * 2 * 3 omillar qoladi.Ularning ko'paytmasi 12. Bu son 48 va 36 sonlarining eng katta umumiy bo'luvchisidir. Uch yoki undan ortiq sonlarning eng katta umumiy bo'luvchisi ham topiladi.

Topmoq eng katta umumiy bo'luvchi

2) ushbu raqamlardan birining kengayishi tarkibiga kiruvchi omillardan boshqa raqamlarning kengayishiga kirmaydiganlarini kesib tashlang;
3) qolgan omillarning mahsulotini toping.

Agar berilgan barcha raqamlar ulardan biriga bo'linadigan bo'lsa, bu raqam bo'ladi eng katta umumiy bo'luvchi berilgan raqamlar.
Misol uchun, 15, 45, 75 va 180 ning eng katta umumiy bo'luvchisi 15 ga teng, chunki u boshqa barcha raqamlarni: 45, 75 va 180 ga bo'linadi.

Eng kichik umumiy ko'p (LCM)

Ta'rif. Eng kichik umumiy ko'p (LCM) a va b natural sonlari a va b ning karrali eng kichik natural sonlardir. 75 va 60 raqamlarining eng kichik umumiy karrali (LCM) bu raqamlarning karralarini ketma-ket yozmasdan topilishi mumkin. Buning uchun biz 75 va 60 ni oddiy omillarga ajratamiz: 75 \u003d 3 * 5 * 5 va 60 \u003d 2 * 2 * 3 * 5.
Biz ushbu raqamlarning birinchisini kengaytirishga kiritilgan omillarni yozamiz va ularga ikkinchi raqamning kengayishidan etishmayotgan 2 va 2 omillarni qo'shamiz (ya'ni omillarni birlashtiramiz).
Biz beshta omilni olamiz 2 * 2 * 3 * 5 * 5, mahsuloti 300. Bu raqam 75 va 60 raqamlarining eng kichik umumiy ko'paytmasidir.

Shuningdek, uchta yoki undan ortiq sonning eng kichik umumiy karralini toping.

Kimga eng kichik umumiy karralini toping bir nechta natural sonlar kerak bo'ladi:
1) ularni asosiy omillarga ajratish;
2) raqamlardan birining kengayishiga kiruvchi omillarni yozing;
3) ularga qolgan raqamlarning kengayishlaridan etishmayotgan omillarni qo'shing;
4) hosil bo'lgan omillarning mahsulotini toping.

E'tibor bering, agar bu raqamlardan biri boshqa barcha raqamlarga bo'linadigan bo'lsa, bu raqam ushbu raqamlarning eng kichik umumiy karrali hisoblanadi.
Masalan, 12, 15, 20 va 60 ning eng kichik umumiy karrali 60 ga teng bo'ladi, chunki u berilgan barcha raqamlarga bo'linadi.

Pifagor (miloddan avvalgi VI asr) va uning shogirdlari sonlarning bo‘linuvchanligi masalasini o‘rgandilar. Uning barcha bo'luvchilari yig'indisiga teng bo'lgan son (raqamning o'zi bo'lmasa), ular mukammal son deb atashgan. Masalan, 6 (6 = 1 + 2 + 3), 28 (28 = 1 + 2 + 4 + 7 + 14) raqamlari mukammaldir. Keyingi mukammal sonlar 496, 8128, 33 550 336. Pifagorchilar faqat birinchi uchta mukammal sonni bilishgan. To'rtinchi - 8128 - 1-asrda ma'lum bo'ldi. n. e. Beshinchisi - 33 550 336 - XV asrda topilgan. 1983 yilga kelib, 27 ta mukammal raqam allaqachon ma'lum edi. Ammo hozirgacha olimlar toq mukammal sonlar bor-yo‘qligini, eng katta mukammal sonlar bor-yo‘qligini bilishmaydi.
Qadimgi matematiklarning tub sonlarga boʻlgan qiziqishi har qanday sonning tub son boʻlishi yoki tub sonlar koʻpaytmasi sifatida ifodalanishi mumkinligi, yaʼni tub sonlarning qolgan natural sonlar qurilgan gʻishtlarga oʻxshashligi bilan bogʻliq.
Siz natural sonlar qatoridagi tub sonlar notekis bo'lishini payqadingiz - qatorning ba'zi qismlarida ular ko'proq, boshqalarida - kamroq. Ammo biz raqamlar qatori bo'ylab qanchalik uzoqlashsak, tub sonlar shunchalik kam bo'ladi. Savol tug'iladi: oxirgi (eng katta) tub son mavjudmi? Qadimgi yunon matematigi Evklid (miloddan avvalgi 3-asr) ikki ming yil davomida matematikaning asosiy darsligi boʻlgan “Boshlanishlar” asarida cheksiz koʻp tub sonlar borligini, yaʼni har bir tub son ortida undan ham kattaroq tub son borligini isbotlagan.
Bosh sonlarni topish uchun xuddi shu davrdagi boshqa yunon matematigi Eratosfen shunday usulni o‘ylab topdi. U 1 dan qaysidir songacha bo‘lgan barcha raqamlarni yozib oldi, so‘ngra tub son ham, qo‘shma son ham bo‘lmagan birlikni kesib tashladi, so‘ngra 2 dan keyingi barcha raqamlarni (2 ga karrali sonlar, ya’ni 4, 6, 8 va hokazo) bittadan kesib tashladi. 2 dan keyin qolgan birinchi raqam 3 edi. Keyin, ikkitadan keyin, 3 dan keyingi barcha raqamlar (3 ga karrali raqamlar, ya'ni 6, 9, 12 va boshqalar) chizilgan. oxirida faqat tub sonlar chizilmagan holda qoldi.

Ikki raqamning GCD (eng katta umumiy bo'luvchi) ni topish uchun sizga kerak bo'ladi:

2. Olingan kengayishlardagi barcha umumiy tub omillarni toping (tagini chizing).

3. Umumiy tub omillar ko‘paytmasini toping.

Ikki raqamning LCM (eng kichik umumiy karrali) ni topish uchun sizga kerak bo'ladi:

1. Bu sonlarni tub ko‘paytuvchilarga ajrating.

2. Ulardan birining kengayishini birinchisining kengayishida bo'lmagan boshqa sonning kengayishi omillari bilan to'ldiring.

3. Olingan omillarning mahsulotini hisoblang.

GCD topilmoqda

GCD eng katta umumiy bo'luvchidir.

Bir nechta sonlarning eng katta umumiy boʻluvchisini topish uchun:

• ikkala raqam uchun umumiy omillarni aniqlash;
• umumiy omillar mahsulotini toping.

GCD ni topishga misol:

315 va 245 raqamlarining GCD ni toping.

315 = 5 * 3 * 3 * 7;

245 = 5 * 7 * 7.

2. Ikkala raqam uchun umumiy omillarni yozing:

3. Umumiy omillar ko‘paytmasini toping:

gcd(315; 245) = 5 * 7 = 35.

Javob: GCD(315; 245) = 35.

MOKni topish

LCM eng kam umumiy ko'paytma hisoblanadi.

Bir nechta sonning eng kichik umumiy karralini topish uchun:

• sonlarni tub omillarga ajratish;
• raqamlardan birining kengayishiga kiritilgan omillarni yozing;
• ularga ikkinchi raqamni kengaytirishdan etishmayotgan omillarni qo'shing;
• hosil bo'lgan omillarning mahsulotini toping.

NOCni topishga misol:

236 va 328 raqamlarining LCM ni toping:

1. Raqamlarni tub omillarga ajratamiz:

236 = 2 * 2 * 59;

328 = 2 * 2 * 2 * 41.

2. Raqamlardan birining kengayishi tarkibiga kiruvchi omillarni yozing va ularga ikkinchi sonning kengayishidagi etishmayotgan omillarni qo'shing:

2; 2; 59; 2; 41.

3. Hosil bo‘lgan omillarning ko‘paytmasini toping:

LCM(236; 328) = 2 * 2 * 59 * 2 * 41 = 19352.

Javob: LCM(236; 328) = 19352.

Eng katta umumiy bo'luvchi kasrlar bilan ishlashni osonlashtiradigan yana bir ko'rsatkichdir. Ko'pincha, hisob-kitoblar natijasida, hisoblagich va maxrajning juda katta qiymatlari bilan kasrlar olinadi. Bunday raqamlarni bosqichma-bosqich kamaytirish mumkin, ammo bu juda uzoq, shuning uchun GCDni darhol topish va uni kamaytirish osonroq. Keling, mavzuni batafsil ko'rib chiqaylik.

NOD nima?

Raqamlar qatorining eng katta umumiy boʻluvchisi (GCD) qatordagi har bir sonni qoldiqsiz boʻlish mumkin boʻlgan eng katta sondir.

NODni qanday topish mumkin?

GCD ni topish uchun raqamlarning har birini tub omillarga ajratish va umumiy qismini ajratib ko'rsatish kerak.

Ular buning uchun maxsus formulani o'ylab topmaganlar, ammo hisoblash algoritmi mavjud.

Ikki natural sonning eng katta umumiy boʻluvchisini topishga misol keltiramiz: 540 va 252. 640 ni tub koʻpaytuvchilarga ajratamiz. Harakatlar ketma-ketligi quyidagicha:

• Biz raqamni mumkin bo'lgan eng kichik tub songa bo'lamiz. Ya'ni, agar raqamni 2, 3 yoki 5 ga bo'lish mumkin bo'lsa, unda siz birinchi navbatda 5 ga bo'lishingiz kerak. Faqat adashmaslik uchun.
• Olingan natija mumkin bo'lgan eng kichik tub songa bo'linadi.
• Olingan har bir natijaning bo'linishini tub son olinmaguncha takrorlaymiz.

Endi biz xuddi shu tartibni amalda bajaramiz.

• 540: 2=270
• 270:2=135
• 135: 3 =45
• 45: 3=15
• 15: 5 = 3

Natijani 540=2*2*3*3*3*5 tenglama shaklida yozamiz. Natijani yozish uchun oxirgi hosil bo'lgan sonni barcha bo'luvchilarga ko'paytirish kerak.

Keling, 252 raqami bilan ham shunday qilaylik:

• 252: 2=126
• 126: 2=63
• 63: 3=21
• 21: 3 = 7

Natijani yozamiz: 252=2*2*3*3*7.

Har bir kengaytmada bir xil raqamlar mavjud. Keling, ularni topamiz, bu ikkita raqam 2 va ikkita raqam 3. Faqat 7 va 3 * 5 farq qiladi.

GCD ni topish uchun siz umumiy omillarni ko'paytirishingiz kerak. Ya'ni, mahsulotda ikkita ikkita va ikkita uchlik bo'ladi.

GCD=2*2*3*3=36

Undan qanday foydalanish mumkin?

Vazifa: $252\540$$ dan ortiq qismini kamaytiring.

Biz allaqachon ushbu ikki raqam uchun GCD ni topdik, endi biz allaqachon hisoblangan qiymatdan foydalanamiz.

Kasrning soni va maxrajini 36 ga kamaytiramiz va javobni olamiz.

$$(252\over540) =(7\over15)$$ - tez kamaytirish uchun raqamlarning kengayishiga qarang.

Agar 540=2*2*3*3*3*5 va GCD=36=2*2*3*3 boʻlsa, 540 = 36*3*5 boʻladi. Agar 540 ni 36 ga bo‘lsak, 3*5=15 bo‘ladi.

GCD bo'lmasa, biz qisqartmalarni bitta uzun qatorda yozishimiz kerak edi. Bundan tashqari, kasrni umuman kamaytirish mumkinmi yoki yo'qmi aniq bo'lmagan holatlar mavjud. Matematikadagi bunday vaziyatlar uchun ular sonlarni asosiy omillarga va GCDga ajratishni o'ylab topdilar.

Biz nimani o'rgandik?

Biz bir juft sonning eng katta umumiy bo'luvchisi nima ekanligini bilib oldik, indikatordan amalda qanday foydalanishni aniqladik, GCD ni topish va kasrlarni kamaytirish uchun GCD dan foydalanish masalasini hal qildik. Biz tushundikki, GCD dan foydalangan holda, hisoblagich va maxraj uchun GCD ni topish orqali katta hajmli kasrlarni kamaytirish osonroq va tezroq.

Mavzu viktorina

Maqola reytingi

O'rtacha reyting: 4.3. Qabul qilingan umumiy baholar: 204.

Gadjetlarga o‘z o‘rnida va joyida o‘rnatilgan kalkulyatorlardan foydalanishga odatlangan zamonaviy maktab o‘quvchilari uchun muammo tug‘diruvchi vazifalardan biri bu ikki yoki undan ortiq sonning eng katta umumiy bo‘luvchisini (GCD) topishdir.

Agar aslida nima so'ralayotgani noma'lum bo'lsa, hech qanday matematik masalani yechish mumkin emas. Buning uchun u yoki bu ibora nimani anglatishini bilishingiz kerak. matematikada ishlatiladi.

Umumiy tushunchalar va ta'riflar

Bilish kerak:

1. Agar ma'lum bir raqam turli xil narsalarni, masalan, to'qqiz ustun, o'n olti uyni hisoblash uchun ishlatilishi mumkin bo'lsa, bu tabiiydir. Ularning eng kichigi bitta bo'ladi.
2. Agar natural son boshqa natural songa boʻlinsa, kichik son kattaning boʻluvchisi deyiladi.
3. Agar ikki yoki undan ortiq turli sonlar ma'lum bir songa qoldiqsiz bo'linadigan bo'lsa, ular ikkinchisi ularning umumiy bo'luvchisi (OD) bo'lishini aytadilar.
4. ODlarning eng kattasi eng katta umumiy bo'luvchi (GCD) deb ataladi.
5. Bunday holda, sonning faqat ikkita tabiiy bo'luvchisi (o'zi va bitta) bo'lsa, u tub deb ataladi. Ularning eng kichigi ikkilikdir, bundan tashqari, bu ularning seriyasidagi yagona juft sondir.
6. Agar ikkita raqam bittaning maksimal umumiy bo'luvchisiga ega bo'lsa, ular ko'paytiriladi.
7. Ikki dan ortiq bo'luvchiga ega bo'lgan songa kompozit son deyiladi.
8. Matematikada bir-biriga ko'paytirilganda mahsulotning boshlang'ich qiymatini beradigan barcha tub omillar topilgan jarayon tub omillarga parchalanish deb ataladi. Bundan tashqari, kengayishdagi bir xil omillar bir necha marta sodir bo'lishi mumkin.

Matematikada quyidagi belgilar qabul qilinadi:

1. Bo'luvchilar D (45) = (1; 3; 5; 9; 45).
2. OD (8;18) = (1;2).
3. GCD (8;18) = 2.

GCDni topishning turli usullari

Javob berish uchun eng oson savol NODni qanday topish mumkin kichik son kattasining bo'luvchisi bo'lganda. Bu holda u eng katta umumiy bo'luvchi bo'ladi.

Masalan, GCD (15;45) = 15, GCD (48;24) = 24.

Ammo matematikada bunday holatlar juda kam uchraydi, shuning uchun GCD ni topish uchun murakkabroq usullar qo'llaniladi, garchi ishni boshlashdan oldin ushbu variantni tekshirish tavsiya etiladi.

Bosh omillarga parchalanish usuli

Agar siz ikki yoki undan ortiq turli raqamlarning GCD ni topishingiz kerak bo'lsa, ularning har birini oddiy omillarga ajratish kifoya, so'ngra ularning har birida mavjud bo'lganlarni ko'paytirish jarayonini amalga oshirish kifoya.

1-misol

GCD 36 va 90 ni qanday topish mumkinligini ko'rib chiqing:

1. 36 = 1*2*2*3*3;
2. 90 = 1*2*3*3*5;

GCD (36;90) = 1*2*3*3 = 18.

Keling, xuddi shu narsani qanday topishni ko'rib chiqaylik uchta raqam bo'lsa, masalan, 54; 162; 42.

Biz 36 ni qanday ajratishni allaqachon bilamiz, qolganlari bilan shug'ullanamiz:

1. 162 = 1*2*3*3*3*3;
2. 42 = 1*2*3*7;

Shunday qilib, GCD (36;162;42) = 1*2*3 = 6.

Shuni ta'kidlash kerakki, kengaytmada birlikni yozish mutlaqo ixtiyoriydir.

Yo'lni ko'rib chiqing faktorizatsiya qilish qanchalik oson, buning uchun chap tomonda kerakli sonni yozamiz, o'ngda esa oddiy bo'luvchilarni yozamiz.

Ustunlar bo'linish belgisi yoki oddiy vertikal chiziq bilan ajratilishi mumkin.

1. 36/2 biz bo'linish jarayonini davom ettiramiz;
2. yana 18/2;
3. 9/3 va yana;
4. 3/3 endi juda oddiy;
5. 1 - natija tayyor.

Kerakli 36 \u003d 2 * 2 * 3 * 3.

Evklid usuli

Bu variant insoniyatga qadimgi yunon tsivilizatsiyasi davridan beri ma'lum bo'lgan, u ancha sodda va buyuk matematik Evklidga tegishli, garchi ilgari juda o'xshash algoritmlar ishlatilgan bo'lsa ham. Ushbu usul quyidagi algoritmdan foydalanishdir, biz katta sonni qoldiq bilan kichikroq raqamga ajratamiz. Keyin bo'linuvchimizni qoldiqga bo'lamiz va bo'linish tugaguncha aylana bo'ylab shu tarzda harakat qilishni davom ettiramiz. Oxirgi qiymat kerakli eng katta umumiy bo'luvchiga aylanadi.

Keling, ushbu algoritmdan foydalanishga misol keltiramiz:

Keling, 816 va 252 uchun qaysi GCD ekanligini aniqlashga harakat qilaylik:

1. 816 / 252 = 3 va qolgan 60. Endi biz 252 ni 60 ga bo'lamiz;
2. 252 / 60 = 4 qolgan bu vaqt 12 bo'ladi. Keling, aylanma jarayonimizni davom ettiramiz, oltmishni o'n ikkiga bo'ling;
3. 60/12 = 5. Shu vaqtdan boshlab biz hech qanday qoldiqni olmadik, natijada tayyormiz, o'n ikki biz izlayotgan qiymat bo'ladi.

Shunday qilib, bizning jarayonimiz oxirida bizda NOD bor (816;252) = 12.

Agar ikkitadan ortiq qiymat ko'rsatilgan bo'lsa, GCD ni aniqlash zarur bo'lganda harakatlar

Ikki xil raqam mavjud bo'lganda nima qilish kerakligini allaqachon aniqlab oldik, endi agar mavjud bo'lsa, qanday harakat qilishni o'rganamiz. 3 yoki undan ko'p.

Ko'rinadigan murakkablikka qaramay, bu vazifa bizga hech qanday muammo tug'dirmaydi. Endi biz istalgan ikkita raqamni tanlaymiz va ular uchun izlayotgan qiymatni aniqlaymiz. Keyingi qadam, olingan natija va berilgan qiymatlarning uchinchisi uchun GCD ni topishdir. Keyin biz yana to'rtinchi beshinchi va boshqalar uchun bizga ma'lum bo'lgan printsipga muvofiq harakat qilamiz.

Xulosa

Shunday qilib, dastlab oldimizga qo'yilgan vazifaning katta murakkabligi bilan, aslida hamma narsa oddiy, asosiysi, bo'linish jarayonini xatosiz bajara olishdir va yuqorida tavsiflangan ikkita algoritmdan biriga yopishib oling.

Ikkala usul ham umumiy maktabda juda maqbul bo'lsa-da birinchi usul ancha keng tarqalgan.. Buning sababi, keyingi ta'lim mavzusini - eng katta umumiy ko'plik (LCM) ta'rifini o'rganishda asosiy omillarga bo'linish kerak bo'ladi. Shunga qaramay, yana bir bor ta'kidlash kerak - Evklid algoritmidan foydalanish hech qanday holatda xato deb hisoblanmaydi.

Video

Video yordamida siz eng katta umumiy bo'luvchini qanday topishni o'rganishingiz mumkin.

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.

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 yoqilgan 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 yoqilgan 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 d k, 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 mutlaq qiymatlari bilan almashtiramiz, 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