Просто о простых числах

9

ПРОСТО О ПРОСТЫХ ЧИСЛАХ

Кандидат физико-математических наук
Г. А. ГАЛЫПЕРИН

Бесконечность множества простых чисел

Все знают, что большинство натуральных чисел раскладывают на множители: 10=2·5, 60=3·4·5, 111=3·37, 144=3·3·2·2·2·2 и так далее. Такие числа называются составными. Но среди натуральных чисел есть и такие, которые подобным образом на множители на раскладываются: например, 11 нельзя представить в виде произведения двух меньших натуральных чисел, оба из которых больше 1. Поэтому 11 называется простым числом. Вообще, простыми числами (или «первоначальными» — по выражению древних греков) называются такие натуральные числа, которые нельзя разложить на два сомножителя, больших 1 (сamy единицу не относит к простым числам). Вот несколько первых простых чисел: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,…. Среди нихровно одно четное — 2, остальные числа нечетные.

Задание 1. Найдите все пары простых чисел, отличающихся: a) на 1, 6) на 17.

С первого же взгляда видно, что ряд простых чисел несколько причудлив; никакого простого закона в его строении не обнаруживается.

Имеет ли этот ряд конец? Этот вопрос поставлен в IX книге «Начал» Евклида и там же дается ответ на него: за каждым простым числом может быть указано еще одно, большое простое число — ряд простых чисел бесконечен.

Доказательство этого утверждения, данное Евклидом, необсячайно остроумно. Евклид рассуждает так: если простых чисел лишь конечное число и p — наиболее из них, то число N=2·3·5…·p+1, поскольку оно больше p, — не простое, а поэтому делится на какое-то простое число из имеющихся простых от 2 до p (ведь других простых чисел, по предположению, нет!). Однако N не делится ни на одно из этих чисел, так как остаток от деления N на любое из них равен 1. Полученное противоречие доказывается, что простых чисел не конечное количество, а бесконечное.

Это доказательство «методом от противного» говорит о существовании скольго угдоно больших простых чисел, но не говорит, как явно найти хотя бы одно простое число, большое p. Впрочем, это сделать не сложно: для этого достаточно проверить на простоту натуральные числа на отрезке от p+1 до N — среди них обязательно есть простое. Действительно, если само N не простое, то оно делится на простое число, притом (как мы видели) больше p, но меньше N, т. е. расположенное на отрезке [p; N].

Отрезки с простыми числами

Разбение числовой прямой на отрезки, в каждом из которых содержится простое число, можно произвольить и по другому. Доказем предварительно следующее утверждение: наименший делитель числа N=n!+1 (где n!=1·2·3…·n) является простым числом, большим n.

Обозначим этот наименший делитель числа p. Так как n!+1 не делится ни на одно из чисел 2, 3, 4, …, n, получаем p>n. С другой стороны, если предположить, что p — составное число, т. е. p делится на неокторе число, меньше p, то p не будет наименшим делителем n!+1, что противоречит предположению. Итак, p — простое число, большое n, что и требовалось доказать.

Из этого доказательства вытекает, что на любом отрезке [n; n!+1] находится хотя бы одно простое число. А тогда числа 2, 2!+1, (2!+1)!+1,

10

((2!+1)!+1)!+1 и т. д. разбиают всю числовую пряму на беконечное число отрезков, в каждом из которых содержится не менее одного простого числа; мы вновь доказали, что простых чисел беконечного много.

Оказывается, что уже в каждом из отрезков [2; 4], [4; 8], [8; 16], [16; 32], … содержится не менее одного простого числа. Но это — трудная теорема, известная под названием «поступат Бертрана»*), которая звучит так: между числами n и 2n−2 при n>7 всегда расположено простое число. Поступат Бертрана доказал в 1852 г. известный русский математик Пафнуть Львович Чебышев (1821—1894 гг.).

Задача 2. Докажите, что если (p−1)!+1 делится на p, то p — простое число. Указание. Использовите доказательство утверждения.

Задача 3. Докажите, используя простотат Бертрана, что для любого натурального n существует по крайней мере: a) одно простое n-значное число; b) 3 простых n-значных числа. Указание. Числа 10^{n−1}, 2·10^{n−1}, 4·10^{n−1} и 8·10^{n−1} — n-значные.

Заметьте, что доказательство Евклида дает во все не ближайшее следующее за p простое число, а лишь неокоторое число, лежащое обычно весма далего от p. Например, в качестве простого числа, заведomo превышающего 11, доказательство дает не 13, а 2311; за 13 оно дает не 17, а 59 — простой делитель числа 30 031.

