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

Визначення 2

Якщо натуральне число a ділиться на натуральне число $b$, $b$ називають дільником числа $a$, а число $a$ називають кратним числа $b$.

Нехай $a$ та $b$-натуральні числа. Число $c$ називають спільним дільником і для $a$ і $b$.

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

$НОД \ (a; b) \ або \ D \ (a; b) $

Щоб знайти найбільший спільний дільник двох, чисел необхідно:

Знайти добуток чисел, знайдених на кроці 2. Отримане число і буде найбільшим шуканим спільним дільником.

Приклад 1

Знайти НОД чисел $121$ і $132.$

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

Вибрати числа, які входять до розкладання цих чисел

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

Знайти добуток чисел, знайдених на кроці 2. Отримане число і буде найбільшим шуканим спільним дільником.

$НОД=2\cdot 11=22$

Приклад 2

Знайти НОД одночленів $63$ і $81$.

Будемо знаходити згідно з представленим алгоритмом. Для цього:

Розкладемо числа на прості множники

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

Вибираємо числа, що входять до розкладання цих чисел

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

Знайдемо добуток чисел, знайдених на кроці 2. Отримане число і буде найбільшим шуканим спільним дільником.

$НОД=3\cdot 3=9$

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

Приклад 3

Знайти НОД чисел $48$ та $60$.

Рішення:

Знайдемо безліч дільників числа $48$: $\left$(\rm 1,2,3.4.6,8,12,16,24,48)\right$$

Тепер знайдемо безліч дільників числа $60$:$\ \left$(\rm 1,2,3,4,5,6,10,12,15,20,30,60)\right$$

Знайдемо перетин цих множин: $ \ left \ (( \ rm 1,2,3,4,6,12) \ right \) $ - це безліч буде визначати безліч спільних дільників чисел $ 48 $ і $ 60 $. Найбільший елемент у даній множині буде число $12$. Значить, найбільший спільний дільник чисел $48$ і $60$ буде $12$.

Визначення НОК

Визначення 3

Загальним кратним натуральних чисел$a$ і $b$ називається натуральне число, яке кратне $a$ і $b$.

Загальними кратними чисел називаються числа які діляться на вихідні без залишку.

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

Щоб знайти НОК двох чисел, необхідно:

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

Приклад 4

Знайти НОК чисел $99$ та $77$.

Будемо знаходити згідно з представленим алгоритмом. Для цього

Розкласти числа на прості множники

$99=3\cdot 3\cdot 11$

Виписати множники, що входять до складу першого

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

Знайти добуток чисел, знайдених на кроці 2.Отримане число і буде шуканим найменшим загальним кратним

$НОК=3cdot 3cdot 11cdot 7=693$

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

Твердження, на яких заснований алгоритм Евкліда:

Якщо $a$ і $b$ --натуральні числа, причому $a\vdots b$, то $D(a;b)=b$

Якщо $a$ і $b$ --натуральні числа, такі що $b

Користуючись $D(a;b)= D(a-b;b)$, можна послідовно зменшувати ці цифри до тих пір, поки не дійдемо до такої пари чисел, що одне з них ділиться на інше. Тоді найменше з цих чисел і буде шуканим найбільшим спільним дільником для чисел $a$ і $b$.

Властивості НОД та НОК

Будь-яке загальне кратне чисел $a$ і $b$ ділиться на K$(a;b)$
Якщо $a\vdots b$ , то $(a;b)=a$

Якщо К$(a;b)=k$ і $m$-натуральне число, то К$(am;bm)=km$

Якщо $d$-загальний дільник для $a$ і $b$, то К($\frac(a)(d);\frac(b)(d)$)=$\ \frac(k)(d) $

Якщо $a\vdots c$ і $b\vdots c$ , то $\frac(ab)(c)$ - загальне кратне чисел $a$ і $b$

Для будь-яких натуральних чисел $a$ і $b$ виконується рівність

$D(a;b)\cdot До(a;b)=ab$

Будь-який спільний дільник чисел $a$ і $b$ є дільником числа $D(a;b)$

1.1 Застосування алгоритму Евкліда

Як і будь-яка добротно виконана робота, алгоритм Евкліда дає набагато більше, ніж від нього очікувалося спочатку отримати. З його розглядання ясно, наприклад, що сукупність дільників і b збігається з сукупністю дільників (a, b). Ще він дає практичний спосіб знаходження чисел u та v з Z (або, якщо завгодно, з теореми пункту 2) таких, що

r n = au + bv = (a, b).

