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

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

Наоѓање со факторинг

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

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

Пример 1Ајде да најдеме GCD (84, 90).

Броевите 84 и 90 ги разложуваме на прости множители:

Значи, ги подвлечевме сите заеднички прости фактори, останува да ги помножиме меѓу себе: 1 2 3 = 6.

Значи gcd(84, 90) = 6.

Пример 2Ајде да го најдеме GCD (15, 28).

Ги разложуваме 15 и 28 на прости фактори:

Броевите 15 и 28 се сопрости бидејќи нивниот најголем заеднички делител е еден.

gcd (15, 28) = 1.

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

Вториот метод (инаку наречен Евклид метод) е да се најде GCD со последователно делење.

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

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

Пример 1Земете два броја 27 и 9. Бидејќи 27 е делив со 9, а 9 е делив со 9, тогаш 9 е заеднички делител на броевите 27 и 9. Овој делител е и најголем, бидејќи 9 не може да се дели со ниту еден број, поголем од 9. Затоа, gcd (27, 9) = 9.

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

1. Од двата дадени броја, поголемиот број се дели со помалиот.
2. Потоа, помалиот број се дели со остатокот што произлегува од делењето на поголемиот број со помалиот.
3. Понатаму, првиот остаток се дели со вториот остаток, кој се добива со делење на помалиот број со првиот остаток.
4. Вториот остаток се дели со третиот, кој се добива со делење на првиот остаток со вториот итн.
5. Така, поделбата продолжува додека остатокот не биде нула. Последниот делител ќе биде најголемиот заеднички делител.

Пример 2Да го најдеме најголемиот заеднички делител на броевите 140 и 96:

1) 140: 96 = 1 (остаток 44)

2) 96: 44 = 2 (остаток 8)

3) 44: 8 = 5 (остаток 4)

Последниот делител е 4, што значи gcd(140, 96) = 4.

Секвенциската поделба може да се запише и во колона:

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

1. Прво, пронајдете го најголемиот заеднички делител на кои било два броја од повеќе збирки на податоци.
2. Потоа го наоѓаме GCD на пронајдениот делител и некој трет даден број.
3. Потоа го наоѓаме GCD на последниот пронајден делител и четвртиот даден број итн.

Пример 3Да го најдеме најголемиот заеднички делител на броевите 140, 96 и 48. Веќе го најдовме GCD на броевите 140 и 96 во претходниот пример (ова е бројот 4). Останува да се најде најголемиот заеднички делител на бројот 4 и третиот даден број - 48:

48 е делив со 4 без остаток. Значи gcd(140, 96, 48) = 4.

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

На пример, записот 110 = 2 5 11 покажува дека бројот 110 е разложен на прости фактори 2, 5 и 11.

Општо земено, секој композитен број може да се разложи на прости множители, а со кој било метод се добива исто разложување, доколку не се земе предвид редоследот на множителите. Според тоа, претставите на бројот 110 како производ од 2 · 5 · 11 или производ од 5 · 2 · 11 се, во суштина, исто разложување на бројот 110 на прости множители.

Кога ги разложуваме броевите на прости множители, користејќи ги знаците за делење со 2, 3, 5 итн., да се потсетиме на начинот на запишување на распаѓањето на број на прости множители. Да го разложиме, на пример, бројот 720 на прости множители.Бројот 720 е делив со 2. Оттука, 2 е еден од простите множители во разградувањето на бројот 720. Поделете 720 со 2. Бројот 2 е запишан на правото на знакот за еднаквост, а количникот 360 се запишува под бројот 720. Бројот 360 поделен со 2 добиваме 180. Се дели 180 со 2, добиваме 90, делиме 90 со 2, добиваме 45, делиме 45 со 3, добиваме 15, делиме 15 со 3, добиваме 5. Бројот 5 е прост, кога се дели со 5 добиваме 1. Факторизацијата е завршена.

720 = 2 2 2 2 3 3 5

Вообичаено е да се замени производот на идентични множители со моќност: 720 = 5. Таквото претставување на бројот 720 се нарекува канонски погледовој број.

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

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

Ајде да го претставиме секој од овие броеви во канонска форма.

3600 = 2 2 2 2 3 3 5 5 = ; 288 = 2 2 2 2 2 3 3 =

