18295

ПРОСТІ І СКЛАДЕНІ ЧИСЛА

Лекция

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

Лекція 22 ПРОСТІ І СКЛАДЕНІ ЧИСЛА Розбиття множини цілих невід’ємних чисел на 4 класи за кількістю дільників. Прості і складені числа. Властивості відношення подільності між двома натуральними числами одне з яких просте. Існування простого дільника у кожно

Украинкский

2013-07-07

116.5 KB

62 чел.

Лекція 22

ПРОСТІ І СКЛАДЕНІ ЧИСЛА

  1.  Розбиття множини цілих невід’ємних чисел на 4 класи за кількістю дільників. Прості і складені числа.
  2.  Властивості відношення подільності між двома натуральними числами одне з яких просте.
  3.  Існування простого дільника у кожного натурального числа більшого одиниці.
  4.  Нескінченність множини простих чисел (теорема Евкліда).
  5.  Критерії простоти натурального числа. Решето Ератосфена.
  6.  Основна теорема арифметики. Канонічний розклад натурального числа більшого 1.
  7.  Загальний вид канонічних розкладів дільників натурального числа. Ознака подільності на складене число.
  8.  Алгоритми знаходження найменшого спільного кратного і найбільшого спільного дільника кількох натуральних чисел за їх канонічним розкладами.

  1.  Розбиття множини цілих невід’ємних чисел на 4 класи

за кількістю дільників. Прості і складені числа

Як відомо, для довільного цілого невід'ємного числа a і натурального числа b, якщо a ділиться на b, то число b називається дільником числа a.

Множину цілих невід'ємних чисел за кількістю натуральних дільників можна розбити на такі 4 класи:

1) клас, єдиним елементом якого є число нуль, що має безліч дільників;

2) клас, єдиним елементом якого є число 1, що має єдиний дільник;

3) клас, елементи якого мають два дільники;

4) клас, елементи якого мають більше як два дільники, але їх скінченна кількість.

Числа останніх двох класів займають у математиці особливе місце. Вони складають обсяги двох важливих понять.

Натуральне число більше одиниці називається:

1) простим, якщо воно має своїми дільниками тільки одиницю і саме себе;

2) складеним, якщо воно має не менше трьох дільників.

Наприклад, за цим означенням числа 2, 3, 5, 7, 11, 13, 17, 19 прості, а числа 4, 6, 8, 9, 10, 12 – складені.

  1.  Властивості відношення подільності між

двома натуральними числами одне з яких просте

Теорема 18. Якщо просте число ділиться на натуральне число більше одиниці, то ці числа рівні.

► Нехай p – просте число і a > 1 – натуральне число таке, що p M a.  p  просте число, то за означенням воно має своїми дільниками лише 1 і p. a > 1 і є дільником p. Отже, a = p.  ◄

Теорема 19. Для довільних натурального числа a і простого числа p має місце одне і тільки одне із відношень: або a ділиться на p, або вони взаємно прості.

► Нехай a – довільне натуральне число, а p – довільне просте число. Розглянемо НСД(ap). Можливі лише два такі випадки: або НСД(ap) = 1, тоді числа a і p взаємно прості; або НСД(ap) = d > l. Звідси одержуємо, що p M d. За теоремою 18 маємо, що p = d, а тому a M p.  ◄

  1.  
    Існування простого дільника у кожного

натурального числа більшого одиниці

Теорема 20. Добуток кількох натуральних множників ділиться на просте число тоді і тільки тоді, коли хоч один із множників ділиться на просте число.

► Необхідність. Нехай p – довільне просте число і a1, a2, ... , an – будь-які натуральні числа такі, що

a1·a2·...·an M p.

Доведемо, що принаймні одне із чисел a1, a2, ..., an ділиться на p. Доведення проведемо методом математичної індукції по кількості множників.

1. Нехай n = 2  і  a1·a2 M p. Для натурального числа a1 і простого числа p за теоремою 19 можливі лише такі два випадки:

а) a1 M p, тоді доводжуване твердження істинне;

б) числа a1 і p взаємно прості. А тому маємо, що добуток двох чисел ділиться на третє число, яке взаємно просте з одним із них. Звідси за теоремою 15 одержуємо, що друге число ділиться на просте число. Отже, твердження істинне для двох множників.