Отрезки без простых чисел

Чтобы дать конкретное представление о сложности структуры множества простых чисел покажем, что в ряде

*) М. И. Baшмаков. Поступат Бертрана. «Квант», 1971, № 5, с. 4.

Арифметические прогрессии и простые числа

Рассмотрим все натуральные числа, дающие при делении на 3 остаток 2: 2, 5, 8, 11, 14, …; общий вид таких чисел 3n+2. Докажем, что и среди всех беконечного много простых чисел. Для этого придетя несколько видно изменить доказательство Евклида,

Таблица 1. Фрагмент распределения простых чисел.

В таблице показано, как меняется число простых чисел на интервале от 8 900 000 до 9 000 000, разбитом на 1000 сотен. В каждом столбце таблицы нижнее число указывает количество тех сотен расматриваемого интервала, в которых число простых чисел равно соответствующему верхнему числу столбца. Например, в одной сотне вообще нет простых чисел, в 117 сотных встречается по 4 простых чисел, в 130 сотных — по 8 простых чисел.

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— |
| 1 | 4 | 13 | 53 | 117 | 177 | 196 | 175 | 130 | 72 | 47 | 11 | 4 |

10

11

Таблица 2. Частота распределения простых чисел в натуральном ряде.

$A_n$ — количество простых чисел среди первых $n$ натуральных чисел. Отношение $A_n/n$ тем больше к 1/ln $n$, чем больше $n$ (частое $A_n/n:1/\ln n$ практические не отличаться от 1 при $n=10^9$).

а именно, вместо числа $N=2\cdot 3 \times 5 \dots p+1$ рассматривается число $M=2\cdot 3\cdot 5 \dots p-1$, которое, будучи на 1 меньше кратного 3, принимает к последовательности 2, 5, 8, 11, 14, …, $3n+2$, …

Задание 4. Приведите полное доказательство того, что $M$ имеет вид $3n+2$.

Число $M$, так же как и $N$, не делится ни на одно из простых чисел 2, 3, 5, …, $p$. Является ли $M$ простым или же раскладывается на несколько простых множителей — в общих случаях эти простые числа будут больше $p$. Но имеет ли среди полученных множителей такой, который имеет бы вид $3n+2$, т. е. содержался бы в последовательности 2, 5, 8, 11, …? Допустим, что нет, т. е. предположим, что все простые множители $M$ имеют вид $3k+1$. Но тогда и их произведение имеет вид $3k+1$ (см. задачу 5, а), а это противоречит тому, что $M$ имеет вид $3n+2$ (см. задачу 4). Следовательно, наше допущение неверно, и хотя бы один простый множитель числа $M$ имеет вид $3k+2$. Поэтому простых чисел вида $3k+2$ бесконечного много.

Задание 5. а) Докажите, что произведение любого количества чисел вида $3k+1$ также имеет вид $3k+1$. б) Докажите аналогично утверждение для чисел вида $4k+1$, в) для чисел вида $6k+1$.

Приведенное рассуджение (с небольшим видом изменением) дает инструмент для доказательства бесконечности множества простых чисел вида $4k+3$ и $6k+5$. Предварительно предполагаем читательм подумать над следующей задачей.

Задание 6. Докажите, что любое простое число, больше 3, имеет: а) вид $4k+1$ или вид $4k+3$; б) вид $6k+1$ или вид $6k+5$.

Здесь мы доказем только бесконечность множества простых чисел вида $6k+5$. Доказательство проведем «от противного» в двух, присущем первоначальную доказательству Евклида. Предположим, что простых чисел этого вида лишь конечное число: $p_1, p_2, \dots, p_n$. Расмотрим число $K=$ $6p_1p_2\dots p_n-1 = 6(p_1p_2\dots p_n-1)+5$. Однако из двух: либо число $K$ само простое, либо оно разлагается на конечное число простых множителей, среди которых нет ни одного из чисел $p_1, p_2, \dots, p_n$ (почему?), и не все из которых имеют вид $6k+1$, поскольку само $k$ не имеет этого вида (см. задачу 5, в). Значит, один из простых множителей числа $k$, не совпадает с $p_1, p_2, \dots, p_n$, имеет вид $6k+5$, что противоречит сделанному нами предположению. Это противоречие показывает, что список простых чисел вида $6k+5$ бесконечен.

Задание 7. Проведите доказательство бесконечности множества простых чисел вида $6k+5$, указав явный способ для нахождения этих чисел.

