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

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

Визначення 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)$

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

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

Визначення.

Найбільший спільний дільникдвох цілих чисел - це найбільше ціле число, що ділить два дані цілих числа.

Для короткого записунайбільшого спільного дільника часто використовують абревіатуру НОД – найбільший спільний дільник. Також найбільший загальний дільник двох чисел a та b часто позначають як НОД(a, b).

Наведемо приклад найбільшого спільного дільника (НДД)двох цілих чисел. Найбільший загальний дільник чисел 6 та −15 дорівнює 3 . Обґрунтуємо це. Запишемо всі дільники числа шість: ±6, ±3, ±1, а дільниками числа −15 є числа ±15, ±5, ±3 та ±1. Тепер можна знайти все спільні дільникичисел 6 та −15 , це числа −3 , −1 , 1 та 3 . Оскільки −3<−1<1<3 , то 3 – это наибольший общий делитель чисел 6 и −15 . То есть, НОД(6, −15)=3 .

Визначення найбільшого спільного дільника трьох та більшої кількостіцілих чисел аналогічно визначенню НОД двох чисел.

Визначення.

Найбільший спільний дільниктрьох і більшої кількості цілих чисел - це найбільше ціле число, що ділить одночасно всі дані числа.

Найбільший загальний дільник n цілих чисел a 1 , a 2 , …, a n ми позначатимемо як НОД (a 1 , a 2 , …, a n) . Якщо знайдено значення b найбільшого спільного дільника цих чисел, можна записати НОД(a 1 , a 2 , …, a n)=b.

Як приклад наведемо НОД чотирьох цілих чисел −8 , 52 , 16 та −12 , він дорівнює 4 , тобто НОД(−8, 52, 16, −12)=4 . Це можна перевірити, записавши усі дільники даних чисел, обравши з них спільні та визначивши найбільший спільний дільник.

Зазначимо, що найбільший загальний дільник цілих чисел може дорівнювати одному з цих чисел. Це твердження є слушним у тому випадку, якщо всі ці числа діляться на одне з них (доказ наведено в наступному пункті цієї статті). Наприклад, НОД(15, 60, −45)=15 . Це дійсно так, тому що 15 ділить і число 15, і число 60, і число -45, і не існує спільного дільника чисел 15, 60 і -45, який перевищує 15.

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

Властивості найбільшого спільного дільника, алгоритм Евкліда

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

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

Найбільший загальний дільник чисел a і b дорівнює найбільшому загальному дільнику чисел b і a, тобто НОД (a, b) = НОД (a, b) .

Ця властивість НОД безпосередньо випливає з визначення найбільшого спільного дільника.

Якщо a ділиться на b, то безліч спільних дільників чисел a і b збігається з безліччю дільників числа b, зокрема НОД(a, b)=b.

Доведення.

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

Зокрема, якщо числа a та b рівні, то НОД(a, b)=НД(a, a)=НД(b, b)=a=b. Наприклад, НОД(132, 132)=132 .

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

Якщо a=b·q+c , де a , b , c і q – цілі числа, то безліч спільних дільників чисел a і b збігаються з безліччю загальних дільників чисел b і c , зокрема, НОД(a, b)=НОД (b, c).

Обгрунтуємо цю властивість НОД.

Так як має місце рівність a = b · q + c, то кожен спільний дільник чисел a і b ділить також і c (це випливає з властивостей ділимості). З цієї причини, кожен спільний дільник чисел b і c ділить a . Тому сукупність спільних дільників чисел a і b збігається із сукупністю загальних дільників чисел b і c. Зокрема, повинні збігатися і найбільші з цих спільних дільників, тобто, має бути справедлива наступна рівність НОД(a, b) = НОД(b, c).

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

Перш ніж дати формулювання теореми, рекомендуємо освіжити в пам'яті теорему з розділу теорії , яка стверджує, що ділене a може бути представлене у вигляді b q + r , де b дільник, q деяке ціле число, зване неповним приватним, а r - ціле число, що задовольняє умову, зване залишком.

