Садржај

• Кораци
• Метода 1 од 2: Алгоритам разделника
• Метод 2 од 2: Главни фактори
• Савјети

Највећи заједнички делитељ (ГЦД) два цела броја највећи је цео број који дели сваки од тих бројева. На пример, гцд за 20 и 16 је 4 (и 16 и 20 имају велике делитеље, али нису уобичајени - на пример, 8 је делитељ 16, али не и делитељ 20). Постоји једноставан и систематичан метод за проналажење ГЦД -а, назван "Еуклидов алгоритам". Овај чланак ће вам показати како пронаћи највећи заједнички делилац два цела броја.

Кораци

Метода 1 од 2: Алгоритам разделника

1. 1 Изоставите све знакове минус.
2. 2 Научите терминологију: када поделите 32 са 5,
   • 32 - дивиденда
   • 5 - делилац
   • 6 - приватно
   • 2 - остатак
3. 3 Одреди већи број. Биће дељив, а мањи број делилац.
4. 4 Запишите следећи алгоритам: (дивиденда) = (делилац) * (количник) + (остатак)
5. 5 Већи број ставите на место дивиденде, а мањи на место делитеља.
6. 6 Одредите колико је пута већи број подељен са мањим и упишите резултат уместо количника.
7. 7 Пронађите остатак и упишите га на одговарајуће место у алгоритму.
8. 8 Поново напишите алгоритам, али (А) напишите претходни делилац као нову дивиденду, и (Б) претходни остатак као нови делитељ.
9. 9 Понављајте претходни корак док остатак не буде 0.
10. 10 Последњи делилац биће највећи заједнички делилац (ГЦД).
11. 11 На пример, пронађимо ГЦД за 108 и 30:
12. 12 Обратите пажњу на то како бројеви 30 и 18 из првог реда чине други ред. Затим 18 и 12 чине трећи ред, а 12 и 6 чине четврти ред. Вишеструки бројеви 3, 1, 1 и 2 се не користе. Они представљају број пута када је дивиденда дељива са делитељем и стога су јединствени за сваки ред.

Метод 2 од 2: Главни фактори

1. 1 Изоставите све знакове минус.
2. 2 Нађи просте чиниоце бројева. Представите их као што је приказано на слици.
   • На пример, за 24 и 18:
     • 24-2 к 2 к 2 к 3
     • 18-2 к 3 к 3
   • На пример, за 50 и 35:
     • 50-2 к 5 к 5
     • 35-5 к 7
3. 3 Пронађите заједничке основне факторе.
   • На пример, за 24 и 18:
     • 24- 2 к 2 к 2 к 3
     • 18- 2 Икс 3 к 3
   • На пример, за 50 и 35:
     • 50 - 2 к 5 к 5
     • 35- 5 к 7
4. 4 Помножите заједничке просте факторе.
   • За 24 и 18, помножите 2 и 3 и добити 6... 6 је највећи заједнички именитељ од 24 и 18.
   • Нема се шта множити за 50 и 35. 5 То је једини заједнички основни фактор, а то је ГЦД.
5. 5 Маде!

Савјети

• Један од начина да се ово напише је: дивиденд> мод делилац> = остатак; ГЦД (а, б) = б ако је мод б = 0, а гцд (а, б) = гцд (б, мод б) у супротном.
• Као пример, пронађимо ГЦД (-77.91). Прво, користите 77 уместо -77: ГЦД (-77.91) се претвара у ГЦД (77.91). 77 је мање од 91, па их морамо замијенити, али размислите о томе како алгоритам ради ако то не учинимо. Приликом израчунавања 77 мод 91, добијамо 77 (77 = 91 к 0 + 77). Пошто ово није нула, разматрамо ситуацију (б, а мод б), односно ГЦД (77,91) = ГЦД (91,77). 91 мод 77 = 14 (14 је остатак). Није нула, па ГЦД (91,77) постаје ГЦД (77,14). 77 мод 14 = 7. Ово није нула, па ГЦД (77.14) постаје ГЦД (14.7). 14 мод 7 = 0 (пошто је 14/7 = 2 без остатка). Одговор: ГЦД (-77.91) = 7.
• Описана метода је веома корисна за поједностављивање разломака. У горњем примеру: -77/91 = -11/13, пошто је 7 највећи заједнички именитељ од -77 и 91.
• Ако су а и б једнаки нули, онда је сваки број различит од нуле њихов делилац, па у овом случају не постоји ГЦД (математичари једноставно верују да је највећи заједнички делилац 0 и 0 0).