Системы счислениния

Рассмотрим теорему о делении натуральных чисел с остатком. В общей теории арифметики существует (см. предыдущий пункт)

Теорема. Для любых натуральных чисел a и b, b ¹ 0, существуют (единственные) числа s и r такие, что a = sb + r, r < b. Если рассматривать арифметику с 0, тогда r находится в пределах 0 £ r < b.

Доказательство:

(единственность): Пусть существует два таких разложения: a = s₁b + r₁ и a = sb + r, тогда можно считать, что r ³ r₁ и вычитая первое из второго будем иметь:

0 = b(s – s₁) + (r – r₁) Þ r – r₁ = b(s₁ – s),

поскольку (r – r₁) ³ 0 и r, r₁ < b, то (r – r₁) < b, из этого следует, что b(s – s₁) = 0 и (r – r₁) = 0, тогда r = r₁ и s = s₁.

(существование): доказательство с использованием математической индукции по числу а при фиксированном b:

1) если a = 0, то 0 = 0 b + 0. Теорема доказана;

2) пусть для a = n Теорема доказана, т.е. n = sb + r и r < b. Тогда n +1 = sb + r +1. Если r +1 < b, то теорема доказана (по разложению). Если r +1 = b (r +1 не может быть больше b, т.к. r < b), то (n +1) = sb + b = b(s +1) +0, тогда теорема доказана, т.к. 0 < b.

Исходя из того, что b у нас было все-таки произвольным, то Теорема в целом доказана.

В арифметике эта Теорема называется Теоремой о делении с остатком, где a – делимое, b – делитель, s – частное, а r – остаток. Как правило, результат получается при делении столбиком.

С помощью теоремы о делении с остатком можно доказать следующую

Теорему: Пусть р – фиксированное натуральное число и p > 1, тогда для любого а существуют числа а₀, а₁, а₂, …, а _n такие, что 0 £ a_i < p ( i = 0, …, n ) и а = а₀р⁰ + а₁р¹ + а₂р² + … + а _npⁿ, при чем это разложение единственно.

Доказательство: (доказательство с использование математической индукции по числу а):

1) Пусть a = 0, то 0 = 0 р. Теорема доказана;

2) Предположим, что для любых чисел строго меньших a теорема верна. Докажем ее для a. Пусть т удовлетворяет следующему условию: р^т+1 > > а ³ р^т, такое т всегда существует (потому что снизу ряд р^т ограничен 1, а сверху ряд р^т не ограничен). Тогда по теореме о делении с остатком будем иметь следующее выражение: a = = s р^т + r, т.к. s ¹ 0, r < a, следовательно, для него теорема верна и мы получаем, что а = sp^m + а₀р⁰ + а₁р¹ + а₂р² + … + + а _kp^k. Для того, чтобы Теорема была доказана необходимо показать, что k <m и s < p (Теорема будет доказана поскольку некоторые слагаемые могут быть равны нулю):

а) если s ³ p, то sр^т ³ p^т+1, а т.к. a = s р^т + r, тоа³р^т+1, противоречие с условием;

б) пусть k ³m и a_k ¹ 0, тогда a_kp^k > p^m, что противоречит условию r < p^m.

Таким образом, теорема доказана.

Для практического нахождения числа a сначала, исходя из условия р^т+1 > а ³ р^т, делим число a на р^т (a / р^т) получаемый остаток делим на р^т-1 и т.д. до р¹.

Эта Теорема позволяет теоретически рассматривать любую позиционную систему счисления. Основанием системы будет являться число р, а цифрами такой системы могут являться все числа от 0 до (р – 1), либо специально придуманные значки. Если р = 10, то мы получаем известную нам десятичную систему счисления, где цифрами являются значки 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Если р = 6 – это шестеричная система счисления, где цифр 6 и это значки 0, 1, 2, 3, 4, 5; а если р = 12, то в качестве цифр можно взять 0, …, 9 и потом придумать еще два значка для замены чисел 11 и 12. Например: сосчитаем чему будет равно следующее выражение 11*12⁰ + 10*12¹ + 4*12² = 707. Число 707 в двенадцатеричной системе счисления будет иметь вид: 4ab₍₁₂₎, где a заменяет цифру 10, а b цифру 11. Рассмотрим теперь запись числа 707 в восьмеричной системе счисления: 8³ = 512, 8⁴ = 2048, поэтому 8⁴ > 707 > 8³. Тогда имеет место, следующее выражение: 707 = 1*8³ + 195 = 1*8³ + 3*8² + 0*8¹ + 3*8⁰. Таким образом, число 707 в восьмеричной системе счисления будет иметь вид: 1303₍₈₎.

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