Nod и nok числа - най-големият общ делител и най-малкото общо кратно на няколко числа. Кимване и нок на три или повече числа Примери за дефиниция на кимване

Определение.Нарича се най-голямото естествено число, на което числата a и b се делят без остатък най-голям общ делител (gcd)тези числа.

Нека намерим най-големия общ делител на числата 24 и 35.
Делителите на 24 ще бъдат числата 1, 2, 3, 4, 6, 8, 12, 24, а делителите на 35 ще бъдат числата 1, 5, 7, 35.
Виждаме, че числата 24 и 35 имат само един общ делител - числото 1. Такива числа се наричат взаимно приме.

Определение.Естествените числа се наричат взаимно примеако техният най-голям общ делител (gcd) е 1.

Най-голям общ делител (НОД)може да се намери, без да се изписват всички делители на дадените числа.

Разлагайки числата 48 и 36 на множители, получаваме:
48 = 2 * 2 * 2 * 2 * 3, 36 = 2 * 2 * 3 * 3.
От факторите, включени в разширяването на първото от тези числа, изтриваме онези, които не са включени в разширяването на второто число (т.е. две двойки).
Остават множителите 2 * 2 * 3. Тяхното произведение е 12. Това число е най-големият общ делител на числата 48 и 36. Намерен е и най-големият общ делител на три или повече числа.

Да намеря най-голям общ делител

2) от факторите, включени в разширяването на едно от тези числа, зачеркнете онези, които не са включени в разширяването на други числа;
3) намерете произведението на останалите множители.

Ако всички дадени числа се делят на едно от тях, то това число е най-голям общ делителдадени числа.
Например най-големият общ делител на 15, 45, 75 и 180 е 15, тъй като той дели всички останали числа: 45, 75 и 180.

Най-малко общо кратно (LCM)

Определение. Най-малко общо кратно (LCM)естествените числа a и b е най-малкото естествено число, което е кратно на a и b. Най-малкото общо кратно (LCM) на числата 75 и 60 може да се намери, без да се записват кратни на тези числа подред. За да направим това, разлагаме 75 и 60 на прости множители: 75 \u003d 3 * 5 * 5 и 60 \u003d 2 * 2 * 3 * 5.
Изписваме факторите, включени в разширението на първото от тези числа, и добавяме към тях липсващите фактори 2 и 2 от разширението на второто число (т.е. комбинираме факторите).
Получаваме пет фактора 2 * 2 * 3 * 5 * 5, чийто продукт е 300. Това число е най-малкото общо кратно на числата 75 и 60.

Също така намерете най-малкото общо кратно на три или повече числа.

Да се намерете най-малкото общо кратноняколко естествени числа, трябва:
1) разложи ги на прости множители;
2) напишете факторите, включени в разширяването на едно от числата;
3) добавете към тях липсващите множители от разширенията на останалите числа;
4) намерете произведението на получените фактори.

Обърнете внимание, че ако едно от тези числа се дели на всички други числа, тогава това число е най-малкото общо кратно на тези числа.
Например най-малкото общо кратно на 12, 15, 20 и 60 би било 60, тъй като се дели на всички дадени числа.