Задание 8. Проведите подробное доказательство бесконечности множества простых чисел вида $4k+3$. Указаниее. Учетверите произведение чисел этого вида и вычитите из произведения 1.

Задание 9. Докажите, что простых чисел, не оказывающих их на 1 (т. е. оканичивающих на 3, на 7 и на 9), бесконечного много. Указаниее. Расмотрите все простые числа вида $10k+a$, где $a \neq 1$, и проведите рассудения, аналогичные изложенным выше.

Обобщением рассмотренных вопросов является следующее теорема, формулированная в 1788 г. французским математиком Лежандром и доказанная немецким математиком Дирихле в 1837 г.

Теорема. В любой бесконечной арифметической прогрессии $a_1, a+d, a+2d, a+3d$, в котором первый член а взаимно прост с разностью $d$, содержится бесконечного много простых чисел. Иными словами, функция $y=dx+a$, где $d$ и $a$ — взаимно простые числа, принимает бесконечного много простых значений, когда $x$ пробезет последовательную ряду натуральных чисел.

Доказательство Дирихле не элементарно, и в течение долгих лет не было видно никаких элементов подховов к доказательству этой замечательной теоремы. Элементарное доказательство было впервые получено в 1949 г. (через 161 год после Ле-

12

Жандра!) видным датским математиком А. Сельбергом, доказавшим многочне очень трудные теоремы теории чисел элементарно, без использования высшей математики.

Близнецы

Вспомним первую задачу, сформулированную в самом начале статьи. Как вы, наверное, доказались, если два простых числа отличаются на нечетное число $p$ (на 1 или 17, как в задаче 1), то одно из этих простых чисел четно, и стало бы равно 2. Позатому другое простое число $q$ отличается от $p$ на 2. Если к тому же и $p$ — простое число (как $p=17$ в задаче 1), то простые числа $p$ и $q$ называются числами-близнецами; в задаче 1 это числа 17 и 19.

Задание 10. Докажите, используя теорему Дирихле, что существует бесконечно много простых чисел, не принадлежих ни к одной паре простых чисел близнецов. Указаны е. Все эти простые числа следует быть, например, из арифметической прогрессии $\{15k+7\}$.

Возникает вопрос: сколько существует пар чисел-близнецов? Например, на отрезке от 0 до 100 000 таких пар 1225, а в интервале от 8 000 000 до 8 100 000 их всего 518. Прекратная ли когда-нибудь такие пары в бесконечно далеко простиращемся ряде простых чисел? Ни на этот, ни на более общий вопрос, поставленный в великам немецким математиком Давидом Гильбертом на 2-м Международном конгрессе математиков в Па-

Риже в 1900 г., — всегда ли разрешимо в простых числах $x$ и $y$ линейное уравнение $ax+by=c$ с целыми коэффициентами $a, b, c$, где $a$ и $b$ взаимно просты? — ответа до сих пор не получено.

Основная теорема арифметики

Любое натуральное число больше единцы допускает одно и только одно (с точностью до порядка множителей) разложение на простые множители.

Докажательство. Если существует хотя бы одно число, допускающее два разложения на различные простые множители, то существует непреемно и наименьшее число $N$, обладающее этим свойством:

$$N = p_1 p_2 \dots p_n = q_1 q_2 \dots q_m,$$

где через $p$ и $q$ обозначает простые числа. Меняя, если потребуется, порядок этих множителей, мы можем допустить, что $p_1 \leq p_2 \leq \dots \leq p_n, q_1 \leq q_2 \leq \dots \leq q_m$. Заметим, что $p_1 \neq q_1$, так как в случае $p_1 = q_1$ натуральное число $N/p_1 = N/q_1$, меньше $N$, имею бы два разных разложения на простые множители, что противоречит предположению о минимальной $N$. Предположим, что $p_1 < q_1$, и рассмотрим число $N' = N - p_1 q_2 \dots q_m$. Легко видеть, что число $N' = p_1(p_2 p_3 \dots p_n - q_1 q_2 q_3 \dots q_m) = (q_1 - p_1)q_2 q_3 \dots q_m$ положительное и меньше $N$. Значит, по нашему предположению, $N'$ имея

13

ет единственное разложение на простые множители. Но как как простое число $p_1$ входит в разложение $N'$, то $p_1$ входит в $q_1 - p_1$ или в $q_2 q_3 \dots q_m$. Из неравенств $p_1 < q_1 \leqslant q_2 \leqslant \dots \leqslant q_m$ следует, что $p_1$ не входит множителем в $q_2 q_3 \dots q_m$. Поэтому $p_1$ входит множителем в $q_1 - p_1$, т. е. $q_1 - p_1$ делится на $p_1$. А тогда и $q_1$ делится на простое число $p_1$. Этого, однako, быть не может, так как $q_1$ — число простое. Противоречие, к которой мы пришли, показывает неосостояльность первого начального допущения, чем и заканчивается доказательство.

