Дефиниција на броеви со нок и нок. Наоѓање на GCD со помош на Евклидов алгоритам и користење на проста факторизација

Да го продолжиме разговорот за најмалиот заеднички множител, кој го започнавме во делот „LCM - најмал заеднички множител, дефиниција, примери“. Во оваа тема ќе разгледаме начини за наоѓање на LCM за три или повеќе броеви, а ќе го разгледаме и прашањето како да се најде LCM на негативен број.

Пресметување на најмалку заедничко повеќекратно (LCM) преку GCD

Веќе ја утврдивме врската помеѓу најмалиот заеднички множител и најголемиот заеднички делител. Сега да научиме како да го одредиме LCM преку GCD. Прво, ајде да дознаеме како да го направиме тоа за позитивни бројки.

Дефиниција 1

Можете да го најдете најмалиот заеднички множител преку најголемиот заеднички делител користејќи ја формулата LCM (a, b) = a · b: GCD (a, b).

Пример 1

Треба да го пронајдете LCM на броевите 126 и 70.

Решение

Да земеме a = 126, b = 70. Ајде да ги замениме вредностите во формулата за пресметување на најмалиот заеднички множител преку најголемиот заеднички делител LCM (a, b) = a · b: GCD (a, b) .

Го наоѓа gcd на броевите 70 и 126. За ова ни треба Евклидов алгоритам: 126 = 70 1 + 56, 70 = 56 1 + 14, 56 = 14 4, затоа GCD (126 , 70) = 14 .

Ајде да го пресметаме LCM: LCD (126, 70) = 126 70: GCD (126, 70) = 126 70: 14 = 630.

Одговор: LCM(126, 70) = 630.

Пример 2

Најдете ги бројот 68 и 34.

Решение

GCD во овој случај не е тешко да се најде, бидејќи 68 е делив со 34. Да го пресметаме најмалиот заеднички множител користејќи ја формулата: LCM (68, 34) = 68 34: GCD (68, 34) = 68 34: 34 = 68.

Одговор: LCM(68, 34) = 68.

Во овој пример, го користевме правилото за наоѓање на најмал заеднички множител на позитивните цели броеви a и b: ако првиот број е делив со вториот, LCM на тие броеви ќе биде еднаков на првиот број.

Наоѓање на LCM со факторингирање на броеви во прости множители

Сега да го погледнеме методот за наоѓање на LCM, кој се заснова на факторингирање на броеви во прости множители.

Дефиниција 2

За да го најдеме најмалиот заеднички множител, треба да извршиме неколку едноставни чекори:

  • го составуваме производот на сите прости множители на броевите за кои треба да го најдеме LCM;
  • ги исклучуваме сите основни фактори од нивните добиени производи;
  • производот добиен по елиминирање на заедничките прости множители ќе биде еднаков на LCM на дадените броеви.

Овој метод за наоѓање на најмал заеднички множител се заснова на еднаквоста LCM (a, b) = a · b: GCD (a, b). Ако ја погледнете формулата, ќе ви стане јасно: производот на броевите a и b е еднаков на производот на сите фактори кои учествуваат во разградувањето на овие два броја. Во овој случај, gcd на два броја е еднаков на производот на сите прости множители кои се истовремено присутни во факторизациите на овие два броја.

Пример 3

Имаме два броја 75 и 210. Можеме да ги факторизираме на следниов начин: 75 = 3 5 5И 210 = 2 3 5 7. Ако го составите производот од сите множители на двата оригинални броеви, ќе добиете: 2 3 3 5 5 5 7.

Ако ги исклучиме факторите заеднички за двата броја 3 и 5, добиваме производ од следнава форма: 2 3 5 5 7 = 1050. Овој производ ќе биде нашиот LCM за броевите 75 и 210.

Пример 4

Најдете го LCM на броеви 441 И 700 , факторингирајќи ги двата броја во прости множители.

Решение

Да ги најдеме сите прости множители на броевите дадени во условот:

441 147 49 7 1 3 3 7 7

700 350 175 35 7 1 2 2 5 5 7

Добиваме два синџири на броеви: 441 = 3 3 7 7 и 700 = 2 2 5 5 7.

Производот на сите фактори кои учествувале во разградувањето на овие броеви ќе има форма: 2 2 3 3 5 5 7 7 7. Ајде да најдеме заеднички фактори. Ова е бројот 7. Да го исклучиме од вкупниот производ: 2 2 3 3 5 5 7 7. Излегува дека НОК (441, 700) = 2 2 3 3 5 5 7 7 = 44 100.

