Перевод натуральных чисел из одной позиционной системы счисления в другую

Теорема. Любое натуральное число т может быть записано в системе счисления с основанием р, причем запись эта единственная
(p Î N, р > 1).

Доказательство. Итак, необходимо представить число т в виде , где коэффициентами

являются цифрами р -ичной системы счисления. Рассмотрим последовательность чисел: р, р ², р ³,..., рⁿ, р^{n +1}, ....

Среди членов этой последовательности найдем число р с наибольшим показателем степени, которое не превышает рассматриваемое натуральное число т. Пусть это будет рⁿ, тогда рⁿ ≤ m < p^{n +1}.

1) Так как рⁿ ≤ m, то т можно разделить на рⁿ с остатком. Тогда получим: т = рⁿ a_n + m_n. Частное a_n и остаток m_n всегда существуют и притом единственные, очевидно 0 < a_n < р и 0 ≤ т_n < рⁿ.

2) Полученный остаток т_n разделим на p^{n -1} с остатком. Тогда получим: m_n = р^{n -1} · a_{n -1} + m_{n -1}, очевидно 0 ≤ a_{п -1} < р и 0 ≤ т_{п -1} < р^{п -1}.

3) Вновь найденный остаток т_{п -1} разделим на р^{п -2} с остатком. Тогда получим: m_{n -1} = р^{n -2} · a_{n -2} + m_{n -2}; 0 ≤ a_{n -2}< р и 0 ≤ т_{n -2}< р^{n -2}.

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

n) На последнем шаге получим:

m ₂= р · a ₁+ m ₁, 0 ≤ a ₁< р и 0 ≤ т ₁ < р. Обозначим т ₁ = а ₀.

Таким образом, подставляя значения остатков из выписанных выше равенств 1), 2), 3), …, n) получим: т = a_n · рⁿ + a_{n -1}· р^{n -1} +... +
+ a ₁ p + а ₀, причем 0 ≤ a_i < р (i = 0, 1, 2,..., n), или 0 ≤ a_i ≤ р – 1, a_n ≠ 0.

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

П р и м е р 1. Запишите в восьмеричной системе счисления число 5437₁₀.

Перевод этого числа выполним, как было доказано в теореме.

Рассмотрим последовательность чисел: 8, 8², 8³, 8⁴, 8⁵, …

(8¹ = 8, 8² = 64, 8³=512, 8⁴ = 4096, 8⁵ = 32768).

Заметим, что 4096 < 5437 < 32768. Разделим 5437 на 8⁴ с остатком. Тогда получим: 5437 = 1 · 8⁴ + 1341. Продолжим деление, как описывалось выше:

1341 = 2 · 8³ + 317;

317 = 4 · 8² + 61;

61 = 7 · 8 + 5;

Т.е. 5437 = 1 · 8⁴ + 2 · 8³ + 4 · 8² + 7 · 8 + 5;

5437₁₀ = 12475₈

На практике вычисления обычно ведутся в обратном порядке.

Рассмотрим снова тоже число 5437 и разделим его на 8.

5437 8

5 679

5437 = 8 · 679 + 5. Это означает, что наше число, кроме некоторого количества восьмерок, содержит еще 5 единиц, т.е. последняя цифра восьмеричной записи есть 5. Для получения следующей цифры нужно полученное частное снова разделить на 8.

Результат выполненных операций можно представить в таком виде:

5437 =8 · 679 + 5

5437 = 8(8 · 84 + 7) + 5

5437 = 8(8(8 · 10 + 4) + 7) + 5

5437 = 8(8(8(1 · 8 + 2) + 4) + 7) + 5 =

= 1 · 8⁴ + 2 · 8³ + 4 · 8² + 7 · 8 + 5.

Коротко решение этого примера записывается так:

 

П р и м е р 2. Запишите в двоичной системе счисления число 47₁₀. Используем тот же прием, здесь р = 2.

 

 

Общее правило можно сформулировать так.

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

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

6375₈ = 6 · 8³ + 3 · 8² + 7 · 8 + 5 = 3325₁₀

11101₂ = 2⁴ + 2³ + 2² + 1 = 16 + 8 + 4+1= 29₁₀.