Приглашение в теорию чисел

4² + 0 • 4 + 1 = 225.

Вообще, когда число задано в системе с основанием b, мы находим это число в обычной десятичной системе, вычисляя значения степеней числа b, умножая каждое из них на соответствующую цифру и складывая, как уже делалось в вышеприведенных примерах.

Теперь рассмотрим обратную задачу. Задается число N и мы хотим представить его при основании b. Мы можем сделать это повторным делением на b. Взгляните на формулу (6.2.1). Можно записать ее в виде

N = (cⁿb^n-1 +… + c₂b + c₁) b + c₀.

Так как с₀ меньше, чем b, то с₀ является остатком при делении числа N на b. Мы можем записать это деление

N = q₁b + c₀, q₁ = c_nb^n-1 +… + c₂b + c₁,

для того чтобы показать, что c₁ получается делением числа q₁ на b тем же способом, и т. д. Таким образом мы находим коэффициенты с_i в результате серии делений на число b:

N = q₁b + c₀,

q₁ = q₂b + с₁,

……

q_n-1 = q_nb + с_n-1,

q_n = 0 b + с_n,

при этом мы продолжаем деление до тех пор, пока не окажутся выполненными соотношения q_n < b, q_{n +1} = 0. Мы приводим два примера, которые помогут вам понять этот процесс.

Пример 1. Выразим число 101 при основании 3. Мы выполняем деление на 3, как указывалось выше, и находим

101 = 33 • 3 + 2,

33 = 11 • 3 + 0,

11 = 3 • 3 + 2,

3 = 1 • 3 + 0,

1 = 0 • 3 + 1.

Отсюда

101 =(1, 0, 2, 0, 2)₃.

Пример 2. Выразим число 1970 при основании 12. Здесь деление на 12 таково:

1970 = 164 • 12 + 2,

164 = 13 • 12 + 8,

13 = 1 • 12 + 1,

1 = 0 • 12 + 1.

Следовательно,

1970 = (1, 1, 8, 2)₁₂.

Система задач 6.2.

1. Выразите числа (1, 2, 3, 4)₅, (1, 1, 1, 1, 1, 1)₃ в десятичной системе.

2. Представьте числа 362, 1969, 10 000 при основаниях b = 2; 6; 17.

§ 3. Сравнение систем счисления

Американское общество сторонников двенадцатеричной системы предложило изменить нашу десятеричную систему на более эффективную и удобную, как они думают, систему с основанием 12. Те, кто предлагает эту систему, указывают, что было бы выгоднее иметь систему с основанием, делящимся на числа 2, 3, 4 и 6, так как процесс деления на эти часто встречающиеся делители упрощается. Доводы такого типа привели бы нас к шестидесятеричной системе, основание которой, число 60, делится на числа

2, 3, 4, 5, 6, 10, 12, 15, 20, 30.

В ряде стран многие вещи все еще считают дюжинами и гроссами (т. е. дюжинами дюжин) и естественно, что для них двенадцатеричная система является вполне возможной. Для перехода в двенадцатеричную систему нужно было бы ввести двенадцать новых символов, что потребует для их разработки столь же много усилий, сколько потребовалось для создания десятеричной системы. Некоторые энтузиасты считают, что необходимо ввести новые символы лишь для 10 и 11, но такой способ не учитывает неудобств, возникающих в период перехода: никто не будет понимать, например, означает ли запись 325

3 • 10² + 2 • 10 + 5 = 325

или

3 • 12² + 2 • 12 + 5 = 461.

Для того чтобы получить представление о том, как меняется количество знаков в числе в зависимости от системы счисления, возьмем число

10ⁿ — 1 = 99… 9 (n раз) = N (6.3.1)

в десятеричной системе. Это самое большое число с n знаками. Чтобы найти m — количество знаков при записи этого числа при основании b — мы должны определить m как целое число, для которого выполняются неравенства

b^m > 10ⁿ — 1 ≥ b^m-1. (6.3.2)

Это условие может быть также записано в виде

b^m ≥ 10ⁿ > b^m-1.

Возьмем логарифмы этих трех чисел. Вспомнив, что lg 10 = 1, получим, что

m lg b ≥ n > (m — 1) lg b.

В свою очередь эти неравенства могут быть переписаны в виде

m ≥ n/lg b > (m — 1); (6.3.3)