К вопросу о делимости целых чисел
Широко известны признаки делимости на 2,3,5,9,10
Однако интересно найти подобные признаки для делимости любого целого числа на любое целое число в любой системе (десятичной, шестнадцатеричной, …).
Займемся этим сейчас.
Для начала
вспомним о признаке делимости на 3,9
в десятичной системе счисления :
если сумма чисел у делимого делится
без остатка на 3 или 9,
то и делимое делится без остатка на
3 или 9.
То есть делимое:
A=
N S i=0 (ai*10i) .
где:
ai - разряд делимого
10i - десять в степени i
то если число |
|
делится на 3 или 9 то и делимое |
|
так жеделится на 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\B = ( |
|
(ai*Qi))\B = ( |
|
((ai*Qi)\B))\B = |
|
((ai*( Qi\B ))\B)\B = |
|
(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 Шуклин Д. Е.