Калкулатор за НОД

Други алатки

Калкулатор за површина{$ ',' | translate $}
Калкулатор за периметар{$ ',' | translate $}
Калкулатор за волумен{$ ',' | translate $}
Таблица множење{$ ',' | translate $}
Менделеев систем{$ ',' | translate $}
Калкулатор за матрици{$ ',' | translate $}
Калкулатор за НОК{$ ',' | translate $}
Калкулатор за тригонометрија{$ ',' | translate $}

Калкулатор за најголем заеднички делител

Пред да се продолжи со дефиницијата на концептот на најголем заеднички делител (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 е тесно поврзан со друга математичка единица - најмалку заеднички делител. Двете дефиниции обично се изучуваат како дел од стандардната училишна програма.

Како да го најдете најголемиот заеднички делител (GCF)

Наоѓањето на најголемиот заеднички делител (gcd) е прилично популарна задача. Оваа акција ни помага да извршиме пресметки во кои се појавуваат обични дропки.

Методи за наоѓање GCD

Постојат неколку трикови за да се најде најголемиот заеднички делител. Ќе ги разгледаме најпопуларните од нив.

Наоѓање на GCD со разложување на броеви на прости множители

Овој метод е еден од најчесто користените во решавањето математички проблеми.

Алгоритмот за одредување на GCD со распаѓање на прости фактори се состои од следниве чекори:

Броевите ги претставуваме како прости фактори. На пример, бројот 20 може да се претстави како производ од 2 ⋅ 2 ⋅ 5.
Изберете ги факторите што ќе бидат присутни во двете проширувања.
Најдете го производот на овие фактори.

Ајде да разгледаме неколку примери за примена на овој алгоритам во пракса:

Определете го GCD на броевите 12 и 8.

Разложувајте ги 12 и 8 на прости множители:

12 = 2 ⋅ 2 ⋅ 3.
8 = 2 ⋅ 2 ⋅ 2.

Гледаме кои фактори се присутни во двете проширувања. Најдете: 2 и 2.

Ги множиме факторите и добиваме:

2 ⋅ 2 = 4.

Одговор: gcd (12, 8) = 4.

Определете го GCD на броевите 75 и 150.

Секвенцата на решенија е слична на претходниот пример.

Да ги претставиме 75 и 150 како прости фактори:

75 = 3 ⋅ 5 ⋅ 5.
150 = 2 ⋅ 3 ⋅ 5 ⋅ 5.

Определете ги факторите што се повторуваат во двете проширувања: 3, 5 и 5.

Добиените броеви ги множиме заедно: 3 ⋅ 5 ⋅ 5 = 75.

Одговор: gcd (75, 150) = 75.

Определете го GCD на броевите 9 и 5.

Овој пример користи прости броеви чиј множител може да биде само 1.

При факторинг 9 и 5 во прости множители, ќе видиме дека тие ги немаат истите фактори:

5 = 5.
9 = 3 ⋅ 3.

Мора да се запомни дека овој случај е посебен. Таквите броеви се сопрости, а нивниот заеднички делител е еден.

Евклидовиот алгоритам

Овој алгоритам го добил името по старогрчкиот математичар Евклид, кој прв го опишал во неговите дела (7-ма и 10-та книга од „Почетоци“). Познато е дека Евклид не бил автор на овој алгоритам. Сепак, тој се смета за еден од најстарите алгоритми што се користат денес.

Евклидовиот алгоритам го олеснува пресметувањето на најголемиот заеднички делител на два позитивни броја.

За да се најде GCD (a, b), овој алгоритам изгледа вака:

Ако a = 0 тогаш gcd(a, b) = b затоа што gcd(0, b) = b и алгоритмот запира.
Ако b = 0 тогаш gcd(a, b) = a затоа што gcd(a, 0) = a и алгоритмот запира.
Поделете a со b со остаток (a = b ⋅ q + r)
Најдете gcd(b, r) користејќи го Евклидовиот алгоритам бидејќи gcd(a, b) = gcd(b, r).

За да ја потврдите ефективноста на методот во пракса, разгледајте пример.

Потребно е да се одреди GCD на броевите 270 и 192.

a = 270, b = 192.
a ≠ 0.
b ≠ 0.

Поделете го a со b, добиваме:

270 / 192 = 1 (остатокот е 78).

Резултатот може да го напишете како: 270 = 192 ⋅ 1 + 78.

Следно, ќе пресметаме gcd (192, 78), бидејќи gcd (270, 192) = gcd (192, 78).

Да продолжиме понатаму.

a = 192, b = 78.
a ≠ 0.
b ≠ 0.

Поделете го a со b, добиваме:

192 / 78 = 2 (остатокот е 36).

Може да се напише како:

192 = 78 ⋅ 2 + 36.

Пресметај gcd(78, 36) бидејќи gcd(192, 78) = gcd(78, 36).

a = 78, b = 36.
a ≠ 0.
b ≠ 0.

Поделете го a со b, добиваме:

78 / 36 = 2 (остатокот е 0).

Ајде да го напишеме резултатот како:

78 = 36 ⋅ 2 + 6.

Пресметај го gcd(36, 6) бидејќи gcd(78, 36) = gcd(36, 6).

a = 36, b = 6.
a ≠ 0.
b ≠ 0.

Поделете го A со B, добиваме 36 / 6 = 6 (остатокот е 0).

Напишете го резултатот во следнава форма:

36 = 6 ⋅ 6 + 0.

Следно наоѓаме gcd(6, 0) бидејќи gcd(36, 6) = gcd(6, 0).

a = 6, b = 0.
a ≠ 0.
b = 0.

Како резултат имаме:

gcd(6, 0) = 6.

Така, ја имаме следната низа на пресметки:

gcd(270, 192) = gcd(192, 78) = gcd(78, 36) = gcd(36, 6) = gcd(6, 0) = 6.

Како резултат, го имаме одговорот:

gcd(270, 192) = 6.

Секој од методите за пребарување опишани погоре има свои предности и недостатоци. Првиот метод е одличен за работа со релативно едноставни примери, за разлика од вториот, кој може да се користи за решавање на посложени математички проблеми.