Отже, нехай для двох ненульових цілих позитивних чисел a і b справедлива низка рівностей

закінчується, коли r k+1 =0 (що неминуче, тому що b>r 1 >r 2 >r 3 , … - ряд зменшуваних цілих чисел, і цей ряд не може містити більш ніж кінцеве числопозитивних чисел), тоді r k - це найбільший загальний дільник чисел a і b, тобто r k = НОД (a, b).

Доведення.

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

Рухатимемося за записаними рівностями знизу вгору. З останньої рівності можна сказати, що r k−1 ділиться на r k . Враховуючи цей факт, а також попередня властивість НОД, передостання рівність r k−2 =r k−1 ·q k +r k дозволяє стверджувати, що r k−2 ділиться на r k , оскільки r k−1 ділиться на r k та r k ділиться на r k . За аналогією з третьої знизу рівності укладаємо, що r k-3 ділиться на r k . І так далі. З другої рівності отримуємо, що b ділиться на r k , та якщо з першої рівності отримуємо, що a ділиться на r k . Отже, r k є спільним дільником чисел a та b .

Залишилося довести, що r k = НОД(a, b) . Для достатньо показати, що будь-який загальний дільник чисел a і b (позначимо його r 0) ділить r k.

Рухатимемося по вихідним рівностям зверху вниз. З попередньої властивості з першої рівності слід, що r 1 ділиться на r 0 . Тоді з другої рівності отримуємо, що r2 ділиться на r0. І так далі. З останньої рівності одержуємо, що r k ділиться на r 0 . Таким чином, r k = НОД(a, b) .

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

Нехай a та b – цілі числа, одночасно не рівні нулютоді існують такі цілі числа u 0 і v 0 , то справедлива рівність НОД(a, b)=a·u 0 +b·v 0 . Остання рівність є лінійне уявлення найбільшого загального дільника чисел a і b , цю рівність називають співвідношенням Безу, а числа u 0 і v 0 - коефіцієнтами Безу.

Доведення.

За алгоритмом Евкліда ми можемо записати такі рівності

З першої рівності маємо r 1 =a−b·q 1 і, позначивши 1=s 1 і −q 1 =t 1 , ця рівність набуде вигляду r 1 =s 1 ·a+t 1 ·b , причому числа s 1 і t 1 – цілі. Тоді з другої рівності отримаємо r 2 =b−r 1 ·q 2 = b−(s 1 ·a+t 1 ·b)·q 2 =−s 1 ·q 2 ·a+(1−t 1 ·q 2)·b. Позначивши −s 1 ·q 2 =s 2 і 1−t 1 ·q 2 =t 2 , останню рівність можна записати у вигляді r 2 =s 2 ·a+t 2 ·b , причому s 2 і t 2 – цілі числа (оскільки сума, різниця і добуток цілих чисел є цілим числом). Аналогічно з третьої рівності отримаємо r 3 = s 3 a + t 3 b, з четвертої r 4 = s 4 a + t 4 b, і так далі. Нарешті, r k = s k · a + t k · b, де s k і t k - Цілі. Оскільки r k = НОД(a, b) , і, позначивши s k =u 0 і t k =v 0 , отримаємо лінійне уявлення НОД необхідного виду: НОД(a, b)=a·u 0 +b·v 0 .

Якщо m – будь-яке натуральне число, то НОД(m·a, m·b)=m·НОД(a, b).

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

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

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

Оскільки a=p·(a:p) і b=p·(b:p) , і з попередньої властивості, ми можемо записати ланцюжок рівностей виду НОД(a, b)=НОД(p·(a:p), p·(b:p))= p·НОД(a:p, b:p) , звідки і слід доводиться рівність.

Щойно доведена властивість найбільшого спільного дільника лежить в основі.

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

Найбільший загальний дільник чисел a 1 , a 2 , …, a k дорівнює числу 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.

