Знайти нок із рішенням. Калькулятор онлайн.Знаходження (обчислення) НОД та НОК

Визначення.Найбільше натуральне число, яке діляться без залишку числа а і b, називають найбільшим спільним дільником (НДД)цих чисел.

Знайдемо найбільший спільний дільник чисел 24 та 35.
Дільниками 24 будуть числа 1, 2, 3, 4, 6, 8, 12, 24, а дільниками 35 будуть числа 1, 5, 7, 35.
Бачимо, що числа 24 і 35 мають лише один спільний дільник – число 1. Такі числа називають взаємно простими.

Визначення.Натуральні числа називають взаємно простимиякщо їх найбільший спільний дільник (НОД) дорівнює 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.

Найменше загальне кратне (НОК)

Визначення. Найменшим загальним кратним (НОК)натуральних чисел а та Ь називають найменше натуральне число, яке кратне і a, і b. Найменше загальне кратне (НОК) чисел 75 і 60 можна знайти і не виписуючи кратні поспіль цих чисел. Для цього розкладемо 75 і 60 на прості множники: 75 = 3*5*5, а 60 = 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, 33550336. Піфагорійці знали тільки перші три досконалих числа. Четверте – 8128 – стало відомо в I ст. н. е. П'яте - 33550336 - було знайдено в XV ст. До 1983 було відомо вже 27 досконалих чисел. Але досі вчені не знають, чи є непарні досконалі числа, чи є найбільше досконале число.
Інтерес древніх математиків до простим числам пов'язані з тим, що будь-яке число або просте, чи то, можливо представлено як твори простих чисел, т. е. прості числа - це хіба що цеглинки, у тому числі будуються інші натуральні числа.
Ви, напевно, звернули увагу, що прості числа у ряді натуральних чисел зустрічаються нерівномірно – в одних частинах ряду їх більше, в інших – менше. Але що далі ми просуваємося по числовому ряду, то рідше зустрічаються прості числа. Виникає питання: чи існує останнє (найбільше) просте число? Давньогрецький математик Евклід (III ст. до н. е.) у своїй книзі «початку», яка була протягом двох тисяч років основним підручником математики, довів, що простих чисел нескінченно багато, тобто за кожним простим числом є ще більше просте число.
Для віднайдення простих чисел інший грецький математик того ж часу Ератосфен придумав такий спосіб. Він записував усі числа від 1 до якогось числа, а потім викреслював одиницю, яка не є ні простим, ні складовим числом, потім викреслював через одне усі числа, що йдуть після 2 (числа, кратні 2, тобто 4, 6 , 8 і т. д.). Першим числом, що залишилося після 2 було 3. Далі викреслювалися через два всі числа, що йдуть після 3 (числа, кратні 3, тобто 6, 9, 12 і т. д.). зрештою залишалися невикресленими лише прості числа.

Продовжимо розмову про найменше спільне кратне, яке ми розпочали у розділі «НОК – найменше загальне кратне, визначення, приклади». У цій темі ми розглянемо способи знаходження НОК для трьох чисел і більше, розберемо питання, як знайти НОК негативного числа.

Yandex.RTB R-A-339285-1

Обчислення найменшого загального кратного (НОК) через НОД

Ми вже встановили зв'язок найменшого загального кратного із найбільшим спільним дільником. Тепер навчимося визначати НОК через НОД. Спочатку розберемося, як це робити для позитивних чисел.

Визначення 1

Знайти найменше загальне кратне через найбільший спільний дільник можна за формулою НОК (a, b) = a · b: НОД (a, b).

Приклад 1

Необхідно знайти НОК чисел 126 та 70 .

Рішення

Приймемо a = 126, b = 70. Підставимо значення у формулу обчислення найменшого загального кратного через найбільший спільний дільник НОК (a, b) = a · b: НОД (a, b).

Знайде НОД чисел 70 та 126 . Для цього нам знадобиться алгоритм Евкліда: 126 = 70 · 1 + 56, 70 = 56 · 1 + 14, 56 = 14 · 4, отже, НОД (126 , 70) = 14 .

Обчислимо НОК: НОК (126, 70) = 126 · 70: НОД (126, 70) = 126 · 70: 14 = 630.

Відповідь:НОК (126, 70) = 630 .

Приклад 2

Знайдіть число 68 і 34 .

Рішення