Одговор: LOC(441, 700) = 44.100.

Да дадеме уште една формулација на методот за пронаоѓање на LCM со разложување на броевите во прости множители.

Дефиниција 3

Претходно, ние исклучивме од вкупниот број на фактори заеднички за двата броја. Сега ќе го направиме поинаку:

  • Да ги факторизираме двата броја во прости множители:
  • на производот на простите множители на првиот број додадете ги множителите што недостасуваат од вториот број;
  • го добиваме производот, кој ќе биде саканиот LCM од два броја.

Пример 5

Да се ​​вратиме на броевите 75 и 210, за кои веќе го баравме LCM во еден од претходните примери. Ајде да ги поделиме на едноставни фактори: 75 = 3 5 5И 210 = 2 3 5 7. На производот од факторите 3, 5 и 5 броеви 75 додадете ги факторите што недостасуваат 2 И 7 броеви 210. Добиваме: 2 · 3 · 5 · 5 · 7 .Ова е LCM на броевите 75 и 210.

Пример 6

Неопходно е да се пресмета LCM на броевите 84 и 648.

Решение

Да ги факторизираме броевите од условот во едноставни фактори: 84 = 2 2 3 7И 648 = 2 2 2 3 3 3 3. Да ги додадеме на производот факторите 2, 2, 3 и 7 броеви 84 недостасуваат фактори 2, 3, 3 и
3 броеви 648. Го добиваме производот 2 2 2 3 3 3 3 7 = 4536.Ова е најмалиот заеднички множител од 84 и 648.

Одговор: LCM (84, 648) = 4.536.

Наоѓање на LCM на три или повеќе броеви

Без оглед на тоа со колку броеви имаме работа, алгоритмот на нашите дејства секогаш ќе биде ист: последователно ќе го најдеме LCM на два броја. Постои теорема за овој случај.

Теорема 1

Да претпоставиме дека имаме цели броеви a 1 , a 2 , ... , a k. НОК m kовие броеви се наоѓаат со секвенцијално пресметување на m 2 = LCM (a 1, a 2), m 3 = LCM (m 2, a 3), ..., m k = LCM (m k − 1, a k).

Сега да погледнеме како теоремата може да се примени за да се решат конкретни проблеми.

Пример 7

Треба да го пресметате најмалиот заеднички множител од четирите броеви 140, 9, 54 и 250 .

Решение

Да ја воведеме ознаката: a 1 = 140, a 2 = 9, a 3 = 54, a 4 = 250.

Да почнеме со пресметување на m 2 = LCM (a 1 , a 2) = LCM (140, 9). Да го примениме Евклидов алгоритам за да го пресметаме GCD на броевите 140 и 9: 140 = 9 15 + 5, 9 = 5 1 + 4, 5 = 4 1 + 1, 4 = 1 4. Добиваме: GCD (140, 9) = 1, GCD (140, 9) = 140 9: GCD (140, 9) = 140 9: 1 = 1.260. Затоа, m 2 = 1.260.

Сега да пресметаме користејќи го истиот алгоритам m 3 = LCM (m 2 , a 3) = LCM (1 260, 54). При пресметките добиваме m 3 = 3 780.

Треба само да пресметаме m 4 = LCM (m 3 , a 4) = LCM (3 780, 250). Го следиме истиот алгоритам. Добиваме m 4 = 94 500.

LCM на четирите броеви од условот на примерот е 94500.

Одговор:НОК (140, 9, 54, 250) = 94.500.

Како што можете да видите, пресметките се едноставни, но доста трудоинтензивни. За да заштедите време, можете да одите на друг начин.

Дефиниција 4

Ви го нудиме следниов алгоритам на дејства:

  • ги разложуваме сите броеви на прости множители;
  • на производот од множителите од првиот број ги додаваме множителите што недостасуваат од производот на вториот број;
  • на производот добиен во претходната фаза ги додаваме факторите што недостасуваат од третиот број итн.;
  • добиениот производ ќе биде најмалиот заеднички множител од сите броеви од условот.

Пример 8

Треба да го пронајдете LCM на пет броеви 84, 6, 48, 7, 143.

Решение

Да ги пресметаме сите пет броеви во прости множители: 84 = 2 2 3 7, 6 = 2 3, 48 = 2 2 2 2 3, 7, 143 = 11 13. Простите броеви, што е бројот 7, не можат да се вклучат во прости множители. Таквите броеви се совпаѓаат со нивното распаѓање на прости множители.