Заметание. Из доказательства основной теоремы арифметики становится понятным, почему edиницу не относит к простым числам. Если ее включить в число простых, то любое натуральное число начинает разлагаться на простые множители многими способами, поскольку в разложение можно добавлять произвольное число единиц.

Bot одно важное следствие основной теоремы арифметики: если простое число $p$ входит множителем в произведение $ab$, то оно входит множителем или в $a$, или в $b$. Действительно, если $p$ не входило множители ни в $a$, ни в $b$, то, переменная разложения на простые множители чисел $a$ и $b$, получили бы разложение на простые множители числа $ab$, не содержащие множителя $p$. С другой стороны, справедливо равенство $ab = pt$, где $t$ — некоторое натуральное число. Поэтому, переменная $p$ и разложение на простые множители числа $t$, получаем разложение числа $ab$ на простые множители, уже содержащие множитель $p$. Таким образом, получаются два разложения $ab$ на различные простые множители, что противоречит основной теореме.

Из основной теоремы вытекает, что число $N$ представляется в виде
$$N = p_1^{k_1} p_2^{k_2} \dots p_s^{k_s},$$ где $k_1, \dots, k_s$ — количество различных простых делителей $p_1, \dots, p_s$ соответствующего в разложении $N$. Все делители $N$ имеют вид $a = p_1^{r_1} p_2^{r_2} \dots p_s^{r_s}$, где $0 \leqslant r_1 \leqslant k_1$, $0 \leqslant r_2 \leqslant k_2$, $0 \leqslant r_s \leqslant k_s$.

Еще раз о бесконечности простых чисел
Единостьность разложения на множители позволяет дать новое доказательство бесконечности простых чисел. Это доказательство принадлежит Леонарду Эйлеру.

Предположим, что 2, 3, 5, …, $p$ — все существующие простые числа. Тогда из формулы для суммы геометрической прогрессии со значенателем, меньше 1, следует, что для любого натурального $n$ $1 + \frac{1}{2} + \frac{1}{2^2} + \dots + \frac{1}{2^n} < \frac{1}{1 - \frac{1}{3}}, \dots, 1 + \frac{1}{p} + \frac{1}{p^2} + \dots + \frac{1}{p^n} < \frac{1}{1 - \frac{1}{p}}$.

Переменная эти неравенства почилен:
$$\left(1 + \frac{1}{2} + \dots + \frac{1}{2^n}\right)\left(1 + \frac{1}{3} + \dots + \frac{1}{3^n}\right) \dots \dots \left(1 + \frac{1}{p} + \dots + \frac{1}{p^n}\right) < \frac{1}{\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right)\dots\left(1 - \frac{1}{p}\right)}$$.

Справа стоит выполне конкретиное число; обозначим его $A$. Произведение слева после раскрытия всех скобок превращается в сумму $S$ чисел, обратных всем делителем числа $N = 2^n 3^n 5^n \dots p^n$ (в этом месте и используется основная теорема арифметики — убедитесь!). Поэтому левая часть неравенства большие суммы $A_n = 1 + 1/2 + 1/3 + 1/4 + 1/5 + \dots + 1/2^n$, в котором входит лишь часть слагаемых суммы $S$. Итак, для любого $n$ $A_n < A$. Но $A_n = 1 + 1/2 + (1/3 + 1/4) + (1/5 + 1/6 + 1/7 + +1/8) + \dots + (1/(2^n - 1) + 1) + \dots + (1/2^n) > 1 + 1/2 + 2 \cdot 1/4 + 4 \cdot 1/8 + \dots + 2^{n-1} \cdot 1/2^n = 1 + n/2$, что сразу приводит к противоречению: $A > 1 + n/2$ при всех $n$. Стало бы, простые числа не могут ограничивать никаким конечным списком, что и требовалось доказать.

Проверка простоты

При разложении $N$ на множители или проверке его на простоту следует проверять делимость $N$ на последовательные простые числа 2, 3, 5, 7, …. При проверке числа $N$ на простоту достаточно ограничиться простых делителей, не превысodiaщих $\sqrt{N}$. Действительно, если $N = ab$, то меньше из чисел $a, b$ не больше $\sqrt{N}$ (если оба были бы больше $\sqrt{N}$, то их произведение было бы больше $N$), и из делимости $N$ на $a$ автоматически следует, что $N$ делится и на $N/a$ (так что делимость на $N/a$ проверять уже не нужно). Первые математические икации (Леонардо Пизанский).