2. Припустимо, що твердження істинне при n = k ³ 2, тобто, що коли a1·a2·...·ak M p, то принаймні один із множників ділиться на p.

3. Доведемо, що твердження істинне при n = k + 1. Дійсно, нехай задано добуток k + 1 множників a1·a2·…·ak·ak+1, який ділиться на p. За властивостями множення цілих невід'ємних чисел добуток можна записати (a1·a2·…·akak+1. Позначивши  a1·a2·…·ak = a, будемо мати  a·ak+1 M p.

Розглянемо число ak+1. Оскільки p – просте число, то можливі лише такі два випадки:

а) ak+1 M p і у цьому випадку твердження істинне при n = k + 1;

б) ak+1 і p взаємно прості числа. У цьому випадку за теоремою 15 одержуємо a M p, тобто a1·a2·…·ak M p. Звідси за припущенням маємо, що хоча б одне із чисел a1, a2, …, ak ділиться на p. Отже, і у цьому випадку твердження істинне при n = k + 1.

Тому за принципом математичної індукції твердження істинне для кожного натурального числа n ³ 2.

Достатність теореми випливає із теореми про подільність добутку.  ◄

Теорема 21. Кожне натуральне число більше одиниці має принаймні один простий дільник.

► Нехай a – довільне натуральне число більше одиниці. Розглянемо множину його дільників більших від 1, яку позначимо M. Вона непорожня, бо їй належить саме число a. За принципом найменшого числа у ній існує найменше число, позначимо його p і доведемо, що воно просте.

Припустимо протилежне, що число p не є простим. Тоді воно ділиться на деяке натуральне число g таке, що 1 < g < p. Маємо a M p і p M g. Звідси за транзитивністю відношення подільності a M g, де 1 < g < p, що суперечить вибору числа p як найменшого дільника числа a. Отже, p є простим дільником числа a.  ◄

З теореми 21 одержується наслідок.

Наслідок 10. Найменший, відмінний від одиниці, дільник натурального числа є числом простим.

  1.  Нескінченність множини простих чисел (теорема Евкліда)

Теорема 22 (теорема Евкліда). Множина простих чисел нескінченна.

► Доведемо теорему методом від супротивного. Припустимо, що множина простих чисел скінченна, тобто, що вона складається із простих чисел p1, p2, ..., pn. Розглянемо число

g = p1·p2· ... ·pn + 1.

Число g натуральне і більше одиниці, а тому воно має принаймні один простий дільник (теорема 21). Таким простим числом не може бути жодне з простих чисел p1, p2, ..., pn, бо число g при діленні на кожне з них дає в остачі 1. Отже, існує просте число, відмінне від чисел p1, p2, ..., pn. Значить, наше припущення про скінченність множини простих чисел хибне.  ◄

Простим чи складеним є задане натуральне число, більше від 1, встановлюється на основі теореми, яка може бути використана як критерій простоти натурального числа.

Теорема 23. Якщо натуральне число a більше одиниці не ділиться на жодне з простих чисел, квадрати яких не перевищують a, то число a просте.

► Доведемо теорему методом від супротивного. Припустимо, що число a складене. Тоді за властивістю простих чисел (наслідок 10) найменший його дільник, більший від 1, є числом простим. Позначимо його g. Матимемо

a = g·a1,   1 < g < a,   a1 > 1.

За вибором числа g воно є найменшим дільником числа a, більшим від одиниці, і простим, а тому g £ a1. Звідси за монотонністю множення цілих невід'ємних чисел g2 £ a1·g, тобто g2 £ a. Отже, g є простим дільником числа a, квадрат якого не перевищує a, а це суперечить умові теореми.  ◄

З теореми 23 одержується наслідок.

Наслідок 11. Найменший простий дільник натурального числа не перевищує кореня квадратного з даного числа.

Задача 3. Встановити, простим чи складеним є число 967.

► Для того, щоб встановити простим чи складеним є число 967, потрібно на основі теореми 23 перевірити, чи є його дільниками всі прості числа від 2 до 31, бо 312 = 961 < 967, а 322 = 1024 > 967.

За ознаками подільності встановлюємо, що число 967 не ділиться на прості числа 2, 3, 5 і 11. Безпосередньо перевіряємо, що це число не ділиться на прості числа 7, 13, 17, 19, 23, 29 і 31.

