Идет двадцать первый век. Кажется, что уже все открыто и переоткрыто. Особенно в такой древней области знаний, как теория чисел... И тем не менее в ней, правда очень редко, среди "дорожной пыли" можно встретить "алмаз". Расскажу о своей находке.
В старые добрые времена конца двадцатого века я любил "играть в числа", в номера госрегистрации автомашин. Тогда эти номера были четырехзначными, и играть было интересно. Номера автомашин различались, как номера автобусных билетов, на счастливые и остальные, не особенно счастливые. В частности, числа, у которых сумма цифр, стоящих на четных местах, равнялась сумме цифр, стоящих на нечетных местах, считались счастливы ми. Известно, что все они делятся на одиннадцать. На одиннадцать делятся также числа, у которых разность суммы цифр, стоящих на четных местах, и суммы цифр, стоящих на нечетных местах, делится без остатка на одиннадцать. Речь идет пока о представлении чисел в десятичной системе счисления.
Находясь на улице или в автобусе, я автоматически сортировал номера автомашин на делящиеся и не делящиеся на одиннадцать. И вдруг неожиданно заметил, что числа, которые делятся на 11, все без исключения, обладают на первый взгляд забавным свойством: путем несложных операций они сводятся к двузначным числам, состоящим из одинаковых цифр.
Сначала нужно разбить число справа налево на двухразрядные числа. Сложив их, получим некоторую сумму. Если разрядность суммы больше двух, повторить первую и вторую операции. Тогда, если число делится на 11, в результате обязательно получится двузначное число, состоящее из одних и тех же цифр.
Например, рассмотрим число 2574. Разбиваем его на 74 и 25. Сложив эти числа, получим 99. Или возьмем другое число - 9581. Разбиваем его на 81 и 95. Сложив их, получим 176. Число 176 разбиваем на числа 76 и 1; сложив их, получаем 77. Оба числа - 2574 и 9581 - делятся на 11.
После некоторых размышлений я пришел к выводу, что этим свойством обладают все числа, которые имеют делители, состоящие из одних единиц. И еще более интересно, что такое свойство присуще любому способу представления чисел. То есть в любой системе счисления все числа, делящиеся без остатка на n-разрядные делители, состоящие из одних единиц, приводятся к n-разрядным числам, состоящим из одинаковых цифр.
Скажу сразу, что признак делимости для произвольного делимого и делителя, состоящего из одних единиц, в произвольной системе счисления доказать мне пока не удалось. Однако теорема о произведении доказывается достаточно просто. Сформулируем и докажем ее.
Для любой системы представления чисел имеет место теорема:
Если умножить некоторое n-разрядное число, состоящее из одних единиц, на любое целое число N, то полученное произведение можно привести к n-разрядному числу, состоящему из одних и тех же цифр. Для этого нужно проделать следующее:
1. Разбить произведение справа налево на числа разрядности n.
2. Сложив эти числа, получим некоторую сумму.
3. Если разрядность суммы больше n, то для нее, как для произведения, повторить операции 1 и 2.
4. Операции 1, 2 и 3 повторять до тех пор, пока разрядность суммы не станет равной n.
Сначала для ясности рассмотрим в десятичной системе представления численные примеры. Умножив, например, 111 на 9876, получим 1 096 236. Разбиваем 1 096 236 на трехразрядные числа. Имеем числа 236, 096 и 1. Сложив их, получим 333. Еще один пример: если число 111 умножить на 89 876, то получим 9 976 236. Разбиваем 9 976 236 на трехразрядные числа. Имеем числа 236, 976 и 9. Сложив их, получим 1221. Разбиваем 1221 на трехразрядные числа. Имеем 221 и 1. Сложив их, получим 222.
Доказательство:
Теорема доказывается методом математической индукции. Для случая N=1, очевидно, теорема верна. Допустим, что она справедлива для N=K. Это значит, что произведение n-разрядного числа, состоящего из одних единиц, и К с помощью операций 1, 2 и 3 приводится к n-разрядно му числу, состоящему из одних и тех же цифр. Обозначим эти цифры буквой А.
Теперь умножим n-разрядное число, состоящее из одних единиц, на К+1. Умножить на К+1 означает, что к произведению n-разрядного числа, состоящего из одних единиц, и К надо прибавить еще одно число, состоящее из одних единиц. Прибавим к ранее полученному n-разрядному числу, состоящему из одинаковых цифр А, n-разрядное число, состоящее из одних единиц.
Рассмотрим два возможных результата. Если А < 10 - 1, где 10 - основание системы счисления сомножителей, то получим n-разрядное число, состоящее из одних и тех же цифр А+1. Если A = 10 - 1, после сложения получим (n+1)-разрядное число, состоящее из n единиц и нуля в первом разряде. Тогда с помощью операции 3 оно приводится к n-разрядному числу, состоящему из одних единиц.
Таким образом, теорема доказана для любого N.
Следствием теоремы является признак делимости на числа, состоящие из одних единиц.
Чтобы убедиться в том, что некоторое число (делимое) делится без остатка на делитель, состоящий из одних единиц, достаточно, не производя деления, проделать следующее:
1. Разбить делимое справа налево на числа, разрядность которых равна разрядности делителя.
2. Сложив эти числа, получим некоторую сумму.
3. Если сумма имеет разрядность больше, чем разрядность делителя, то для нее, как для делимого, повторить операции 1 и 2.
4. Операции 1, 2 и 3 повторять до тех пор, пока разрядность суммы не станет равной или меньшей разрядности делителя. Если сумма имеет разрядность делителя и состоит из одинаковых цифр, то делимое делится на делитель без остатка. Во всех остальных случаях - не делится.
Этот признак делимости не зависит от системы счисления. При этом для случая представления чисел в двоичной системе пункт 4 звучит значительно проще:
Делимое делится на делитель без остатка, если в результате операций 1, 2 и 3 делимое приводится к делителю. В противном случае - не делится.
В качестве примера рассмотрим два числа в десятичной системе счисления: 777 и 7770, которые делятся на 3 и на 7. Эти числа в двоичной системе имеют вид 1 100 001 001 и 1 111 001 011 010 соответственно. Эти числа с помощью операций 1, 2 и 3 они приводятся к 11 и 111 и, следовательно, делятся без остатка на 11 и 111, то есть делятся на три и семь. Кроме того, число 7770 делится также на 15; следовательно, в двоичной системе приводится к 1111.
Вот такой "бриллиант" мне посчастливилось встретить на дорогах России.
