К вопросу о делимости целых чисел

Широко известны признаки делимости на 2,3,5,9,10

Однако интересно найти подобные признаки для делимости любого целого числа на любое целое число в любой системе (десятичной, шестнадцатеричной, …).

Займемся этим сейчас.

Для начала вспомним о признаке делимости на 3,9 в десятичной системе счисления : если сумма чисел у делимого делится без остатка на 3 или 9,
то и делимое делится без остатка на 3 или 9.

То есть делимое:

A=

N S i=0

(ai*10i)

.

где:

a_i - разряд делимого
10ⁱ - десять в степени i

Теперь запишем общий вид этой зависимости

Пусть:

A	-	делимое
B	-	делитель
Q	-	основание системы счисления
N S i=0	-	операция суммирования по индексу i от 0 до N
ai	-	i-й разряд числа A
N	-	количество разрядов числа A
X\Y	-	операция получения остатка деления числа X на число Y
XY	-	операция возведения числа X в число Y

Если:

A=

N S i=0

(ai*Qi)

;

Тогда:

A\B=

N S i=0

(ai*( Qi\B ))\B

.

 

Доказательство:

Сначала докажем следующие свойства:

1. (X\W)\W=X\W - Очевидно.

2. (X+Y)\W=(X\W+Y\W)\W

Так как X=L*W+X\W; Y=M*W+Y\W - по определению операции деления то:
(X+Y)\W=(L*W+X\W+M*W+Y\W)\W=((L+M)*W +X\W+Y\W)\W=((L+M)*W)\W+(X\W+Y\W)\W
Очевидно, что ((L+M)*W)\W=0. тогда (X+Y)\W=(X\W+Y\W)\W

3. (X*Y)\W=(X*(Y\W))\W

(X*Y)\W=(X*(M*W+Y\W))\W=(X*M*W+X*(Y\W))\W=((X*M*W)\W+(X*(Y\W))\W)\W
Очевидно, что (X*M*W)\W, тогда (X*Y)\W=((X*(Y\W))\W)\W=(X*(Y\W))\W

Что и требовалось доказать.

Частные случаи:

Для системы счисления с постоянным основанием Q выражение Qⁱ\B - набор констант, зависящих от индекса i.

Для случая, когда выражение

Qi\B

всегда равно 1 то A\B=

N S i=0

(ai)\B.

Мы пришли к уже известному правилу для Q=10, B=3 или 9.

 

В случае, когда Q\B=0 мы приходим к Q⁰\B=1; Qⁱ\B=0,i>0 то A\B=a₀\B.

Мы пришли к уже известному правилу для Q=10, B=2,5 или 10.

Пример 1:

Узнаем, делится ли 1234 на 7.

10\7=3, 100\7=2, 1000\7=6

1234\7=(1*6+2*2+3*3+4)\7=23\7=2

Итак 1234=176*7+2

Пример 2:

Следует заметить, что если нам надо узнать остаток от деления 1234567 на 99 то мы можем взять Q=100

Q\W=100\99=1, 100i\99=1

01 23 45 67\99= 01\99 + 23\99 + 45\99 + 67\99 = (1+23+45+67)\99=136\99=1\99+36\99=37

Как ни странно, это правильный результат: 1234567=12470*99+37!!!

1999-04-22 / 2000-04-24 Шуклин Д. Е.