Отже, число 967 не ділиться на жодне з простих чисел, квадрати яких не перевищують числа 967, а тому воно буде простим.

Відповідь: число 967 – просте.  ◄ 

  1.  Критерії простоти натурального числа. Решето Ератосфена

Прості числа у натуральному ряді розподілені нерівномірно. Можна вказати досить великі проміжки натурального ряду, в яких немає жодного простого числа. Наприклад, серед чисел виду

n! + 2, n! + 3, n! + 4, …, n! + n

при достатньо великому n немає жодного простого числа. Нагадаємо, що n! = 1×2×3××n. Разом із тим існують послідовні непарні числа, що є простими. Такими, зокрема, є числа 3 і 5, 5 і 7, 11 і 13, 17 і 19, ... , 1000061087 і 1000061089, ... .

Для вивчення розподілу простих чисел у натуральному ряді та інших задач теорії чисел потрібно знати всі прості числа, які не перевищують заданого натурального числа. Для розв'язання цієї задачі є спеціальний метод, який називається решетом Ератосфена. Суть його полягає у наступному.

1. Виписують всі натуральні числа від 2 до n.

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ..., n.

(1)

2. Число 2 ділиться тільки на 1 і саме на себе, отже, воно є простим. Викреслюють у ряді (1) усі числа кратні двом, крім самого числа 2.

3. Перше, наступне за 2 не викреслене число, буде 3. Воно не ділиться на 2 (інакше його б викреслили). Отже, 3 ділиться тільки на 1 і самого себе, а тому також буде простим. Викреслюють усі числа кратні 3, крім самого числа 3.

4. Перше, наступне за 3 не викреслене число, буде 5. Воно не ділиться ні на 2, ні на 3. Отже, 5 ділиться тільки на 1 і саме на себе, тому воно також буде простим. Викреслюють усі числа кратні 5, крім самого числа 5 і т. д.

Процес буде закінчено, коли одержиться просте число p таке, що p2 £ n, але для першого, наступного за p невикресленого простого числа p1, p12 > n. Усі не викреслені числа від 2 до n будуть простими.

Наприклад, щоб скласти таблицю простих чисел, які не перевищують 1000, викреслювання потрібно закінчити при p = 31, тому що 312 = 961 < 1000. Для наступного числа за 31, тобто для числа 32, маємо 322 = 1024 > 1000, а тому й поготів для наступного простого за 31 числа будемо мати таку ж нерівність.

Зауваження. 1. Щоб викреслити всі складені числа кратні простому числу p, не потрібно знати ознаки подільності на p, для цього досить у ряді (1) викреслити кожне p-те число після числа p, враховуючи й ті, які вже раніше були викреслені.

2. Викреслювання чисел кратних простому числу p слід починати з p2, тому що всі складені числа між p і p2 уже викреслені як кратні простим числам, меншим від p (на основі теореми 23).

  1.  Основна теорема арифметики.

Канонічний розклад натурального числа більшого 1

Прості числа відіграють особливу роль у математиці, вони є своєрідними "цеглинками", з яких будується кожне натуральне число більше одиниці. Це випливає з наступної теореми, яку називають основною теоремою арифметики.

Теорема 24. Кожне натуральне число більше одиниці є або простим або розкладається у добуток простих множників, причому цей розклад єдиний з точністю до порядку слідування множників.

► І. Спочатку покажемо, що кожне натуральне число більше одиниці є або простим, або розкладається в добуток простих множників. Для цього скористаємося методом математичної індукції.

1. 2 – просте число. Отже, твердження істинне при a = 2.

2. Припустимо, що твердження істинне для довільного натурального числа k такого, що 2 £ k < a, тобто, що кожне таке число є або простим, або розкладається в добуток простих множників.

3. Доведемо істинність твердження і для числа a.

Оскільки натуральне число a більше одиниці, то воно має принаймні один простий дільник (теорема 21). Позначимо його p1.

a = p1·k1.

(1)

У рівності (1) k1 є натуральним числом, отже, для нього можливі лише два такі випадки: або k1 = 1, або k1 > 1.

Якщо k1 = 1, то число a є простим, і доводжуване твердження у цьому випадку істинне і для a.

