18294

СПІЛЬНІ КРАТНІ І ДІЛЬНИКИ

Лекция

Математика и математический анализ

Лекція 21 СПІЛЬНІ КРАТНІ І ДІЛЬНИКИ Спільні кратні та найменше спільне кратне кількох натуральних чисел і його властивості. Спільні дільники та найбільший спільний дільник кількох натуральних чисел і його властивості. Взаємно прості та попарно взаємнопрості...

Украинкский

2013-07-07

101 KB

18 чел.

Лекція 21

СПІЛЬНІ КРАТНІ І ДІЛЬНИКИ

  1.  Спільні кратні та найменше спільне кратне кількох натуральних чисел і його властивості.
  2.  Спільні дільники та найбільший спільний дільник кількох натуральних чисел і його властивості. Взаємно прості та попарно взаємнопрості числа.
  3.  Властивості найменшого спільного кратного та найбільшого спільного дільника двох чисел.
  4.  Теорема про подільність, що пов’язані із взаємо простими числами. Ознака подільності на числа, що є добутком двох взаємо простих чисел.
  5.  Алгоритм Евкліда.

  1.  Спільні кратні та найменше спільне кратне кількох

натуральних чисел і його властивості

Нехай a1, a2, a3, …, an – довільні натуральні числа. Натуральне число, яке ділиться на кожне із заданих чисел, називається їх спільним кратним, а найменше із спільних кратних – їх найменшим спільним кратним і позначається НСК(a1, a2, …, an).

