Приглашение в теорию чисел
Шрифт:
……
qn– 1 = qnb + сn– 1,
qn = 0 b + сn,
при этом мы продолжаем деление до тех пор, пока не окажутся выполненными соотношения qn < b, qn+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)3.
Пример 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)12.
Система задач 6.2.
1. Выразите числа (1, 2, 3, 4)5, (1, 1, 1, 1, 1, 1)3 в десятичной системе.
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 • 102 + 2 • 10 + 5 = 325
или
3 • 122 + 2 • 12 + 5 = 461.
Для того чтобы получить представление о том, как меняется количество знаков в числе в зависимости от системы счисления, возьмем число
10n — 1 = 99… 9 (n раз) = N (6.3.1)
в десятеричной системе. Это самое большое число с n знаками. Чтобы найти m — количество знаков при записи этого числа при основании b — мы должны определить m как целое число, для которого выполняются неравенства
bm > 10n — 1 ≥ bm– 1. (6.3.2)
Это
bm ≥ 10n > bm– 1.
Возьмем логарифмы этих трех чисел. Вспомнив, что lg 10 = 1, получим, что
m lg b ≥ n > (m — 1) lg b.
В свою очередь эти неравенства могут быть переписаны в виде
m ≥ n/lg b > (m — 1); (6.3.3)
таким образом, m является первым целым числом не меньшим, чем n/lg b.
Отсюда делаем вывод, что, грубо говоря, m — новое количество знаков, может быть получено делением числа n на lg b.
Примеры. Пусть вновь n будет количеством знаков числа в десятичной системе. Для b = 2 мы имеем: lg 2 = 0,30103, таким образом, количество цифр в двоичной системе приблизительно равно 3,32 n. Когда b = 60, мы имеем: lg 60 = 1,778, отсюда количество знаков приблизительно равно 0,56 n, т. е. немного больше, чем половина количества знаков в десятичной системе.
Ясно, что короткими числами удобнее оперировать. Но, с другой стороны, числа при больших основаниях имеют ряд недостатков. Во-первых, нужно иметь названия и обозначения для b различных цифр, чего обычно нет для больших значений b. Например, в вавилонской шестидесятеричной системе считали единицы до 60, группируя их по десять, как показано на рис. 15.
Рис. 15.
Это означает в действительности, что эта система расщеплялась на подсистемы с десятеричной записью. Аналогичная ситуация существует в двадцатеричной системе народа майя. Здесь цифры до 20 считались пятерками, как показано на рис. 16.
Рис. 16.
Вторым и гораздо большим недостатком является трудность, возникающая при попытках вычислений с помощью обычных методов. Когда мы выполняем действие умножения, то пользуемся знанием наизусть таблицы умножения, т. е. знанием произведений всех десяти цифр. Эта таблица Пифагора, как ее называют во многих странах, вдалбливалась нам в течение первых школьных лет, и знаем мы ее почти автоматически. Это знание не столь тривиально, как мы склонны думать. Из средневековых арифметических манускриптов ясно видно, что умножение было на грани высшей математики, а деление больших чисел было в действительности редким искусством. Но можно привести и гораздо более поздние примеры.