Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/1998/04/08.pdf Дата изменения: Fri Dec 23 19:24:40 2005 Дата индексирования: Tue Oct 2 00:09:23 2012 Кодировка: Windows-1251 Поисковые слова: п п п п п п п п п п п п п п п п п п п п п

8
иметь разложение на простые сомножители и, значит, должно делиться на некоторое простое число. Мы приходим к противоречию с предположением о конечности множества простых чисел, что и требовалось доказать. С простыми числами связано много задач, формулировка которых очень проста, но решение до сих пор не найдено. Например, неизвестно, конечно или бесконечно число простых чисел вида 2 1 или вида n + 1. Также до сих пор не доказано и не опровергнуто предположение Эйлера о том, что любое четное число, больше двух, можно представить в виде суммы двух простых чисел. В последовательности натуральных чисел встречаются пары простых, отличающиеся на двойку, например 3 и 5; 17 и 19; 59 и 61 и т.д. Предполагают, что таких пар 'простых близнецов' бесконечно много, однако до настоящего времени доказать это не удалось, несмотря на усилия многих очень сильных математиков. Вместе с тем, легко построить примеры сколь угодно длинных промежутков из последовательных натуральных чисел, не содержащих простых чисел; например, очевидно, все числа N + 2, N + 3, ..., N + 1000, где N = 2 3 K 1000 составные (так как они делятся соответственно на 2, 3, ..., 1000). Французскому математику Жозефу Луи Франсуа Бертрану при исследовании некоторых вопросов из высшей алгебры пришлось воспользоваться одним интересным свойством простых чисел. Бертран не смог доказать это утверждение и принял его в качестве постулата. Постулат Бертрана. Между n и 2n обязательно найдется простое число р, каково бы ни было натуральное n. Доказать постулат Бертрана удалось выдающемуся русскому математику Пафнутию Львовичу Чебышеву. Мы приведем упрощенный вариант доказательства Чебышева, в котором применяется его замечательное тождество о связи между произведением наименьших общих кратных и факториалом числа. Для понимания доказательства постулата Бертрана требуется лишь умение проводить несложные преобразования с алгебраическими выражениями и неравенствами. Задачи,
n 2

КВАНТ

1998

/?

4
жение 1000! в степени

приведенные в конце статьи, помогут получить более полное представление о методе Чебышева. Список литературы адресован тем, кто захочет более глубоко изучить методы элементарной теории простых чисел. Начнем с определения двух важных понятий арифметики канонического разложения натурального числа и показателя простого числа в каноническом разложении. Если в разложении натурального числа n на простые сомножители записать произведение одинаковых простых сомножителей р в виде p , то получится каноническое разложение числа n:

1000 5 + 1000 25 +
+ 1000 125 + 1000 625 = 249 , т.е. 1000! в десятичной записи оканчивается 249 нулями. Перейдем к доказательству постулата Бертрана. Обозначим через А(х) наименьшее общее кратное всех натуральных чисел, не превосходящих х:

A x = НОК 1, 2, 3, K, x .
Легко понять, что каждое простое р входит в разложение А(х) на простые сомножители в степени kp , где kp максимальное целое число, удовлетkp воряющее неравенству p x , т.е. kp равно числу решений неравенства k p x в натуральных k. Найдем теперь показатель ap x , с которым простое р входит в произведение

bg

c

h

n = p1 1 K ps s ,
где все простые p1 , ..., p s различны 3 2 (например, 360 = 2 3 5 ). Будем говорить, что простое число р входит в разложение n с показателем k , если р = pk . Если же n не делится на простое число р, то будем считать, что показатель равен нулю. Прежде чем доказывать постулат Бертрана, решим следующую задачу: Найти показатель p x , с которым простое р входит в разложение на простые сомножители произведения всех натуральных чисел, не превосходящих некоторого числа x 1. Наибольшее целое число, не превосходящее х, принято записывать в виде [x] (читается: 'целая часть х'). Произведение всех натуральных чисел от 1 до n обозначают символом n! (читается: 'n факториал'). Заметим, что показатель простого числа р в произведении





bg

bg

числу решеp k ний неравенства p x n в натуральных n и k. При каждом фиксироk решений ванном k имеется x p этого неравенства, следовательно,

bg b g b g Очевидно, a b xg равно bg

A x A x 2 A x 3 K A x x .

c

h

ap x = x p + x p

2

+
3

+xp

+ K = p x ,

bg
h

т.е. разложение на простые сомножители произведения

A x A x 2 A x 3 K A x x

bg b g b g

c

x ! = 1 2 3 K x

зависит только от тех сомножителей, которые делятся на р, т.е. равен показателю р в произведении
p 2p K x p p = p

совпадает с разложением на простые сомножители [x]!. Тем самым доказано Тождество Чебышева.3 При любом x 1

bg

xp

xp!

A x A x 2 A x 3 K

bg b g b g

Следовательно,

K A x x = x ! .
Основная идея доказательства постулата Бертрана состоит в том, что достаточно проверить справедливость неравенства

p x = x p + p x p =
= xp+xp
2

bg

bg

c

h

+ p x p
2

e

2

j

=
3

=xp + x p

+ x p +... ,
k

Ax Ax2 >A

bg b g

2

e xj

. ( )

где слагаемые вида x p добавляk ются, пока x p . Например, число 5 входит в разло-

3 Чебышев применял это тождество в равносильной форме, получающейся логарифмированием приведенного выражения.