Питагор (VI в. пр. н. е.) и неговите ученици изучават въпроса за делимостта на числата. Число, равно на сумата от всичките му делители (без самото число), те наричат ​​перфектно число. Например числата 6 (6 = 1 + 2 + 3), 28 (28 = 1 + 2 + 4 + 7 + 14) са перфектни. Следващите съвършени числа са 496, 8128, 33 550 336. Питагорейците са знаели само първите три съвършени числа. Четвъртият - 8128 - става известен през 1 век. н. д. Петият - 33 550 336 - е намерен през 15 век. До 1983 г. вече са известни 27 съвършени числа. Но досега учените не знаят дали има нечетни съвършени числа, дали има най-голямото съвършено число.
Интересът на древните математици към простите числа се дължи на факта, че всяко число е или просто, или може да бъде представено като произведение на прости числа, тоест простите числа са като тухли, от които са изградени останалите естествени числа.
Вероятно сте забелязали, че простите числа в редицата от естествени числа се срещат неравномерно - в някои части на редицата са повече, в други - по-малко. Но колкото по-нататък се движим по редицата от числа, толкова по-редки са простите числа. Възниква въпросът: съществува ли последното (най-голямото) просто число? Древногръцкият математик Евклид (3 век пр. н. е.) в книгата си „Начала“, която в продължение на две хиляди години е основният учебник по математика, доказва, че има безкрайно много прости числа, тоест зад всяко просто число стои четно число. по-голямо просто число.
За намиране на прости числа друг гръцки математик от същото време, Ератостен, измисли такъв метод. Той записа всички числа от 1 до някакво число и след това задраска единицата, която не е нито просто, нито съставно число, след това задраска през едно всички числа след 2 (числа, кратни на 2, т.е. 4, 6, 8 и т.н.). Първото останало число след 2 беше 3. След това, след две, всички числа след 3 бяха задраскани (числа, кратни на 3, т.е. 6, 9, 12 и т.н.). накрая само простите числа останаха незадраскани.

За да намерите НОД (най-голям общ делител) на две числа, трябва:

2. Намерете (подчертайте) всички общи прости множители в получените разширения.

3. Намерете произведението на общи прости множители.

За да намерите LCM (най-малкото общо кратно) на две числа, трябва:

1. Разложете тези числа на прости множители.

2. Допълнете разширението на едно от тях с онези множители на разширението на другото число, които не са в разширението на първото.

3. Изчислете произведението на получените множители.

Намиране на GCD

НОД е най-големият общ делител.

За да намерите най-големия общ делител на няколко числа:

• определяне на множителите, общи за двете числа;
• намерете произведението на общите множители.

Пример за намиране на GCD:

Намерете НОД на числата 315 и 245.

315 = 5 * 3 * 3 * 7;

245 = 5 * 7 * 7.

2. Напишете коефициентите, които са общи за двете числа:

3. Намерете произведението на общите множители:

gcd(315; 245) = 5 * 7 = 35.

Отговор: НОД(315; 245) = 35.

Намиране на НОК

LCM е най-малкото общо кратно.

За да намерите най-малкото общо кратно на няколко числа:

• разлагат числата на прости множители;
• напишете факторите, включени в разширяването на едно от числата;
• добавете към тях липсващите множители от разлагането на второто число;
• намерете произведението на получените множители.

Пример за намиране на NOC:

Намерете НОК на числата 236 и 328:

1. Разлагаме числата на прости множители:

236 = 2 * 2 * 59;

328 = 2 * 2 * 2 * 41.

2. Запишете множителите, включени в разширението на едно от числата и добавете към тях липсващите множители от разширението на второто число:

2; 2; 59; 2; 41.

3. Намерете произведението на получените фактори:

LCM(236; 328) = 2 * 2 * 59 * 2 * 41 = 19352.

Отговор: LCM(236; 328) = 19352.

Най-големият общ делител е друг индикатор, който улеснява работата с дроби. Много често в резултат на изчисления се получават дроби с много големи стойности на числителя и знаменателя. Възможно е да се намалят такива числа на етапи, но това е изключително дълго, така че е по-лесно незабавно да се намери GCD и да се намали. Нека разгледаме по-отблизо темата.

Какво е NOD?

Най-големият общ делител (НОД) на поредица от числа е най-голямото число, на което всяко от числата в поредицата може да бъде разделено без остатък.

Как да намеря NOD?

За да се намери НОД, е необходимо всяко от числата да се разложи на прости множители и да се подчертае общата част.

Те не са измислили специална формула за това, но има алгоритъм за изчисление.