Сега да го земеме производот на простите множители 2, 2, 3 и 7 од бројот 84 и да ги додадеме множителите што недостасуваат од вториот број. Бројот 6 го разложивме на 2 и 3. Овие фактори се веќе во производот од првиот број. Затоа, ги испуштаме.

Продолжуваме да ги собираме множителите што недостасуваат. Да преминеме на бројот 48, од производот на чии прости множители земаме 2 и 2. Потоа го собираме простиот фактор 7 од четвртиот број и множителите 11 и 13 од петтиот. Добиваме: 2 2 2 2 3 7 11 13 = 48.048. Ова е најмалиот заеднички множител од оригиналните пет броеви.

Одговор: LCM(84, 6, 48, 7, 143) = 48.048.

Наоѓање на најмал заеднички множител на негативни броеви

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

Пример 9

LCM (54, − 34) = LCM (54, 34) и LCM (− 622, − 46, − 54, − 888) = LCM (622, 46, 54, 888).

Ваквите дејствија се дозволени поради фактот што ако го прифатиме тоа аИ − а- спротивни броеви,
тогаш множеството множители на некој број асе совпаѓа со множеството множители на некој број − а.

Пример 10

Неопходно е да се пресмета LCM на негативни броеви − 145 И − 45 .

Решение

Да ги замениме бројките − 145 И − 45 на нивните спротивни броеви 145 И 45 . Сега, користејќи го алгоритмот, го пресметуваме LCM (145, 45) = 145 · 45: GCD (145, 45) = 145 · 45: 5 = 1.305, откако претходно го одредивме GCD користејќи го Евклидов алгоритам.

Добиваме дека LCM на броевите е − 145 и − 45 еднакви 1 305 .

Одговор: LCM (− 145, − 45) = 1.305.

Доколку забележите грешка во текстот, означете ја и притиснете Ctrl+Enter

Евклидовиот алгоритаме алгоритам за наоѓање на најголемиот заеднички делител (GCD) на пар цели броеви.

Најголем заеднички делител (GCD)е број кој дели два броја без остаток и самиот е делив без остаток со кој било друг делител на дадените два броја. Едноставно кажано, ова е најголемиот број со кој два броја за кои се бара gcd може да се поделат без остаток.

Алгоритам за наоѓање GCD со делење

  1. Поделете го поголемиот број со помалиот број.
  2. Ако се подели без остаток, тогаш помалиот број е GCD (треба да излезете од циклусот).
  3. Ако има остаток, тогаш поголемиот број заменете го со остатокот од делењето.
  4. Да преминеме на точка 1.

Пример:
Најдете gcd за 30 и 18.
30 / 18 = 1 (остаток 12)
18 / 12 = 1 (остаток 6)
12 / 6 = 2 (остаток 0)
Крај: GCD е делител на 6.
GCD (30, 18) = 6

a = 50 b = 130 додека a != 0 и b != 0 : ако a > b: a = a % b друго : b = b % a печатење (a + b)

Во јамката, остатокот од поделбата се запишува на променливата a или b. Јамката завршува кога барем една од променливите е нула. Ова значи дека другиот содржи gcd. Сепак, не знаеме кој точно. Затоа, за GCD го наоѓаме збирот на овие променливи. Бидејќи една од променливите е нула, таа нема ефект врз резултатот.

Алгоритам за наоѓање GCD со одземање

  1. Одземете го помалиот број од поголемиот број.
  2. Ако резултатот е 0, тоа значи дека броевите се еднакви еден на друг и се GCD (треба да излезете од јамката).
  3. Ако резултатот од одземањето не е еднаков на 0, тогаш поголемиот број заменете го со резултатот од одземањето.
  4. Да преминеме на точка 1.

Пример:
Најдете gcd за 30 и 18.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 - 6 = 0
Крај: GCD е минуенд или подзаконски.
GCD (30, 18) = 6

a = 50 b = 130 додека a != b: ако a > b: a = a - b друго : b = b - печатење (а)

Деленик е цел број кој дели друг цел број без да остави остаток. За неколку броеви, можете да најдете заеднички фактори, меѓу кои ќе бидат најголемите. Тоа е најголемиот заеднички делител кој има голем број корисни својства.

Најголем заеднички делител