Доказ виходить з алгоритму Евклида. Загальні дільники чисел a 1 і 2 збігаються з дільниками d 2 . Тоді загальні дільники чисел a 1 , a 2 і a 3 збігаються із загальними дільниками чисел d 2 і a 3 , отже, збігаються з дільниками d 3 . Загальні дільники чисел a 1 , a 2 , a 3 та a 4 збігаються із загальними дільниками d 3 та a 4 , отже, збігаються з дільниками d 4 . І так далі. Нарешті, загальні дільники чисел a 1 , a 2 , …, ak збігаються з дільниками d k . Оскільки найбільшим дільником числа d k є саме число d k , то НОД(a 1 , a 2 , …, a k) = d k.

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

Список літератури.

Віленкін Н.Я. та ін Математика. 6 клас: підручник для загальноосвітніх закладів.
Виноградов І.М. Основи теорії чисел.
Михелович Ш.Х. Теорія чисел.
Куликов Л.Я. та ін. Збірник завдань з алгебри та теорії чисел: Навчальний посібникдля студентів фіз.-мат. спеціальностей педагогічних інститутів

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

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

Необхідно знати:

Якщо деяке число можна використовувати для підрахунку різних предметівНаприклад, дев'ять стовпів, шістнадцять будинків, то воно є натуральним. Найменшим із них буде одиниця.
Коли натуральне число ділиться на інше натуральне число, то кажуть, що менше - це дільник більшого.
Якщо два і більше різних числаділяться на деяке число без залишку, то кажуть, що останнє буде їхнім спільним дільником (ОД).
Найбільший з ОД називається максимальним загальним дільником (НОД).
У такому разі, коли у числа є лише два натуральних дільника(Воно саме і одиниця), воно називається простим. Найменше серед них — двійка, до того ж вона й єдина парна в їхньому ряду.
Якщо у двох чисел максимальним спільним дільником є одиниця, вони будуть взаємно простими.
Число, у якого більше ніж два дільники, називається складовим.
Процес коли знаходяться всі прості множники, які при множенні між собою дадуть у творі початкове значення математики називають розкладанням на прості множники. Причому однакові множники у розкладанні можуть неодноразово зустрічатися.

У математиці прийнято такі записи:

Дільники Д (45) = (1; 3; 5; 9; 45).
ОД (8; 18) = (1; 2).
НОД (8; 18) = 2.

Різні способи знайти НОД

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

Наприклад, НОД (15; 45) = 15, НОД (48; 24) = 24.

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

Спосіб розкладання на прості співмножники

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

Приклад 1

Розглянемо, як знаходити НОД 36 і 90:

36 = 1*2*2*3*3;
90 = 1*2*3*3*5;

НОД (36; 90) = 1 * 2 * 3 * 3 = 18.

Тепер подивимося як знаходити те саме в випадку трьохчисел, Візьмемо для прикладу 54; 162; 42.

Як розкласти 36 ми вже знаємо, розберемося з рештою:

162 = 1*2*3*3*3*3;
42 = 1*2*3*7;

Таким чином, НОД (36; 162; 42) = 1 * 2 * 3 = 6.

Слід зазначити, що одиницю у розкладанні писати необов'язково.

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

Розділяти колонки можна як знаком розподілу, так і простою вертикальною рисою.

36/2 продовжимо наш процес поділу;
18/2 далі;
9/3 і ще раз;
3 / 3 сьогодні дуже просто;
1 - результат готовий.

Шукане 36 = 2 * 2 * 3 * 3.

Евклідів спосіб

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

Наведемо приклад використання даного алгоритму:

спробуємо з'ясувати який НОД у 816 і 252:

816/252 = 3 і залишок 60. Зараз 252 розділимо на 60;
252/60 = 4 у залишку цього разу виявиться 12. Продовжимо наш круговий процес, розділимо шістдесят на дванадцять;
60 / 12 = 5. Оскільки цього разу жодного залишку ми не отримали, то у нас готовий результат, дванадцять буде знаходженням для нас значенням.

