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

М А Т Е М А Т И Ч Е С К И Й К КРУЖОК МАТЕМАТИЧЕСКИЙ Р У Ж О К

43

Прогулка до теоремы Чебышева
В.УФНАРОВСКИЙ
Не так уж и трудно задачи решать: Проблема дает вдохновенье. Искусство же в том, чтоб суметь отыскать Задачу, когда есть решенье. П. Хэйн. Груки

за глядят': идешь, сам не зная куда, и вдруг встречаешь что-то совсем неожиданное, чего и в голову не могло прийти, когда начинал прогулку. Давайте и мы прогуляемся по одной хитрой математической тропинке. Мы начнем ее с признака делимости на 9: число п делится на 9 тогда и только тогда, когда сумма его цифр делится на 9. Можно даже более внушительно: если от числа п отнять его сумму цифр, которую мы обозначим ( n ), то результат всегда будет делиться на 9. А теперь присядем и поговорим об обозначениях. От их выбора, как ни странно, зависит очень и очень многое, поэтому в обозначениях математики всегда достаточно консервативны. Например, обозначение n любому математику скажет, что речь идет о целых, скорее всего, натуральных числах (кстати, а какое n у нас?). Неспроста мы выбрали и обозначение как-никак это маленькая буква 'сигма', а большая издревле используется для обозначения сумм. У нас сумма маленькая, так что и букву возьмем маленькую. Посмотрим на обозначения еще с одной стороны. Вы, конечно, знаете, арабы пишут не так, как мы слева направо, а наоборот, справа налево. Но задумывались ли вы о том, что сами-то мы с числами обращаемся по-арабски справа налево. Ну да, не поверите вы, ведь числа мы пишем слева направо. Это да. А складываете вы как? С какой цифры начинаете, с первой или с последней? А умножаете? Попробуйте наоборот! Это неудивительно, цифры и обозначения у нас, как известно, арабские. В действительности удобнее было бы писать и цифры справа налево, но что поделаешь: привычка вторая натура. Чтобы обойти привычку, будем записывать число в другой форме не через цифры, а через разложение в степени десятки; скажем, не 234, а 4 + 3 10 + 2 100. Против этого наша привычка не восстает, поэтому запишем и наше число п в таком виде:

Е

СТЬ ОСОБАЯ ПРЕЛЕСТЬ В ПРОГУЛКАХ 'КУДА ГЛА-

Ну а теперь ничего не стоит доказать наше утверждение:
n - (n ) = ( a0 - a0 ) + a1 (10 - 1) +
2 k + a2 10 - 1 + K + ak 10 - 1 =

(

)

(

)

= 0 + 9a1 + 99a2 + K + 99 K 9ak , что, конечно же, делится на 9 (кстати, сколько девяток в последней записи?). Налюбовавшись результатами своего труда, продолжим прогулку. Что еще можно получить так же просто, не особенно напрягаясь? Можно менять одно из трех: задачу, доказательство, обозначения. Доказательство менять не хочется. Можем ли мы поменять задачу? Да, нетрудно придумать и доказать признак делимости на 11 только сумму нужно брать знакочередующуюся ( a0 - a1 + a2 - a3 + K). Если копнуть глубже, то получится что-то вроде универсального признака делимости (докажите его в качестве упражнения): Пусть m натуральное число и p1, p2 , K , pk остатки k чисел 10, 10 2 ,..., 10 при делении на m. Тогда число n - (a0 + a1p1 + a2 p2 + K + ak pk ) делится на m. При m = 9 получаем уже доказанный ранее результат. (А как насчет 11?) Для m = 7 получаем последовательность {pi }: 3, 2, 6; 4, 5, 1, 3, 2 и т. д. Поэтому, например, остаток от 1992 при делении на 7 равен остатку 2 + 9 3 + 9 2 + 1 6 = 53 , что в свою очередь равно остатку 3 + 5 3 = 18 , что в свою очередь... Пожалуй, можно остановиться и сказать, что это 4. Не слишком интересно... Пойдем в другую сторону попробуем поменять обозначения. Как еще можно обозначить наше число n? Тот, кто хоть немного знаком с программированием, сразу скажет надо использовать другую систему счисления, например двоичную:

n = b0 + b1 2 + b2 22 + K + bm 2m ,
где bi это нули и единицы. (Например, 25 = 1 + 0 2 + + 0 4 + 1 8 + 1 6 .) Тут тоже своя сумма цифр: 2 ( n ) = b0 + + b1 + b2 + K (Цифра 2, конечно же, намекает на основание системы счисления, так что наша это 10 .) Соответствующая теорема звучит так: n - 2 ( n ) делится на... А в самом деле, на что? В десятичной системе делилось на 9 = 10 1, значит, здесь должно делиться на 2 1 = 1. Факт верный, но малоценный. А может, попробовать в общем случае, в р-ичной системе счисления, где р произвольное

n = a0 + a1 10 + a2 102 + K + ak 10k ,
где a0 последняя цифра, a1 предпоследняя, ..., ak первая, так что всего цифр k + 1, а их сумма равна
( n ) = a0 + a1 + a2 + K + ak .
Опубликовано в 'Кванте' ?6 за 1992 год.