Во простата факторизација на најголемиот заеднички делител на броевите 3600 и 288, сите заедничко едноставно множење,кои се содржани во проширувањата на дадените броеви и од секој од нив мора да се земе најнискиот индикаторсо што влегува во двете проширувања. Според тоа, проширувањето на најголемиот заеднички делител на броевите 3600 и 288 ќе ги вклучи факторите и . Значи D (3600? 288) = · = 144.

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

К (3600, 288) = 5 = 7200.

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

2) Формираме производ од прости множители заеднички за сите дадени броеви и секој од нив се зема со најмалиот експонент со кој влегува во сите проширувања на овие броеви;

3) Ја наоѓаме вредноста на овој производ - тој ќе биде најголемиот заеднички делител на овие броеви.

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

1) Секој даден број го претставуваме во канонска форма;

2) Формираме производ од сите прости множители кои се наоѓаат во проширувањата на овие броеви и секој се зема со најголемиот експонент со кој влегува во сите проширувања на овие броеви;

3) Ја наоѓаме вредноста на овој производ - тоа ќе биде најмалиот заеднички множител од овие броеви.

Број на билет 45. Најмал заеднички множител на броеви. Неговите својства и методи на пронаоѓање. Примери.

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

Еден начин да се најде најмалиот заеднички множител се заснова на односот помеѓу LCM и GCD. Постоечката врска помеѓу LCM и GCD ви овозможува да го пресметате најмалиот заеднички множител од два позитивни цели броеви преку познатиот најголем заеднички делител. Соодветната формула ја има формата LCM(a, b)=a b: GCM(a, b) . Размислете за примери за наоѓање на LCM според горната формула.

Пример.

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

Решение.

Во овој пример a=126, b=70. Дозволете ни да ја искористиме врската помеѓу LCM и GCD изразена со формулата LCM(a, b)=a b: GCM(a, b). Односно, прво треба да го најдеме најголемиот заеднички делител на броевите 70 и 126 , по што можеме да го пресметаме LCM на овие броеви според напишаната формула.

Ајде да најдеме GCD (126, 70), користејќи го Евклидовиот алгоритам: 126=70 1+56, 70=56 1+14, 56=14 4, оттука, gcd(126, 70)=14.

Сега го наоѓаме потребниот најмал заеднички множител: LCM(126, 70)=126 70: GCM(126, 70)=126 70:14=630.

Одговор:

LCM(126, 70)=630.

Пример.

Што е еднакво на NOC (68, 34)?

Решение.

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

Одговор:

LCM(68, 34)=68.

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

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

Друг начин да се најде најмалиот заеднички множител е врз основа на факторингирање на броевите во прости множители. Ако направиме производ од сите прости множители на овие броеви, по што од овој производ ги исклучиме сите заеднички прости множители кои се присутни во проширувањата на овие броеви, тогаш добиениот производ ќе биде еднаков на најмалиот заеднички множител од овие броеви.

Од еднаквоста произлегува и најавеното правило за наоѓање на ЛКМ LCM(a, b)=a b: GCM(a, b). Навистина, производ на броеви аи бе еднаков на производот на сите фактори вклучени во проширувањето на броевите аи б. За возврат gcd(a, b)е еднаков на производот на сите прости множители кои се истовремено присутни во проширувањата на броевите аи б(што е опишано во делот за пронаоѓање на GCD со факторингирање на броевите во прости множители).

Да земеме пример. Дозволете ни да го знаеме тоа 75=3 5 5и 210=2 3 5 7. Составете го производот од сите фактори на овие проширувања: 2 3 3 5 5 5 7. Сега од овој производ ги исклучуваме сите фактори кои исто така се присутни во проширувањето на бројот 75 и во проширувањето на бројот 210 (такви фактори се 3 и 5 ), тогаш производот ќе добие форма 2 3 5 5 7. Вредноста на овој производ е еднаква на најмалиот заеднички множител од броевите 75 и 210 , тоа е, LCM(75, 210)= 2 3 5 5 7=1 050.

Пример.

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

Решение.

Ајде да ги разложиме бројките 441 и 700 за основните фактори:

Добиваме 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. На овој начин, LCM(441, 700)=2 2 3 3 5 5 7 7=44 100.

Одговор:

LCM(441, 700)= 44 100.

