Просте число

Матеріал з Вікіпедії — вільної енциклопедії.

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

— не є простими,

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

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

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

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

Зміст [сховати] 1 Деякі факти про прості числа 1.1 Розкладання числа у добуток простих чисел 1.2 Нескінченність множини простих чисел 2 Застосування простих чисел 3 Дивіться також

[ред.] Деякі факти про прості числа

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

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

Доведення: Спочатку доведемо існування розкладу для будь-якого числа 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³⁰⁰) використовуються в криптографії з відкритим ключем. Прості числа також використовуються в хеш-таблицях і для генерації псевдовипадкових чисел.

[ред.] Дивіться також

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

Статті з математики, пов'язані з числами

Число | Натуральні числа | Цілі числа | Раціональні числа | Ірраціональні числа | Constructible numbers | Алгебраїчні числа | Computable numbers | Дійсні числа | Комплексні числа | Подвійні числа | Бікомплексні числа | Гіперкомплексні числа | Кватерніони | Октоніони | Седеніони | Superreal numbers | Hyperreal numbers | Surreal numbers | Nominal numbers | Ординальні числа | Кардинальні числа | p-adic numbers | Послідовності натуральних чисел | Математичні константи | Великі числа | Нескінченність