Највећи заједнички чинилац, такође познат као највећи заједнички делилац и највећи заједнички чинилац, односи се на највећи делилац који деле два или више целих бројева.
Највећи заједнички делилац а, б означава се као (а, б). Слично, највећи заједнички делилац а, б, ц се означава као (а, б, ц). Највећи заједнички делиоци више целих бројева имају исти предзнак.
Постоји много начина да се пронађе највећи заједнички делилац. Уобичајени фактори укључују основну факторизацију, кратку поделу, поделу у фази померања и више одузимања.
Концепт који одговара највећем заједничком делиоцу је најмањи заједнички вишекратник, а најмањи заједнички вишекратник а, б се бележи као [а, б].
Ако је број а дељив бројем б, а се назива вишекратник броја б, а б се назива делилац а.
И делиоци и вишекратници представљају однос једног целог броја према другом и не могу постојати сами. На пример, можемо само рећи да је 16 вишекратник одређеног броја, а 2 делилац одређеног броја, али не можемо рећи изоловано да је 16 вишеструки, а 2 делилац.
Највећи заједнички делилац (НЗД), такође назван највећи заједнички делилац (НЗД), два или више целих бројева је највећи позитиван број који их све дели тачно (без остатка).
На пример, НЗД бројева 18 и 24 је 6, јер је 6 највећи број који оба дели подједнако.
НЗД је користан за:
Поједностављивање разломака на њихове најниже чланове.
Растављање на факторе и решавање математичких једначина.
Свођење односа на њихов најједноставнији облик.
Решавање проблема теорије бројева који укључују дељивост или модуларну аритметику.
Проналажење заједничких образаца у целим бројевима или оптимизација алгоритама који се ослањају на понављајуће структуре.
Помаже у елиминисању сувишности и проналажењу ефикасности у математичким и реалним применама.
Постоји неколико метода за проналажење НЗД два броја:
Навођење чинилаца: Наведите све делитеље сваког броја и пронађите највећи који им је заједнички.
Распоређивање простих чинилаца: Разложите оба броја на њихове просте чиниоце и помножите их уобичајене.
Еуклидов алгоритам: Више пута одузимајте мањи број од већег или користите дељење са остацима док остатак не буде нула. Последњи остатак који није нула је НЗД.
Пример Еуклидовог алгоритма за НЗД(a, b):
НЗД(48, 18):
48 ÷ 18 = 2 остатак 12
18 ÷ 12 = 1 остатак 6
12 ÷ 6 = 2 остатак 0
→ НЗД је 6
Користите НЗД када:
Свођење разломака или односа на најједноставнији облик.
Решавање Диофантове једначине (једначине са целобројним решењима).
Оптимизација алгоритама који укључују циклусе, ротације или партиције.
Одређивање да ли су два броја релативно проста (тј. њихов НЗД је 1).
Подела елемената у групе са највећом могућом једнаком величином (нпр., равномерно дељење нечега међу људима или контејнерима).
НЗД је фундаменталан и у основној аритметици и у напреднијој теорији бројева или дизајну алгоритама.