Правилото за наоѓање на LCM со користење на разложување на броеви во прости множители може да се формулира малку поинаку. Ако на факторите од проширувањето на бројот адодадете ги факторите што недостасуваат од проширувањето на бројот б, тогаш вредноста на добиениот производ ќе биде еднаква на најмалиот заеднички множител од броевите аи б .

На пример, да ги земеме сите исти броеви 75 и 210 , нивните факторизации се како што следува: 75=3 5 5и 210=2 3 5 7. До множители 3 , 5 и 5 од разложувањето на бројот 75 2 и 7 од разложувањето на бројот 210 , го добиваме производот 2 3 5 5 7, чија вредност е NOC (75, 210).

Пример.

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

Решение.

Прво го добиваме разложувањето на броевите 84 и 648 на основните фактори. Тие изгледаат како 84=2 2 3 7и 648=2 2 2 3 3 3 3 3. До множители 2 , 2 , 3 и 7 од разложувањето на бројот 84 додавање на фактори кои недостасуваат 2 , 3 , 3 и 3 од разложувањето на бројот 648 , го добиваме производот 2 2 2 3 3 3 3 7, што е еднакво на 4 536 . Така, саканиот најмал заеднички множител на броевите 84 и 648 еднакви 4 536 .

Одговор:

LCM(84, 648)=4536.

Да разгледаме два главни методи за пронаоѓање на GCD на два главни начини: користење на Евклидовиот алгоритам и со факторинг. Ајде да ги примениме двата методи за два, три и повеќе броеви.

Yandex.RTB R-A-339285-1

Евклидовиот алгоритам за пронаоѓање на GCD

Евклидовиот алгоритам го олеснува пресметувањето на најголемиот заеднички делител на два позитивни броја. Ги дадовме формулациите и доказот на Евклидовиот алгоритам во делот Најголемиот заеднички делител: Детерминанта, Примери.

Суштината на алгоритмот е доследно да се изврши поделба со остаток, при што се добиваат низа еднаквости на формата:

a = b q 1 + r 1, 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1

Можеме да ја завршиме поделбата кога rk + 1 = 0, при што r k = gcd (a , b).

Пример 1

64 и 48 .

Решение

Да ја воведеме ознаката: a = 64 , b = 48 .

Врз основа на Евклидовиот алгоритам, ќе ја извршиме поделбата 64 на 48 .

Добиваме 1, а остатокот 16. Излегува дека q 1 = 1, r 1 = 16.

Вториот чекор е да се подели 48 за 16, добиваме 3. Тоа е q2 = 3, А r 2 = 0.Така, бројот 16 е најголемиот заеднички делител за броевите од условот.

Одговор: gcd (64, 48) = 16.

Пример 2

Што е GCD на броеви 111 и 432 ?

Решение

Подели 432 на 111 . Според Евклидовиот алгоритам, го добиваме синџирот на еднаквости 432 = 111 3 + 99 , 111 = 99 1 + 12 , 99 = 12 8 + 3 , 12 = 3 4 .

Така, најголемиот заеднички делител на броеви 111 и 432 е 3.

Одговор: gcd (111, 432) = 3.

Пример 3

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

Решение

Ние последователно ќе ги поделиме броевите и ќе го добиеме GCD (661 , 113) = 1 . Ова значи дека 661 и 113 се релативно прости броеви. Можеме да го сфатиме ова пред да започнеме со пресметките ако ја погледнеме табелата со прости броеви.

Одговор: gcd (661, 113) = 1.

Наоѓање на GCD со факторингирање на броеви во прости фактори

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

Пример 4

Ако ги разложиме броевите 220 и 600 на прости множители, добиваме два производа: 220 = 2 2 5 11и 600 = 2 2 2 3 5 5. Заеднички фактори во овие два производи ќе бидат 2, 2 и 5. Ова значи дека NOD (220, 600) = 2 2 5 = 20.

Пример 5

Најдете го најголемиот заеднички делител на броевите 72 и 96 .

Решение

Најдете ги сите прости множители на броевите 72 и 96 :

72 36 18 9 3 1 2 2 2 3 3

96 48 24 12 6 3 1 2 2 2 2 2 3

