18294

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

Лекция

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

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

Украинкский

2013-07-07

101 KB

15 чел.

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


 

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

75725. Порядок расследования одиночного несчастного случая на производстве 19.73 KB
  Порядок расследования одиночного несчастного случая на производстве. Производственный травматизм и профессиональные заболевания это сложные многофакторные явления обусловленные действием на человека в процессе его трудовой деятельности опасных вызывающих травмы и вредных вызывающих заболевание факторов. Расследование и учет несчастных случаев на производстве необходимы для разработки и осуществления мероприятий по профилактике травматизма улучшению состояния условий и охраны труда. Несчастный случай на производстве это случай...
75726. Порядок расследования тяжелого, группового несчастного случая и несчастного случая со смертельным исходом на производстве 15.81 KB
  Порядок расследования тяжелого группового несчастного случая и несчастного случая со смертельным исходом на производстве. Несчастные случаи подлежащие расследованию и учету Порядок проведения расследований несчастных случаев При расследовании каждого несчастного случая комиссия в предусмотренных случаях государственный инспектор труда самостоятельно проводящий расследование несчастного случая выявляет и опрашивает очевидцев происшествия лиц допустивших нарушения требований охраны труда получает необходимую информацию от работодателя...
75727. Порядок оформления акта по форме Н-1 о несчастном случае на производстве и учета несчастного случая на производстве 18.73 KB
  Указывается число месяц год и время проишетвиям несчастного случая количество полных часов от начала работы смены. Почтовый юридический адрес указывается в последовательности установленной правилами оказания услуг связи: почтовый индекс название и вид населенного пункта название улицы номер дома номер корпуса номер офиса если организация не занимает здание полностью. При наличии в организации нескольких ОКВЭД в акте указывается только основной вид экономической деятельности. Наименнование структурного подразделения организации...
75728. Методы изучения причин несчастных случаев на производстве 14.61 KB
  Методы изучения причин несчастных случаев на производстве. Вывешенные на стене такие планы постоянно сигнализируют напоминают о местах несчастных случаев. Повторение несчастных случаев в определенных местах будет свидетельствовать о неблагополучии с охраной труда на данных объектах. Путем дополнительного обследования указанных мест выявляют причины вызвавшие несчастные случаи и намечают текущие и перспективные мероприятия по устранению несчастных случаев для каждого отдельного объекта.
75729. Расчет показателей(коэф-ов) , характеризующих состояние производственного травматизма 101.75 KB
  Для характеристики уровня производственного травматизма в бригаде участке цехе предприятии отрасли и народном хозяйстве в целом а также для сопоставления состояния травматизма в этих структурных подразделениях используются относительные показатели коэффициенты частоты тяжести несчастных случаев и нетрудоспособности. Показатели рассчитываются на основе данных отчета о пострадавших при несчастных случаях.Показатель частоты несчастных случаев кч:...
75730. Статистический метод анализа причин производственного травматизма 14.48 KB
  Статистический метод анализа причин производственного травматизма Статистический метод анализа причин производственного травматизма служит сегодня пожалуй основным методом позволяющим вырабатывать политику действий и намечать конкретные меры по предотвращению этого печального и нежелательного явления. Для анализа собирают массив данных по всем изучаемым показателям. С помощью статистического анализа можно обнаруживать закономерности свойственные этим показателям изучать особенности возникновения несчастных случаев в отдельных...
75731. Условия и факторы производственной среды, вредно влияющие на организм человека. Нормативные документы, регламентирующие их параметры 36 KB
  Условия и факторы производственной среды вредно влияющие на организм человека. Производственная среда это часть окружающей человека среды включающая природно-климатические факторы и факторы связанные с профессиональной деятельностью шум вибрация токсичные пары газы пыль ионизирующие излучения и др. Опасными называются факторы способные при определенных условиях вызывать острое нарушение здоровья травму и гибель организма; вредными факторы отрицательно влияющие на работоспособность или вызывающие профессиональные заболевания и...
75732. Показатели, характеризующие метеорологические условия производственной среды. Понятие терморегуляции 43 KB
  В понятие метеорологических условий производственной среды или микроклимата входят: температура воздуха его влажность и скорость движения атмосферное давление и тепловое излучение от нагретых поверхностей. Исследования показывают что повышение температуры воздуха выше 2022С снижает работоспособность на 24 на каждый градус повышения температуры а при температуре в 30С и выше на 46 на каждый градус. При температуре воздуха более 30С и значительном тепловом излучении от нагретых поверхностей наступает нарушение терморегуляции...
75733. Оптимальные параметры микроклимата производственной среды. Организация и проведение контроля параметров микроклимата 47.5 KB
  В этих нормах отдельно нормируется каждый компонент микроклимата в рабочей зоне производственного помещения: температура относительная влажность скорость движения воздуха в зависимости от способности организма человека к акклиматизации в разное время года характера одежды интенсивности производимой работы и характера тепловыделений в рабочем помещении. Перепады температуры воздуха по высоте и по горизонтали а также изменения температуры воздуха в течение смены при обеспечении оптимальных величин микроклимата на рабочих местах не должны...