НОД у разі нейти нескладно, оскільки 68 ділиться на 34 . Обчислимо найменше загальне кратне за формулою: НОК (68, 34) = 68 · 34: НОД (68, 34) = 68 · 34: 34 = 68.

Відповідь:НОК (68, 34) = 68 .

У цьому прикладі ми використовували правило знаходження найменшого загального кратного для цілих позитивних чисел a і b: якщо перше число ділиться на друге, що НОК цих чисел дорівнюватиме першому числу.

Знаходження НОК за допомогою розкладання чисел на прості множники

Тепер давайте розглянемо спосіб знаходження НОК, який ґрунтується на розкладанні чисел на прості множники.

Визначення 2

Для знаходження найменшого загального кратного нам знадобиться виконати низку нескладних дій:

складаємо добуток всіх простих множників чисел, для яких нам потрібно знайти НОК;
виключаємо їх отриманих творів усі прості множники;
отриманий після виключення загальних простих множників твір дорівнюватиме НОК даних чисел.

Цей спосіб знаходження найменшого загального кратного заснований на рівні НОК (a, b) = a · b: НОД (a, b). Якщо подивитися на формулу, то стане зрозуміло: добуток чисел a та b дорівнює добутку всіх множників, які беруть участь у розкладанні цих двох чисел. При цьому НОД двох чисел дорівнює добутку всіх простих множників, які одночасно присутні в розкладах на множники цих двох чисел.

Приклад 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. Цей твір буде нашим НОК для чисел 75 і 210 .

Приклад 4

Знайдіть НОК чисел 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.

Відповідь:НОК (441, 700) = 44 100 .

Дамо ще одне формулювання методу знаходження НОК шляхом розкладання чисел на прості множники.

Визначення 3

Раніше ми виключали з усієї кількості множників спільні для обох чисел. Тепер ми зробимо інакше:

розкладемо обидва числа на прості множники:
додамо до твору простих множників першого числа відсутні множники другого числа;
отримаємо твір, який і буде шуканий НОК двох чисел.

Приклад 5

Повернемося до числа 75 і 210, для яких ми вже шукали НОК в одному з попередніх прикладів. Розкладемо їх на прості множники: 75 = 3 · 5 · 5і 210 = 2 · 3 · 5 · 7. До твору множників 3 , 5 5 числа 75 додамо відсутні множники 2 і 7 числа 210 . Отримуємо: 2 · 3 · 5 · 5 · 7 .Це і є НОК чисел 75 та 210 .

Приклад 6

Необхідно обчислити НОК чисел 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.

Відповідь:НОК (84, 648) = 4536.

Знаходження НОК трьох та більшої кількості чисел

Незалежно від того, з якою кількістю чисел ми маємо справу, алгоритм наших дій завжди буде однаковим: ми будемо послідовно знаходити НОК двох чисел. На цей випадок є теорема.

Теорема 1

Припустимо, що ми маємо цілі числа a 1 , a 2 , … , a k. НОК m kцих чисел перебуває при послідовному обчисленні m 2 = НОК (a 1 , a 2) , m 3 = НОК (m 2 , a 3) , … , m k = НОК (m k − 1 , a k) .

Тепер розглянемо, як можна застосовувати теорему на вирішення конкретних завдань.

Приклад 7

Необхідно обчислити найменше загальне кратне чотирьох чисел 140, 9, 54 та 250 .

Рішення

Введемо позначення: a 1 = 140 , a 2 = 9 , a 3 = 54 , a 4 = 250 .

Почнемо з того, що обчислимо m 2 = НОК (a 1, a 2) = НОК (140, 9). Застосуємо алгоритм Евкліда для обчислення НОД чисел 140 і 9: 140 = 9 · 15 + 5, 9 = 5 · 1 + 4, 5 = 4 · 1 + 1, 4 = 1 · 4. Отримуємо: НОД (140, 9) = 1, НОК (140, 9) = 140 · 9: НОД (140, 9) = 140 · 9: 1 = 1260. Отже, m 2 = 1260 .

Тепер обчислимо за тим алгоритмом m 3 = НОК (m 2 , a 3) = НОК (1 260 , 54) . У результаті обчислень отримуємо m 3 = 3 780 .

Нам залишилося обчислити m4 = НОК (m3, a4) = НОК (3780, 250). Діємо за тим самим алгоритмом. Отримуємо m 4 = 94500 .