Якщо k1 > 1, то в силу рівності (1), 2 £ k1 < a. Звідси та з припущення одержуємо, що для числа k1 можливі лише два такі випадки:

а) число k1 є простим і тоді число a є добутком двох простих множників;

б) число k1 є складеним і розкладається у добуток простих чисел, тобто k1 = p2·p3·…·pn, і тоді a = p1·p2·…·pn.

Отже, твердження істинне для a і у випадку, коли k1 > 1. Таким чином, твердження істинне для a.

Звідси на основі принципу математичної індукції твердження істинне для довільного натурального числа a ≥ 2.

ІІ. Доведемо тепер, що для складеного натурального числа його розклад у добуток простих множників єдиний з точністю до порядку слідування множників. Дійсно, нехай складене число a має принаймні два розклади у добуток простих чисел

a = p1·p2·…·pn   і   a = g1·g2·...·gs.

Тоді

p1·p2·…·pn = g1· g2·...·gs.

(2)

З рівності (2) випливає, що добуток p1·p2·…·pn ділиться на просте число g1, а тому на основі теореми 20 про подільність добутку на просте число робимо висновок, що принаймні один із множників p1, p2, …, pn ділиться на число g1. Не обмежуючи загальності міркувань, можна вважати, що таким множником є число p1. Оскільки p1 і g1 – прості числа, то на основі теореми 18 про властивість простих чисел p1 = g1. Cкорочуючи обидві частини рівності (2) на p1, матимемо

p2·p3·…·pn = g2·g3·…·gs.

Повторюючи аналогічні міркування, через скінченне число кроків дістанемо

p1 = g1,   p2 = g2, …, pk = gk  і або n = s, або  n ≠ s.

Покажемо, що n = s. Дійсно, якщо припустити, що n < s, то

1 = gn+1·gn+2·…·gs,

що неможливо, бо добуток простих чисел більший 1. Аналогічно розглядається випадок, коли n > s.

Отже, n = s і розклади не відрізняються простими множниками, тобто він єдиний з точністю до порядку слідування множників.  

  1.  Загальний вид канонічних розкладів дільників натурального числа. Ознака подільності на складене число

Якщо для складеного натурального числа знайдено його представлення у вигляді добутку простих множників, і у ньому рівні прості множники записано у вигляді степенів простих множників, а самі прості множники розміщені у порядку зростання, то такий запис складеного числа у вигляді добутку простих множників називається канонічним розкладом натурального числа , де p1, p2, …, pn – різні прості дільники числа a і p1 < p2 < … < pn.

Якщо натуральне число a є простим, то сам його запис і є канонічним розкладом числа a.

Говорять, що просте число p входить у канонічний розклад числа , якщо воно дорівнює одному з чисел p1, p2, …, pn.

На основі поняття канонічного розкладу з основної теореми арифметики одержується наслідок.

Наслідок 12. Канонічний розклад складеного числа єдиний.

Щоб знайти канонічний розклад складеного числа, випробовують його подільність на прості числа у порядку зростання. При цьому користуються відомими ознаками подільності на прості числа. Результати обчислень зручно розташовувати так, як показано у наступній задачі.

Задача 4. Знайти канонічний розклад натурального числа 446688.

► Користуючись ознаками подільності на відомі нам прості числа, матимемо

446688

2

223344

2

111672

2

55836

2

27918

2

13959

3

4653

3

1551

3

517

11

47

47

1

Відповідь: 446688 = 25·33·11·47.  

  1.  Алгоритми знаходження найменшого спільного кратного і найбільшого спільного дільника кількох натуральних чисел за їх канонічним розкладами

При розгляді кількох натуральних чисел можна вважати, що їх канонічні розклади містять степені одних і тих самих простих множників, при цьому показники степенів у деяких з них можуть бути рівні нулеві, бо за означенням нульового показника степеня x0 = 1 для довільного числа x ≠ 0.

За допомогою канонічного розкладу натуральних чисел можна встановити вигляд їх дільників.

Теорема 25. Якщо натуральне число a має канонічний розклад

,

то натуральне число b є його дільником тоді і тільки тоді, коли воно має канонічний розклад   і  0 ≤ β1 ≤ α1,  0 ≤ β2 ≤ α2, …, 0 ≤ βn ≤ αn.