Делител на цел број А е цел број Б со кој А се дели без остаток. На пример, делителите на бројот 24 се 1, 2, 3, 4, 6, 8, 12, 24. Секој број е делив сам по себе и со еден, така што можеме да ги игнорираме овие делители. Броевите кои се деливи само со себе и еден се сметаат за прости броеви и имаат голем број единствени својства. Сепак, за повеќето броеви можеме да избереме делители, од кои некои ќе бидат вообичаени. На пример, за бројот 36, таквите фактори би биле 2, 3, 4, 6, 9, 12, 18. Повеќето од нив се совпаѓаат со факторите на бројот 24 даден погоре, но најголемиот од нив е 12. Ова е gcd од парот 24 и 36 Концептот на најмал заеднички делител е бесмислен бидејќи секогаш е еден.

Наоѓање на gcd

За пресметување на GCD се користат три методи. Првиот, најлесно за разбирање, но во исто време и најмногу одзема време, е едноставно пребарување на сите делители на пар и избирање на најголемиот од нив. На пример, за 12 и 16 GCD се наоѓа на следниов начин:

  • запиши ги делителите за 12 - 2, 3, 4 и 6;
  • запиши ги делителите за 16 - 2, 4 и 8;
  • определи ги заедничките делители на броевите - 2, 4;
  • изберете го најголемиот од нив - 4.

Вториот метод е потежок за разбирање, но пресметковно поефикасен. Во овој случај, GCD се наоѓа со факторингирање на броевите во прости множители. За да се разложат во прости множители, потребно е последователно да се подели број без остаток на броеви од низата прости множители 2, 3, 5, 7, 11, 13...

За истите броеви, GCD се пресметува според следнава шема:

  • го факторизираме 12 во прости множители и добиваме 2 × 2 × 3;
  • распоред 16 - 2 × 2 × 2 × 2;
  • ги филтрираме факторите кои не се совпаѓаат и добиваме 2 × 2;
  • множете ги факторите и одредите gcd = 4.

Третиот метод е најсоодветен за одредување на gcd на парови на кој било, без разлика колку е голем, броеви. Евклидов алгоритам е метод за наоѓање на најголемиот заеднички делител на пар цели броеви A и B, со оглед на A>B.

Според алгоритмот, мораме да го поделиме А со Б, што ќе резултира со:

каде што A1 е цел број, C е остатокот од поделбата.

По ова, поделете го B со остатокот C и означете го резултатот како B1. Сега имаме нов пар на броеви А1 и Б1.

Да ги повториме чекорите. Поделете A1 со B1, што резултира со A2 и C1. После тоа, поделете го B1 со C1 и добијте B2. Алгоритмот се повторува додека остатокот од Cn не биде еднаков на нула.

Да го разгледаме детално користејќи ги броевите 1729 и 1001. Постапката е следна. Имаме пар (1001, 1729). За да се користи Евклидов алгоритам, првиот број во парот мора да биде поголем. Ајде да ја извршиме трансформацијата за правилно функционирање на алгоритмот - ќе го оставиме помалиот број на место, а поголемиот ќе го замениме со нивната разлика, бидејќи ако двата броја се деливи со GCD, тогаш нивната разлика е исто така делива. Добиваме (1001, 728). Ајде да ги направиме пресметките:

  • (1001, 728) = (728, 273) = (273, 182) - наместо да ја барате разликата многу пати, можете да го напишете остатокот од 728 поделен со 273.
  • (273, 182) = (91, 182) = (91, 0) = 91.

Така, gcd на парот 1001 и 1729 е 91.

Користење на GCD

Во пракса, најголемиот заеднички делител се користи при решавање на диофантински равенки од формата ax + by = d. Ако GCD (a, b) не го дели d без остаток, тогаш равенката не е решлива во цели броеви. Така, диофантинската равенка има целобројни корени само ако односот d/gcd(a, b) е цел број.

Нашиот онлајн калкулатор ви овозможува брзо да го пронајдете најголемиот заеднички делител и за пар и за кој било произволен број на броеви.

Примери од реалниот живот

Училишна задача

Аритметичкиот проблем бара наоѓање на gcd од четири броеви: 21, 49, 56, 343. За да го решиме со помош на калкулатор, треба само да го означиме бројот на броеви и да ги внесеме во соодветните ќелии. По ова ќе добиеме одговор дека gcd (21, 49, 56, 343) = 7.

Диофантинска равенка

Да имаме диофантинска равенка од формата 1001 x + 1729 y = 104650. Треба да провериме дали е решлива во цели броеви. Веќе го пресметавме gcd за овој пар користејќи го Евклидов алгоритам. Ајде да ја провериме точноста на пресметките и повторно да го пресметаме GCD на калкулаторот. Навистина, GCD (1001, 1729) = 91. Ја проверуваме можноста за целобројно решение користејќи го условот d / GCD (a, b) = 104650/91 = 1150. Следствено, оваа равенка има целобројни корени.

