2. Обчислення найбільшого спільного дільника і найменшого спільного кратного за канонічним розкладом чисел

Теорема. НСД (а,b) є найменшим спільним кратним усіх спільних дільників чисел а і b.

Нехай треба знайти НСД і НСК двох чисел 360 і 525. За основною теоремою арифметики ці числа можна подати однозначно у канонічному вигляді.( Будь-яке натуральне число, більше 1, може бути розкладене в добуток простих співмножників. Цей розклад є єдиним, якщо не враховувати порядок слідування співмножників.)

360 = 2³3²5; 525 = 35²7. У розклад на прості множники НСД цих чисел повинні ввійти всі спільні прості множники, причому кожний з них треба взяти з найменшим показником, з яким він входить в канонічні розклади даних чисел. Отже, НСД (360, 525) = 35 = 15.

У розклад на прості множники НСК (360, 525) повинні ввійти всі прості множники, які входять принаймні в один розклад, причому кожний з них треба взяти з найбільшим показником. НСК (360, 525) = 2³  3²  5²  7 = 12600.

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

Теорема. НСД(а, b)  НСК(а, b) = а  b.

Наслідок. Якщо НСД(а, b) = 1, то НСК(а, b) = аb.

Таким чином, НСК двох чисел дорівнює добутку цих чисел тоді і тільки тоді, коли ці числа взаємно прості.

Щоб знайти НСД натуральних чисел за їхнім канонічним розкладом, треба спочатку розкласти ці числа на прості множники. Для великих чисел це складна задача. З часів Евкліда (ІІІ ст. н. е.) відомий більш ефективний спосіб знаходження НСД, який оснований на діленні з остачею і називається алгоритмом Евкліда.

Лема 1. Якщо а  b, то НСД(а, b) = b.

Лема 2. Якщо a = bq + r, де a, b, r – натуральні числа, то НСД(а, b) = НСД(b, r).

Покажемо, що сукупність спільних дільників а і b збігається з множиною дільників b і r то d буде спільним дільником а = bq + r і b. Справедливе й обернене, якщо d – спільний дільник а і b, то d є дільником і числа r = a – bq, a отже, спільним дільником чисел b i r. Таким чином, множина спільних дільників чисел а і b збігається з множиною спільних дільників b i r. Тому вони мають один і той самий найбільший дільник. Отже, НСД(а, b) = НСД(b, r). Лему доведено.

3. Алгоритм Евкліда

Розглянемо алгоритм Евкліда для знаходження НСК довільних натуральних чисел а і b. Нехай а  b. Якщо а  b, то за лемою 1 НСД(а, b) = b. Якщо а = bq + r, де r  0, то за лемою 2 задача знаходження НСД зводиться до обчислення НСД чисел b i r, де r < b. Якщо b  r, то НСД(b, r) = r, а отже, і НСД(а, b) = r. Якщо при діленні b на r матимемо остачу 0 < r₁ < r, то b = rq₁ + r₁, і тому НСД(а, b) = НСД(b, r) = НСД(r, r₁). Продовжуючи описаний процес, діставатимемо все менші і менші остачі : r, r₁, … r_m. З рештою дістанемо остачу, яка ділить попередню остачу. Згідно з лемою 2, ця, відмінна від 0 , остача і є НСД(а, b).

Таким чином, доведено теорему: НСД двох натуральних чисел дорівнює останній, відмінній від нуля остачі в алгоритмі Евкліда для цих чисел.

Алгоритм Евкліда як спосіб послідовного ділення зручно записувати у вигляді многократного ділення кутом.

Приклад. Знайдемо НСД(90, 35).

90 35 Таким чином,

70 2 90 = 35  2 + 20

35. 2 0

2 0 1 35 = 20  1 + 15

20. 1 5

15 1 20 = 15  1 + 5

15. 5

15. 3 15 = 5  1 + 0

0

Отже, остання відмінна від нуля остача дорівнює 5, тому НСД(90,35) = 5.

Позначимо 90 через а, 35 – через b. Рівність 20 = 15  1+ 5 запишемо так: 5 = 20 – 15  1. З попередньої рівності знайдемо: 15 = b – 20  1. Підставимо це значення 15 у вираз 5 = 20 – 15  1. Дістанемо: 5 = 20 –(b – 20  1)1. З рівності: 90=35  2 + 20 запишемо 20 =а – b  2. Підставимо це значення у попередній вираз. Тоді 5 = а – b  2-(b - (a – b  2) 1). Після виконання обчислень матимемо: 5= а  2 + b  (-5). Отже, d=ax - by.

З алгоритма Евкліда випливає таке твердження: для будь-яких двох натуральних чисел а і b знайдуться такі натуральні числа x i y, що НСД(а, b) = ax – by.

На основі цього твердження можна дійти висновку про те, що коли d = НСД(a,b), то рівняння виду d = ax – by завжди розв’язне у множині цілих чисел.

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

Справді, нехай добуток ab натуральних чисел a i b ділиться на просте число p. Припустимо, що а не ділиться на p. Тоді НСД(а, p) =1. Отже, знайдуться такі числа x i y, що 1 = ax + py. Помножимо дану рівність на число b. Дістанемо: b = abx + pby. Як бачимо, кожний з доданків суми ділиться на р, тому й b  p.

Після обчислення за допомогою алгоритма Евкліда НСД двох чисел, можна знайти їхнє НСК, використовуючи залежність між НСД і НСК. Так, НСК(90, 35) = 90  35 : 5 = 630.

Алгоритм Евкліда є тим загальним методом, за яким через скінчене число кроків можна обчислити НСД і НСК будь-яких двох і більше натуральних чисел.