Tarkib

• Qadamlar
• 2 -usul 1: Ajratuvchi algoritmi
• 2 -usul 2: asosiy omillar
• Maslahatlar

Ikki butun sonning eng katta umumiy bo'linuvchisi (GCD) - bu sonlarning har birini ajratadigan eng katta butun son. Masalan, 20 va 16 uchun gcd - 4 (16 va 20 da katta bo'linuvchilarga ega, lekin ular keng tarqalgan emas - masalan, 8 - 16 ga bo'linadi, lekin 20 - bo'luvchi emas). GCDni topishning "Evklid algoritmi" deb nomlangan oddiy va tizimli usuli mavjud. Ushbu maqola sizga ikkita butun sonning eng katta umumiy bo'linuvchisini qanday topishni ko'rsatib beradi.

Qadamlar

2 -usul 1: Ajratuvchi algoritmi

1. 1 Har qanday minus belgilarini qoldiring.
2. 2 Terminologiyani o'rganing: 32 ni 5 ga bo'lganda,
   • 32 - dividend
   • 5 - bo'luvchi
   • 6 - shaxsiy
   • 2 - qoldiq
3. 3 Raqamlarning eng kattasini aniqlang. Bu bo'linadigan bo'ladi, va kichik soni bo'luvchi bo'ladi.
4. 4 Quyidagi algoritmni yozing: (dividend) = (bo'luvchi) * (qism) + (qolgan)
5. 5 Dividend o'rniga kattaroq raqamni va bo'luvchi o'rniga kichikroq raqamni qo'ying.
6. 6 Katta sonning kichik soniga necha marta bo'linishini toping va natijani qismning o'rniga yozing.
7. 7 Qolganini toping va algoritmda kerakli joyga yozing.
8. 8 Algoritmni yana yozing, lekin (A) oldingi bo'linuvchini yangi dividend sifatida, (B) oldingi qoldiqni yangi bo'luvchi sifatida yozing.
9. 9 Qolganlari 0 bo'lgunga qadar oldingi qadamni takrorlang.
10. 10 Oxirgi bo'luvchi eng katta umumiy bo'luvchi bo'ladi (GCD).
11. 11 Masalan, 108 va 30 uchun GCDni topamiz:
12. 12 E'tibor bering, birinchi qatordan 30 va 18 raqamlari ikkinchi qatorni qanday tashkil qiladi. Keyin 18 va 12 uchinchi qatorni, 12 va 6 esa to'rtinchi qatorni tashkil qiladi. 3, 1, 1 va 2 sonlari ishlatilmaydi. Ular dividendni bo'luvchi tomonidan bo'linish sonini ifodalaydi va shuning uchun har bir qatorga xosdir.

2 -usul 2: asosiy omillar

1. 1 Har qanday minus belgilarini qoldiring.
2. 2 Raqamlarning asosiy omillarini toping. Ularni rasmda ko'rsatilgandek taqdim eting.
   • Masalan, 24 va 18 uchun:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • Masalan, 50 va 35 uchun:
     • 50 x 2 x 5 x 5
     • 35- 5 x 7
3. 3 Umumiy asosiy omillarni toping.
   • Masalan, 24 va 18 uchun:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • Masalan, 50 va 35 uchun:
     • 50 - 2 x 5 x 5
     • 35- 5 x 7
4. 4 Umumiy asosiy omillarni ko'paytiring.
   • 24 va 18 uchun ko'paytiring 2 va 3 va oling 6... 6 - 24 va 18 ning eng katta umumiy mohiyati.
   • 50 va 35 ga ko'paytirish uchun hech narsa yo'q. 5 Bu yagona asosiy omil va bu GCD.
5. 5 Ishlab chiqarilgan!

Maslahatlar

• Buni yozishning bir usuli: dividend> mod bo'luvchi> = qoldiq; Agar mod b = 0 bo'lsa, GCD (a, b) = b, aks holda gcd (a, b) = gcd (b, a mod b).
• Misol tariqasida GCD (-77.91) ni topamiz. Birinchidan, -77 o'rniga 77 dan foydalaning: GCD (-77.91) GCD (77.91) ga aylanadi. 77 - 91dan past, shuning uchun biz ularni almashtirishimiz kerak, lekin agar qilmasak, algoritm qanday ishlashini ko'rib chiqing. 77 mod 91 ni hisoblashda biz 77 (77 = 91 x 0 + 77) ni olamiz. Bu nolga teng bo'lmaganligi uchun biz vaziyatni (b, a b mod), ya'ni GCD (77.91) = GCD (91.77) deb hisoblaymiz. 91 mod 77 = 14 (qolgan 14). Bu nol emas, shuning uchun GCD (91.77) GCD (77.14) ga aylanadi. 77 mod 14 = 7. Bu nol emas, shuning uchun GCD (77.14) GCD (14.7) ga aylanadi. 14 mod 7 = 0 (14/7 = 2 qolganidan beri). Javob: GCD (-77.91) = 7.
• Ta'riflangan usul kasrlarni soddalashtirish uchun juda foydali. Yuqoridagi misolda: -77/91 = -11/13, chunki 7 -77 va 91 ning eng katta umumiy ayiruvchisi.
• Agar a va b nolga teng bo'lsa, u holda har qanday nol bo'lmagan raqam ularning bo'luvchisidir, shuning uchun bu holatda GCD bo'lmaydi (matematiklar shunchaki 0 ​​va 0 ning eng katta umumiy bo'linuvchisi 0 ga ishonishadi).