Пред да се продолжи со дефиницијата на концептот на најголем заеднички делител (GCD), неопходно е да се разбере што е генерално заеднички делител.
Познато е дека цел број може да има повеќе делители. Ние сме заинтересирани за истовремен пристап до нив од неколку цели броеви. Сметаме дека заедничкиот делител на неколку цели броеви е бројот што може да дејствува како делител за секој број од наведената серија.
На пример, броевите 8 и 12 ги имаат следните заеднички делители: 1 и 4. Ова може лесно да се потврди со пишување математички изрази: 8 = 4 ⋅ 2; 12 = 3 ⋅ 4.
Треба да се забележи дека секој број првично има најмалку два заеднички делители: кој било број е делив сам со себе без остаток, а исто така е делив со 1.
Одредување на најголемиот заеднички делител
Најголемиот заеднички делител (GCD) на два природни броја е најголемиот од природните броеви со кои можеме да поделиме два од нашите броеви. Ако вредноста на најголемиот заеднички делител на два природни броја е 1, тогаш овие броеви ги нарекуваме сопрости.
За два броја a и b, најголемиот заеднички делител е бројот со кој a и b може да се поделат без остаток. Овој израз е напишан на следниов начин: gcd (a, b) = c.
Друг начин да се напише GCD: (a, b) = c. Меѓутоа, во повеќето случаи се користи првата опција.
Значи, на пример, броевите 4 и 16 имаат најголем заеднички делител еднаков на 4. Ајде да напишеме: gcd (4, 16) = 4.
Ајде да опишеме како дојдовме до овој резултат:
- Ги напишавме сите делители на бројот 4. Добивме: 4, 2, 1.
- Следно, ги насликавме сите делители на 16. Добивме: 16, 8, 4, 2, 1.
- Избравме делители кои се заеднички и за 4 и за 16. Добивме: 4, 2, 1.
- Од добиените заеднички делители, беше избран најголемиот. Ова е 4.
- Го добиваме одговорот: за броевите 4 и 16 GCD е 4.
Слично, можете да го најдете GCD за три или повеќе цели броеви. Во овој случај, тоа ќе биде најголемиот цел број со кој можете да ги поделите сите броеви од предложената серија.
Значи, на пример, најголемиот делител за цели броеви 6, 12, 18, 42 ќе биде бројот 6, односно gcd (6, 12, 18, 42) = 6. Одговорот е добиен со помош на алгоритам слично на она што беше опишано погоре - за броеви од серија, сите делители беа последователно испишани, по што беа избрани најголемите од нив.
Својства на GCD
Најголемиот заеднички делител има голем број на својства кои ќе бидат релевантни за GCD на позитивни цели броеви со делители поголеми од нула.
Својство 1
Од менување на местата на броевите, конечната вредност на GCD нема да се промени. Оваа изјава можете да ја напишете вака:
- gcd(a, b) = gcd(b, a).
Својство 2
Ако a е делив со b, тогаш множеството заеднички делители на a и b е исто со множеството делители на b. Напишано вака:
- gcd(a, b) = b.
Докажаното својство на најголем делител може да се користи за да се најде gcd на два броја кога еден од нив е делив со другиот. Во овој случај, GCD е еднаков на еден од овие броеви, со кој друг број се дели.
На пример:
- gcd(12, 4) = 4.
Слично:
- gcd(10, 1) = 1.
Својство 3
Ако a = bq + c, каде што a, b, c и q се цели броеви, тогаш множеството заеднички делители на a и b е исто како и множеството заеднички делители на b и c.
Еднаквоста gcd (a, b) = gcd (b, c) станува валидна.
Својство 4
Изразот gcd(ma, mb) = m ⋅ gcd(a, b) е точно под услов m да е кој било природен број.
Својство 5
Да речеме, p е секој заеднички делител на a и b.
Потоа:
- gcd(a / p, b / p) = gcd(a, b) / стр.
Ако p = gcd(a, b), добиваме:
- gcd (a / gcd (a, b), b / gcd (a, b)) = 1,
Така, броевите a / gcd (a, b) и b / gcd (a, b) се копрости.
Својство 6
Било кои два броја имаат барем еден заеднички делител - ова е бројот 1.
Познавањето на теоретските основи на концептот GCD, како и практичните вештини во неговото дефинирање, се неопходни за работа со обични дропки. Покрај тоа, GCD е тесно поврзан со друга математичка единица - најмалку заеднички делител. Двете дефиниции обично се изучуваат како дел од стандардната училишна програма.