Справді, з ланцюжка рівностей маємо:

r n = r n -2 - r n -1 q n = r n -2 - (r n -3 - r n -2 q n -1) q n =...

(Йдемо по ланцюжку рівностей знизу вгору, висловлюючи з кожної наступної рівності залишок і підставляючи його в вираз, що вийшов до цього моменту)

Au + bv = (a, b).

Безсумнівно, описана Евклідом процедура визначення загальної міри двох величин стосовно числа (а загальна міра двох натуральних чисел, очевидно, є їх найбільший спільний дільник) була винайдена задовго до Евкліда. Так само знаходили НОД і древні китайські математики. І тільки те, що ця процедура стала відома в епоху Відродження саме з «Початок, дало їй назву алгоритм Евкліда»

Швидше за все, вона виникла з комерційної практики древніх купців, коли треба було порівнювати різні відносини цілих чисел. Як, наприклад, порівнювати відносини чисел 3703700 та 1234567 та чисел 22962965 та 7654321? Цілком природною була спроба дізнатися, скільки разів менша кількість вкладається в більшому. Легко перевірити, що 3703700 = 2 · 1234567 + 1234566, а 22962965 = 3 · 7654321 + 2. Зрозуміло тепер, що відношення 3703700 до 1234567 менше, ніж відношення 22965.

2,99999919 <= 3, 000000261,

Стародавні обчислювачі пояснювали довгою фразою.

Якби довелося порівняти ближчі відносини чисел, наприклад, і, то обчислення були б складнішими:

71755875 = 61735500 + 10020375;

61735500 = 6 · 10020375 + 1613250;

10020375 = 6 · 1613250 + 340875;

1613250 = 4 · 340875 + 249750;

340875 = 249750 + 91125;

249750 = 2 · 91125 + 67500;

91125 = 67500 + 23625;

67500 = 2 · 23625 + 20250;

23625 = 20250 + 3375;

20250 = 6 · 3375.

Алгоритм Евкліда тут дозволяє визначити НОД чисел 71755875 і 61735500, рівний 3375 і відповідає розкладу відношення 71755875 до 61735500 ланцюговий дріб:

Алгоритм Евкліда виявляється еквівалентним сучасної процедури розкладання числа в ланцюгову дріб і більше, дозволяє «округлити» відносини чисел, тобто. замінювати дріб із великим знаменником на дуже близький до нього дріб із меншим знаменником. Справді, вираз

рівне дробу, в сучасній математиці називається «відповідним дробом» розкладання відношення б = в ланцюговий (або безперервний) дріб.

Зрозуміло, що

б = 1 +< 1 + и б=1 + > 1+ = ,

оскільки

Наведене порівняння було виконано в III ст. до н.е. Аристархом Самоським у трактаті «Про відстань і розміри Місяця та Сонця».

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

Алгоритми з багаточленами

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

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

Аналіз алгоритму Евкліда в кільцях Евкліда

Перш ніж приступити до аналізу алгоритму Евкліда розглянемо числа Фібоначчі. Суть послідовності Фібоначчі в тому, що, починаючи з 1,1, наступне число виходить додаванням двох попередніх. 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ……

Історія формування поняття "алгоритм". Найвідоміші алгоритми в історії математики

Алгоритм Евкліда є універсальним способомщо дозволяє обчислювати найбільший загальний дільник двох позитивних цілих чисел. Опис алгоритму знаходження НОД розподілом: 1. Більше число ділимо на менше 2. Якщо ділиться без залишку...

Кільце цілих чисел Гауса

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

Математичні засади системи залишкових класів

Розглянемо приклад. Нехай р = 6. Тоді маємо шість класів розбиття множини цілих чисел за модулем 6: r = 0; r = 1; r = 2; r = 3; r = 4; r = 5; де через r позначено залишок від розподілу цілого числа на 6...

Методика вивчення багаточленів на факультативних заняттях у старших класах середньої загальноосвітній школі

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

Основні етапи становлення та структура сучасної математики

У III столітті до нашої ери в Олександрії з'явилася книга Евкліда з тією ж назвою, в перекладі "Початку". Від латинської назви "Початок" походить термін "елементарна геометрія". Незважаючи на те...

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

Застосування методів дискретної математики економіки.

Фірмі, що займається перевезенням швидкопсувних товарів, необхідно доставити товар з Суйфеньхе в Хабаровськ, причому маршрутів, якими можна зробити доставку кілька. Відстань між Суйфеньхе та містом 2 складає 15 км.

