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

Систематической записью натурального числа N по основанию ρ называют представление этого числа в виде суммы:

N = а_nρⁿ+...+а₁ρ, + а₀

где а_n, ..., а₁, а₀ - числа принимающие значения 0, 1, ..., ρ - 1, причем, а_n≠0.

Позиционная система счисления с основанием ρ называется ρ — ичной (двоичной, троичной и так далее). На практике чаще всего применяется десятичная ρ= 10).

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

Для ρ - ичной системы счисления нужно ρ цифр. Если ρ < 10, то применяются те же обозначения цифр, что и в десятичной системе счисления (только берутся цифры, меньше основания системы).

В системах с основанием ρ > 10 для чисел, больших или равных 10, не вводят специальных символов, а используют десятичную запись этих чисел, заключая эту запись в скобки. Например, в четырнадцатеричной системе имеется четырнадцать цифр: 0, 1, 2, 3 ... 9, (10), (11), (12), (13).

В системе счисления с основанием ρ, так же как и в десятичной системе счисления, место, занимаемое цифрой, считая, справа налево, называется разрядом.

Число N= а_nρ ⁿ + . . . +a₁ρ +а₀ содержит а₀ единиц первого разряда, а₁ единиц второго разряда, а₂ единиц третьего разряда и так далее. Единица следующего разряда в ρ раз больше единицы предыдущего разряда.

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

Теорема.  Любое натуральное число N может быть записано в системе с основание ρ и притом единственным образом.

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

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

N=a_nρ_n +a _n-1 ρ_n-1 + ... +аρ+а₀                (1)

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

Представление числа N в виде (1) возможно для первых р-1 натуральных чисел 1, 2,..., ρ-1, так как n=1 и число совпадает с данным числом. Представление числа в виде (1) для чисел 1, 2, . . . ,ρ-1, очевидно, возможны только единственным способом: 1=1, 2=2,. . . ,ρ-1=ρ-1.

Предположим, что все натуральные числа N≤k (к≥1)  представимы в виде (1). Докажем что число к+1 так же представимо в виде (1). Для этого разделим с остатком число к+1 на ρ:

K+l=s_ρ+r, 0<г<ρ-1           (2)

где s - неполное частное и г - остаток.

Так как число  s≤k, то  оно  по  предположению индукции представимо в виде (1):

s = а_nρⁿ+ . . . +a₁ρ +а₀           (3)

где 1≤а_n≤ρ -1, 0≤ a_i ≤ρ -l, (i=0,1,..,n-1)

Подставим выражения (2) и (3), получим:

k+l= (a_nρ+ ... +а_iρ +а₀) ρ + г = а_nρ +... + a_iρ +a₀ρ +г       (4)

где 1 ≤ a_n ≤ρ -1, 0≤ a_j ≤ ρ -1, 0 ≤ г ≤ ρ -1 0=0,1,. . ,n-1)

Это выражение (4) дает представление числа к+1 в виде (1):

К+1=b _n+1ρ  ⁿ⁺¹ + b_n ρ _n + ... + b₁ρ  +b₀

где b₀ =r, b_i+1- a_i (i=0,l,.. ,n-l)

2. Докажем единственность представления любого натурального числа в виде (1).

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

Для чисел 1, 2,... , ρ -1 представление в виде (1) единственно.

Предположим что для  всех  натуральных N≤k  (к≥1)  представление  в  виде (1) единственно. Докажем, что число к+1 может быть представлено в виде (1) только одним способом. Для этого разделим с остатком число к+1 на ρ:

K+l=s_ρ+r, 0<г< ρ -1                  (5)

Предположим, что к+1 имеет два различных способа представления:

к+1=а _nρ ⁿ + а_n-1 ρ ^n-1 + ....+ а₁ρ  +а₍₎                            (6)

к+1 =b _mρ  ^m + b_m-1 ρ ^m-1 + ... + b₁ρ  +b₀                       (7)

Представим: равенства (6) и (7) в виде:

k+1= (а _nρ ^n-1 + a_n-1 ρ ^n-2+ ... + а₁)ρ+а₀                        (6*)

k+1 = (b _mρ ^m-1 + b_m-1 ρ ^m-2+ ... + b)ρ+b₀                                  (7^*)

Так как 0 ≤ а₀ ≤ρ -1 и 0 ≤ b₀ ≤ρ -1, то из (6*) и (7*) следует, что неполное частное s и остаток г в формуле (5) будут:

S= а_nρ ^n-1 + а_n-1 ρ ^n-2 + ... + a₁=b_mρ ^m-1 + b_m-1 ρ ^m-2+ ... + b_1.  r = a₀ = b₀

Так как s ≤ k, из индуктивного предположения следует, что число s имеет единственно представление в виде (1), то есть

n-l = m-l, a_i =b_i , (i=0,1, . . ,n-1).

Из последнего равенства имеем а₀=b_о. Таким образом, n=m, a_i=bi (i=0,l, . . ,n-l), но это противоречит допущению, что число k+1. имеет два различных представления (6) и (7). Следовательно, число к+1 представляется в виде (1) единственным образом. На основании принципа математической индукции утверждение справедливо для любого N . Теорема доказана.