Множина спільних кратних для натуральних чисел a1, a2, …, an нескінченна. Це випливає з того, що за теоремою про подільність добутку число a1·a2·…·an є спільним кратним заданих чисел, а тому і кожне число виду (a1·a2· …·ank, де k Î N, також буде їх спільним кратним. За принципом найменшого числа у множині спільних кратних існує найменше число, яке і буде найменшим спільним кратним заданих чисел. Отже, для довільних натуральних чисел a1, a2, …, an їх найменше спільне кратне існує і причому єдине.

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

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

" ab Î N: a M b ® НСK(ab) = a.

Наступна теорема виражає основну властивість найменшого спільного кратного.

Теорема 9. Кожне спільне кратне кількох натуральних чисел ділиться на їх найменше спільне кратне.

► Нехай a1, a2, …., an довільні натуральні числа, m = НСК(a1, a2, …, an) і M – довільне спільне кратне цих чисел. Поділимо M на m з остачею

M = m·g + r,  r < m.

(1)

M і m – спільні кратні чисел a1, a2, …, an, то для кожного i = 1, 2, …, n  M M ai  і m M ai. За теоремою про подільність добутку, m·g M ai, i = 1, 2, …, n.

Отже, у рівності (1) усі члени, крім одного r, діляться на кожне з чисел ai, i = 1, 2, …, n. Звідси за наслідком 6 r M ai, i = 1, 2, …, n. Оскільки r < m і m є найменшим спільним кратним заданих чисел, то r = 0 і M = m·g, тобто M M m.  ◄

  1.  Спільні дільники та найбільший спільний дільник кількох натуральних чисел і його властивості.

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

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

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

Теорема 10. Для довільних натуральних чисел a і b, якщо a ділиться на b, то їх найбільший спільний дільник дорівнює b:

" ab Ï N: a M b ® НСД(ab) = b.

Наступна теорема виражає основну властивість найбільшого спільного дільника.

Теорема 11. Довільний спільний дільник заданих натуральних чисел є дільником їх найбільшого спільного дільника.

► Нехай a1, a2, …, an – довільні натуральні числа, D = НСД(a1, a2, …, an) і d – їх довільний спільний дільник. Тоді за означенням найбільшого спільного дільника D ³ d. Припустимо, що D не ділиться на d. Нехай m = НСK(Dd). Оскільки , то m > D. Числа D і d є спільними дільниками кожного із чисел ai, і = 1, 2, ..., n, тобто кожне з даних чисел є спільним кратним чисел d і D. За основною властивістю найменшого спільного кратного кожне з чисел ai, i = 1, 2, ... , n, буде кратним числу m, тобто m є їх спільним дільником. А це неможливо, бо D – найбільший спільний дільник чисел a1, a2, ..., an. Одержане протиріччя і доводить теорему.  ◄

Натуральні числа a1, a2, ..., an називаються взаємно простими, якщо їх найбільший спільний дільник дорівнює одиниці, і попарно взаємно простими, якщо НСД(aiaj) = 1 для всіх i ¹ j,  ij = 1, 2, …, n.

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

  1.  
    Властивості найменшого спільного кратного та

найбільшого спільного дільника двох чисел

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

Теорема 12. Для довільних натуральних чисел a і b їх найменше спільне кратне дорівнює добутку даних чисел, що ділиться на їх найбільший спільний дільник:

" ab Î N: НСK(ab) = .

► Нехай d – довільний спільний дільник натуральних чисел a і b. Розглянемо число

M = .

(1)

Рівність (1) можна записати ще й так

.

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

M = mt,  m = НСK(ab)  і  t Î N.

(2)

Скориставшись (2), рівність (1) можна записати

mt = .

Тоді

d = .

(3)

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

НСД (ab) = .

Отже,

НСК(ab) = .   ◄

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

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

Теорема 12 не може бути застосована більше, ніж до двох чисел, бо, наприклад, НСК(2, 4, 6) = 12, тоді як за теоремою НСК(2, 4, 6) =  = 24.

Теорема 13. Для того щоб спільний дільник d натуральних чисел a і b був їх найбільшим спільним дільником, необхідно і достатньо, щоб числа  і  були взаємно простими.

 Необхідність. Нехай d = НСД(ab). Доведемо, що числа  і  – взаємно прості. Припустимо протилежне, тобто, що числа  і  не взаємно прості. Отже, вони мають спільний дільник k > 1. Тоді

  і   .

Звідси

a = (d·ka1   і   b = (d·kb1,

тобто a M (d·k) і b M (d·k), де d·k > d, що суперечить вибору числа d, як найбільшого спільного дільника чисел a і b.

Значить, числа  і  взаємно прості.

Достатність. Нехай d – є спільним дільником чисел a і b таким, що числа  і  взаємно прості. Доведемо, що d = НСД(ab). Припустимо, d не є найбільшим спільним дільником чисел a і b. Нехай D = НСД(ab). За основною властивістю найбільшого спільного дільника та необхідною ознакою подільності натуральних чисел матимемо D = d·k, де k > 1. Звідси видно, що a M (d·k) і b M (d·k). Отже, числа  і  мають спільний дільник k > 1, що суперечить умові.  ◄

Теорему 13 можна узагальнити на довільну скінченну сукупність натуральних чисел.

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

" abc Î N: НСД(a·c, b·c) = c · НСД(a·b);

" abc Î N: НСК(a·c, b·c) = c · НСК(a·b).

► 1. Нехай D = НСД(ab). Розглянемо число D1 = c · D.

Матимемо

НСД() = НСД() = НСД().

За теоремою 13 числа  і  будуть взаємно простими, тобто НСД() = 1. Отже, НСД() = 1.

За тією ж теоремою 13 НСД(a·c, b·c) = D1. А тому

НСД(a·c, b·c) = c · НСД(ab).

2. Маємо

НСД(a·c, b·c) = за теоремою 12

= () = за доведеним у першій частині теореми

=  = за теоремою 12

c · НСК(ab).

Отже, НСК(a·cb·c) = c · НСК(ab).   ◄

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

НСК(45, 60) = 15 ∙ НСК(3, 4) = 15 · 3 · 4 = 180;

НСД(45, 60) = 15 ∙ НСД(3, 4) = 15.

Теорему 14 також можна узагальнити на довільну скінчену сукупність натуральних чисел.

  1.  Теорема про подільність, що пов’язані із

Взаємо простими числами. Ознака подільності на числа,

що є добутком двох взаємо простих чисел

З поняттям про взаємно прості числа пов'язані дві важливі теореми про подільність.

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

" abc Î N: a·b M  c Ù НСД(bc) = 1 ® a M c.

► Нехай a, b і c – довільні натуральні числа такі, що

a·b M c  і  НСД(bc) = 1.

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

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

" abc Î N: (a M bÙ (a M cÙ НСД(bc) = 1 ® a M b·c.

► Нехай a, b і c – довільні натуральні числа такі, що

a M b, a M c і НСД(bc) = 1.

Доведемо, що a M b·c. За умовою теореми число a є спільним кратним чисел b і c. На підставі основної властивості найменшого спільного кратного матимемо a M НСК(bc), Числа b і c взаємно прості, отже, НСК(bc) = b·c, а тому a M b·c.  ◄

Відомо, що коли число ділиться на добуток, то воно ділиться і на кожний множник. Користуючись цим фактом та теоремою 16, одержуємо наслідок.

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

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

Задача 1. Встановити ознаку подільності на 165.

► Число 165 = 3 · 55, де числа 3 і 55 взаємно прості. На основі наслідку 9

a M 165 Û a M 3 Ù a M 55.

(1)

Число 55 = 5 · 11, де числа 5 і 11 взаємно прості. На основі наслідку 9

a M 55 Û a M 5 Ù a M 11.

Підставивши в (1) замість a M 55 йому рівносильне твердження a M 5 Ù a M 11, одержимо

a M 165 Û a M 3 Ù a M 5 Ù a M 11.

Отже, число ділиться на 165 тоді і тільки тоді, коли воно ділиться на числа 3, 5 і 11.

За цією ознакою число 8745 ділиться на 165, бо сума його цифр ділиться на 3, закінчується цифрою 5 і (5 + 7) – (4 + 8) = 0 M 11.  ◄

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

Відомі властивості найменшого спільного кратного і найбільшого спільного дільника двох чисел не завжди дають можливість їх обчислювати. За теоремою 12

" ab Î N: НСК(ab) = .

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

Теорема 17. Для довільних натуральних чисел a, b, g і r, якщо між ними має місце залежність

a = b·g + r,

то множина спільних дільників чисел a і b дорівнює множині спільних дільників чисел b і r, зокрема

НСД(ab) = НСД(br).

► Нехай між натуральними числами a, b, g і r має місце залежність

a = b·g + r.

(1)

1. Якщо d – будь-який спільний дільник чисел a і b, то за теоремою про подільність добутку b·g M d. Тоді з рівності (1) за властивістю подільності алгебраїчної суми r M d. Отже, кожний спільний дільник чисел a і b є спільним дільником чисел b і r.

2. Навпаки, якщо d – будь-який спільний дільник чисел b і r, то за теоремою про подільність добутку і суми a M d. Отже, кожний спільний дільник чисел b і r є спільним дільником чисел a і b.

З пунктів 1 і 2 доведення випливає, що множини спільних дільників чисел a і b та b і r збігаються, а тому і

НСД(ab) = НСД(br).  ◄

Алгоритм Евкліда полягає у тому, що:

1. Число a ділиться на число b з остачею

a = b·g1 + r1,   r1 < b.

Якщо r1 = 0, то b = НСД(ab).

2. Якщо r1 > 0, то число b ділять на число r1 з остачею

b = r1·g2 + r2,  r2 < r1.

Якщо r2 = 0, то r1 = НСД(br1) = НСД(ab).

3. Якщо r2 > 0, то число r1 ділять на число r2 з остачею

r1 = r2·g3 + r3,   r3 < r2.

Якщо r3 = 0, то

r2 = НСД(r1r2) = НСД(br1) = НСД(ab).

4. Якщо r3 > 0, то повторюють ділення аналогічно пункту 3, поки не отримають остачу, рівну нулю.

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

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

► Застосуємо до чисел 20553 і 713 алгоритм Евкліда.

20553 = 713 · 28 + 589,

713 = 589 · 1 + 124,

589 = 124 · 4 + 93,

124 = 93 · 1 + 31,

93 = 31 · 3 + 0.


Обчислення зручно проводити за такою схемою:

28

1

4

1

3

20553

713

589

124

93

31

1426

589

496

93

93

6293

124

93

31

0

5704

589

Остання, відмінна від нуля, остача дорівнює 31, а тому

НСД(20553, 713) = 31.

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

НСК(20553, 713) = 

Відповідь: НСД(20553, 713) = 31, НСК(20553, 713) = 472719.  ◄


 

А также другие работы, которые могут Вас заинтересовать

37861. РОЗВ’ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ 566 KB
  Множина чисел яка перетворює кожне з рівнянь системи на тотожність називається розвязком системи. Методи виключення Гаусса Методи виключення Гаусса послідовного виключення змінних ґрунтуються на ідеї еквівалентного перетворення зведення вихідної системи до трикутного вигляду прямий хід і подальшого її розвязання зворотний хід. Поділивши перше рівняння системи 3. Тоді поділивши на нього перше рівняння системи 3.
37862. ИЗУЧЕНИЕ ТЕПЛОЕМКОСТЕЙ ГАЗОВ 223.5 KB
  Внутренняя энергия системы состоит из кинетической энергии молекул составляющих систему потенциальной энергии их взаимодействия друг с другом внутримолекулярной энергии т. энергии взаимодействия атомов или ионов в молекулах энергии электронных оболочек атомов и ионов внутриядерной энергии и энергии электромагнитного излучения в системе. Система может обладать также и внешней энергией которая представляет собой сумму кинетической энергия движения системы как целого кинетической энергии центра масс системы и потенциальной энергии...
37863. Визначення оптимального асортименту продукції 310.5 KB
  Визначення оптимального асортименту продукції. Підприємство виготовляє два види продукції П1 і П2 яка надходить в оптовий продаж. Витрата сировини на одиницю продукції наведена у таблиці.1 Сировина Витрата сировини на одиницю продукції Запас сировини од.
37864. Основы статистической обработки информации с использованием EXCEL. Определение некоторых числовых характеристик экспериментальных статистических данных 618.5 KB
  Создать массив признаков интервалов и посчитать для них частоту. Для создания массива признаков сначала рассчитывают цену деления c= Rx k. откл 6765655 6821 6162 6168 6819 7062 эксцесс 0057761 ассиметрия 0385736 Для построения гистограммы и полигона частот используется функция Excel ЧАСТОТА массив_данных; массив_интервалов. Эта функция относится к классу статистических и производит операции над массивами.
37865. Распределения непрерывных случайных величин 97 KB
  Цель: познакомиться с распределениями непрерывных случайных величин. Сформировать представления о виде функции и плотности непрерывных распределений.
37866. ДОСЛІДЖЕННЯ ТИПІВ, ЩО ВИЗНАЧАЮТЬСЯ (ПЕРЕЛІЧУВАЛЬНІ, ІНТЕРВАЛЬНІ, МНОЖИННІ ТИПИ) 84 KB
  Теоретичні відомості Визначення типу У мові Pscl користувач може визначити його власні типи використовуючи наперед визначені типи та спеціальні операції визначення. тип що визначається :: =type позначка типу = опис типу позначка типу :: = ідентифікатор опис типу :: = позначка типу опис типу Перелічувальний тип Перечислювальні типи створюються шляхом перелічення ряду значень. Перечислювальні типи є дискретними типами тому їм властива певна кінцева упорядкована множина значень в якій кожне наступне значення типу є більшим за попереднє....
37869. Простейшие средства отладки в среде DELPHI. Программирование циклических алгоритмов 124.5 KB
  Вывод: изучил простейшие средства отладки в среде DELPHI. Научился программировать циклические алгоритмы.