2. Розклад складених чисел на прості множники.

Теорема(основна теорема арифметики). Будь-яке натуральне число >1 або є простим, або може бути представлене, і, притому єдиним способом у вигляді добутку простих чисел.

(Два представлення, які відрізняються лише порядком розміщення множників, вважаються однаковими).

Доведення:

I. Існування розкладу.

Нехай п = 2. Оскільки 2 — просте число, то для п = 2 твердження теореми є справедливим.

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

Розглянемо натуральне число п. Якщо п — просте, то твердження має місце. Якщо п — складене, то його можна записати у вигляді п =∙,

Де 1 < < n і 1 < < n.

Для чисел і згідно з індуктивним припущенням буде справедливим =∙... ∙ і .

Тоді, тобто існування розкладу для довільного п доведено.

II. Єдиність розкладу.

Нехай п = 2, це просте число, отже його розклад єдиний.

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

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

n=∙∙... ∙ і .

Тоді ∙∙... ∙=

Ліва частина цієї рівності ділиться на ,тоді на повинен ділитися один із множників добутку .Нехай . Оскільки — просте число і > 1, то .Поділимо обидві частини рівності на і отримаємо

∙... ∙=Оскільки ∙... ∙і — числа, менші за n, то згідно індуктивного припущення з останньої рівності випливає, що l=s, , ....

Отже, теорему доведено.

Згідно з основною теоремою арифметики будь-яке складене число п > 1 можна представити у вигляді добутку простих чисел. Серед цих простих множників можуть зустрічатись однакові. Нехай, наприклад, зустрічається раз, — раз, ... , — раз, тоді розклад числа п на прості множники можна записати таким чином

(*)

Множники , , ... , переважно розміщуються в порядку зростання. Перетворення натурального числа п до виду (*) називається факторизацією числа, а сама форма (*) — канонічною.

Приклади. 1176 = 2³∙3∙7²; 136125 = 5³∙11².

Наслідки: Нехай маємо два числа а і b, їх канонічний розклад

, ,

тоді (а, b) =де = min(,),

[а, b]= , де = max(,), звідки випливає тотожність [а, b]= (а, b) = ab. (Довести самостійно).

5. Нескінченість множини простих чисел. Решето Ератосфена.

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

Доведення (від супротивного). Припустимо, що множина простих чисел скінченна; нехай це будуть числа ,,..., де — найбільше просте число. Утворимо добуток чисел ∙∙... ∙ і розглянемо натуральне число п = ∙∙... ∙+1. Оскільки п > то п повинно бути складеним, отже воно повинно ділитись на одне з чисел ,,..., нехай — на . Оскільки добуток ∙∙... ∙ ділиться на також, то й другий доданок, тобто 1, також повинен ділитись на , але це неможливо.

Отже наше припущення невірне, а тому множина простих чисел нескінченна.

Решето Ератосфена. В III ст. до н. є. грецький математик Ератосфен знайшов спосіб виділення простих чисел з будь-якої скінченної послідовності натуральних чисел 1, 2, 3, ..., п за допомогою послідовного викреслювання числа 1; всіх чисел кратних 2; всіх чисел кратних 3; і т. д., до тих пір поки не зустрінеться найбільше просте число ≤.

Приклад. Виділимо прості числа з ряду 1, 2, З, ...,40.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26,27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40.

Отже, прості числа це: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37. (Чому у відповіді відсутнє число 1?).

Розкладання натурального числа на прості множники, розпізнавання простих чисел є трудомістким і складним процесом. Цю роботу можна спростити за допомогою Теореми 6.

Приклад 1. Встановимо, яким числом, простим чи складеним, є число 917.

Якщо число 917 — складене, то його найменший простий дільник не може бути більший за . Знаходимо 30< <31. Випишемо всі прості числа, менші за 30: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Перевіримо кожне з них; число 917 на жодне з них не ділиться, отже 917 — просте число.

Приклад 2. Чи є простим число 323?

Знаходимо 18 < < 19, перевіримо всі прості числа до 18: 2, З, 5, 7, 11, 13, 17. Встановлюємо, що 323 ділиться на 17, отже 323 — складене.

Приклад 3. Розкласти на прості множники число 7469.

Знаходимо, що 86 << 87. Перевіряємо всі прості числа, що не перевищують 86: 2, 3, 5, 7, 11, 13, 17, 19,23,29,31,37,41,43, 47, 53, 59, 61, 71, 73, 79, 83. Встановлюємо, що 7469 не ділиться на 2, 3, 5, але ділиться на 7: 7469 = 7∙1067. Далі знаходимо 32 < < 33. Перевіряємо тепер числа 7, 11, 13, 17, 19, 23, 29, 31; встановлюємо, що 1067 не ділиться на 7, але ділиться на 11: 1067 = 11∙97, а 97 — просте число, отже 7469 = 7∙11∙97.