Мазмұны

• Қадамдар
• 2 -ші әдіс 1: Бөлгіш алгоритмі
• 2 -ші әдіс 2: Prime Factors
• Кеңестер

Екі бүтін санның ең үлкен ортақ бөлгіші (GCD) - бұл сандардың әрқайсысын бөлетін ең үлкен бүтін сан. Мысалы, 20 және 16 үшін gcd - 4 (16 да, 20 да үлкен бөлгіштерге ие, бірақ олар ортақ емес - мысалы, 8 - 16 -ға бөлінуші, бірақ 20 -ға бөлінуші емес). GCD табудың «Евклид алгоритмі» деп аталатын қарапайым және жүйелі әдісі бар. Бұл мақалада екі бүтін санның ең үлкен ортақ бөлгішін қалай табуға болатындығы көрсетіледі.

Қадамдар

2 -ші әдіс 1: Бөлгіш алгоритмі

1. 1 Кез келген минус белгілерді алып тастаңыз.
2. 2 Терминологияны біліңіз: 32 -ні 5 -ке бөлгенде
   • 32 - дивиденд
   • 5 - бөлуші
   • 6 - жеке
   • 2 - қалдық
3. 3 Сандардың үлкенін анықтаңыз. Бұл бөлінетін болады, ал кіші сан бөлгіш болады.
4. 4 Келесі алгоритмді жазыңыз: (дивиденд) = (бөлуші) * (үлес) + (қалдығы)
5. 5 Дивиденд орнына үлкен санды, ал бөлгіш орнына кішісін қойыңыз.
6. 6 Үлкен санның кішіге неше есе бөлінетінін табыңыз және үзіндінің орнына нәтижені жазыңыз.
7. 7 Қалғанын тауып, оны алгоритмге сәйкес орынға жазыңыз.
8. 8 Алгоритмді қайтадан жазыңыз, бірақ (A) алдыңғы бөлгішті жаңа дивиденд ретінде, (B) алдыңғы қалдықты жаңа бөлгіш ретінде жазыңыз.
9. 9 Алдыңғы қадамды қалдық 0 болғанша қайталаңыз.
10. 10 Соңғы бөлгіш ең үлкен ортақ бөлгіш болады (GCD).
11. 11 Мысалы, 108 және 30 үшін GCD табайық:
12. 12 Бірінші жолдан 30 және 18 сандары екінші жолды қалай құрайтынына назар аударыңыз. Содан кейін 18 мен 12 үшінші қатарды, ал 12 мен 6 төртінші қатарды құрайды. 3, 1, 1 және 2 еселіктері қолданылмайды. Олар дивидендті бөлушіге қанша рет бөлетінін білдіреді, сондықтан әр жолға ғана тән.

2 -ші әдіс 2: Prime Factors

1. 1 Кез келген минус белгілерді алып тастаңыз.
2. 2 Сандардың жай көбейткіштерін табыңыз. Оларды суретте көрсетілгендей көрсетіңіз.
   • Мысалы, 24 және 18 үшін:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • Мысалы, 50 және 35 үшін:
     • 50- 2 x 5 x 5
     • 35- 5 х 7
3. 3 Негізгі негізгі факторларды табыңыз.
   • Мысалы, 24 және 18 үшін:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • Мысалы, 50 және 35 үшін:
     • 50 - 2 х 5 x 5
     • 35- 5 x 7
4. 4 Негізгі факторларды көбейтіңіз.
   • 24 пен 18 үшін көбейтіңіз 2 және 3 және алыңыз 6... 6 - 24 пен 18 санының ең үлкен ортақ белгісі.
   • 50 мен 35 -ке көбейтетін ештеңе жоқ. 5 Жалғыз негізгі фактор болып табылады және бұл GCD.
5. 5 Жасалды!

Кеңестер

• Мұны жазудың бір жолы: дивиденд> mod divider> = remainder; GCD (a, b) = b, егер b = 0 модулі, ал gcd (a, b) = gcd (b, a b b), әйтпесе.
• Мысал ретінде GCD (-77.91) табайық. Біріншіден, -77 орнына 77 пайдаланыңыз: GCD (-77.91) GCD (77.91) түрлендіреді. 77 91 -ден аз, сондықтан біз оларды ауыстыруымыз керек, бірақ егер олай болмаса, алгоритм қалай жұмыс істейтінін қарастырыңыз. 77 mod 91 -ді есептегенде біз 77 аламыз (77 = 91 x 0 + 77). Бұл нөл емес болғандықтан, біз жағдайды қарастырамыз (b, a b mod), яғни GCD (77.91) = GCD (91.77). 91 режимі 77 = 14 (14 - қалдық). Бұл нөл емес, сондықтан GCD (91.77) GCD (77.14) болады. 77 mod 14 = 7. Бұл нөл емес, сондықтан GCD (77.14) GCD (14.7) болады. 14 mod 7 = 0 (14/7 = 2 болғандықтан қалдықсыз). Жауап: GCD (-77.91) = 7.
• Сипатталған әдіс бөлшектерді жеңілдету үшін өте пайдалы. Жоғарыдағы мысалда: -77/91 = -11/13, өйткені 7 -77 мен 91 -дің ең үлкен ортақ бөлгіші.
• Егер а мен b нөлге тең болса, онда кез келген нөлден басқа сан олардың бөлгіші болып табылады, сондықтан бұл жағдайда GCD болмайды (математиктер 0 мен 0 -дің ең үлкен ортақ бөлгіші 0 деп есептейді).