Простое число

Простое число — целое число, большее 1, которое нельзя разложить в произведение меньших сомножителей, называется простым. Примеры простых чисел:

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

Числа, для которых такое разложение существует называются составными.

Понятие простого числа является основным при изучении делимости натуральных (то есть целых положительных) чисел. Так, основная теорема элементарной теории чисел утверждает, что всякое натуральное число, отличное от 1, может быть представлено в виде произведения простых чисел, причём такое представление единственно с точностью до порядка сомножителей. Таким образом, простые числа играют роль своеобразных «кирпичиков», из которых строятся все остальные натуральные числа.

Ещё в III в. до н. э. Евклид доказал бесконечность множества простых чисел, а несколько позднее Эратосфен нашёл способ выделения простых чисел из множества натуральных чисел (так называемое «решето Эратосфена»).

Л. Эйлер нашёл доказательство бесконечности множества простых чисел, основанное на использовании средств математического анализа. Дальнейшее развитие аналитического метода Эйлера оказалось очень плодотворным и легло в основу современных аналитических методов исследования проблем распределения простых чисел.

В 1837 г. П.Г.Л. Дирихле доказал, что в любой прогрессии вида dn+b, n=0, 1, 2,…, где разность прогрессии d и её первый член b взаимно просты (то есть не имеют общих натуральных делителей, отличных от 1), содержится бесконечно много простых чисел.

Один из основных вопросов теории распределения простых чисел связан с изучением скорости роста функции π(x), равной количеству простых чисел, не превосходящих числа x. Теорема Евклида утверждает, что эта функция стремится к бесконечности при неограниченном возрастании x, однако ничего не говорит о скорости стремления.

Первый существенный результат в этом направлении принадлежит П.Л. Чебышеву, которому удалось показать, что для некоторых положительных постоянных a<1 и b>1 при всех x≥2 справедливы неравенства

ax/lnx<π(x)<bx/lnx.

Развивая идеи Эйлера, Г.Ф.Б. Риман предложил новый подход к изучению распределения простых чисел, который привёл к полученному в 1896 г. независимо Ш.Ж. де Ла Валле Пуссеном и Ж. Адамаром доказательству так называемого асимптотического закона распределения простых чисел, который утверждает, что отношение π(x) к x/lnx стремится к 1 при стремлении x к бесконечности.

Существует глубокая связь простых чисел не только с мультипликативной, но и с аддитивной структурой натуральных чисел. Так, в переписке X. Гольдбаха с Л. Эйлером были поставлены две знаменитые проблемы: всякое нечётное число, большее 5, есть сумма трёх простых (тернарная проблема Гольдбаха), а чётное, большее 2, — сумма двух простых (бинарная проблема Гольдбаха). Первая проблема была по сути решена в 1937 г. И.М. Виноградовым, показавшим, что всякое достаточно большое нечётное число является суммой трёх простых; вторая проблема не решена до сих пор.

Существует много других нерешённых проблем, связанных с простыми числами. Таковыми являются, например, вопросы о бесконечности множества простых чисел вида p=2^n-1 (числа Мерсенна) или p=2^{2^n}+1 (числа Ферма), простых чисел-близнецов (простых чисел p и q таких, что p-q=2).