► Необхідність. Нехай число  ділиться на число b. Отже, a = b·g або, що те саме,  = b·g.

Внаслідок єдиності розкладу на прості множники, до канонічного  розкладу чисел b і g не можуть входити прості числа, відмінні від чисел p1, p2, ..., pn. А тому

 і  .

Отже,

 = ()·() = = .

Звідси, завдяки єдиності канонічного розкладу, одержуємо

.

Числа aі, bi і gi є цілими невід'ємними числами, тому з попередніх рівностей

£ b1 £ a1,  0 £ b2 £ a2,  …,  0 £ bn £ an.

Достатність. Нехай число b має такий канонічний розклад, як вказано у теоремі. Тоді число a можна записати

 = ()·().

Різниці ai – bi існують завдяки умові 0 £ bі £ ai, i = 1, 2, …, n. 3 одержаної рівності випливає, що число b є дільником числа a.  ◄

З теореми 25 випливають наслідки.

Наслідок 13. Натуральне число ділиться на просте число тоді і тільки тоді, коли дане просте число входить до його канонічного розкладу.

Наслідок 14. Два натуральних числа взаємно прості тоді і тільки тоді, коли їх канонічні розклади не мають спільних простих дільників.

Наслідок 15. Якщо кожне з двох даних натуральних чисел взаємно просте з третім натуральним числом, то і їх добуток взаємно простий з даним числом.

Теорема 25 також дає можливість за канонічними розкладами кількох натуральних чисел знайти їх найбільший спільний дільник і найменше спільне кратне.

Теорема 26.

1. Канонічний розклад найбільшого спільного дільника кількох натуральних чисел містить ті ж самі прості множники, що й канонічні розклади цих чисел, але взятими з найменшими показниками степенів.

2. Канонічний розклад найменшого спільного кратного кількох натуральних чисел містить ті ж самі прості множники, що й канонічні розклади даних чисел, але взяті з найбільшими показниками степенів.

► Нехай задано кілька натуральних чисел і відомі їх канонічні розклади

.

Позначимо через m1 – найменше, а через n1 – найбільше з чисел a1, b1, … l1, тобто

m1 = min{a1, b1, …, l1},   n1 = max{a1, b1, …, l1}.

Аналогічно

m2 = min{a2, b2, …, l2},   n2 = max{a2, b2, …, l2},

………………………………

mn = min{an, bn, …, ln},   nn = max{an, bn, …, ln}.

На основі введених позначень, щоб довести теорему, потрібно показати, що

НСД(ab, …, l) = ,

(1)

НСК(ab, …, l) = 

(2)

Доведемо рівність (1). Нехай d = . Тоді за теоремою 25 число d є спільним дільником чисел a, b, …, l. За основною властивістю найбільшого спільного дільника число d є дільником числа D = НСД(ab, …, l). Знову, за теоремою 25 число D = , де s1 ³ mi,  i = 1, 2, …, n.

Покажемо, що s1 = mi, i = 1, 2, …, n. Дійсно, якби при деякому i0 було , то те з чисел a, b, …, l, до канонічного розкладу якого входить число , не ділилося б на D. Отже, s1 = mі,  i = 1, 2, …, n, тобто

НСД(ab, … , l) = .

Аналогічно доводиться рівність (2).  

Задача 5. Знайти найбільший спільний дільник і найменше спільне кратне чисел 4680, 7722 і 4368 за їх канонічними розкладами.

► Знаходимо канонічні розклади даних чисел:

4680

2

7722

2

4368

2

2340

2

3861

3

2184

2

1170

2

1287

3

1092

2

585

3

429

3

546

2

195

3

143

11

273

3

65

5

13

13

91

7

13

13

1

13

13

1

1

Маємо 4680 = 23×32×5×13.

7722 = 2×33×11×13.

4368 = 24×3×7×13.

Отже, за теоремою 26 НСД(4680, 7722, 4368) = 2×3×13 = 78 і НСК(4680, 7722, 4368) = 24×33×5×7×11×13 = 2162160.

Відповідь:  НСД(4680, 7722, 4368) = 78,

НСК(4680, 7722, 4368) = 2162160.  ◄


 

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