НОК чотирьох чисел із умови прикладу дорівнює 94500 .

Відповідь:НОК (140, 9, 54, 250) = 94500.

Як бачите, обчислення виходять нескладними, але досить трудомісткими. Щоб заощадити час, можна йти іншим шляхом.

Визначення 4

Пропонуємо вам наступний алгоритм дій:

розкладаємо всі числа на прості множники;
до твору множників першого числа додаємо множники, що відсутні, з твору другого числа;
до отриманого на попередньому етапі твору додаємо множники третього числа, що бракують, і т.д.;
отриманий твір буде найменшим загальним кратним усіх чисел з умови.

Приклад 8

Необхідно знайти НОК п'яти чисел 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 . Це і є найменша загальна кратність п'яти вихідних чисел.

Відповідь:НОК (84, 6, 48, 7, 143) = 48 048.

Знаходження найменшого загального кратного негативних чисел

Для того, щоб знайти найменше загальне кратне негативних чисел, ці числа необхідно спочатку замінити на числа з протилежним знаком, а потім провести обчислення за наведеними вище алгоритмами.

Приклад 9

НОК (54, -34) = НОК (54, 34), а НОК (-622, -46, -54, -888) = НОК (622, 46, 54, 888).

Такі дії допустимі у зв'язку з тим, що якщо прийняти, що aі − a- Протилежні числа,
то безліч кратних числа aзбігається з безліччю кратних числа − a.

Приклад 10

Необхідно обчислити НОК негативних чисел − 145 і − 45 .

Рішення

Зробимо заміну чисел − 145 і − 45 на протилежні їм числа 145 і 45 . Тепер за алгоритмом обчислимо НОК (145, 45) = 145 · 45: НОД (145, 45) = 145 · 45: 5 = 1305, попередньо визначивши НОД за алгоритмом Евкліда.

Отримаємо, що НОК чисел – 145 та − 45 одно 1 305 .

Відповідь:НОК (− 145 , − 45) = 1 305 .

Якщо ви помітили помилку в тексті, будь ласка, виділіть її та натисніть Ctrl+Enter

Математичні висловлювання та завдання вимагають безлічі додаткових знань. НОК - це одне з основних, особливо часто застосовується в Тема вивчається в середній школі, при цьому не є особливо складним у розумінні матеріалом, людині знайомій зі ступенями та таблицею множення не важко виділити необхідні числа та виявити результат.

Визначення

Загальне кратне - число, здатне націло розділитись на два числа одночасно (а і b). Найчастіше це число отримують методом перемноження вихідних чисел a і b. Число має ділитися одночасно на обидва числа, без відхилень.

НОК - це прийнята для позначення коротка назва, зібрана з перших букв.

Способи отримання числа

Для знаходження НОК не завжди підходить спосіб перемноження чисел, він краще підходить для простих однозначних або двозначних чисел. прийнято розділяти на множники, що більше число, то більше вписувалося множників буде.

Приклад №1

Для найпростішого прикладу у школах зазвичай беруться прості, однозначні чи двоцифрові числа. Наприклад, необхідно вирішити наступне завдання, знайти найменше загальне кратне від чисел 7 і 3, рішення досить просте, їх просто перемножити. У результаті є число 21, менше просто немає.

Приклад №2

Другий варіант завдання набагато складніший. Дано числа 300 і 1260, знаходження НОК - обов'язково. Для вирішення завдання передбачаються такі дії:

Розкладання першого та другого чисел на найпростіші множники. 300 = 2 2 * 3 * 5 2; 1260 = 2 2 * 3 2 * 5 * 7. Перший етап завершено.

Другий етап передбачає роботу з отриманими даними. Кожне з отриманих чисел має брати участь у обчисленні підсумкового результату. Для кожного множника зі складу вихідних чисел береться найбільша кількість входжень. НОК - це загальна кількість, тому множники з чисел повинні в ньому повторяться все до одного, навіть ті, що присутні в одному екземплярі. Обидва початкові числа мають у своєму складі числа 2, 3 і 5, у різних ступенях, 7 є тільки в одному випадку.

Для обчислення підсумкового результату необхідно взяти кожне число у найбільшій їх представлених ступенів, до рівняння. Залишається тільки перемножити і отримати відповідь, при правильному заповненні завдання укладається у дві дії без пояснень:

