Просте число
Просте число - це натуральне число. має рівно два різних натуральних дільника. 1 і саме себе. Вивченням властивостей простих чисел займається теорія чисел.
1 не є ні простим числом, ні складеним числом.
Послідовність простих чисел починається з
Натуральне число, що має більше двох дільників, називається складовим. Таким чином, всі натуральні числа, за винятком одиниці, розбиваються на прості і складові.
Розкладання натуральних чисел на витвір простих [ред]
Основна теорема арифметики стверджує, що кожне натуральне число. більше одиниці (1), представимо у вигляді добутку простих чисел, причому єдиним способом (з точністю до порядку проходження сомножителей). Таким чином, прості числа - «елементарні будівельні блоки» натуральних чисел.
Подання натурального числа у вигляді добутку простих називається розкладанням на прості або факторизації числа. На даний момент невідомо поліноміальних алгоритмів факторизації чисел, хоча і не доведено, що таких алгоритмів не існує. (Тут і далі мова йде про полиномиальной залежності часу роботи алгоритму від логарифма перевіряється числа, тобто від кількості його цифр). На алгоритмічної складності завдання факторизації базується криптосистема RSA.
Решето Ератосфена. решето Сундарама і решето Аткіна дають прості способи знаходження списку простих чисел до деякого значення.
Для деяких класів чисел існують спеціалізовані ефективні тести простоти. Наприклад, для перевірки на простоту чисел Мерсенна використовується тест Люка - Лемера.
Скільки існує простих чисел? [Ред]
Простих чисел нескінченно багато. Найстаріше відоме доказ цього факту було дано Евклідом в «Засадах» (книга IX, твердження 20). Його доказ може бути коротко відтворено так:
Уявімо, що кількість простих чисел звичайно. Перемножимо їх і додамо одиницю. Отримане число не ділиться ні на одне з кінцевого набору простих чисел, тому що залишок від ділення на будь-який з них дає одиницю. Значить, число має ділитися на деякий просте число, що не включене в цей набір.
Математики пропонували інші докази. Одне з них (наведене Ейлером) показує, що сума всіх чисел, зворотних до простих, розходиться.
Відома теорема про розподіл простих чисел стверджує, що кількість простих чисел менших \ (n \), що позначається \ (\ pi (n) \), росте як \ (n / \ ln (n) \).
Найбільше відоме просте [ред]
Числа Мерсенна вигідно відрізняються від інших наявністю ефективного тесту простоти. тесту Люка - Лемера. Завдяки йому прості числа Мерсенна давно утримують рекорд як найбільші відомі прості. За перебування простого числа з більш ніж 10 7 десяткових цифр EFF призначила [2] нагороду в 100000 доларів США.
Деякі властивості [ред]
- Якщо \ (p \) - просте, і \ (p \) ділить \ (a b \), то \ (p \) ділить \ (a \) або \ (b \). Доказ цього факту було дано Евклідом і відомо як лема Евкліда. Воно використовується в доведенні основної теореми арифметики.
- Кільце відрахувань \ (\ mathbb_n \) є полем тоді і тільки тоді, коли \ (n \) - просте.
- Характеристика кожного поля - це нуль або просте число.
- Якщо \ (p \) - просте, а \ (a \) - натуральне, то \ (a ^ p - a \) ділиться на \ (p \) (мала теорема Ферма).
- Якщо \ (G \) - кінцева група з \ (p ^ n \) елементів, то \ (G \) містить елемент порядку \ (p \).
- Якщо \ (G \) - кінцева група, і \ (p ^ n \) - максимальний ступінь \ (p \), яка ділить \ (| G | \), то \ (G \) має підгрупу порядку \ (p ^ n \), звану сіловской підгрупою. більш того, кількість сіловскіх підгруп одно \ (pk + 1 \) для деякого цілого \ (k \) (теореми Силова).
- Натуральне \ (p> 1 \) є простим тоді і тільки тоді, коли \ ((p - 1)! + 1 \) ділиться на \ (p \) (теорема Вільсона).
- Якщо \ (n> 1 \) - натуральне, то існує просте \ (p \), таке, що \ (n
- Ряд чисел, зворотних до простих, розходиться. Більш того, при \ (x \ to \ infty \)
Відкриті питання [ред]
До сих пір існує багато відкритих питань щодо простих чисел, найбільш відомі з яких були перераховані Ландау (Landau) на п'ятому математичному конгресі [3]:
- Проблема Гольдбаха (перша проблема Ландау) про те, що кожне парне число більше двох може бути представлено у вигляді суми двох простих чисел, а кожне непарне число більше 5 може бути представлено у вигляді суми трьох простих чисел.
- Друга проблема Ландау про нескінченність безлічі простих близнюків - простих чисел, різниця між якими дорівнює 2.
- Гіпотеза Лежандра (третя проблема Ландау) про те, що між \ (n ^ 2 \) і \ ((n + 1) ^ 2 \) завжди знайдеться просте число.
- Четверта проблема Ландау про нескінченність кількості простих виду \ (n ^ 2 + 1 \).
Відкритою проблемою є також існування нескінченної кількості простих чисел в багатьох цілочисельних послідовностях, включаючи числа Фібоначчі. число Ферма і т. д.