Нека дадем пример за намиране на най-големия общ делител на две естествени числа: 540 и 252. Нека разложим 640 на прости множители. Последователността на действията е следната:

• Разделяме числото на най-малкото възможно просто число. Тоест, ако числото може да се раздели на 2, 3 или 5, тогава първо трябва да разделите на 5. Само за да не се объркате.
• Полученият резултат се разделя на най-малкото възможно просто число.
• Повтаряме делението на всеки получен резултат, докато получим просто число.

Сега ще проведем същата процедура на практика.

• 540: 2=270
• 270:2=135
• 135: 3 =45
• 45: 3=15
• 15: 5 = 3

Нека запишем резултата като уравнение 540=2*2*3*3*3*5. За да запишете резултата, трябва да умножите последното получено число по всички делители.

Нека направим същото с числото 252:

• 252: 2=126
• 126: 2=63
• 63: 3=21
• 21: 3 = 7

Нека запишем резултата: 252=2*2*3*3*7.

Всяко разширение има еднакви числа. Нека ги намерим, това са две числа 2 и две числа 3. Само 7 и 3 * 5 се различават.

За да намерите НОД, трябва да умножите общите множители. Тоест в продукта ще има две двойки и две тройки.

НОД=2*2*3*3=36

Как може да се използва?

Задача: намалете дробта $$252\over540$$.

Вече намерихме GCD за тези две числа, сега просто ще използваме вече изчислената стойност.

Нека намалим числителя и знаменателя на дробта с 36 и ще получим отговора.

$$(252\over540) =(7\over15)$$ - за бързо намаляване, просто погледнете разширението на числата.

Ако 540=2*2*3*3*3*5 и НОД=36=2*2*3*3, тогава 540 = 36*3*5. И ако разделим 540 на 36, получаваме 3*5=15.

Без GCD би трябвало да пишем съкращения в един дълъг ред. Освен това има случаи, когато не е ясно дали дадена дроб изобщо може да бъде намалена. За такива ситуации в математиката те измислиха разлагане на числата на прости множители и НОД.

Какво научихме?

Научихме какъв е най-големият общ делител на двойка числа, разбрахме как да използваме индикатора на практика, решихме проблема с намирането на НОД и използването на НОД за съкращаване на дроби. Разбрахме, че с използването на НОД е по-лесно и по-бързо да намалим обемистите дроби, като намерим НОД за числителя и знаменателя.

Тематическа викторина

Рейтинг на статията

Среден рейтинг: 4.3. Общо получени оценки: 204.

Една от задачите, които създават проблем за съвременните ученици, които са свикнали да използват калкулатори, вградени в джаджи на място и не на място, е намирането на най-големия общ делител (НОД) на две или повече числа.

Невъзможно е да се реши какъвто и да е математически проблем, ако не се знае какво всъщност се иска. За да направите това, трябва да знаете какво означава този или онзи израз.използвани в математиката.

Общи понятия и определения

Трябва да знам:

1. Ако определено число може да се използва за преброяване на различни обекти, например девет стълба, шестнадесет къщи, тогава това е естествено. Най-малкият от тях ще бъде един.
2. Когато едно естествено число се дели на друго естествено число, по-малкото число се нарича делител на по-голямото.
3. Ако две или повече различни числа се делят на определено число без остатък, тогава се казва, че последният ще бъде техният общ делител (OD).
4. Най-голямата от OD се нарича най-голям общ делител (НОД).
5. В такъв случай, когато едно число има само два естествени делителя (себе си и единица), то се нарича просто. Най-малкото сред тях е двойката, освен това е единственото четно число в тяхната серия.
6. Ако две числа имат максимален общ делител едно, тогава те ще бъдат взаимно прости.
7. Число с повече от два делителя се нарича съставно число.
8. Процесът, при който се намират всички прости множители, които, умножени един с друг, ще дадат началната стойност в произведението в математиката, се нарича разлагане на прости множители. Освен това едни и същи фактори в разширяването могат да се появят повече от веднъж.

