Найбільший спільний дільник (НСД)

⇐ ПредыдущаяСтр 2 из 4Следующая ⇒

Найбільше натуральне число, на яке ділиться кожне з чисел a і b, називається найбільшим спільним дільником чисел a і b і позначається НСД (a; b).

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

Наприклад: 12 = 2∙2∙3; 18 = 2∙3∙3.

НСД (12;18) = 2∙3 = 6.

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

Наприклад: 2100 = 2²∙3·5²∙7; 280 = 2³∙5∙7.

НСД (2100;280) = 2²∙5∙7 = 140.

Якщо всі дані числа кратні одному з них, це число буде найбільшим спільним дільником даних чисел. Наприклад: НСД (12;48;6;24) = 6.

Два натуральних числа, найбільший спільний дільник яких дорівнює 1, називаються взаємно простими. Два прості числа завжди будуть взаємно простими (наприклад, 13 і 23). Степені різних простих чисел також є взаємно простими.

Наприклад: 49 = 7∙7; 27 = 3∙3∙3.

НСД (49;27) = 1.

Найменше спільне кратне (НСК)

Найменшим спільним кратним натуральних чисел a і b називається найменше натуральне число, яке ділиться на кожне з цих чисел. НСК можна шукати для будь-якої кількості чисел. Щоб знайти найменше спільне кратне кількох чисел, кожне з них розкладають на прості множники й помножують усі множники, які зустрічаються хоча б в одному розкладанні.

Наприклад: 24 = 2∙2∙2∙3; 36 = 2∙2∙3∙3.

НСК (24;36) = 2∙2∙2∙3∙3 = 72.

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

Наприклад: 18 = 2∙3²; 24 = 2³∙3; 54 = 2·3³.

НСК (18;24;54) = 2³·3³ = 2∙2∙2∙3∙3∙3 = 216.

Якщо одне з даних чисел кратне іншим, то воно є найменшим спільним кратним цих чисел. Наприклад, НСК(24;12;8;3) = 24. Найменшим спільним кратним взаємно простих чисел (зокрема простих чисел) є їх добуток.

Наприклад: НСК(11;17) = 187, НСК (25;12) = 300.

Інші відомості про НСК та НСД

НСД двох чисел a та b це найбільше ціле число d, на яке a та b діляться без остачі. Не важко обчислити, наприклад, НСД(12, 18) = 6. Але що робити, якщо одне з чисел дорівнює 0? А якщо a чи b від’ємне? Над цим питанням на шкільних уроках, напевне, міркував не кожен учень. Для того щоб коректно відповісти на ці питання, наведемо означення найбільшого спільного дільника.

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

Виходячи з означення, мають місце наступні співвідношення:

НСД(a, b) = НСД(b, a),

НСД(a, b) = НСД(-a, b)

НСД(a, 0) = |a|

Чому, наприклад, НСД(-12, 18) дорівнює 6, а не -6? Адже ж числа -12 та 18 діляться націло на 6 та на -6. Відповідь є простою: НСД – це найбільший спільний дільник, а число 6 більше за -6.

З поняттям найбільшого спільного дільника тісно пов’язане поняття найменшого спільного кратного.

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

Основна теорема арифметики стверджує, що довільне натуральне число n можна подати у вигляді добутку простих чисел:

n =

Такий розклад натурального числа називається канонічним. З нього випливає, що якщо a = , b = , то

НСД(a, b) = ,

НСК(a, b) =

Приклад 1.Розглянемо числа a = 24 та b = 18. Розкладемо їх на прості множники: 24 = 2³ * 3, 18 = 2 * 3². Отже

НСД(24, 18) = 2^min(3,1) * 3^min(1,2) = 2¹ * 3¹ = 6,

НСК(24, 18) = 2^max(3,1) * 3^max(1,2) = 2³ * 3² = 8 * 9 = 72

Як раз такий метод, базований на використанні канонічного розкладу чисел, ми вивчаємо у школі для знаходження НСД та НСК. Але цей метод не є ефективним для реалізації алгоритмів їх обчислення.

Розглянемо наступний факт. Якщо НСД(a, b) = d, то a та b діляться на d. Отже їх різниця a – b також ділиться на d. Має місце наступне рекурентне співвідношення для обчислення НСД:

НСД(a, b) =

Приклад 2. Нехай a = 32, b = 12. Тоді

НСД(32, 12) = НСД(32 – 12, 12) = НСД(20, 12) = НСД(20 – 12, 12) = НСД(8, 12) =

НСД(8, 12 – 8) = НСД(8, 4) = НСД(8 – 4, 4) = НСД(4, 4) = НСД(4 – 4, 4) = =НСД(0,4) = 4

Наведений метод обчислення також не є оптимальним. Наприклад, для знаходження НСД(1000000, 2) слід виконати 500000 операцій віднімання. Для прискорення обчислення НСД операцію віднімання замінимо операцією взяття залишку від ділення:

НСД(a, b) =

Приклад 3.Нехай a = 78, b = 14. Тоді

НСД(78, 14) = НСД(78 mod 14, 14) = НСД(8, 14) = НСД(8, 14 mod 8) = НСД(8, 6) =

НСД(8 mod 6, 6) = НСД(2, 6) = НСД(2, 6 mod 2) = НСД(2, 0) = 2

Теорема. Між НСД та НСК двох чисел має місце наступне співвідношення:

a * b = НСД(a, b) * НСК(a, b)

Дата добавления: 2018-02-18; просмотров: 2184; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 123 4 Следующая ⇒

Мы поможем в написании ваших работ!