Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Міністерство освіти і науки України
Комунальний вищий навчальний заклад
«Бериславський педагогічний коледж імені В. Ф. Беньковського»
Херсонської обласної ради
|
Предмет: Основи початкового курсу математики Модуль № 2 Семестр: VІ Кількість годин: 2 |
ЛЕКЦІЯ № 10 (69-70)
Тема: Найбільший спільний дільник та найменше спільне кратне натуральних чисел, способи їх знаходження
|
Розглянуто і затверджено на засіданні предметної (циклової) комісії викладачів фізико-математичних дисциплін та нових інформаційних технологій Протокол № ___ від _________ 2013р. Голова предметної (циклової) комісії: _________________ Г. Ю. Шкворченко |
м. Берислав
Тема лекції: Найбільший спільний дільник та найменше спільне кратне натуральних чисел, способи їх знаходження
Студенти повинні знати:
Студенти повинні вміти:
Тип лекції: тематична
Ключові поняття: просте і складене число, найбільший спільний дільник та найменше спільне кратне натуральних чисел, властивості НСД і НСК, взаємно прості числа.
План
Основна література
С. 82-84.
Інтернет-ресурси
Структура лекції
1. Поняття найбільшого спільного дільника та найменшого спільного кратного натуральних чисел
Візьмемо два числа 8 і 12, випишемо їх дільники.
Число 12 ділиться на 1, 2, 3, 4, 6, 12.
Число 8 ділиться на 1, 2, 4, 8. У чисел 8 і 12 є спільні дільники. Це числа 1, 2, 4. Серед них є найбільше число 4 і його називають найбільшим спільним дільником чисел 12 та 8.
Означення. Спільним дільником натуральних чисел а і b називається будь-яке натуральне число, яке являється дільником кожного із даних чисел.
Означення. Найбільшим спільним дільником (НСД) натуральних чисел а і b називається найбільше натуральне число із усіх спільних дільників даних чисел.
D (a, b) = c D (16, 8) = 8
Властивості НСД
Означення: Якщо НСД (а1,а2,…, аk) = 1, то числа а1,а2,…, аk називаються взаємно простими. Якщо, крім того, кожна пара цих чисел взаємно проста, то числа а1,а2,…, аk називаються попарно взаємно простими.
Так числа 4, 6, 7 – взаємно прості, НСД (4,6,7) = 1. Проте вони не є попарно взаємно простими, НСД (4,6) = 2.
У числах 12 і 8 є спільні кратні. Це числа 24, 48, 72, … Серед них є найменше число 24. Його називають найменшим спільним кратним чисел 12 і 8.
Означення. Спільним кратним натуральних чисел a і b називається будь-яке натуральне число, яке кратне кожному із даних чисел.
Означення. Найменшим спільним кратним (НСК) натуральних чисел a і b називається найменше натуральне число із усіх спільних кратних даних чисел.
К (16, 8) = 16
Властивості НСК
Теорема: НСД (а,b) є найменшим спільним кратним усіх спільних дільників чисел а і b.
Отже, найбільшим спільним дільником натуральних чисел а і b називається найбільше число з усіх спільних дільників даних чисел і позначається НСД (а, b) або Д (а, b). Найменшим спільним кратним натуральних чисел а і b називається найменше число з усіх спільних кратних даних чисел. Найменше спільне кратне позначається НСК (а, b) або К (а, b).
Питання для узагальнення
2. Способи знаходження найбільшого спільного дільника і найменшого спільного кратного
Знаходження НСД та НСК розкладом на прості множники
Знайдемо НСК і НСД чисел 360 і 525. Ці числа можна подати у канонічному вигляді: 360 = 23 ∙ 32 ∙ 5; 525 = 3 ∙ 52 ∙ 7. У розклад на прості множники НСД цих чисел повинні ввійти всі спільні прості множники, причому кожний з них треба взяти з найменшим показником, з яким він входить в канонічні розклади даних чисел. Отже, НСД (360, 525) = 3 ∙ 5 = 15.
У розлад на прості множники НСК (360, 525) повинні ввійти всі прості множники, які входять принаймні в один розклад, причому кожний з них треба взяти з найбільшим показником. НСК (360, 525) = 23 ∙ 32 ∙ 52 ∙ 7 = 12 600.
Теорема: НСК (а, b) ∙ НСД (а, b) = а ∙ b.
Наслідок: Якщо НСК (а, b) = 1, то НСК (а, b) = а ∙ b .
Знайдемо НСД і НСК чисел 3600 і 288.
D (3600, 288) = 2 · 3 = 144
|
3600 1800 900 450 225 75 25 5 1 |
2 2 2 2 3 3 5 5 1 |
288 144 72 36 18 9 3 1 |
2 2 2 2 2 3 3 1 |
3600 = 2 · 3· 5
288 = 2 · 3
К (3600, 288) = 2 · 3· 5· 2
Знаходження НСД за алгоритмом Евкліда
Лема 1: Якщо а ділиться на b, то НСД (а, b) = b.
Лема 2: Якщо а = bq+ r, де а, b, r – натуральні числа, то НСД (а, b) = НСД (b, r).
Розглянемо алгоритм Евкліда для знаходження НСД довільних натуральних чисел а і b. Нехай а ≥ b. Якщо а ділиться на b,то за лемою 1 НСД ((а, b) = b. Якщо а = bq+ r, де r ≠ 0, то за лемою 2 задача знаходження НСД зводиться до обчислення НСД чисел b, r, де r < b. Якщо br, то НСД (b, r) = r, а отже, і НСД (а, b) = r. Якщо при діленні b на r матимемо остачу 0 < r1 < r, то b = rq1+r1, і тому НСД (а, b) = НСД (b, r) = НСД (r, r1). Продовжуючи описаний процес, діставатимемо все менші і менші остачі: r, r1, …, rm. Зрештою дістанемо остачу, яка ділить попередню остачу. Згідно з лемою 2, ця, відмінна від нуля, остача і є НСД (а, b). Таким чином НСД двох натуральних чисел дорівнює останній, відмінній від нуля остачі в алгоритмі Евкліда для цих чисел.
Алгоритм Евкліда як спосіб послідовного ділення зручно записувати у вигляді многократного ділення кутом.
D (525; 231) = D (231; 63) = D (63; 42) = D (42; 21) = 21
|
525 |
231 |
||
|
462 |
2 |
||
|
231 |
63 |
||
|
189 |
3 |
||
|
63 |
42 |
||
|
42 |
1 |
||
|
42 |
21 |
||
|
42 |
2 |
||
|
0 |
К (525; 231) =
Зв’язок між НСК і НСД двох чисел a і b
Після обчислення за допомогою алгоритму Евкліда НСД двох чисел можна знайти НСК, використовуючи залежність між НСД і НСК.
К (a, b) · D (a, b) = a · b
К (a, b) =
Отже, існує два способи обчислення НСД і НСК: 1) за канонічним розкладом чисел, 2) за алгоритмом Евкліда.
Питання для узагальнення
Загальний висновок
Найбільшим спільним дільником натуральних чисел а і b називається найбільше число з усіх спільних дільників даних чисел і позначається НСД (а, b) або Д (а, b). Найменшим спільним кратним натуральних чисел а і b називається найменше число з усіх спільних кратних даних чисел. Найменше спільне кратне позначається НСК (а, b) або К (а, b).
Для знаходження НСД і НСК існує два способи: за розкладом на прості множники і за алгоритмом Евкліда.
Запитання для узагальнення студентам
Повідомлення домашнього завдання
Р. 2, п. 80-81, впр. 1, 3 (С.212), впр.2 (С.214).