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


 

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

12138. ИЗМЕРЕНИЕ КОЭФФИЦИЕНТА ПОГЛОЩЕНИЯ ГАММА-ИЗЛУЧЕНИЯ В СВИНЦЕ 750 KB
  Лабораторная работа №23 ИЗМЕРЕНИЕ КОЭФФИЦИЕНТА ПОГЛОЩЕНИЯ ГАММАИЗЛУЧЕНИЯ В СВИНЦЕ Цель работы: Измерение коэффициентов поглощения излучения твердыми телами. Определение энергии квантов и механизма взаимодействия излучения с веществом по коэффициентам...
12139. ИССЛЕДОВАНИЕ СТАТИСТИЧЕСКОГО ХАРАКТЕРА РАСПРЕДЕЛЕНИЯ КОСМИЧЕСКИХ ЧАСТИЦ (РАСПРЕДЕЛЕНИЕ ПУАССОНА) 106 KB
  Лабораторная работа №24 ИССЛЕДОВАНИЕ СТАТИСТИЧЕСКОГО ХАРАКТЕРА РАСПРЕДЕЛЕНИЯ КОСМИЧЕСКИХ ЧАСТИЦ РАСПРЕДЕЛЕНИЕ ПУАССОНА Цель работы: ознакомиться с устройством принципом работы счетчика Гейгера и методикой измерения радиоактивного излучения: изучение хара...
12140. Изучение схемы АВР асинхронных электродвигателей 336 KB
  Изучение схемы АВР асинхронных электродвигателей. Цель работы: По принципиальной схеме составить монтажную схему. Собрать ее на действующем стенде включить в работу и изучить все возможные варианты. План проведения работы.
12141. Исследование схемы управления электродвигателем постоян-ного тока на тиристерных преобразователях 668 KB
  ЛАБОРАТОРНАЯ РАБОТА 2. Тема: Исследование схемы управления электродвигателем постоянного тока на тиристерных преобразователях. Цель работы: Изучение работы тиристорного преобразователя для электродвигателя постоянного тока с регулируемой частотой враще
12142. Исследование схем автоматического пуска электродвигателя в функции времени 324 KB
  Исследование схем автоматического пуска электродвигателя в функции времени. Цель работы: По принципиальной схеме составить монтажную схему собрать схему на действующем стенде включить в работу и изучить возможные варианты
12143. Снятие и построение нагрузочных диаграмм 477.5 KB
  ЛАБОРАТОРНАЯ РАБОТА 4. Тема: Снятие и построение нагрузочных диаграмм. Цель работы: Изучение режимов работы электрических двигателей и получение опытных данных для построения нагрузочных диаграмм и поверка мощности приводного двигателя. План про
12144. Изучение принципиальной схемы управления электроприводом грузового лифта 175 KB
  ЛАБОРАТОРНАЯ РАБОТА 5. Тема: Изучение принципиальной схемы управления электроприводом грузового лифта. Цель работы: Изучить работу принципиальной схемы управления электроприводом грузового лифта. Краткие теоретические сведения В различных отрасл
12145. Изучение схемы управления электроприводом вентиляционной системы. 374 KB
  ЛАБОРАТОРНАЯ РАБОТА 6. Тема: Изучение схемы управления электроприводом вентиляционной системы. Цель работы: По принципиальной схеме составить монтажную схему. Собрать ее на действующем стенде включить в работу и изучить все возможные варианты. Вентиляц...
12146. Системы численных вычислений. Основы работы в среде Matlab. 906.42 KB
  Отчет по выполнению лабораторной работы № 26 Системы численных вычислений. Основы работы в среде Matlab. Цель работы: научиться проводить прямые вычисления и создавать Мфайлы в пакете автоматизации математических расчетов MATLAB.