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

МАТЕМАТИЧЕСКИЙ

КРУЖОК

45

Теорема 2. Если р простое число, то максимальная n степень р, делящая Cm + n , равна количеству переносов при сложении чисел m и n в р-ичной системе счисления. Вот до какой теоремы мы добрели! Что бы извлечь из такого неочевидного факта? Глаза разбегаются. Ну давайте, n простоты ради, начнем с изучения C2 n самого большого биномиального коэффициента среди всех, входящих в раз2n ложение бинома ( x + y ) . (Кстати, а можете ли вы доказать, что он и впрямь самый большой?) Максимальная степень p , на которую он делится, равна количеству переносов, получающихся при сложении n с самим собой в р-ичной системе счисления. Допустим, что n < р < 2n. Тогда п в р-ичной системе записывается одной р-ичной 'цифрой' (собственно n), а 2n двумя; скажем, 2n = r + 1 p . Это значит, что происходит ровно один перенос и, следоваn тельно, р входит в C2 n ровно один раз. Таким образом, произведение всех простых чисел, заключенных между п и n 2n, не превосходит C2n . Нельзя ли получить что-то попривn лекательнее? Оценим C2n грубо. Если положить в биноме Ньютона x = y = 1, то получится, что 1 2 2n n 1 + C2n + C2n + K + C2n + K + C2n -1 + 1 = 22 n , откуда n C2n < 4n . Точно таким же образом произведение всех простых чисел между n/2 и п меньше 4n 2 , между n/4 и n/2 меньше 4n 4 и т.д. Тогда произведение всех простых чисел между 1 и n меньше 4 n 2 4 n 4 4 n 8 K = 4n 2 + n 4 + n 8 +K < 4n. В итоге мы бесплатно получили совсем неочевидный факт: Теорема 3. Произведение всех простых чисел, меньших п, не превосходит 4 n .
Упражнение 3. Докажите это строго: мы слишком небрежно делили пополам, 'забыв', что бывают и нечетные числа. (Возможно, что лучший способ строгого подхода индукция.)

1) Простые числа, большие п (и, естественно, меньшие 2n), каждое по одному разу. 2) Простые числа, меньшие 2n/3, но большие 2n , каждое не более одного раза. 3) Простые числа, меньшие 2n . Тут возможна делимость на pk с k > l, но все равно полный вклад pk каждого такого простого числа не превосходит 2n. Интересно, а может ли быть так, что первая группа отсутствует, т.е. между n и 2n нет простых чисел? Тогда все сосредоточено во второй и третьей группах. Можем ли мы оценить их реальный вклад? Произведение всех чисел второй группы, по теореме 3, не превосходит 42n 3 . Простых чисел в третьей группе заведомо меньше чем 2n - 1 , так что 2 n -1 их общий вклад, по лемме 3, не превосходит (2n ) .В итоге: если между n и 2n нет простых чисел, то справедливо неравенство
n C2n < 42 n3

(2n

)

2 n -1

.

( )

Какая мысль! Ведь если мы докажем, что это неравенство ложно, то одновременно докажем знаменитый постулат Бертрана: между n и 2п всегда имеется хотя бы одно простое n число. Попробуем оценить C2n . Коль скоро это самый большой из биномиальных коэффициентов, входящих в 2n бином (1 + 1) , и так как их всего там 2n +1< 4n, то заведомо n 4 n . Из полученных неравенств следует, что C2n > 4n 2n 4n 2 n -1 , 4 n 3 < 2 (2n ) , < 4 2 n 3 (2 n ) 4n n 1 1 < 2n log 4 2n + , n < 18 log 4 2n + . 2 3 2 Но хорошо известно, что логарифм функция медленная, и n ее обгонит. Осталось понять, когда. Прикинем, что будет при n = 1000. Заведомо, 1000 > 30 , log4 2000 < log 4 4096 = 1 = log4 46 = 6 , т.е. 30 < 18 6 + , что неверно. Значит, при 2 n = 1000 и (как вы, надеемся, легко с помощью производной докажете) для n > 1000 неравенство ( ) ложное. Следовательно, для этих значений п справедлива Теорема Чебышева (постулат Бертрана). Между n и 2п всегда имеется хотя бы одно простое число. Хорошо, а что делать с маленьким n? Там же, вроде бы, неравенство верно. Ну и бог с ним постулат-то Бертрана тоже верен, и в этом легко убедиться, попросту просмотрев таблицу простых чисел или написав махонькую программку. Если хотите, можно и иначе проявив больше щепетильности к оценкам, получить более точное неравенство (см., например, книгу В.Серпинского '250 задач по элементарной теории чисел'). Это уж дело вкуса. Но, пожалуй, наша прогулка затянулась. Пора и отдохнуть, а если вы еще захотите прогуляться для затравки несколько задачек.
1. Докажите, что для простого р и любых целых х, у число p x + y ) - x p - yp делится на р. 2. Обобщите предыдущую задачу на случай нескольких слагаемых и выведите отсюда малую теорему Ферма: x p - x делится на р. 3. Докажите, что если N = pm , где р простое, делит биномиальi ный коэффициент Cn , то N n . 4. Докажите, что есть два простых числа между n и 2n для n > 5.

Пусть теперь p n . Тогда в разложении п по крайней мере две р-ичные цифры. Если в разложении 2n их ровно две, то 2n < p 2 , и заведомо происходит не более одного переноса. Следовательно, верна Лемма 1. Если p > 2n , то максимальная степень р, n делящая C2n , не превосходит 1. Интересно, а когда делимости нет вообще? Так как 2n < p 2 , то n = a0 + a1p , где a0 < p , a1 < p 2 . Чтобы не было переносов, должно быть a0 < p 2 . В частности, при a1 = 1 получаем, что если a0 = n - p < p 2 , то р не является делителем n C2n . Отсюда следует Лемма 2. Если n p > 2n 3 , то р не является делителем n C2n (п > 2). Доказательство: n < р + р/2 = 3р/2, откуда р > 2n/3. Прикинем теперь, что происходит при малых значениях p 2n . Там переносов уже может быть несколько, но во всяком случае не больше чем k, если 2n = a0 + a1p + a2 p2 + K K + ak pk . Так как 2n p k , то log p 2n k , и мы можем n сказать, что максимальная степень р, делящая C2n , не превосходит log p 2n . Значит, для произвольного р справедлива n Лемма 3. Пусть N = pm является делителем C2n . Тогда N 2n . log 2n Доказательство: pm p p = 2n. Ну вот, теперь мы более или менее представляем структуру n числа C2n . Его разложение на степени простых чисел состоит из трех типов сомножителей:

(

5. Докажите, что если pk есть k-e по счету простое число, то pk + 2 < 2 pk . 6. Докажите, что n! не является степенью никакого числа при любом n > 1.