Прості числа

Всі натуральні числа, крім одиниці поділяються на прості і складові. Просте число – це натуральне число, яке має тільки два дільника: одиницю й саме себе. Всі інші називаються складовими. Дослідженням властивостей простих чисел займається спеціальний розділ математики – теорія чисел. В теорії кілець прості числа співвідносять з непріводімимі елементами.

Наведемо послідовність простих чисел починаючи з 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, … і т.д.

Згідно з основною теоремою арифметики кожне натуральне число, яке більше одиниці можна представити у вигляді добутку простих чисел. Разом з тим це є єдиним способом подання натуральних чисел з точністю до порядку проходження сомножителей. Виходячи з цього, можна сказати, що прості числа – це елементарні частини натуральних чисел.

Таке уявлення натурального числа називається розкладанням натурального числа на прості числа або факторизації числа.

Одним з найдавніших і ефективних способів обчислення простих чисел є «решето Ерастофен».

Практика показала, що після обчислення простих чисел за допомогою решета Ерастофен потрібно перевірити, чи є дане число простим. Для цього розроблені спеціальні тести, так звані тести простоти. Алгоритм цих тестів є ймовірними. Найчастіше їх застосовують в криптографії.

До речі сказати, що для деяких класів чисел існують спеціалізовані ефективні тести простоти. Наприклад, для перевірки чисел Мерсенна на простоту застосовують тест Люка-Лемера, а для перевірки на простоту чисел Ферма – тест Пепина.

Всі ми знаємо, що чисел нескінченно багато. Справедливо виникає питання: скільки ж тоді існує простих чисел? Простих чисел також нескінченну кількість. Найбільш древнім доказом цього судження є доказ Евкліда, яке викладено в «Засадах». Доказ Евкліда має наступний вигляд:

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

Теорема розподілу простих чисел стверджує, що кількість простих чисел менших n, позначається π (n), росте як n / ln (n).

За тисячі років дослідження простих чисел, було виявлено, що найбільшим відомим простим числом є 243112609 – 1. Це число включає 12 978 189 десяткових цифр і є простим числом Мерсенна (M43112609). Це відкриття було зроблено 23 серпня 2008 року на математичному факультеті університету uCLA в рамках проекту по розподілених пошуку простих чисел Мерсенна GIMPS.

Головною відмінною рисою чисел Мерсенна є наявність високо ефективного тесту простоти Люка – Лемера. З його допомогою прості числа Мерсенна протягом тривалого періоду часу є найбільшими з відомих простих чисел.

Однак донині багато питань щодо простих чисел не отримали точних відповідей. На 5-му Міжнародному математичному конгресі Едмунд Ландау сформулював основним проблеми в області простих чисел:

Проблема Гольдбаха або перша проблема Ландау полягає в тому, що необхідно довести або спростувати, що кожне парне число, більше двох, може бути представлено у вигляді суми двох простих чисел, а кожне непарне число, більше 5, може бути представлено у вигляді суми трьох простих чисел.
Друга проблема Ландау вимагає знайти відповідь на питання: нескінченно чи безліч «простих близнюків» – простих чисел, різниця між якими дорівнює 2?
Гіпотеза Лежандра або третя проблема Ландау така: чи вірно, що між n2 і (n + 1) 2 завжди знайдеться просте число?
Четверта проблема Ландау: нескінченно чи безліч простих чисел виду n2 + 1?
Крім перерахованих вище проблем існує проблема визначення нескінченної кількості простих чисел в багатьох цілочисельних послідовностях типу числа Фібоначчі, числа Ферма і т. Д.

Основний сферою докладання простих чисел є криптографія. Найбільшого поширення в цій області отримали прості числа порядку 10300. Крім цього прості числа використовуються в хеш-таблицях, а також для генерації псевдовипадкових чисел (зокрема, в ГПСЧ Вихор Мерсенна).

Посилання на основну публікацію