24786. ТЕОРИЯ УПРАВЛЕНИЯ 168 KB
  В изучаемом курсе нас будет интересовать общая теория управления. И Кнорринг считает что управление в широком понимании этого термина – непрерывный процесс воздействия на объект управления личность коллектив технологический процесс предприятие государство для достижения оптимальных результатов при наименьших затратах времени и ресурсов[19]. Понятие управление используется в следующих значениях: 1 управление как наука – система упорядоченных знаний в виде концепций теорий принципов способов и форм управления; 2 управление как...
24787. Направления административных реформ в странах Запада и в России: сравнительный анализ 75 KB
  Суть административной реформы АР в Российской Федерации в комплексной трансформации системы органов государственного управления с целью обеспечения их большей гибкости и эффективности. Концепция нового государственного управления: мировая практика. Стремление осуществить АР в РФ соответствует идеям и мировой практике совершенствования государственного управления. во многих странах Запада был реализован значительный объем широкомасштабных и комплексных программ реформирования системы государственного управления на основе концептуальных...
24788. ТЕОРИЯ ОРГАНИЗАЦИИ. Сущность системного подхода к организациям. Синергетический эффект в организациях 97.5 KB
  Системный подход стал фактически тем инструментом который позволил создать современную теорию организации. Можно сказать что теория организации как наука родилась именно в рамках этого подхода. Цели организации задаются извне или вырабатываются внутри нее с учетом этих целей выбираются форма и устройство организации.
24789. УПРАВЛЕНИЕ ПРСОНАЛОМ 147.5 KB
  Набор персонала заключается в комплектовании необходимого резерва кандидатов на все должности и специальности из которых организация отбирает подходящих для нее работников.; составление базы данных по кандидатам на вакантные должности; отбор персонала выявление различий между кандидатами и соответствующими требованиями будущей деятельности выбор лучших кандидатов; решение о приеме на работу; введение в должность адаптация работника. Это более тонкая по сравнению с отбором процедура идентификации характеристик человека и...
24790. РАЗРАБОТКА УПРАВЛЕНЧЕСКОГО РЕШЕНИЯ 73 KB
  Требования предъявляемые к управленческим решениям Сущность и виды управленческих решений Решение это выбор альтернативы. Решения принимаемые в процессе управления могут быть классифицированы по различным признакам. По уровню управления различают решения принимаемые на разных уровнях: начальника цеха начальника отдела; заместителя директора; директора; министра.
24791. УПРАВЛЕНИЕ ОБЩЕСТВЕННЫМИ ОТНОШЕНИЯМИ 42 KB
  Организация связей с общественностью в системе государственного и муниципального управления: общее и особенное. управления можно отнести: участие в демократизации государственного управления содействие становлению гражданского общества. Существует прямая зависимость между уровнем управления и особенностями служб PR: в региональных и муниципальных органах власти широко реализуется коммуникативная функция и общение с гражданами постоянно и организованно. Возможности PR могут быть использованы в целях повышения открытости государственного...
24792. ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ УПРАВЛЕНИЯ 59.5 KB
  наличие централизованных информационных центров генераторов баз данных 2. Например: Федеральная налоговая служба организовала Банк Данных глобальную базу данных. Локальные и распределенные базы данных системы управления базами данных. Информационные ресурсы представляют собой отдельные документы и отдельные массивы документов в информационных системах библиотеках архивах фондах банках данных других видах информационных систем.
24793. ИННОВАЦИОННЫЙ МЕНЕДЖМЕНТ. Технологические уклады, основные периоды. Прогноз 73 KB
  Инновации и жизненный цикл товара. Этап внедрения начинается с момента появления товара на тынке. Цены на первом этапе могут быть низкими либо высокими в зависимости от специфики и особенностей товара и потребителя. Примером товара находящегося на первом этапе ЖЦТ может служить цифровая фотокамера.
24794. ГОСУДАРСТВЕННЫЕ И МУНИЦИПАЛЬНЫЕ ФИНАНСЫ. Структура государственных финансов РФ 120 KB
  Структура государственных финансов РФ. Структура государственных финансов . Структуру государственных финансов можно определять с двух точек зрения. Государственные финансы могут быть рассмотрены с точки зрения преемственности к тем или иным органам государственной власти или с позиции разделения государственных финансов на бюджетные и не бюджетные фонды.