1) 300 = 2 2 * 3 * 5 2 ; 1260 = 2 2 * 3 2 *5 *7.

2) НОК = 6300.

Ось і вся задача, якщо спробувати обчислити потрібне число за допомогою перемноження, то відповідь однозначно не буде правильною, оскільки 300 * 1260 = 378000.

Перевірка:

6300/300 = 21 - вірно;

6300/1260 = 5 - вірно.

Правильність отриманого результату визначається за допомогою перевірки - розподілу НОК на обидва вихідні числа, якщо число ціле в обох випадках, то відповідь вірна.

Що означає НОК у математиці

Як відомо, у математиці немає жодної марної функції, ця – не виняток. Найпоширенішим призначенням цього є приведення дробів до спільного знаменника. Що вивчають зазвичай у 5-6 класах середньої школи. Також додатково є спільним дільником для всіх кратних чисел, якщо такі умови стоять у завданні. Подібний вираз може знайти кратне не тільки до двох чисел, але й до значно більшої кількості – трьох, п'яти тощо. Чим більше чисел – тим більше дій у завданні, але складність від цього не збільшується.

Наприклад, дані числа 250, 600 і 1500, необхідно знайти їх загальний НОК:

1) 250 = 25 * 10 = 5 2 * 5 * 2 = 5 3 * 2 - на цьому прикладі детально описано розкладання на множники, без скорочення.

2) 600 = 60 * 10 = 3 * 2 3 *5 2 ;

3) 1500 = 15 * 100 = 33 * 5 3 *2 2 ;

Для того щоб скласти вираз, потрібно згадати всі множники, в цьому випадку дано 2, 5, 3 - для всіх цих чисел потрібно визначити максимальний ступінь.

Увага: всі множники необхідно доводити до спрощення, по можливості, розкладаючи до рівня однозначних.

Перевірка:

1) 3000/250 = 12 - вірно;

2) 3000/600 = 5 - вірно;

3) 3000/1500 = 2 - вірно.

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

Ще один спосіб

У математиці багато що пов'язано, багато що можна вирішити двома і більше способами, те саме стосується пошуку найменшого загального кратного, НОК. Наступний спосіб можна використовувати у випадку із простими двозначними та однозначними числами. Складається таблиця, в яку вносяться по вертикалі множинне, по горизонталі множник, а в клітинах стовпця, що перетинаються, вказується твір. Можна відобразити таблицю за допомогою рядка, береться число і в ряд записуються результати множення цього числа на цілі числа, від 1 до нескінченності, іноді вистачає і 3-5 пунктів, друге та наступні числа піддаються тому ж обчислювальному процесу. Все відбувається до того, як знайдеться загальне кратне.

Дані числа 30, 35, 42 необхідно знайти НОК, що пов'язує всі числа:

1) Кратні 30: 60, 90, 120, 150, 180, 210, 250 і т.д.

2) Кратні 35: 70, 105, 140, 175, 210, 245 і т.д.

3) Кратні 42: 84, 126, 168, 210, 252 і т.д.

Помітно, що всі числа досить різні, єдине серед них число 210, ось воно і буде НОК. Серед пов'язаних з цим обчисленням процесів є також найбільший спільний дільник, що обчислюється за схожими принципами і часто зустрічається в задачах, що сусідять. Відмінність невелика, але досить значуще, НОК передбачає обчислення числа, яке ділиться попри всі дані вихідні значення, а НОД передбачає під собою обчислення найбільшого значення яке діляться вихідні числа.

Друге число: b=

Розділювач розрядівБез роздільника пробіл " ´

Результат:

Найбільший спільний дільник НОД( a,b)=6

Найменше загальне кратне НОК( a,b)=468

Найбільше натуральне число, яке діляться без залишку числа a і b, називається найбільшим спільним дільником(НД) цих чисел. Позначається НОД(a,b), (a,b), gcd(a,b) або hcf(a,b).

Найменше загальне кратне(НОК) двох цілих чисел a та b є найменше натуральне число, яке ділиться на a та b без залишку. Позначається НОК(a,b), або lcm(a,b).

Цілі числа a та b називаються взаємно простимиякщо вони не мають жодних спільних дільників крім +1 і −1.

Найбільший спільний дільник

