uniqueness of digital representation

Theorem.  Let the positive integer b be the base of a http://planetmath.org/node/3313positional digital system.  Every positive integer a may be represented uniquely in the form

a=snbn+sn-1bn-1++s1b+s0, (1)

where the integers si satisfy  0sib-1  and  sn0.

The theorem means that the integer a may be represented e.g. in the http://planetmath.org/node/9839decimal system in the form


in one and only one way.

Proof.  Let bn be the highest integer power of b not exceeding a.  By the division algorithm for integers, we obtain in succession

a=snbn+r1 (0<sn<b,0r1<bn),
r1=sn-1bn-1+r2 (0sn-1<b,0r2<bn-1),
r2=sn-2bn-2+r3 (0sn-2<b,0r3<bn-2),
rn-2=s2b2+rn-1 (0s2<b,0rn-1<b2),
rn-1=s1b+s0 (0s1<b,0s0<b).

Adding these equations yields the equation (1) with  0sib-1,  sn0.

For showing the uniqueness of (1) we suppose also another


with  0tis-1,  bm0.  The equality

snbn+sn-1bn-1++s1b+s0=tmbm+tm-1bm-1++t1b+t0 (2)

immediately implies


Since now  |s0-t0|b-1,  we infer that  s0-t0=0  and thus  t0=s0.  Consequently, we can then infer from (2) that  s1bt1b(modb2), whence  s1t1(modb),  and as before,  t1=s1.  We may continue in manner and see that always  ti=si, whence also  m=n.  Accordingly, the both are identical. Q.E.D.

Remark.  There is the following generalisation of the theorem.  — If we have an infinite sequenceb1,b2,  of integers greater than 1, then a may be represented uniquely in the form


where the integers si satisfy  0si<bi+1  and  sn0.  Cf. the factorial base.

Title uniqueness of digital representation
Canonical name UniquenessOfDigitalRepresentation
Date of creation 2013-03-22 18:52:16
Last modified on 2013-03-22 18:52:16
Owner pahio (2872)
Last modified by pahio (2872)
Numerical id 15
Author pahio (2872)
Entry type Theorem
Classification msc 11A63
Classification msc 11A05
Synonym uniqueness of decimal representation
Synonym digital representation of integer
Related topic UnambiguityOfFactorialBaseRepresentation
Related topic UniquenessOfFourierExpansion
Related topic UniquenessOfLaurentExpansion
Related topic ZeckendorfsTheorem
Related topic RepresentationOfRealNumbers