Просте число

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

Зміст

1 Загальні відомості
2 Деякі факти про прості числа
- 2.1 Розкладання в числа добуток простих чисел
- 2.2 Нескінченна кількість простих чисел

[ред.] Загальні відомості

Просте число - натуральне_число p називається простим, якщо воно має рівно два дільники - 1 і само число p. Наприклад, числа 1, 4, 36 - не є простими, а 2, 3, 11 - прості. Найменшими простими числами є 2, 3, 5, 7, 11, 13, 17, 19, ... (дивись список простих чисел)

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

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

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

Спочатку доведемо існування розкладу для будь-якого числа 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, що протирічить нашому припущенню. Отже, існує нескінченно багато простих чисел.