Просте число

Натуральне число $p$ називається простим, якщо воно має рівно два дільники — $1$ і саме число p. Наприклад, числа

$4=2\cdot 2,\quad 15=3\cdot 5,\quad 3913=7\cdot 13\cdot 43$ — не є простими,

а >2, 11, 59 — прості.

Перші десять простих чисел такі:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29

дивіться також список простих чисел.

Деякі факти про прості числа

Розкладання числа у добуток простих чисел

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

Доведення: Спочатку доведемо існування розкладу для будь-якого числа M. Число M або є простим (і, отже єдиним чином розкладається у добуток 1*M), або має якнайменше один дільник окрім 1 та M (назвемо цей дільник d). Додамо число d до списку дільників числа M, і продовжимо наш процес з числом M¹ = M / d. Очевидно, що на кожному кроці нашого процесу число зменшується. Оскільки число M скінченне, то через скінченну кількість кроків ми отримаємо повний список простих дільників числа M.

Доведемо тепер однозначність розкладу (знову скористаємось методом від супротивного). Нехай існують два різних розклади M = P₁*P₂*...*P_N та M = S₁*S₂*...*S_K. Очевидно, має існувати множник P_i, який міститься в першому розкладі, але не міститься в другому. Оскільки P_i міститься в першому розкладі числа M, то число M має ділитись на P_i, а, отже, і добуток S₁*S₂*...*S_K має ділитись на P_i. Оскільки P_i - просте, і не має інших дільників крім 1 і себе, то для того, щоб добуток S₁*S₂*...*S_K ділився на P_i, то деякий множник S_j має ділитись на P_i. Оскільки S_j — просте число, що ділиться на P_i, то це означає, що S_j = P_i. Отже, P_i міститься у другому розкладі також, що суперечить нашому припущенню. Доведення закінчено.

Нескінченність множини простих чисел

Як було доведено грецьким математиком Евклідом, існує нескінченно багато простих чисел. Евклід використав метод доведення від супротивного. Припустимо, що множина простих чисел — скінченна. Тоді ми можемо перенумерувати всі прості числа: P₁, P₂, P₃, ..., P_N. Розглянемо число M = P₁*P₂*P₃*...*P_N + 1. Очевидно, число М не може ділитись націло на жодне з простих чисел P₁, ..., P_N (оскільки число (M - 1) ділиться націло на кожне з них). Отже, або число М є простим, або воно ділиться на якесь інше просте число, яке не увійшло до нашого списку. У будь-якому випадку, ми знайшли просте число, яке не входить до нашого списку простих чисел P₁, P₂, P₃, ..., P_N, що протирічить нашому припущенню. Отже, існує нескінченно багато простих чисел.

Застосування простих чисел

Великі прості числа (порядка 10³⁰⁰) використовуються в криптографії з відкритим ключем. Прості числа також використовуються в хеш-таблицях і для генерації псевдовипадкових чисел.

Дивіться також

• Прості числа-близнюки
• Натуральне число
• Решето Ератосфена