Примеры. а) Если $N = 91$, то $\sqrt{91} < 10$; проверив простые числа 2, 3, 5, 7, находим, что $91 = 7 \cdot 13$.

14

6. Если $N=1987$, то $\sqrt{N}<45$, …, и так как $N$ не делится ни на одно из простых чисел до 43, то 1987 — простое.

В некоторых случаях при определении простых числа $N$ можно не производить указанных делений на простые числа. Следующие несложное утверждение, сформулированное Эйлером еще в XVIII века, позволяет определить простую числа $N$ совсем другим способом.

Первый критерий Эйлера. Если нечетное число $N>1$ может быть представлено в виде разности квадратов двух натуральных чисел более чем одним способом, то $N$ — составное; если же такой способ только один, то $N$ — простое.

Доказательство. Считаем $N$ не точным квадратом, поскольку точный квадрат всегда составное число. Пусть $N=m^2-n^2=(m-n)(m+n)$. Отсюда следует, что $m-n$ и $m+n$ — делители $N$. Если $N$ простое, то $m-n=1$, $m+n=N$ и числа $m=(N+1)/2$, $n=(N-1)/2$ определяются числом $N$ однозначно, а поэтому $N$ не может быть представлено еще и другим способом в виде разности двух квадратов.

Если же $N$ составное, т. е. $N=ab$, причем $a>b>1$ — нечетные числа, то, взяв $x=(a+b)/2$ и $y=(a-b)/2$, получаем: $a=x+y$, $b=x-y$, откуда $N=ab=x^2-y^2$: получено еще одно представление $N$ в виде разности квадратов.

Отсюда вытекает, что если $N$ представляется более чем одним способом в виде разности квадратов, то $N$ не может быть простым: для простого $N$ такое представление единственного. Если же $N$ представляется всего один способом в виде разности квадратов, то $N$ не может быть составным (по доказанному выше), стало бы, оно простое. Критерий установлен.

Этот критерий дает возможность вместе испытания делителей $N$ пользоваться таблицей квадратов, и, прибавляя последовательно к $N$ квадраты $n^2$ целых чисел, проверять, получается ли в сумме при $n<(N-1)/2$ точный квадрат или нет.

Разложим, например, 3551 на множители этим способом. Добавляя к 3551 последовательно числа $1^2$, $2^2$, $3^2$, …, проверяем каждый раз, является ли полученная сумма точным квадратом. Проверка (с помощью таблицы квадратов) показывает, что $3551+7^2=60^2$. Значит, $3551=60^2-7^2=53\cdot67$.

Задание 11. Разложите указанным способом на множители числа 6557, 19019, 209209.

Несложно также доказывается.

Второй критерий Эйлера. Если натуральное число может быть представлено в виде суммы двух квадратов натуральных чисел более чем одним способом (считается, что перестановка сладаетых не дает нового способа), то $N$ — составное число.

Из второго критерия Эйлера следует, что если простое число представляется в виде суммы двух квадратов натуральных чисел, то только один способом. Но какие простые числа представляются в таком виде?

Задание 12. Докажите, что числа вида $4k+3$ не могут быть представлены в виде суммы двух квадратов. Указание. Квадрат четного числа делится на 4, а квадрат нечетного дает в остатке 1.

Претendentами остаются простые числа вида $4k+1$, и, как доказал Пьер Ферма, все такие числа представляются в виде суммы двух квадратов. Поэтому нетрудно ответить, например, на такой вопрос: какие из трех простых чисел 1973, 1979 и 1987 представны в виде суммы двух квадратов?

Задание 13. а) Докажите, что при всех натуральных $n$ число $N=n^4+4$ — составное (теорема Софи Жермен). 6) Докажите, что при всех натуральных $m$ и $n$ число $N=n^4+4m^4$ составное. Указание. $N=(n^2-2m^2)^2+(2mn)^2$; примените второй критерий Эйлера.

Многочлены, выдающие простые числа

С простыми числами все было бы простое, если бы существовала общая формула для их нахождения. Попытки конструкировать такой формулу were made, из которых только простые значения. Но уже при $n=40$ его значение равно $41^2$. Несложно доказать, что никакой многочлен от одной переменной не может принимать только простые значения.

Совсем недавно был найден многочлен, все положительные значения

(Окончание см. на с. 38)