В математиката се приемат следните обозначения:

1. Делители D (45) = (1; 3; 5; 9; 45).
2. OD (8;18) = (1;2).
3. НОД (8;18) = 2.

Различни начини за намиране на GCD

Най-лесният въпрос за отговор как да намерите NODкогато по-малкото число е делител на по-голямото. Това ще бъде най-големият общ делител в този случай.

Например НОД (15;45) = 15, НОД (48;24) = 24.

Но такива случаи в математиката са много редки, следователно, за да се намери GCD, се използват по-сложни техники, въпреки че все още е силно препоръчително да проверите тази опция, преди да започнете работа.

Метод на разлагане на прости множители

Ако трябва да намерите НОД на две или повече различни числа, достатъчно е да разложим всеки от тях на прости множители и след това да извършим процеса на умножаване на онези от тях, които са във всяко от числата.

Пример 1

Помислете как да намерите GCD 36 и 90:

1. 36 = 1*2*2*3*3;
2. 90 = 1*2*3*3*5;

НОД (36;90) = 1*2*3*3 = 18.

Сега нека видим как да намерим същото в случай на три числа, вземете например 54; 162; 42.

Вече знаем как да разложим 36, нека се заемем с останалото:

1. 162 = 1*2*3*3*3*3;
2. 42 = 1*2*3*7;

Така НОД (36;162;42) = 1*2*3 = 6.

Трябва да се отбележи, че записването на единицата в разлагането е абсолютно незадължително.

Обмислете начина колко лесно е да се факторизира, за това отляво ще напишем нужното число, а отдясно ще напишем прости делители.

Колоните могат да бъдат разделени или със знак за разделяне, или с обикновена вертикална лента.

1. 36 / 2 ще продължим нашия процес на разделяне;
2. 18/2 по-нататък;
3. 9/3 и отново;
4. 3/3 вече е съвсем елементарно;
5. 1 - резултатът е готов.

Желаните 36 \u003d 2 * 2 * 3 * 3.

Евклидов път

Тази опция е известна на човечеството от времето на древногръцката цивилизация, тя е много по-проста и се приписва на великия математик Евклид, въпреки че много подобни алгоритми са били използвани по-рано. Този метод е да се използва следният алгоритъм, разделяме по-голямото число с остатък на по-малкото. След това разделяме нашия делител на остатъка и продължаваме да действаме по този начин в кръг, докато делението приключи. Последната стойност ще се окаже желаният най-голям общ делител.

Нека дадем пример за използване на този алгоритъм:

Нека се опитаме да разберем кой GCD за 816 и 252:

1. 816 / 252 = 3 и остатъкът е 60. Сега разделяме 252 на 60;
2. 252 / 60 = 4 остатъкът този път ще бъде 12. Нека продължим нашия кръгов процес, разделяме шестдесет на дванадесет;
3. 60 / 12 = 5. Тъй като този път не получихме остатък, имаме готов резултат, дванадесет ще бъде стойността, която търсим.

И така, в края на нашия процес получихме NOD (816;252) = 12.

Действия, ако е необходимо да се определи GCD, ако са посочени повече от две стойности

Вече разбрахме какво да правим в случай, че има две различни числа, сега ще научим как да действаме, ако има такива. 3 или повече.

Въпреки привидната сложност, тази задача няма да ни създаде проблеми. Сега избираме произволни две числа и определяме стойността, която търсим за тях. Следващата стъпка е да се намери НОД за получения резултат и третата от дадените стойности. След това отново действаме според вече познатия ни принцип за четвъртата пета и т.н.

Заключение

И така, при привидната голяма сложност на задачата, поставена пред нас първоначално, всъщност всичко е просто, основното е да можете да извършите процеса на разделяне без грешкаи се придържайте към някой от двата алгоритъма, описани по-горе.