Отже, після завершення нашого процесу ми отримали НОД (816;252) = 12.

Дії при необхідності визначення НОД якщо задано більше двох значень

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

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

Висновок

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

Хоча обидва способи і є цілком прийнятними, загальноосвітній школі набагато частіше застосовується перший спосіб. Це з тим, що розкладання на прості множники знадобиться щодо наступної навчальної теми- Визначення найбільшого загального кратного (НОК). Але все ж таки варто ще раз помітити — застосування алгоритму Евкліда жодною мірою не може вважатися помилковим.

Відео

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

Чи не отримали відповідь на своє запитання? Запропонуйте авторам тему.

Розв'яжемо завдання. У нас є два типи печива. Одні шоколадні, інші прості. Шоколадних 48 штук, а простих 36. Необхідно скласти з цього печива максимально можливе числоподарунків, при цьому треба використовувати їх усі.

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

Отримуємо,

48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48.
36: 1, 2, 3, 4, 6, 9, 12, 18, 36.

Знайдемо серед дільників спільні, які є як у першого, так і другого числа.

Спільними дільниками будуть: 1, 2, 3, 4, 6, 12.

Найбільшим із усіх спільних дільників є число 12. Це число називають найбільшим загальним дільником чисел 36 та 48.

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

Визначення найбільшого спільного дільника

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

Іноді для скорочення запису використовують абревіатуру НОД.

Деякі пари чисел мають як найбільшого загального дільника одиницю. Такі числа називають взаємно простими числами.Наприклад, числа 24 і 35. Мають НОД =1.

Як знайти найбільший спільний дільник

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

Можна зробити інакше. Спочатку розкласти на прості множники обидва числа.

48 = 2*2*2*2*3,
36 = 2*2*3*3.

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

48 = 2*2*2*2*3 ,
36 = 2*2*3 *3.

Залишаться множники 2, 2 і 3. Їх добуток дорівнює 12. Це число і буде найбільшим спільним дільником чисел 48 і 36.

Це правило можна поширити на випадок із трьома, чотирма і т.д. числами.

Загальна схема знаходження найбільшого спільного дільника

1. Розкласти числа на прості множники.
2. З множників, що входять до розкладання одного з цих чисел, викреслити ті, які не входять до розкладання інших чисел.
3. Порахувати твір множників, що залишилися.

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

Yandex.RTB R-A-339285-1

Що таке спільні дільники

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

У статті про кратних і дільників ми говорили, що ціле число завжди має кілька дільників. Тут нас цікавлять дільники відразу певної кількості цілих чисел, особливо загальні (однакові) всім. Запишемо основне визначення.

Визначення 1

Спільним дільником кількох цілих чисел буде таке число, яке може бути дільником кожного числа із зазначеної множини.

Приклад 1

Ось приклади такого дільника: трійка буде спільним дільником для чисел - 12 і 9, оскільки вірні рівності 9 = 3 · 3 і - 12 = 3 · (- 4). Числа 3 і - 12 мають інші спільні дільники, такі, як 1 , − 1 і − 3 . Візьмемо інший приклад. У чотирьох цілих чисел 3 , − 11 , − 8 та 19 буде два спільні дільники: 1 та - 1 .

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

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

Що таке найбільший спільний дільник (НДД)

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

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

Переходимо до формулювання основного визначення.

Визначення 2

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

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

Приклад 2

Який можна навести приклад НОД для двох цілих чисел? Наприклад, для 6 та - 15 це буде 3 . Обґрунтуємо це. Спочатку запишемо всі дільники шести: ±6, ±3, ±1, а потім усі дільники п'ятнадцяти: ±15, ±5, ±3 та ±1. Після цього ми вибираємо загальні: це − 3 , − 1 , 1 та 3 . З них треба вибрати найбільше число. Це буде 3 .

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

Визначення 3

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

