Page 261 - 1975_matematika-izium
P. 261
1. Системы счиc:.nеНI{Я и признаки делимости
Задав натуральное чиc:.nо Ь (основание системы СЧllсления) , мы
можем l<аждое натуральное чис.10 N предстаВIIТЬ единственным об
разом в виде k k
N = a k b + a k_lb - l + • • • + a 1 b + a " , :(1 )
где каждое а; равно одному из чисел О, 1, . • . , Ь - 1 . Такое ЧIIСЛО
записывается в виде
• • • a 1 ao '
akak_1 • • •
В десятичной системе счиc:.nения общеизвестен nrlli311aK де.lIIМО
сти на 9 If менее известен признак де.1ИМОСТИ на 1 1 В системе СЧIIС
ления с основанием Ь также имеются эти два призuака.
а. Для того чтобы число N делилось на Ь - 1, необходuлlO 11
дGстаТОЧ1l.0, чтобы сумма цифр его b-иЧ1l.0Й записи делuлась на
b - I.
В самом деле, используя (1) , находим
N - ( ao + • . . + a k ) = a k (b - k l ) + • • • + a 2 ( b2 - I ) + а, (Ь - I ) .
посI<олы<y
b' - l = (b - l ) ( b'-I + . . . + Ь + l ) ,
разность N - (йо + . . . + аА) делится иа Ь - 1, а тогда оба ЧIIС.1а
N и ао + . . . + ah делятся на Ь - 1 ИЛII нет одновременно.
б. Для того чтобы число N делилось на Ь + 1, н.еобхоrJu !/о 11 до
статочно, чтобы разность J,fежду суммами цифр, СТО!/ЩIlХ в его
b-иЧ1l.0Й записи на четных и нечетных местах, делилаС/J на Ь + 1.
В самом де.'1е,
N - (ao - al + а 2 - • • • + ( - I ) k ak) =
= а l (Ь + 1 ) + а2 (Ь2 - 1 ) + . . . + ak ( b k - ( _ I )k).
Остается заметить, что
b2n+ l + l = (b + l ) ( b2n _ b �n- l + • . . - Ь + l ) ,
b�n - 1 = (Ь + 1 ) (Ь - 1 ) (b�n-? + ь2n-4 + . . . + ь2 + 1)
и остальиое де.qается, l<ак в c:.nучае а.
2. Арифметика остатков
В оригинале I<ННГИ Тригга и особенно в допо.qНlIте,lЬНЫХ зала
чах часто используются сравнения mod Ь. При работе над перево,
дом я старался заменить соответствующие места "епосредствен
нымн рассуждениями с остатками от дмения на Ь. ОСIIОВНое, что
здесь надо знать, сводится 1< следующему. ЕСЛII N I1 N' имеют пр"
де. 1еНИII на Ь остатки r и г', то есть
N = k b + r , N' = k'b + r ',
то числа N + N', N - N'. NN' 11 Nm имеют пр" !lС.1еIl l Ш на Ь те же
остатки,' что
'
г + ". г - г ', гг , гrtl
СООтветствеНlIО.
264