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

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

Означення: дільником натурального числа а називається таке натуральне число b, на яке дане число а ділиться без остачі.

Із означення випливає, що будь-який дільник даного числа не більший, ніж дане число а. Це означає, що кількість дільників у даного числа скінченна і найменшим дільником є число 1. Отже, всі дільники деякого числа а знаходяться на проміжку [1;a]. Спробуємо згрупувати всі цілі невід’ємні числа за кількістю дільників у певні класи. До першого класу віднесемо число 0, бо воно ділиться на будь-яке натуральне число, тобто має безліч дільників. Цей клас позначимо К₁={0}. До другого класу віднесемо натуральне число 1, яка має рівно один дільник. Цей клас позначимо К₂={1}. До третього класу, який позначимо К₃, віднесемо всі натуральні числа, що мають рівно два дільники. І нарешті, до четвертого класу, який позначимо К₄, віднесемо натуральні числа, що мають три і більше дільників. Оскільки кожен із вказаних класів непорожній, класи попарно не перетинаються, а їх об’єднання утворює всю множину цілих невід’ємних чисел, то ми розбили множину цілих невід’ємних чисел на класи, що попарно не перетинаються. Розглянемо більш детально два останніх класи. Елементи кожного із класів приводять до появи нових понять: „просте число” і „складене число”.

Означення: більші за одиницю натуральні числа, які мають рівно два дільники, називаються простими.

Означення: більші за одиницю натуральні числа, які мають більше, ніж два дільники, називаються складеними.

Числа 0 і 1 не відносяться ні до простих, ні до складених. В означеннях простих і складених чисел нічого не говориться про їх існування, а тому потрібно довести відповідні теореми.

Теорема (про існування простих чисел): найменший, відмінний від 1, дільник більшого за 1 натурального числа а є просте число.

Доведення: за умовою аєZ₀ і а>1. Множина дільників числа а не може бути порожньою, бо і . Крім того, ця множина є скінченною, а тому на проміжку [1;а] існує найменший, відмінний від одиниці дільник числа а. Нехай таким дільником буде число p. Тоді , причому 1<р£а. З’ясуємо, простим чи складеним є число p. Припустимо, що число p – складене, тоді воно має принаймні три дільники (1, р₁, р), де 1< р₁< р. Оскільки і , то за властивістю транзитивності . Отже, р₁ є дільником числа а. Це суперечить вибору числа p, як найменшого дільника числа а. Ця суперечність говорить про те, що наше припущення про те, що p – складене число, було хибним. Отже, p – просте число, тобто прості числа існують. Теорема доведена.

Доведена теорема була сформульована і доведена у 3 ст. до н. е. Евклідом. Це єдина проблема теорії простих чисел, яку вдалося розв’язати античним математикам. Разом з тим доведена теорема нічого не говорить про кількість простих чисел, а тому слід довести теорему.

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

Доведення: проведемо методом від супротивного, припустивши, що множина простих чисел скінченна. Задамо цю множину переліком: А={p₁,p₂,p₃,…p_k}, де вони записані у порядку зростання. Утворимо нове число b=p₁·p₂·p₃·…·p_k+1. Легко бачити, що b>1, а тому, згідно з теоремою про існування простих чисел, число b буде мати відмінний від 1 простий дільник. Нехай це буде число p. Оскільки, p – дільник числа b, то . Оскільки p – просте число, то pєА. Тоді за теоремою про подільність добутку цей добуток буде ділитись націло на p. Це означає, що число p дорівнює якомусь елементу з множини А. Тоді справедливим буде твердження: (p₁·p₂·p₃·…·p_k) р, бо там записані всі прості числа. Нехай для визначеності р=р₂, тоді . Оскільки і , то за теоремою про подільність різниці, різниця (в-p₁·p₂·p₃·…·p_k) p₂, тобто 1 p₂. Це суперечить тому, що р₂>1. Ця суперечність і говорить, що наше припущення про скінченність множини простих чисел було хибним. Теорема доведена.

Для того, щоб з’ясувати, чи є дане число простим чи складеним, доводиться виконувати досить громіздку процедуру, яка полягає в тому, що перевіряють, чи є серед дільників даного числа менші, ніж дане число. Для спрощення цього процесу можна використовувати таблиці простих чисел. Вперше їх почав будувати старогрецький математик Ератосфен. На восковій дощечці він записував всі натуральні числа. Оскільки 1 не відноситься ні до простих, ні до складених чисел, то він його виколював. Наступним числом є число два, яке є простим. Після цього він виколював всі числа, які діляться на 2, бо вони матимуть принаймні три дільника 1, 2 і саме себе. Число 3 не виколювалося, але виколювалися всі числа, що діляться на 3. наступним простим числом є число 5, а виколюються числа 10, 15, 20, 25,... Таким чином, на восковій дощечці не виколотими залишалися лише прості числа. Такий спосіб побудови таблиці простих чисел одержав назву решета Ератосфена. Цим методом з деякими удосконаленнями користуються для складання таблиць простих чисел і нині. У 1909 р. було видано таблицю простих чисел, менших, ніж 50 млн., у 1961 році – таблиці, які містили перші 6 тис. простих чисел, Для цього перебрали числа від 2 до 104345301. Але відомі і інші прості числа. Зокрема, найбільшим на даний час є число = 2¹¹²¹³-1.

Спостерігаючи за таблицею простих чисел, можна виявити прості числа–близнюки, різниця між якими дорівнює двом (5 і 7, 17 і 19). Існують надзвичайно великі проміжки натурального ряду, на яких немає жодного простого числа. На даний час відомо такий проміжок . На даний час невідомо скінченною чи нескінченною є множина простих чисел–близнюків. Є ще багато нерозв’язаних питань у теорії простих чисел.

Для спрощення процесу знаходження простих дільників у даного числа доводять теореми:

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

Доведення: нехай цим числом є число p, тобто . Доведемо, що . Оскільки , то . Порівняємо p і b: b³р, бо в противному разі число b мало б прості дільники, менші, ніж p, а тому число p не було б найменшим простим дільником числа а. Оскільки b³р, то помноживши обидві частини на p, маємо: вр³р². Таким чином, . Теорема доведена.

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

Доведення: нехай аєN і а>1. За теоремою про існування простого дільника число а має такий простий дільник. Крім того, за попередньою теоремою цей простий дільник не перевищує . Якщо число а – складене, то його найменший простий дільник, відмінний від одиниці, за попередньою теоремою не перевищує . За умовою даної теореми число а не ділилося на жодне із простих чисел, які не перевищують квадратного кореня із цього числа, а тому число а є простим. Теорема доведена.

Доведена теорема дає можливість значно спростити процес знаходження простих дільників даного числа а. Проілюструємо це з допомогою наступної вправи. „З’ясувати, простим чи складеним є число 1223?”

Розв’язання: за попередньою теоремою, якщо число 1223 має прості дільники, то вони не перевищують . Оскільки <35, то для відшукання простих дільників числа 1223 спробуємо поділити його на всі прості числа, менші 35. легко переконатися у справедливості таких тверджень: , , , , , , 1223:17, 1223:19, 1223:23, 1223:29, 1223:31. Оскільки число 1223 не ділиться на жодне із простих чисел, меньших, ніж 35, то число 1223 – просте.