Заклучок

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

Запомнете!

Ако природен број е делив само со 1 и со самиот себе, тогаш тој се нарекува прост.

Секој природен број е секогаш делив со 1 и со самиот себе.

Бројот 2 е најмалиот прост број. Ова е единствениот парен прост број; сите други прости броеви се непарни.

Има многу прости броеви, а првиот меѓу нив е бројот 2. Сепак, нема последен прост број. Во делот „За проучување“ можете да преземете табела со прости броеви до 997.

Но, многу природни броеви се деливи и со други природни броеви.

На пример:

  • бројот 12 се дели со 1, со 2, со 3, со 4, со 6, со 12;
  • Бројот 36 се дели со 1, со 2, со 3, со 4, со 6, со 12, со 18, со 36.

Броевите со кои бројот се дели со целина (за 12 тоа се 1, 2, 3, 4, 6 и 12) се нарекуваат делители на бројот.

Запомнете!

Делител на природен број a е природен број што го дели дадениот број „а“ без остаток.

Природниот број кој има повеќе од два делители се нарекува композитен.

Ве молиме имајте предвид дека броевите 12 и 36 имаат заеднички фактори. Овие броеви се: 1, 2, 3, 4, 6, 12. Најголем делител на овие броеви е 12.

Заеднички делител на два дадени броја „а“ и „б“ е бројот со кој двата дадени броеви „а“ и „б“ се делат без остаток.

Запомнете!

Најголем заеднички делител(GCD) од два дадени броја „а“ и „б“ е најголемиот број со кој двата броја „а“ и „б“ се делат без остаток.

Накратко, најголемиот заеднички делител на броевите „а“ и „б“ е напишан на следниов начин:

GCD (а; б) .

Пример: gcd (12; 36) = 12.

Делителите на броевите во записот за решение се означуваат со големата буква „Д“.

D (7) = (1, 7)

D (9) = (1, 9)

GCD (7; 9) = 1

Броевите 7 и 9 имаат само еден заеднички делител - бројот 1. Таквите броеви се нарекуваат копрости броеви.

Запомнете!

Копрости броеви- ова се природни броеви кои имаат само еден заеднички делител - бројот 1. Нивниот gcd е 1.

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

За да го пронајдете gcd на два или повеќе природни броеви, ви треба:

  1. разложува делители на броеви на прости множители;

Удобно е да се пишуваат пресметки користејќи вертикална лента. Лево од линијата прво ја запишуваме дивидендата, десно - делителот. Следно, во левата колона ги запишуваме вредностите на количниците.

Ајде да објасниме веднаш со пример. Да ги вброиме броевите 28 и 64 во прости множители.


  1. Ги нагласуваме истите прости фактори и кај двата броја.
    28 = 2 2 7

    64 = 2 2 2 2 2 2

  2. Најдете го производот на идентични прости множители и запишете го одговорот;
    GCD (28; 64) = 2 2 = 4

    Одговор: GCD (28; 64) = 4

Можете да ја формализирате локацијата на GCD на два начина: во колона (како што е направено погоре) или „по ред“.

Заеднички делителнеколку броеви е бројот со кој се дели секој од дадените броеви. На пример, дадени два броја: 6 и 9. Бројот 6 има делители 1, 2, 3, 6. Бројот 9 има делители 1, 3, 9. Гледаме дека броевите 6 и 9 имаат заеднички делители 1 и 3.

Најголем заеднички делител(скратено GCD) од неколку броеви се нарекува најголем заеднички делител со кој секој од овие броеви се дели без остаток.

Така, од сите заеднички фактори на броевите 6 и 9, најголемиот заеднички фактор е бројот 3.

Обично најголемиот заеднички делител се пишува на следниов начин: GCD ( а, б, ...) = x.

Според ова, го запишуваме најголемиот заеднички делител на броевите 6 и 9:

GCD (6, 9) = 3.

Се повикуваат броеви чии gcd е еднаква на еден копрости броеви. На пример, броевите 14 и 15 се релативно прости: GCD (14, 15) = 1.

GCD калкулатор

Овој калкулатор ќе ви помогне да го пронајдете најголемиот заеднички делител на броеви. Само внесете броеви одделени со празни места или запирки и кликнете на копчето Пресметај GCD.