18294

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

Лекция

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

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

Украинкский

2013-07-07

101 KB

16 чел.

Лекція 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.  ◄


 

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

81700. Матеріальне буття та його форми: субституційний та реляційний підходи 19.31 KB
  Виходячи з цього сутність матеріального буття розкривається через поняття матерії та форм її існування. Матеріалісти античності ототожнювали її з першоосновою буття всіх речей останнім неподільним елементом дном за межами якого нічого не існує.
81701. Основні категорії онтології сутність-явище простір-час причина-наслідок 25.81 KB
  Явище і сутність діалектично повязані між собою протилежності. Так міраж це явище що виникає внаслідок викривлення променів світла атмосферою. Разом із тим явище і сутність передбачають одне одного.
81703. Свідомість як філософська категорія культурний і суспільний феномен 27.73 KB
  Для розрізнення свідомості та психіки мислення й розуму їх варто розрізняти. Але окрім цього варто не забувати що центром свідомості є людське Я. Предметним середовищем реалізації свідомості є світ.
81704. Свідомість як форма психічної діяльності:ідеальне і психічне 25.83 KB
  Свідомість -це найвища, притаманна людям якість, яка полягає в узагальненому і цілеспрямованому відображенні дійсності, уявній побудові дій і передбаченні їх результатів, регулюванні і самоконтролі поведінки, яка має зовнішні форми відображення творчого перетворювального характеру та повязана з мовою.
81705. Структура свідомості: її компонентний та рівневий вияви 25.51 KB
  Можна виділити такі рівні свідомості та їх елементи. Базовим і найбільш давнім рівнем свідомості є чуттєвоафективний пласт до якого належать: відчуття відображення в мозкові окремих властивостей предметів та явищ обєктивного світу що безпосередньо діють на наші органи чуттів; сприйняття образ предмета в цілому який не зводиться до суми властивостей та сторін; уявлення конкретні образи таких предметів чи явищ які в певний момент не викликають у нас відчуттів але які раніше діяли на органи чуттів різного роду афекти тобто...
81706. Проблема людини в філософії: екзистенційна та субстанійна концепції 28.3 KB
  Вона є теоретичним усвідомленням драматизму першої половини XX століття трагізму людини котра потрапила на межу життя і смерті буття і небуття в результаті реальної загрози її існуванню як людини як виду. Моделлю людини як такого для екзистенціалістів стала страждаюча зневірена людина яка знаходиться в прикордонній ситуації ситуації на межі життя та смерті. Ірраціональність буття абсурдність самого існування людини сумніви у можливості раціонального пізнання світу це все складові філософії екзистенціалізму.
81707. Проблема походження людини та суспільства 26.28 KB
  Релігійна гіпотеза походження людини базується на біблійних переказах про створення Богом світу і людини гріхопадіння Адама і Єви Всесвітній потоп про те що заповідав Бог людям та регламентацію життєдіяльності людини яка викладена в заповідях. Космічна гіпотеза походження людини базується на припущенні що життя принесено на Землю з Космосу у тому числі в його цивілізованих проявах. Еволюційна гіпотеза походження життя...
81708. Поэма Н. В. Гоголя «Мертвые души» как «малый род эпопеи». Гоголь о замысле поэмы 46.75 KB
  Гоголь о замысле поэмы. Гоголь задумал монументальное произведение в трех томах великую национальную поэму стремясь показать не только современную Россию Русь с одного боку но пытался заглянуть в ее завтрашний день раскрыть положительные начала русской жизни указать родине путь к спасению. Гоголь стал изображать людей обыкновенных а не приятные только исключения из общих правил . Гоголь раскрывает ту социальную основу которая сформировала характеры героев поэмы: дворянский паразитизм расцветший на почве...