Нехай дані два позитивні числа a 1 і a 2 1). Потрібно знайти спільний дільник цих чисел, тобто. знайти таке число λ , яке ділить числа a 1 і a 2 одночасно. Опишемо алгоритм.

1) У цій статті під словом число будемо розуміти ціле число.

Нехай a 1 ≥ a 2 , і нехай

де m 1 , a 3 деякі цілі числа, a 3 <a 2 (залишок від розподілу a 1 на a 2 має бути менше a 2).

Припустимо, що λ ділить a 1 і a 2 , тоді λ ділить m 1 a 2 та λ ділить a 1 −m 1 a 2 =a 3 (Затвердження 2 статті "Дільність чисел. Ознака ділимості"). Звідси випливає, що кожен спільний дільник a 1 і a 2 є спільним дільником a 2 та a 3 . Справедливе і протилежне, якщо λ спільний дільник a 2 та a 3 , то m 1 a 2 та a 1 =m 1 a 2 +a 3 також поділяються на λ . Отже спільний дільник a 2 та a 3 є також спільний дільник a 1 і a 2 . Так як a 3 <a 2 ≤a 1 , то можна сказати, що розв'язання задачі знаходження загального дільника чисел a 1 і a 2 зведено до більш простого завдання знаходження загального дільника чисел a 2 та a 3 .

Якщо a 3 ≠0, то можна розділити a 2 на a 3 . Тоді

де m 1 і a 4 деякі цілі числа, ( a 4 залишок від розподілу a 2 на a 3 (a 4 <a 3)). Подібними міркуваннями ми приходимо до висновку, що спільні дільники чисел a 3 та a 4 збігаються із загальними дільниками чисел a 2 та a 3 , а також із спільними дільниками a 1 і a 2 . Так як a 1 , a 2 , a 3 , a 4 , ... числа, що постійно убувають, і так як існує кінцева кількість цілих чисел між a 2 і 0, то на якомусь кроці n, залишок від ділення a n на a n+1 дорівнюватиме нулю ( a n+2 = 0).

Кожен спільний дільник λ чисел a 1 і a 2 також дільник чисел a 2 та a 3 , a 3 та a 4 , .... a n та a n+1. Справедливо та зворотне, спільні дільники чисел a n та a n+1 є також дільниками чисел a n−1 та a n, ...., a 2 та a 3 , a 1 і a 2 . Але спільний дільник чисел a n та a n+1 є число a n+1, т.к. a n та a n+1 без залишку поділяються на a n+1 (згадаймо, що a n+2 = 0). Отже a n+1 є і дільником чисел a 1 і a 2 .

Зазначимо, що число a n+1 є найбільшим дільником чисел a n та a n+1 , оскільки найбільший дільник a n+1 є сам a n+1. Якщо a n+1 можна як твори цілих чисел, то ці числа також є загальними дільниками чисел a 1 і a 2 . Число a n+1 називають найбільшим спільним дільникомчисел a 1 і a 2 .

Числа a 1 і a 2 може бути як позитивними, і негативними числами. Якщо один із чисел дорівнює нулю, то найбільший загальний дільник цих чисел дорівнюватиме абсолютній величині іншого числа. Найбільшого загального дільника нульових чисел не визначено.

Вищевикладений алгоритм називається алгоритмом Евклідадля знаходження найбільшого спільного дільника двох цілих чисел.

Приклад знаходження найбільшого спільного дільника двох чисел

Знайти найбільший спільний дільник двох чисел 630 та 434.

Крок 1. Ділимо число 630 на 434. Залишок 196.
Крок 2. Ділимо число 434 на 196. Залишок 42.
Крок 3. Ділимо число 196 на 42. Залишок 28.
Крок 4. Ділимо число 42 на 28. Залишок 14.
Крок 5. Ділимо число 28 на 14. Залишок 0.

На кроці 5 залишок від розподілу дорівнює 0. Отже, найбільший загальний дільник чисел 630 і 434 дорівнює 14. Зауважимо, що числа 2 і 7 також є дільниками чисел 630 і 434.

Взаємно прості числа

Визначення 1. Нехай найбільший спільний дільник чисел a 1 і a 2 дорівнює одиниці. Тоді ці числа називаються взаємно простими числами, які не мають спільного дільника

Теорема 1. Якщо a 1 і a 2 взаємно прості числа, а λ якесь число, то будь-який спільний дільник чисел λa 1 і a 2 є також загальним дільником чисел λ і a 2 .