Для чисел a 1 , a 2 , … , a n дільник зручно позначати як НОД (a 1 , a 2 , … , a n) . Саме значення дільника записується як НОД (a 1, a 2, …, a n) = b.

Приклад 3

Наведемо приклади найбільшого загального дільника кількох цілих чисел: 12,8,52,16. Він дорівнюватиме чотирьом, отже, ми можемо записати, що НОД (12 , - 8 , 52 , 16) = 4 .

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

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

Приклад 4

Так, найбільший загальний дільник чисел 60 , 15 і - 45 дорівнює 15 , оскільки п'ятнадцять ділиться як на 60 і - 45 , а й саме себе, і більшого дільника всім цих чисел немає.

Особливий випадок становлять взаємно прості числа. Вони є цілими числами з найбільшим загальним дільником, рівним 1 .

Основні властивості НОД та алгоритм Евкліда

Найбільший спільний дільник має деякі характерні властивості. Сформулюємо їх як теорем і доведемо кожне їх.

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

Визначення 4

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

Ця властивість випливає із самого визначення НОД і не потребує доказів.

Визначення 5

Якщо число a можна розділити на число b, то безліч спільних дільників цих двох чисел буде аналогічно до безлічі дільників числа b, тобто НОД (a, b) = b.

Доведемо це твердження.

Доказ 1

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

Використовуючи цю властивість, ми можемо знайти найбільший спільний дільник двох чисел, якщо одне з них можна поділити на інше. Такий дільник дорівнює одному з двох чисел, на яке можна розділити друге число. Наприклад, НОД (8 , 24) = 8 , оскільки 24 є число, кратне восьми.

Визначення 6 Доказ 2

Спробуємо довести цю властивість. У нас спочатку є рівність a = b · q + c і будь-який спільний дільник a і b буде ділити і c, що пояснюється відповідною властивістю ділимості. Тому будь-який спільний дільник b і c ділитиме a. Значить, безліч спільних дільників a і b збігається з безліччю дільників b і c, у тому числі й найбільші з них, отже, рівність НОД (a, b) = НОД (b, c) справедлива.

Визначення 7

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

Перед тим, як сформулювати властивість, радимо вам повторити теорему, яку ми доводили у статті про поділ із залишком. Відповідно до неї, ділене число a можна представити у вигляді b · q + r , причому b тут є дільником, q - деяким цілим числом (його також називають неповним приватним), а r - залишком, який задовольняє умові 0 ≤ r ≤ b .

Припустимо, у нас є два цілих числа більше 0, для яких будуть справедливі наступні рівності:

a = b · q 1 + r 1, 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1

Ці рівності закінчуються тоді, коли r k + 1 дорівнює 0 . Це трапиться обов'язково, оскільки послідовність b > r 1 > r 2 > r 3 … являє собою ряд спадних цілих чисел, який може включати в себе тільки кінцеве їх кількість. Отже, r k є найбільшим спільним дільником a і b, тобто r k = НОД (a, b).

Насамперед нам треба довести, що r k – це спільний дільник чисел a і b , а після цього – те, що r k не просто дільником, саме найбільшим спільним дільником двох даних чисел.

Переглянемо перелік рівнів, наведений вище, знизу нагору. Відповідно до останньої рівності,
r k − 1 можна поділити на r k . Виходячи з цього факту, а також попередньої доведеної властивості найбільшого спільного дільника, можна стверджувати, що r k − 2 можна поділити на r k , оскільки
r k − 1 ділиться на r k та r k ділиться на r k .

Третя знизу рівність дозволяє зробити висновок, що r k − 3 можна розділити на r k , і т.д. Друге знизу – що ділиться на r k , а перше – що a ділиться на r k . З цього укладаємо, що r k – загальний дільник a і b .

Тепер доведемо, що r k = НОД (a, b). що потрібно для цього зробити? Показати, що будь-який спільний дільник a та b буде ділити r k . Позначимо його r0.

