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.  ◄


 

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

84961. Ознайомлення з клавішами-стрілочками, BS, Delete 144.71 KB
  Ознайомлення учнів з клавішами - стрілочками (вліво, вправо, вгору, вниз), BS, Delete. Закріплення навичок роботи з клавішами Enter, ESC. Розвиток логічного мислення. Виховання акуратності, охайності при роботі з комп’ютером...
84962. Створення вітальної листівки з використанням графічного редактора Paint і тексту 59.76 KB
  Створення вітальної листівки з використанням графічного редактора Pint і тексту Мета. Формування основних навичок роботи з компонентами графічного редактора Pint. ПК із завантаженим графічним редактором Pint роздатковий матеріал Хід уроку І. Допоможе нам працювати графічний редактор PINT.
84963. Правила дорожнього руху. Комп’ютерна підтримка уроку основи здоров’я 166.04 KB
  Компютерна підтримка уроку основи здоровя. Виховання спостережливості уваги інтересу до компютера. Повторення правил безпечної поведінки в компютерному класі. На початку уроку ми повторили правила роботи з компютером.
84964. Комп’ютерна підтримка української мови. Звуки голосні й приголосні. Програма “Незвичайний поїзд” 437.9 KB
  Формування вміння працювати з теоретичним матеріалом підручника, знаходити в ньому потрібну інформацію. Розвиток мовленнєвих та творчих здібностей, логічного мислення, уваги, пам’яті. Виховання культури мовлення.
84965. Комп’ютерна підтримка української мови. Ненаголошені е та и. Програма “Незнайка на містку” 175.63 KB
  Удосконалення вмінь працювати мишкою у програмі “Незнайко на містку”. Закріплення правил правопису ненаголошених е, и в корені слів, Розвиток вмінь практично застосовувати набуті знання; Підвищення інтересу до роботи з комп’ютером.
84966. Комп’ютерна підтримка української та англійської мови. Програма “Ведмедик-поліглот” 293.5 KB
  Удосконалення знань слів української та англійської мови, уміння їх перекладати. Розвиток просторової уяви, логічного мислення, уваги. Продовження формування умінь і навичок роботи з комп’ютером.
84967. Техніка безпеки при роботі з комп’ютером 94.4 KB
  Техніка безпеки при роботі з компютером Мета. Навчити учнів поводитися в компютерному класі дотримуючись усіх правил техніки безпеки ТБ. Виховувати культуру поведінки в компютерному класі толерантність при роботі в парах культуру мовлення і бережливе ставлення до держмайна. Хто знає в який клас ми прийшли Чи доводилось тобі працювати з компютером А чи знаєш ти що таке компютер Робота з тлумачним словником.
84968. Обговорення можливостей і демонстрація режимів комп’ютера. Гра “Стрільці по яблуках” 131.78 KB
  Дати уявлення про використання комп’ютера в побутовій сфері. Познайомити з маніпулятором “миша”, вчити дітей керувати подіями за допомогою миші. Розвивати логічне мислення, збагачувати мовлення учнів словами: “миша”, “стрілка-вказівник”, “килимок”. Розвивати загальний кругозір учнів, дрібну моторику руки...
84969. Застосування комп’ютера у різних сферах діяльності 59.72 KB
  Ознайомити учнів з можливостями застосування комп’ютера у різних сферах діяльності. Повторити правила техніки безпеки. Закріплювати уміння працювати з клавіатурою, використовуючи клавіші “Space” (пропуск)...