на 5"). После этого цифра 5" будет играть роль обычной единицы и в£е рассуждения для такой системы счисления будут аналогичны рассуждениям относительно обычной цифры 1 и исходной системы счисления.

Покажем,, что другого способа представления единицы в рассматриваемых системах счисления не су- . ществует. Для этого надо толь-ко показать, что никакая комбинация цифр в разрядах, имеющих веса с отрицательными степенями 5, не может дать при суммировании единицы. Предположим противное. Пусть

. Если есть максимальная степень, то или

= [(«y)U.-5". + + ... + .

Ho при произвольном 5 это равенство невозможно.

Аналогичным образом можно показать, что среди цифр должны быть цифры, соответствующие коли- чественным эквивалентам 2, 3, ..., 5-1. Цифра, имеющая количественный эквивалент, равный S, уже не нужна, так как ее появление делает систему избыточной. В самом деле, если среди цифр с эквивален- тами О, 1, 2,... , 5-1 появится еще цифра с эквивалентом S, то число x = S можно представить двумя способами: или как 10 ... 0,0 ... , или как ... 0, О ... , где в первой записи единица стоит в разряде с номером т, а во второй записи цифра Ь, имеющая количественный эквивалент стоит в нулевом разряде записи числа.

Итак, мы получили, что в качестве множества цифр неизбыточной системы счисления можно взять цифры с количественными эквивалентами О, 1,2,... , 5-1. Вместо этого набора можно брать любой набор, в котором каждая цифра приведенного множества цифр умножена на одну и ту же степень основания 5.

Б-79.-2 17.

Как уже отмечалось выше, такая операция приводит просто к перемещению начала отсчета на разрядной-сетке.

Теперь покажем, что введенного множества цифр достаточно для точного представления любого целого числа.

Теорема Ы; Набор цифр О, 1, 2,... , S - 1 позволяет в системе счисления с натуральным основанием S выражать конечным образом любое целое положительное число.

Доказательство будем вести по индукции. Мы уже убедились, что введенные нами цифры поз-, воляют выразить 5 чисел О, 1, 2,... , S-1. Предположим теперь, что с их помощью можно выразить некоторое натуральное число N, и докажем, что в этом случае натуральное число Л/Ч-1 также представляется в системе счисления с данными цифрами конечным образом.

Пусть число Лвыражается как

N{{a,)],S+[{aj)\, ,.S- + ... + Mo-S".

Рассмотрим два случая. [(ау)]о<5 -1; в этом случае число N-\-\ будет выражаться как

1 =1№-5*+ + - + + \VS.

Во втором случае (предполагая для общности, что 1(«)1о = = ... = = 5-1) оно будет вы-

ражаться как]

1 = {{aiX-S" + .:. + [{aj) + lL-i-5" + ... + O-S".

Если теперь предположить, что цифрам из А сопоставлены только отрицательные целые числа, то все наши вышеприведенные рассуждения окажутся верными и для этого случая. Только в этом случае нужно говорить не о представлении положительных целых чисел,, а о представлении отрицательных целых чисел.

Что же касается представления дробей, то при требовании конечного представления с заданной степенью точности е можно всегда найти такое число разрядов п справа от запятой, что S" < е < (5 - 1) 5""+ в этом числе разрядов представление любой дроби будет иметь точность, не меньшую, чем е.

Определение 1.3. Канонические системы счисления, у которых все количественные эквиваленты цифр только положительны или только отрицательны, называются смещенными системами счисления.

Смещенные системы счисления получили весьма широкое распространение и в повседневной практике и в вычислительных машинах.

Теперь будем предполагать, что среди количественных эквивалентов цифр есть как положительные эквиваленты, так и отрицательные эквиваленты. Для таких систем снова обязательно наличие нуля среди цифр системы, так как при натуральном основании невозможно в конечном виде представить число нуль. Пусть вначале основание системы счисления 5=2+1 есть нечетное число. Возьмем набор количественных эквивалентов цифр вдда {-R, ~R + \, ... , -Л, Q, 1, ... , R) и покажем, что с помощью этого набора цифр можно выразить любое целое число конечным образом.

Теорема 1.2. Для системы с нечетным натуральным основанием 5 = 2/? 4- 1 набор цифр с количественными эквивалентлми { -R, -R-\-\, ... ,-1, О, 1,..., R\ позволяет представить любое целое число в конечном виде.

Доказательство. Покажем, что с помощью данных цифр возможно выразить все количественные эквиваленты, соответствующие цифрам смещенных систем для данного основания S. Это следует из следующих равенств:

/? + 1 = 1-S + (-= 2/? + 1 -,/? + 2 = l.S + (-/? + l)-S = 2/?+l-/? + l, -

2/? = 1.5+ (-1)-S= 2/? + 1 - 1,

I = ( i).si +/.s"=-2;? - 1 +

~R-~2{-l)-S + {R+\)=-~2R-\+R-~\,

-2;? = (-1).5 + Ь5=-2/?-1 + 1..

Нужно показать, что выбранная нами система цифр не является неизбыточной. Справедливость этого утверждения следует из того, что все введенные нами цифры используются при доказательстве справедли-

2* • 19