Date: Thu, 22 Apr 1999 18:43:44 +0300
--------------9682DAF810BBC90D72F10655
Content-Type: text/plain; charset=koi8-r
Content-Transfer-Encoding: 8bit
Рассмотрим вопрос о делимости одного целого числа на другое.
Широко известны признаки делимости на 2,3,5,9,10
Однако интересно найти подобные признаки для делимости любого целого
числа
на любое целое число в любой системе (десятичной, шестнадцатиричной,
...)
Займемся этим сейчас.
Для начала вспомним о признаке делимости на 3,9 в десятичной системе
счисления : если сумма чисел у делимого делится без остатка на 3 или 9,
то и делимое делится без остатка на 3 или 9.
То есть:
делимое A=Si=0N(ai*10i)
где:
ai - разряд делимого
10i - десять в степени i
то если число Si=0N(ai) делится на 3 или 9 то и делимое A=Si=0N(ai*10i)
так же
делится на 3 или 9.
Теперь запишем общий вид этой зависимости
Пусть:
* A - делимое
B - делитель
Q - основание системы счисления
Si=0N - операция суммирования по индексу i от 0 до N
ai - i-й разряд числа A
N - количество разрядов числа A
X\Y - операция получения остатка деления числа X на число Y
XY - операция возведения числа X в число Y
Тогда:
A=Si=0N(ai*10i)
A\B=Si=0N(ai*( Qi\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=Si=0N(ai*10i) то
A\B=(Si=0N(ai*10i))\B=(Si=0N((ai*Qi)\B))\B=Si=0N((ai*( Qi\B
))\B)\B=Si=0N(ai*( Qi\B ))\B
Что и требовалось доказать.
Для системы счисления с постоянным основанием Q выражение Qi\B - набор
констант, зависящих от индекса i.
Для случая, когда выражение Qi\B всегда равно 1 то A\B=Si=0N(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.
Узнаем, делится ли 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
Content-Type: text/html; charset=koi8-r
Content-Transfer-Encoding: 8bit
Рассмотрим вопрос о делимости одного целого числа на другое.
Широко известны признаки делимости на 2,3,5,9,10
Однако интересно найти подобные признаки для делимости любого целого
числа
на любое целое число в любой системе (десятичной, шестнадцатиричной,
...)
Займемся этим сейчас.
Для начала вспомним о признаке делимости на 3,9 в десятичной системе
счисления : если сумма чисел у делимого делится без остатка на 3 или 9,
то и делимое делится без остатка на 3 или 9.
То есть:
делимое A=Si=0N(ai*10i)
где:
ai - разряд делимого
10i - десять в степени i
то если число Si=0N(ai)
делится на 3 или 9 то и делимое A=Si=0N(ai*10i)
так же
делится на 3 или 9.
Теперь запишем общий вид этой зависимости
Пусть:
-
A - делимое
B - делитель
Q - основание системы счисления
Si=0N - операция суммирования
по индексу i от 0 до N
ai - i-й разряд числа A
N - количество разрядов числа A
X\Y - операция получения остатка деления числа
X на число Y
XY - операция возведения числа X в
число Y
Тогда:
A=Si=0N(ai*10i)
A\B=Si=0N(ai*(
Qi\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=Si=0N(ai*10i)
то
A\B=(Si=0N(ai*10i))\B=(Si=0N((ai*Qi)\B))\B=Si=0N((ai*(
Qi\B ))\B)\B=Si=0N(ai*(
Qi\B ))\B
Что и требовалось доказать.
Для системы счисления с постоянным основанием Q
выражение Qi\B - набор констант, зависящих
от индекса i.
Для случая, когда выражение Qi\B всегда
равно 1 то A\B=Si=0N(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.
Узнаем, делится ли 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--