Найбільший спільний дільник натуральних чисел

Означення. 1) Спільним  дільником натуральних чисел а₁, а₂, ..., а_n називається натуральне число d, таке, що  a₁ : d,  а₂ : d, ...,  а_n : d.

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

Позначення : d =НСД (а₁, а₂, ..., а_n).

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

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

Наприклад,  числа 4 та 45 взаємно прості, проте числа 4 та 8 не взаємно прості.

Зауваження. Якщо розклад чисел 180 і 840 на прості множники запи­сати у вигляді добутку степенів:

180 = 2²3²5¹,

840 = 2³3¹5¹7¹ , то

НСД зручно знайти за таким правилом:

1.    Визначити степені, основи яких є спільними прости­ми дільниками даних чисел (у розглядуваному прикладі це основи 2, 3, 5).

2.    З кожної пари степенів з однаковими основами вибра­ти степінь з меншим показником (у розглядуваному при­кладі це 2², 3¹, 5¹).

3.    Перемножити вибрані степені.

Отриманий добуток є шуканим найбільшим спільним дільником

 (у наведеному прикладі НСД (180; 840) = 2²3¹5¹).

Приклад. Знайти НСД чисел 1173 и 323.

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

1173 = 323´3 + 204;

323=204´1+119;

204=119´1+85;

119=85´1+34;

85=34´2+17;

34=17´2;

так що  НСД(1173, 323) = 17.

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

ах + bу = 1,

це згідно алгоритму Евкліда.

Теорема. Для довільних двох цілих чисел а і b, з яких хоча б одне відмінне від нуля(а² + b² ≠ 0) існують два цілі числа х та у, які задовольняють рівність  ах + bу = НСД(а, b).

Властивості взаємно простих чисел.

1) Якщо а та b взаємно прості з  с, то добуток аb та­кож взаємно простий з с.

2) Якщо аb ділиться без остачі на с, що взаємно просте з а, то b ділиться без остачі на с.

3) Якщо с ділиться на а і b, що взаємно прості, то с ділиться й на добуток аb.

4) Нехай натуральні а,  b та с, m . Якщо аb= с^m, і НСД(а, b) = 1, то

а= k^m,  b= r^m, де натуральні k, r, причому НСД(k, r) = 1 і k∙r=с.

38. Комплексне завдання на дослідження властивостей  НСД(а, b).

Розподілити  16 тверджень на три групи:

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

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

·         третя група тверджень, які не входять до першої та до другої групи.

1. Якщо шестицифрове число не містить рівних цифр, тоді добуток цифр є число парне.
2. В таблиці 3х3 у верхніх кутових клітинках зліва направо поставили цифри 1 та 2. Розмістити в порожніх клітинках таблиці числа від 3 до 9 так, щоб виконувались дві такі умови: 1) сума чотирьох чисел в будь-якому квадраті 2х2 була однакова; 2) число записане в центрі таблиці було - найбільш можливим. В середній клітинці не може стояти цифра 9.
3. Михайло записує число. Він використовує лише цифри 1,2,3,4,5 і слідує таким правилам: 1) будь-які дві сусідні цифри даного числа відрізняються між собою; 2)всі двоцифрові числа , що складаються з любих двох сусідніх цифр даного числа записаних у порядку   зліва - направо, відрізняються між собою. Наприклад, число 123134252 задовольняє умовам , а число 12315412 - ні, гак як число 12 присутнє два рази в записі числа. 25 цифр − це максимальна кількість цифр, з якого може складатися запис числа Михайло.
4.   На дошці написано число 1. Кожну секунду до числа на дошці додають суму його цифр. Через деякий час на дошці з’явитися число 126.
5.   Якщо а:b , де a та b натуральні числа, то  найбільший спільний дільник а і b(скорочено записують  НСД(а, b))  не дорівнює b, тобто  НСД(а, b)≠b.
6. НСД(х, у)=НСД(х+у, у)=НСД(х+у, х).
7. НСД (х, у)=НСД(х-у, у)=НСД(х-у, х).
8. НСД (х, у)=НСД(7х+3у, 8у)=НСД(7х+3у, 5х).
9. Якщо а:b(ост. к), тобто а=b∙m+k, де a , b, m, к натуральні числа, то НСД(а, b)= НСД(а, к)
10. Якщо а, с, к довільні натуральні числа, то НСД(а, с)=НСД(а∙к, с∙к)
11. Якщо m:n,  k:n  і  mx+ky = n,  де  x, y, n, m, k – натуральні числа, то найбільший спільний дільник чисел m, k дорівнює n,  тобто   НСД(m, k) = n.
12. Частки від ділення натуральних чисел m і n на їх найбільший дільник k( тобто діляться на їх  НСД(m, n)=k),  є два взаємно прості числа, тобто НСД(m:k, n:k) = 1.
13. Якщо n, m, k – натуральні числа, то найбільший спільний дільник чисел m∙n  та  k∙n дорівнює НСД(m, k)∙n, тобто завжди виконується рівність НСД(m∙n, k∙n) = НСД(m, k) ∙ n.
14. Якщо НСД(m, n)=1, тоді НСД(mс, n) ≠ НСД(n, с),  де  с, m, k – натуральні числа.
15. Якщо НСД(m, n)=1 і   mс:n, тоді  с:n, де  c, m, k – натуральні числа.
16. Якщо НСД(m, n)=1 і  с:m, с:n, тоді  с: (n∙ m), де  c, m, k – натуральні числа.