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

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

Для того, щоб знайти найбільший  спільний дільник (НСД) кількох натуральних чисел, потрібно:

1)                   розкласти їх у прості множники;

2)                   з множників, що входять до розкладання одного з цих чисел, викреслити ті, які не входять до розкладання інших чисел;

3)                   знайти добуток множників, що залишилися.

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

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

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

Приклад 1. Знайти НСД(4074, 2716)

4074 – 2716 = 1358,  отже, НСД(4074,2716) = НСД(2716,1358);

2716 – 1358 = 1358,  отже, НСД(2716,1358) = НСД(1358,1358); 1358 = 1358 , тому:  НСД(4074, 2716) = 1358.

Приклад 2. Знайти НСД(274, 1781).

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

НСД(274, 1781) = НСД(274, 1507) = НСД(274, 1233) = НСД(274, 959) = 

НСД(274, 685) = НСД(274, 411) =  НСД(274, 137) =  НСД(137,137) = 137

Як бачимо, віднімання довелось виконувати декілька разів. Виявляється, цього можна уникнути, якщо згадати про ділення чисел з остачею ( a = b  q + r).

 Для числа 1781 можемо записати:  1781 = 274  6 + 137

Отже, число 1781 можна відразу замінити на остачу від його ділення на 274, тому НСД( 274, 1781)  = НСД(274,137)

Таким чином, отримуємо ще одну властивість найбільшого спільного дільника:

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

НСД( a, b) = НСД (r, b), де r – остача від ділення  a на b.

Зазначимо ще один факт.

Для будь-яких двох натуральних чисел a і b добуток їх найбільшого спільного дільника на їх найменше спільне кратне дорівнює добутку самих чисел:  НСД(a, b)· НСК(a, b) = a· b

Приклад 3. Знайти  найменше спільне кратне  чисел 648 і 392.

За алгоритмом Евкліда знайдемо НСД (648, 392) = 8. (Перевірте самостійно!)

Використовуючи формулу, отримуємо:

НСД(648,392)· НСК(648,392) = 648·392,  тому  НСК(648,392) = 648·392:16 = 31752.

Отже, для будь-яких двох натуральних чисел а і b ми можемо за алгоритмом Евкліда знайти їх найбільший спільний дільник, а потім, скориставшись формулой, знайти їх найменше спільне кратне.

Приклад 4. Довести, що числа 2𝑛+3 і  5𝑛+7 взаємно прості при будьякому натуральному 𝑛.

За алгоритмом Евкліда знайдемо НСД (2𝑛+3;  5𝑛+7)

НСД (2𝑛+3;  5𝑛+7) = НСД (2𝑛+3;  3𝑛+4) = НСД (2𝑛+3;  𝑛+1) =  НСД (𝑛+2;  𝑛+1) = НСД (1;  𝑛+1) = 1, що й треба було довести.

З розвитком комп'ютерної техніки алгоритм Евкліда було покладено в основу програм знаходження найбільшого спільного дільника чисел

Вправи

1.          Знайдіть за алгоритмом Евкліда НСД(846, 246).

2.          Знайдіть за алгоритмом Евкліда НСД (3776, 7611).

3.          Знайдіть за алгоритмом Евкліда НCД (15283,10013). 

4.          Доведіть, що НСД (а, b) = НСД (а, а + b).

5.          Доведіть, що НСД (n, n + 1) = 1 при будь-якому натуральному  п.

6.          Доведіть, що НСД (2n, 2n + 2) = 2 при будь-якому натуральному  п.

7.          Доведіть, що НСД (a, b) = НСД (5a + 3b, 8a + 5b).

8.          Доведіть, що числа 14𝑛+3 і  21𝑛+4 взаємно прості при будь-якому натуральному 𝑛.

9.          Доведіть, що дріб  нескоротний при будь-якому натуральному 𝑛.

10.     Доведіть, що якщо а і b взаємно прості, то НСД (аm, b) = НСД (m, b).

11.     Доведіть, що якщо кожне з двох натуральних чисел a, b ділиться на m, то їх найбільший спільний дільник ділиться на m. 

12.     Знайдіть  НСК(846, 246). 

13.     Знайдіть НСК(3776, 7611).

14.     Знайдіть НСК(717, 843).

15.     Чи ділиться НСК(а, b) на НСД(а, b)?

Література

1.   Виноградов И.М. Основы теории чисел. М.: Наука, 1972

2.   Шнирельман Л.Г. Простые числа. М.-Л.: ГИТТЛ, 194

3.   Арнольд И.В. Теоретическая арифметика. М.: ГУПИ, 1938

4.   Тадеєв В.О. Неформальна математика. 6-9 класи. Навчальний посібник для учнів, які хочуть знати більше, ніж вивчається у школі. – Тернопіль: Навчальна книга – Богдан, 2003