Простое число
Просто́е число́, натуральное (целое положительное) число , имеющее только 2 делителя – и :Числа, имеющие не менее трёх различных делителей, называются составными. Понятие простого числа является основным при изучении делимости натуральных чисел. Так, основная теорема элементарной теории чисел утверждает, что всякое натуральное число, отличное от единицы, либо простое, либо если оно составное, может быть представлено в виде произведения простых чисел. При этом такое представление единственно (с точностью до расположения сомножителей). Запись этого произведения в виде степеней одинаковых простых чисел, а самих простых чисел в порядке возрастания, даёт каноническое разложение натурального числа:
C помощью канонических разложений натуральных чисел находят наибольший общий делитель и наименьшее общее кратное этих чисел. С помощью канонического разложения натурального числа вычисляются значения теоретико-числовых функций , и , которые обозначают соответственно число делителей, сумму делителей числа и количество натуральных чисел , взаимно простых с [т. е. таких, что ]:
Существенной особенностью этих формул является их зависимость от арифметической структуры натурального аргумента .
Простые числа играют роль своеобразных «кирпичиков», из которых строятся все остальные натуральные числа. Ещё в 3 в. до н. э. Евклид доказал бесконечность множества простых чисел, а Эратосфен нашёл способ отсеивания простых чисел из множества натуральных чисел (см. Решето Эратосфена). Л. Эйлер нашёл доказательство бесконечности множества простых чисел, основанное на использовании средств математического анализа. Дальнейшее развитие аналитического метода Эйлера оказалось очень плодотворным. П. Л. Чебышёв открыл ряд новых законов, которым подчиняются простые числа. В частности, с помощью элементарных рассуждений, использующих каноническое разложение для числа , П. Л. Чебышёв нашёл неравенства, которым должно удовлетворять количество простых чисел :
где , – некоторые положительные константы. Наиболее глубокие закономерности, которым подчиняется поведение последовательности простых чисел, были получены путём углубления исходных идей П. Л. Чебышёва с помощью аналитических и, в ряде случаев, элементарных методов (см. Распределение простых чисел).
Простые числа связаны не только с мультипликативной, но и с аддитивной структурой натуральных чисел. Достаточно характерной в этом отношении является проблема Гольдбаха о разбиении натуральных чисел на сумму трёх простых чисел, решённая в 1937 г. И. М. Виноградовым (см. Аддитивная теория чисел). Изучение законов разложения простых чисел в алгебраических полях проливает свет на свойства обычных простых чисел. Например, рассматривая закон разложения простых чисел в поле гауссовых чисел, получают теорему Гаусса: тогда и только тогда, когда
Существует много пока ещё (на 2022) не решённых проблем, относящихся к простым числам. Например:
будет ли бесконечным множество простых чисел Мерсенна:
будет ли бесконечным множество простых чисел Ферма:
существует ли бесконечное множество простых чисел и «близнецов», т. е. таких, что .
Экспериментальные и эвристические соображения свидетельствуют в пользу положительного решения сформулированных выше проблем и других аналогичных задач.