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

Однако интересно найти подобные признаки для делимости любого целого
числа

на любое целое число в любой системе (десятичной, шестнадцатиричной,
...)

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

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

то и делимое делится без остатка на 3 или 9.

То есть:

делимое A=S_i=0^N(a_i*10ⁱ)

где:

a_i - разряд делимого

10ⁱ - десять в степени i

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

Пусть:

• 
  A - делимое



B - делитель

Q - основание системы счисления

S_i=0^N - операция суммирования
по индексу i от 0 до N

a_i - i-й разряд числа A

N - количество разрядов числа A

X\Y - операция получения остатка деления числа
X на число Y

X^Y - операция возведения числа X в
число Y

A\B=S_i=0^N(a_i*(
Qⁱ\B ))\B

Докажем это:

Для этого сначала докажем следующие свойства:

1. (X\W)\W=X\W

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

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

1. Очевидно.

Так как X=L*W+X\W; Y=M*W+Y\W - по определению операции деления то:

2.

(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*(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=S_i=0^N(a_i*10ⁱ)
то

A\B=(S_i=0^N(a_i*10ⁱ))\B=(S_i=0^N((a_i*Qⁱ)\B))\B=S_i=0^N((a_i*(
Qⁱ\B ))\B)\B=S_i=0^N(a_i*(
Qⁱ\B ))\B

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

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

Для случая, когда выражение Qⁱ\B всегда
равно 1 то A\B=S_i=0^N(a_i)\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.

Узнаем, делится ли 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

Следует заметить, что если нам надо узнать остаток от деления 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 17:50 Шуклин Д.Е. shduser@hotmail.com

 

 

--------------9682DAF810BBC90D72F10655--