Есть несколько работ, которые посвящены признакам деления в разных СС. Сергея Гашкова (МГУ). например, или господина Воробьева, "Признаки делимости"адресованных учащимся.
Мне кажется, подход к теме вэтих работах поверхостный. Например, признак делимости на девятку (N-1) позволяет с учетом представленного ниже алгоритма, быстро определять делимость числа на ряд последовательных модулей, без вычисления даже , самих остатков, иначе говоря, возможна быстрая проверка чисел на простоту, что доказывает возможность решения проблем без особых математических "наворотов".
Для того, что бы разделить любое число на
и найти остаток, достаточно
сложить все цифры числа. Видно на примере:
и остаток 5 (
)
и остаток 8 (
)
Аналогично можно найти остаток при делении
"Принцип девятки" работает в системах счисления с любым целочисленным основанием. Роль «девятки» выполняет число на 1-цу меньшее основания системы счисления (СС), например, если основание СС равно
..
Возьмем число
и представим в системе счисления с основанием
. Для этого разделим число
на
один раз.
;
Значит число
представлено в СС с основанием
. Запишем его так:
, или
–это двухразрядное число, у которого старший разряд
, младший
; (b-одноразрядное выраженное в смешанной системе счисления - тысячерично- десятичной)
Теперь, что бы разделить его на
на
и найти остаток
, достаточно сложить разряды числа в новой СС:
.
Значит
; остаток от деления
на
равен
.
Но, разделив
на
мы фактически перевели его в СС с основанием
и получили число
, где
(старший разряд),
(младший разряд) тоже одноразрядное. Теперь число
делим на
в СС с основанием
:
Остаток от деления равен
;
Результат деления записываем как
;
Теперь мы имеем право, по тем же правилам, разделить на
. Причем
- однозначное число в этой СС и на 1-цу меньше основания. То есть “девятка” в данной СС.
Т.о. мы заменили последовательное стандартное деление по последовательным модулям, сложением разрядов.
На некотором этапе данного алгоритма мы видим, что остаток увеличивается на 3 единицы, но этап заканчивается, когда происходит переполнение младшего разряда. Переполнение, это, когда младший разряд b становится равным, или большим "
" - больше основания счисления и тогда необходимо выполнить перенос единицы в старший разряд "
".
Теперь остаток будет увеличиваться на старший разряд ("a" плюс "единица переноса"). Величина единицы переноса определяется целой частью дроби
, где
это
-ный перевод в очередную систему счисления (
),
Вот и все в общих чертах.
Зачем этот алгоритм нужен? Я лично пытался на компе выполнить деление на последовательные модули быстрее, чем компьютер обычно эту процедуру, программу выполняет. Однозначного ответа не получил. Много факторов вмешивается. Например, само кустарное программирование алгоритма.
Есть еще направление исследования:
факторизация числа. Проблема творческая. Я не владею методикой определения сложности алгоритма, что бы сравнить его с существующими. Хотя, признаки деления чисел на основание СС минус единица, позволяют надеяться на конструирование алгоритма факторизации,
вполне конкурентоспособного. Теперь, кажется , высказался. Могу только добавить, что подобных алгоритмов , в которых используется скользящее изменение основания системы счисления, я не нашел. Данный алгоритм как бы существует в пространстве многих систем счисления, но при этом, число "А" представлено в каждой из них. На каждом этапе вычисления остатков от деления на очередной модуль, мы имеем не что иное, как число "А" , но в новой системе счисления, содержащее одновременно искомый остаток в младших разрядах.