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

 

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

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

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

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

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

A=
N
S
i=0
(ai*10i) .

где:

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

то если число
N
S
i=0
(ai)
делится на 3 или 9 то и делимое
A=
N
S
i=0
(ai*10i)
так жеделится на 3 или 9.

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

Пусть:

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

Так как по определению
A=
N
S
i=0
(ai*Qi)
то:
A\B = (
N
S
i=0
(ai*Qi))\B = (
N
S
i=0
((ai*Qi)\B))\B =
N
S
i=0
((ai*( Qi\B ))\B)\B =
N
S
i=0
(ai*( Qi\B ))\B  

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

 

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

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

Для случая, когда выражение Qi\B всегда равно 1 то A\B=
N
S
i=0
(ai)\B.

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

 

В случае, когда Q\B=0 мы приходим к Q0\B=1; Qi\B=0,i>0 то A\B=a0\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 Шуклин Д. Е.