Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2002/05/39.pdf Дата изменения: Fri Dec 23 19:27:04 2005 Дата индексирования: Tue Oct 2 00:13:54 2012 Кодировка: Windows-1251 Поисковые слова: ngc 4676

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

КРУЖОК

39
y A L B

Иногда прибегают к такой записи: йn й n щ йк n щъ к ъ + к 2 ъ + K + кк k лк p ыъ кл p ъы кл p имея в виду, что в написанной сумме с некоторого места, равны нулю.
Упражнения

щ ъ +K, ъ ъы все слагаемые, начиная

При x = k (k натуральное число) на отрезке KL лейp щ жат к kъ точек с целыми кл q ъы координатами. Таким образом, их общее количество равно сумме

16. а) При каких натуральных n число n! делится на 2n ? б) Существует ли такое k, что n! делится 2n-k при всех n? в) Пусть р > 2 простое число. Существует ли такое k, что n! делится на pn -k при всех n? 17. На какую степень двойки делится число (n + 1) (n + 2)K(2n) ? 18. Докажите, что (n !)! делится на (n !) n-1 ! . 19. На какую степень простого числа р делится число а) (2n) !! = 2 Ч 4 Ч K Ч (2n) ; б) (2n - 1) !! = 1 Ч 3 Ч 5 Ч K Ч (2n - 1) ?

й(q - 1) p щ й p щ й 2 pщ ъ, к ъ + к ъ +K+ к к ъ q кл q ъы кл q ъы л ы Рис. 5 что и доказывает равенство из условия задачи. Точно так же доказывается, что й к кл q p

K k

Cx

Подсчет количества целых точек Начнем с совсем простого вопроса. Сколько целых чисел содержится в интервале (; ) ? Ясно, что если целое число m удовлетворяет неравенствам < m < , то [ ] + 1 ? m <

< [] , но таких чисел имеется в точности [] - [] . Это так же легко понять, как и то, что между 1 и 10 мая ровно 8 дней. Аналогичный вопрос. Сколько чисел, кратных данному x > 0 (т.е. чисел вида nx, где n целое число), содержится в промежутке (; ) ? Ответ очевиден таких чисел ровно й щ йщ к ъ-к ъ. лк x ыъ лк x ыъ Теперь решим задачу. Задача 8. Докажите, что если x > 0 и n натуральное, то й [ x]щ й x щ к ъ =к ъ. к n ъ лк n ыъ лы Решение. Рассмотрим натуральные числа, меньшие х и йxщ делящиеся на n. Таких чисел ровно к ъ . Но те же самые кл n ъы числа образуют множество чисел, не превосходящих [ x] и делящихся на n. Отсюда и следует доказываемое равенство.
Упражнение 20. Найдите количество натуральных чисел, меньших х и делящихся на 2 или на 3.

й ( p - 1) q щ ( p - 1) (q - 1) щ й 2q щ ъ= . ъ + к ъ +K+ к к ъ 2 p ъы кл p ъы л ы Разберем еще один пример. Обозначим через (n) количество делителей натурального числа n, и решим такую задачу. Задача 10. Докажите, что йnщ й nщ й nщ (1) + ( 2 ) + K + (n) = к ъ + к ъ + K + к ъ . 1 ыъ лк 2 ыъ лк лк n ыъ
Решение. Количество чисел из множества 1, 2, ..., n, й nщ делящихся на некоторое число k, равно к ъ (это числа k, кл k ъы йnщ й nщ й nщ й nщ 2k, ..., к ъ k ). Сумма к ъ + к ъ + K + к ъ равна количеству лк k ыъ лк 1 ыъ лк 2 ыъ лк n ыъ чисел, делящихся на 1, плюс количество чисел, делящихся на 2, ..., плюс количество чисел, делящихся на n. Но ведь это и есть сумма (1) + (2) + (3) + K + (n ) . Этот результат тем более интересен, что количество делителей натурального n выражается через n весьма непросто. Пусть n = p1 1 K pk k , где p1, p2, K pk простые числа. Тогда

Следующая важная для теории чисел задача решается с помощью подсчета числа целых точек на плоскости. Задача 9. Пусть р и q взаимно простые целые числа. Докажите, что й(q - 1) p щ ( p - 1) (q - 1) й pщ й 2pщ ъ к ъ + к ъ +K+ к . к ъ= q 2 кл q ыъ лк q ыъ л ы Решение. Рассмотрим на плоскости хОу точки (x; y) с целыми координатами, такие, что 1 ? x ? q - 1 , 1 ? y ? ? p - 1 , т.е. точки, лежащие внутри прямоугольника ОАВС (рис.5). Всего имеется (p - 1)(q - 1) таких точек. Заметим, что на диагонали ОВ этого прямоугольника нет точек с целыми координатами, кроме точек О и В. (В самом деле, p прямая ОВ имеет уравнение y = x . Если целая точка q n p (m; n) лежит на ОВ, причем 1 < m < q , то m = q , т.е. qn = =mp. Но так как q и р взаимно просты, то n делится на р, а m делится на q, т.е. m ? q , n ? p . Противоречие.) Поэтому в треугольнике ОВС содержится ровно половина рассматри( p - 1) (q - 1) ваемых целых точек, т.е. . 2 Подсчитаем теперь это же количество другим способом.

(n) = (1 + 1)(2 + 1)K(k + 1) . Для доказательства достаточно заметить, что всякий делитель d числа n имеет разло жение вида d = p1 1 K pk k , где 0 ? i ? i , i = 1, 2, ..., k, т.е. однозначно определяется набором чисел (1, 2, K k ) . Но всего таких наборов существует (1 + 1, 2 + 1, k + 1) . Отметим еще одно полезное соотношение. Задача 11. Пусть (n) сумма всех делителей числа n. Тогда
(1) + ( 2 ) + K + (n) = кк 1 ъъ + 2 кк 2 ъъ + K + n кк n ъъ . лы лы лы
й nщ йnщ й nщ

n Решение. Число 1 делитель всех чисел, поэтому = n 1 n n сумма всех единиц. На 2 делится чисел, так что 2 2 2 есть сумма всех двоек делителей чисел от 1 до n. Вообще, n k количество чисел, не больших n и делящихся на k. n Поэтому k это сумма всех делителей, равных k. k n Следовательно, сумма по k всех чисел вида k есть в k точности левая часть доказываемого равенства.
Упражнение 21. Докажите, что

[ x ] + к x + n ъ + K + к x + n ъ = [nx ] . кл ъы кл ъы

й

1щ

й

n - 1щ