Розвиток поняття "Простір" та неевклідова геометрія

Спеціальні методи інтегрування раціональних виразів

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

Теорія залишків

Визначення. Число d Z , що ділить одночасно числа а, b, c, ..., k Z, називається загальним дільником цих чисел. Найбільше d з такою властивістю називається найбільшим спільним дільником. Позначення: d = (a, b, c, ..., k). Теорема. Якщо (a, b) = d...

Теорія залишків

Нехай потрібно вирішити лінійне діофантове рівняння: ax + by = c, де a, b, c Z; a та b - не нулі. Спробуємо поміркувати, дивлячись на це рівняння. Нехай (a, b) = d. Тоді a = a 1 d; b = b 1 d і рівняння виглядає так: a 1 d x + b 1 d y y = c , тобто. d·(a 1 x + b 1 y) = c...

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

Навігація на сторінці.

Алгоритм Евкліда для знаходження НОД

Зауважимо, що якби ми від початку звернулися до таблиці простих чисел , то з'ясували б, що числа 661 і 113 – прості, звідки можна було б відразу сказати, що й найбільший спільний дільник дорівнює 1 .

Відповідь:

НОД (661, 113) = 1 .

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

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

Наведемо приклад пояснення правила перебування НОД. Нехай нам відомі розкладання чисел 220 і 600 на прості множники, вони мають вигляд 220 = 2 · 2 · 5 · 11 і 600 = 2 · 2 · 2 · 3 · 5 · 5 . Загальними простими множниками, що беруть участь у розкладанні чисел 220 і 600 є 2 , 2 і 5 . Отже, НОД (220, 600) = 2 · 2 · 5 = 20 .

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

Розглянемо приклад знаходження НОД за озвученим правилом.

приклад.

Знайдіть найбільший спільний дільник чисел 72 та 96 .

Рішення.

Розкладемо на прості множники числа 72 і 96:

Тобто, 72 = 2 · 2 · 2 · 3 · 3 і 96 = 2 · 2 · 2 · 2 · 2 · 3 . Загальними простими множниками є 2, 2, 2 та 3. Таким чином, НОД(72, 96)=2·2·2·3=24 .

Відповідь:

НОД (72, 96) = 24 .

На закінчення цього пункту зауважимо, що справедливість наведеного правила знаходження НОД випливає з якості найбільшого спільного дільника, яка стверджує, що НОД(m·a 1 , m·b 1)=m·НОД(a 1 , b 1), де m – будь-яке ціле додатне число.

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

