Прості числа

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

Означення і приклади

Просте число — це натуральне число, яке ділиться без остачі лише на одиницю і на само себе, при цьому сама одиниця простим числом не є. Найменше просте число — два: воно ділиться без остачі на одиницю і на двійку. Це також єдине просте число, яке є парним. Усі інші прості числа непарні, бо будь-яке інше парне число ділиться, крім одиниці й самого себе, ще й на двійку.

Послідовність кількох перших простих чисел: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271…

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

Властивості простих чисел

• Простих чисел нескінченно багато. Доведення наведено в статті про доведення від супротивного.
• Для кожного цілого числа z>1 в інтервалі (z; 2z) існує принаймні одне просте число. Приклад: для z = 2 маємо інтервал (2; 4). Єдине ціле число в цьому інтервалі — трійка, і вона проста. Для z = 5 отримаємо інтервал (5; 10), тобто числа 6, 7, 8, 9. Число 7 просте. Так само й для більших z.
• Просте число Мерсенна — це просте число, яке на одиницю менше за деякий цілий степінь двійки. Просте число Мерсенна M має вигляд M = 2^z − 1, де z — деяке натуральне число. Прикладом є просте число 3, бо 2² − 1 = 3, або 7, бо 2³ − 1 = 7.
• Найбільші відомі прості числа, як правило, є числами Мерсенна. Наприклад, 23 серпня 2008 року було знайдено просте число Мерсенна M_43112609, де нижній індекс означає показник степеня z. Це просте число 2^43112609−1, яке має 12,978,189 цифр і на той час було найбільшим відомим простим числом.

Послідовність без простих чисел

Можна знайти як завгодно довгу скінченну послідовність послідовних натуральних чисел, серед яких немає жодного простого. Така послідовність може мати вигляд k!+2, k!+3, …, k!+k і містить k − 1 послідовних складених чисел (знак оклику означає факторіал).

Наприклад, для k = 6 отримаємо п'ять послідовних складених чисел: 720 + 2, 720 + 3, 720 + 4, 720 + 5, 720 + 6. Ці числа по черзі діляться на два, три, чотири, п'ять і шість, бо число 6! = 720 напевно ділиться на всі ці числа, адже воно є їхнім добутком: 6! = 6 · 5 · 4 · 3 · 2. Якщо число 720 ділиться на три, то й число 720 + 3 мусить ділитися на три. Так само й для решти.

Мала теорема Ферма

Для кожного простого числа p і для кожного цілого числа z такого, що z не кратне p, число z^p − z ділиться на просте число p.

Приклад: візьмемо просте число p = 3 і ціле число z = 4. Число чотири не кратне трьом, тож можемо продовжувати. Обчислимо значення 4³ − 4. Воно дорівнює 60. При цьому 60:3 = 20, тобто трійка ділить шістдесят без остачі, що відповідає теоремі Ферма. Інший приклад: p = 7, z = 10. Обчислимо проміжний результат 10⁷ − 10 = 9999990 і поділимо його на сім: 9999990:7 = 1428570. Знову отримали результат без остачі.

Невирішені питання

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

• Нескінченність пар простих чисел-близнюків: пара простих чисел-близнюків — це пара чисел (z; z + 2), у якій обидва числа прості. Наприклад, (3; 5) або (29; 31). Питання в тому, чи є таких пар нескінченно багато. Вважають, що так, але доведення немає.
• Гіпотеза Рімана: усі нетривіальні нулі дзета-функції Рімана мають дійсну частину, що дорівнює $\frac12$. Гіпотеза пов'язана з розподілом простих чисел і є однією з так званих проблем тисячоліття, а за її розв'язання на тебе чекає винагорода в мільйон доларів.