Перегляньмо той же список рівностей, але вже зверху донизу. Виходячи з попередньої властивості, можна зробити висновок, що r 1 ділиться на r 0 , отже, відповідно до другої рівності r 2 ділиться на r 0 . Йдемо за всіма рівностями вниз і з останнього робимо висновок, що r k ділиться на r 0 . Отже, r k = НОД (a, b).

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

Перейдемо до інших властивостей.

Визначення 8

Якщо a і b є цілими числами, не рівними 0 , то повинні існувати два інших цілих числа u 0 і v 0 , при яких справедлива рівність НОД (a , b) = a · u 0 + b · v 0 .

Рівність, наведена у формулюванні властивості, є лінійним уявленням найбільшого загального дільника a та b . Воно зветься співвідношення Безу, а числа u 0 і v 0 називаються коефіцієнтами Безу.

Доказ 3

Доведемо цю властивість. Запишемо послідовність рівностей за алгоритмом Евкліда:

Перша рівність свідчить, що r 1 = a − b · q 1 . Позначимо 1 = s 1 і − q 1 = t 1 і перепишемо цю рівність у вигляді r 1 = s 1 · a + t 1 · b . Тут числа s1 і t1 будуть цілими. Друга рівність дозволяє зробити висновок, що r 2 = b − r 1 · q 2 = b − (s 1 · a + t 1 · b) · q 2 = − s 1 · q 2 · a + (1 − t 1 · q 2) · b. Позначимо − s 1 · q 2 = s 2 і 1 − t 1 · q 2 = t 2 і перепишемо рівність як r 2 = s 2 · a + t 2 · b , де s 2 і t 2 також будуть цілими. Це тим, що сума цілих чисел, їх твір і різницю також є цілі числа. Точно так само отримуємо з третьої рівності r 3 = s 3 · a + t 3 · b , з наступного r 4 = s 4 · a + t 4 · b і т.д. Наприкінці укладаємо, що r k = s k a + t k b при цілих s k і t k . Оскільки r k = НОД (a , b) , позначимо s k = u 0 і t k = v 0 , У результаті ми можемо отримати лінійне подання НОД у необхідному вигляді: НОД (a , b) = a · u 0 + b · v 0 .

Визначення 9

НОД (m · a, m · b) = m · НОД (a, b) при будь-якому натуральне значення m.

Доказ 4

Обґрунтувати цю властивість можна так. Помножимо на число m обидві сторони кожної рівності в алгоритмі Евкліда і отримаємо, що НОД (m · a, m · b) = m · r k, а r k - це НОД (a, b). Значить, НОД (m · a, m · b) = m · НОД (a, b). Саме ця властивість найбільшого загального дільника використовується при знаходженні НОД методом розкладання на прості множники.

Визначення 10

Якщо у чисел a і b є спільний дільник p, то НОД (a: p, b: p) = НОД (a, b): p. У разі, коли p = НОД (a , b) отримаємо НОД (a: НОД (a , b) , b: НОД (a , b) = 1 , отже, числа a: НОД (a , b) і b: НОД (a, b) є взаємно простими.

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

Визначення 11

Найбільшим загальним дільником a 1 , a 2 , … , a k буде число 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 .

Ця властивість корисна при знаходженні найбільшого загального дільника трьох чи більше чисел. За допомогою нього можна звести цю дію до операцій із двома числами. Його основою є наслідок алгоритму Евкліда: якщо безліч спільних дільників a 1 , a 2 і a 3 збігається з безліччю d 2 і a 3 , воно збігається і з дільниками d 3 . Дільники чисел a 1 , a 2 , a 3 і a 4 збігатимуться з дільниками d 3 , отже, вони співпадуть і з дільниками d 4 і т.д. Наприкінці ми отримаємо, що спільні дільники чисел a 1 , a 2 , … , a k збігатимуться з дільниками d k , а оскільки найбільшим дільником числа d k буде саме це число, то НОД (a 1 , a 2 , … , a k) = d k .

Це все, що ми хотіли б розповісти про властивості найбільшого спільного дільника.

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