Доведення. Розглянемо алгоритм Евкліда знаходження найбільшого спільного дільника чисел a 1 і a 2 (див. вище).

З умови теореми випливає, що найбільшим спільним дільником чисел a 1 і a 2 , і отже a n та a n+1 є 1. Тобто. a n+1 =1.

Помножимо всі ці рівності на λ тоді

Нехай спільний дільник a 1 λ і a 2 є δ . Тоді δ входить множником у a 1 λ , m 1 a 2 λ і в a 1 λ -m 1 a 2 λ =a 3 λ (Див. "Дільність чисел",Твердження 2). Далі δ входить множником у a 2 λ і m 2 a 3 λ , і, отже, входить множником у a 2 λ -m 2 a 3 λ =a 4 λ .

Розмірковуючи так ми переконуємось, що δ входить множником у a n−1 λ і m n−1 a n λ , і, отже, в a n−1 λ −m n−1 a n λ =a n+1 λ . Так як a n+1 =1, то δ входить множником у λ . Отже число δ є спільним дільником чисел λ і a 2 .

Розглянемо окремі випадки теореми 1.

Слідство 1. Нехай aі cпрості числа щодо b. Тоді їхній твір acє простим числом щодо b.

Справді. З теореми 1 acі bмають тих же спільних дільників, що й cі b. Але числа cі bвзаємно прості, тобто. мають єдиний спільний дільник 1. acі bтакож мають єдиний спільний дільник 1. Отже acі bвзаємно прості.

Слідство 2. Нехай aі bвзаємно прості числа та нехай bділить ak. Тоді bділить і k.

Справді. З умови затвердження akі bмають спільний дільник b. У силу теореми 1, bмає бути спільним дільником bі k. Отже bділить k.

Наслідок 1 можна узагальнити.

Слідство 3. 1. Нехай числа a 1 , a 2 , a 3 , ..., a m прості щодо числа b. Тоді a 1 a 2 , a 1 a 2 · a 3 , ..., a 1 a 2 a 3 ··· a m , добуток цих чисел простий щодо числа b.

2. Нехай маємо два ряди чисел

таких, що кожне число першого ряду просте по відношенню до кожного числа другого ряду. Тоді твір

Потрібно знайти такі числа, які поділяються на кожне із цих чисел.

Якщо число ділиться на a 1 , то воно має вигляд sa 1 , де sякесь число. Якщо qє найбільший спільний дільник чисел a 1 і a 2 , то

де s 1 - деяке ціле число. Тоді

є найменшим загальним кратним чисел a 1 і a 2 .

a 1 і a 2 взаємно прості, то найменше загальне кратне чисел a 1 і a 2:

Потрібно знайти найменше загальне кратне цих чисел.

З вищевикладеного випливає, що будь-яке кратне чисел a 1 , a 2 , a 3 має бути кратним чисел ε і a 3 і назад. Нехай найменше загальне кратне чисел ε і a 3 є ε 1 . Далі, кратне чисел a 1 , a 2 , a 3 , a 4 має бути кратним чисел ε 1 і a 4 . Нехай найменше загальне кратне чисел ε 1 і a 4 є ε 2 . Таким чином з'ясували, що всі кратні чисел a 1 , a 2 , a 3 ,...,a m збігаються з кратними деякого певного числа ε n, яке називають найменшим загальним кратним даних чисел.

В окремому випадку, коли числа a 1 , a 2 , a 3 ,...,a m взаємно прості, то найменше загальне кратне чисел a 1 , a 2 як було показано вище має вигляд (3). Далі, оскільки a 3 просте по відношенню до чисел a 1 , a 2 , тоді a 3 просте стосовно числа a 1 · a 2 (Наслідок 1). Значить найменше загальне кратне чисел a 1 ,a 2 ,a 3 є число a 1 · a 2 · a 3 . Розмірковуючи аналогічним чином, ми приходимо до наступних тверджень.

Твердження 1. Найменше загальне кратне взаємно простих чисел a 1 , a 2 , a 3 ,...,a m дорівнює їхньому твору a 1 · a 2 · a 3 ··· a m.

Твердження 2. Будь-яке число, яке поділяється на кожне із взаємно простих чисел a 1 , a 2 , a 3 ,...,a m ділиться також на їх твір a 1 · a 2 · a 3 ··· a m.