Въпреки че и двата метода са доста приемливи, в общообразователно училище първият метод е много по-често използван.. Това се дължи на факта, че разлагането на прости множители ще е необходимо при изучаването на следващата образователна тема - дефиницията на най-голямото общо кратно (LCM). Но все пак си струва да се отбележи отново - използването на алгоритъма на Евклид в никакъв случай не може да се счита за погрешно.

Видео

С помощта на видеото можете да научите как да намерите най-големия общ делител.

Нека разгледаме два основни метода за намиране на НОД по два основни начина: с помощта на алгоритъма на Евклид и чрез факторизиране. Нека приложим двата метода за две, три и повече числа.

Алгоритъм на Евклид за намиране на НОД

Алгоритъмът на Евклид улеснява изчисляването на най-големия общ делител на две положителни числа. Дадохме формулировките и доказателството на алгоритъма на Евклид в раздела Най-голям общ делител: детерминант, примери.

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

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

Какво е НОД на числата 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.

Решение

Ще разделим последователно числата и ще получим НОД (661 , 113) = 1 . Това означава, че 661 и 113 са относително прости числа. Можем да разберем това, преди да започнем изчисленията, ако погледнем таблицата на простите числа.

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

Намиране на НОД чрез разлагане на числа на прости множители

За да се намери най-големият общ делител на две числа чрез разлагане на множители, е необходимо да се умножат всички прости множители, които се получават при разлагането на тези две числа и са общи за тях.

Пример 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 (m a 1 , m b 1) = m gcd (a 1 , b 1) , където m е всяко положително цяло число .

Намиране на НОД на три или повече числа

Независимо от броя на числата, за които трябва да намерим НОД, ще следваме същия алгоритъм, който се състои в намиране на НОД на две последователни числа. Този алгоритъм се основава на прилагането на следната теорема: НОД на няколко числа a 1 , a 2 , … , a kе равно на числото dk, който се намира при последователното изчисление на gcd (a 1 , a 2) = d 2, НОД (d 2 , a 3) = d 3 , НОД (d 3 , a 4) = d 4 , … , НОД (d k - 1 , a k) = d k .

Пример 6

Намерете най-големия общ делител на четирите числа 78, 294, 570 и 36 .

Решение

Нека въведем обозначението: a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.

Нека започнем с намирането на НОД на числата 78 и 294: d2= GCD (78 , 294) = 6 .

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

Намерете d 4 \u003d НОД (d 3, a 4) \u003d НОД (6, 36) . 36 се дели на 6 без остатък. Това ни позволява да получим d4= GCD (6 , 36) = 6 .

d4 = 6, тоест GCD (78 , 294 , 570 , 36) = 6 .

Отговор:

А сега нека разгледаме друг начин за изчисляване на GCD за тези и още числа. Можем да намерим gcd, като умножим всички общи прости множители на числата.

Пример 7

Изчислете НОД на числата 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.

Оказва се, че NOD (78, 294, 570, 36) = 2 3 = 6.

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

Намиране на gcd на отрицателни числа

Ако трябва да се занимаваме с отрицателни числа, тогава можем да използваме модулите на тези числа, за да намерим най-големия общ делител. Можем да направим това, като знаем свойството на числата с противоположни знаци: числа нИ -нимат еднакви делители.

Пример 8

Намерете gcd на отрицателни цели числа − 231 И − 140 .

Решение

За да извършим изчисления, нека вземем модули от числа, дадени в условието. Това ще бъдат числата 231 и 140. Нека го кажем накратко: GCD (− 231 , − 140) = НОД (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

Определете НОД на три числа - 585, 81 и − 189 .

Решение

Нека заменим отрицателните числа в горния списък с техните абсолютни стойности, получаваме НОД (− 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 .

Отговор:НОД (− 585 , 81 , − 189) = 9 .

Ако забележите грешка в текста, моля, маркирайте я и натиснете Ctrl+Enter