Знаходження найбільшого загального дільника трьох чи більшої кількості чисел може бути зведено до послідовного знаходження НОД двох чисел. Ми про це згадували при вивченні властивостей НОД. Там ми сформулювали і довели теорему: найбільший загальний дільник кількох чисел a 1 , a 2 , …, ak дорівнює числу d k , яке знаходиться при послідовному обчисленні НОД(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.

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

приклад.

Знайдіть найбільший спільний дільник чотирьох чисел 78 , 294 , 570 та 36 .

Рішення.

У цьому прикладі a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.

Спочатку за алгоритмом Евкліда визначимо найбільший спільний дільник d 2 перших двох чисел 78 і 294 . При розподілі отримуємо рівності 294 = 78 · 3 +60; 78 = 60 · 1 +18; 60 = 18 · 3 +6 і 18 = 6 · 3 . Таким чином, d 2 = НОД (78, 294) = 6 .

Тепер обчислимо d 3 = НОД (d 2 , a 3) = НОД (6, 570). Знову застосуємо алгоритм Евкліда: 570 = 6 · 95, отже, d 3 = НОД (6, 570) = 6 .

Залишилось обчислити d 4 = НОД (d 3 , a 4) = НОД (6, 36). Оскільки 36 ділиться на 6 , то d 4 = НОД (6, 36) = 6 .

Отже, найбільший загальний дільник чотирьох даних чисел дорівнює d 4 =6 , тобто НОД(78, 294, 570, 36)=6 .

Відповідь:

НОД (78, 294, 570, 36) = 6 .

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

приклад.

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

Рішення.

Розкладемо числа 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 . Отже, НОД (78, 294, 570, 36) = 2 · 3 = 6.

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

Обчислення НОД поділом

Найбільший спільний дільник пари чисел – це найбільше число, яке ціле ділить обидва числа пари. Нехай потрібно обчислити НОД для чисел 108 і 72. Алгоритм обчислення поділом буде таким:

Розділимо більше (ділене) на менше (ділитель): 108 / 72 = 1, залишок 36.
Оскільки залишок не дорівнював нулю, то зробимо дільник ділимим, а залишок – дільником: 72 / 36 = 2, залишок 0.
Коли залишок дорівнює нулю, дільник є шуканим НОД для пари заданих чисел. Тобто НОД(108, 72) = 36. Справді, 108/36 = 3 і 72/36 = 2.

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

106/16 = 6, залишок 10
16/10 = 1, залишок 6
10/6 = 1, залишок 4
6/4 = 1, залишок 2
4/2 = 2, залишок 0
НОД(106, 16) = 2

Обчислення НІД відніманням

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

Нехай потрібно знайти НОД(108, 72):

108 - 72 = 36
72 - 36 = 36
36 - 36 = 0
НОД(108, 72) = 36

Знайдемо НОД(44, 60):

60 - 44 = 16
44 - 16 = 28
28 - 16 = 12
16 - 12 = 4
12 - 4 = 8
8 - 4 = 4
4 - 4 = 0
НОД(44, 60) = 4

Цей алгоритм іноді описують по-іншому. Віднімання закінчують раніше, на кроці, коли одне число націло ділить інше. Тобто комбінують віднімання з перевіркою ділимості. Тоді перебування НОД для 44 і 60 буде виглядати так:

Чи ділить 44 націло 60? Ні. 60 – 44 = 16.
Чи ділить 16 націло 44? Ні. 44 – 16 = 28.
Чи ділить 16 націло 28? Ні. 28 – 16 = 12.
Чи ділить 12 націло 16? Ні. 16 – 12 = 4.
Чи ділить 4 націло 12? Так. Отже, НОД(44, 60) = 4.

Зверніть увагу, НОДом є не приватне, а дільник. Якщо у прикладі ми розділимо 12 на 4, то отримаємо 3. Але це не НОД.

Доказ алгоритму Евкліда

Візьмемо до уваги факт, що якщо одне натуральне число з пари націло ділить інше, то їх НОД дорівнюватиме меншому з них. Записати це можна так:

якщо a/b націло, то НОД(a, b) = b. Наприклад, НОД(15, 5) = 5.

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

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

якщо a< b, то НОД(a, b) = НОД(a, b - a).

Довести, що НОД(a, b) = НОД(a, b - a) можна в такий спосіб. Нехай b – a = c. Якщо якесь число x ділить націло a і b, воно буде також ділити націло c. Адже якщо a і b різні, то дільник у них вкладається ціле, але різне число разів. І якщо відняти одне з іншого, то дільник також повинен вкладатися ціле число разів у отриману різницю.

Якщо послідовно зменшувати a і b, то рано чи пізно дійдемо такого значення меншого з них, яке націло ділить більше. Найменше у такій парі буде найбільшим спільним дільником для вихідної пари натуральних чисел. У цьому полягає алгоритм Евклида.

Алгоритм Евкліда- Це алгоритм знаходження найбільшого загального дільника (НДД) пари цілих чисел.

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

Алгоритм знаходження НОД поділом

Більше ділимо на менше.
Якщо ділиться без залишку, то менше і є НОД (слід вийти з циклу).
Якщо є залишок, то більше замінюємо на залишок від поділу.
Переходимо до пункту 1.

Приклад:
Знайти НОД для 30 та 18.
30/18 = 1 (залишок 12)
18/12 = 1 (залишок 6)
12/6 = 2 (залишок 0)
Кінець: НОД – це дільник 6.
НОД (30, 18) = 6

a = 50 b = 130 while a != 0 and b != 0 : if a > b: a = a % b else : b = b % a print (a + b)

У циклі змінну a або b записується залишок від поділу. Цикл завершується, коли хоча б одна із змінних дорівнює нулю. Це означає, що інша містить НОД. Проте яка саме ми не знаємо. Тому для НОД знаходимо суму цих змінних. Оскільки в одній із змінних нуль, він не впливає на результат.

Алгоритм знаходження НІД відніманням

З більшого числа віднімаємо менше.
Якщо виходить 0, то означає, що числа дорівнюють один одному і є НОД (слід вийти з циклу).
Якщо результат віднімання не дорівнює 0, то більшу кількість замінюємо на результат віднімання.
Переходимо до пункту 1.

Приклад:
Знайти НОД для 30 та 18.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 - 6 = 0
Кінець: НОД - це зменшується або віднімається.
НОД (30, 18) = 6

a = 50 b = 130 while a != b: if a > b: a = a - b else : b = b - a print (a)