Заеднички прости множители за два броја: 2 , 2 , 2 и 3 . Ова значи дека NOD (72, 96) = 2 2 2 3 = 24.

Одговор: gcd (72, 96) = 24.

Правилото за наоѓање на најголемиот заеднички делител на два броја се заснова на својствата на најголемиот заеднички делител, според кои gcd (ma 1 , mb 1) = m gcd (a 1 , b 1) , каде што m е секој позитивен цел број .

Наоѓање GCD од три или повеќе броеви

Без разлика на бројот на броеви за кои треба да го најдеме GCD, ќе го следиме истиот алгоритам, кој се состои во наоѓање на GCD на два броја едноподруго. Овој алгоритам се заснова на примена на следната теорема: GCD од неколку броеви a 1 , a 2 , ... , a kе еднаков на бројот дк, што се наоѓа во секвенцијалната пресметка на gcd (a 1, a 2) = d 2, GCD (d 2 , a 3) = d 3 , GCD (d 3 , a 4) = d 4 , … , GCD (d k - 1 , a k) = d k .

Пример 6

Најдете го најголемиот заеднички делител на четирите броеви 78, 294, 570 и 36 .

Решение

Да ја воведеме ознаката: a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.

Да почнеме со наоѓање на GCD на броевите 78 и 294: d2= GCD (78 , 294) = 6 .

Сега да започнеме да наоѓаме d 3 \u003d GCD (d 2, a 3) \u003d GCD (6, 570) . Според Евклидовиот алгоритам 570 = 6 95 .Тоа значи дека d 3 = GCD (6 , 570) = 6 .

Најдете d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36) . 36 се дели со 6 без остаток. Ова ни овозможува да добиеме d4= GCD (6 , 36) = 6 .

d4 = 6, односно GCD (78 , 294 , 570 , 36) = 6 .

Одговор:

И сега да погледнеме друг начин за пресметување на GCD за тие и повеќе броеви. Можеме да го најдеме gcd со множење на сите заеднички прости множители на броевите.

Пример 7

Пресметај го gcd на броевите 78 , 294 , 570 и 36 .

Решение

Ајде да ги разложиме овие броеви на прости множители: 78 = 2 3 13 , 294 = 2 3 7 7 , 570 = 2 3 5 19 , 36 = 2 2 3 3 .

За сите четири броеви, заеднички прости множители ќе бидат броевите 2 и 3.

Излегува дека НОД (78, 294, 570, 36) = 2 3 = 6.

Одговор: gcd(78, 294, 570, 36) = 6.

Наоѓање на gcd на негативни броеви

Ако треба да се справиме со негативни броеви, тогаш можеме да ги користиме модулите на овие броеви за да го најдеме најголемиот заеднички делител. Ова можеме да го направиме, знаејќи го својството на броевите со спротивни знаци: броеви nи -nимаат исти делители.

Пример 8

Најдете го gcd на негативни цели броеви − 231 и − 140 .

Решение

За да извршиме пресметки, да земеме модули со броеви дадени во условот. Тоа ќе бидат броевите 231 и 140. Накратко да кажеме: ГЦД (− 231 , − 140) = GCD (231, 140) . Сега да го примениме Евклидовиот алгоритам за да најдеме прости множители на два броја: 231 = 140 1 + 91 ; 140 = 91 1 + 49; 91 = 49 1 + 42; 49 = 42 1 + 7 и 42 = 7 6. Добиваме дека gcd (231, 140) = 7 .

И бидејќи NOD (− 231 , − 140) = GCD (231 , 140) , потоа gcd од броеви − 231 и − 140 еднакви 7 .

Одговор: gcd (− 231, − 140) = 7.

Пример 9

Одреди го gcd на три броја - 585, 81 и − 189 .

Решение

Ајде да ги замениме негативните броеви во горната листа со нивните апсолутни вредности, добиваме GCD (− 585 , 81 , − 189) = GCD (585 , 81 , 189) . Потоа ги разложуваме сите дадени броеви на прости множители: 585 = 3 3 5 13, 81 = 3 3 3 3 и 189 = 3 3 3 7. Простите множители 3 и 3 се заеднички за трите броеви. Излегува дека gcd (585 , 81 , 189) = gcd (- 585 , 81 , - 189) = 9 .

Одговор: GCD (− 585, 81, − 189) = 9.

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