Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Prove that for every $a\in\mathbb{N}$ there is one and only one way to express it in the system with base $\mathbb{N}\ni s>1$.

Seems classical, but I don't have any specific argument.

share|improve this question
    
The most direct proof sketch, I think, is that there is an algorithm for computing the $k$-th digit of $a$. This statement (as stated) wouldn't even make sense if $s$-adic representation were not unique! To flesh out the sketch, you revisit the argument that the algorithm computes what is stated. –  Hurkyl Aug 16 '12 at 14:22

4 Answers 4

up vote 1 down vote accepted

Suppose that some positive integer $N$ has two representations base $s$. Then we can write $$N=\sum_{k=0}^ma_ks^k=\sum_{k=0}^nb_ks^k\;,\tag{1}$$ where $0\le a_1,\dots,a_m,b_1,\dots,b_n\le s-1$ are integers, and without loss of generality we may assume that $m\le n$.

Suppose first that $m<n$. Then

$$\begin{align*} \sum_{k=0}^ma_ks^k&\le\sum_{k=0}^m(s-1)s^k\\ &=\sum_{k=0}^ms^{k+1}-\sum_{k=0}^ms^k\\ &=\sum_{k=1}^{m+1}s^k-\sum_{k=0}^ms^k\\ &=s^{m+1}-1\\ &<s^n\\ &\le\sum_{k=0}^nb_ks^k\;, \end{align*}$$

contradiction the assumption $(1)$. Thus, we assume that $m=n$.

Now make the further assumption that $N$ is the smallest positive integer with two different base $s$ representations. Without loss of generality assume that $a_n\le b_n$, and let $M=N-a_ns^n$. Then

$$M=\sum_{k=0}^{n-1}a_ks^k=\sum_{k=0}^{n-1}b_ks^k+(b_n-a_n)s^n\;.\tag{2}$$

We just proved that this is impossible if $b_n-a_n\ne 0$, so $(2)$ must simplify to

$$M=\sum_{k=0}^{n-1}a_ks^k=\sum_{k=0}^{n-1}b_ks^k\;.$$

But then $M$ is a number with two base $s$ representations that is smaller than $N$, contradicting our choice of $N$. It follows that no such $N$ exists and hence that every positive integer has a unique representation base $s$.

share|improve this answer

We can express a natural number $a$ to any base $s$ by writing $k = \lceil \log_s a \rceil$, the number of digits we'll need, $a_k=\max(\{n\in \mathbb{N}: ns^k\leq a\}),$ and recursively $a_{i}=\max(\{n\in \mathbb{N}: ns^i \leq a-\sum_{j=i+1}^k a_j s^j\})$. It's immediate that each of these maxes exists, since $0s^i\leq a$ no matter what and $a s^i\geq a$, and that they're unique by, say, the well-ordering of $\mathbb{N}$. Then $$a=\sum_{j=0}^k a_j s^k$$

share|improve this answer

We show existence by (strong) induction. Suppose the result is true for all $m\lt n$. Show it is true at $n$.

Let $s^k$ be the largest power of $s$ that is $\le n$. Then $1\le n/s^k \lt s$. So if $d=\lfloor n/s^k\rfloor$ then $s=ds^k +m$ where $0\le m\lt n$ and $m\lt s^k$. If $m=0$ we are finished, else apply induction hypothesis.

For uniqueness, again we can use induction. The lead digit is uniquely determined by the condition in the preceding paragraph.

Another way: Uniqueness is particularly easy to prove by an induction running in the other direction. Take a particular representation, of a possible several. The "units" digit $d_0$ is uniquely determined as the remainder when $n$ is divided by $s$. But then the next digit $d_1$ is the remainder when $(n-d_0)/s$ is divided by $s$. This is determined completely by $n$. But then the next digit is the remainder when $(n-d_0-d_1s)/s^2$ is divided by $s$, again completely determined by $n$. And so on.

Existence can be proved in the same way. Let $d_0$ be the remainder when $n$ is divided by $s$. Then $n=ms+d_0$, and by induction hypothesis $m$ has a representation.

share|improve this answer

This is a variation of "another way" by André Nicolas, proving existence and existence at uniqueness at the same time. The main reason I write this answer is that I feel that any complete proof should explicitly use in the uniqueness part the fact that a leading digit "$0$" is forbidden, and in the existence part that $s>1$. So the statement to prove is:

For $s\in\mathbb N$ with $s>1$ and any $a\in\mathbb N$ there exists a unique sequence $(a_{k-1},\ldots,a_0)$ with $k\in\mathbb N$ and $a_i\in\{0,\ldots,s-1\}$ for $0\leq i<k$, and $a_{k-1}\neq0$ if $k>0$, such that $a=\sum_{0\leq i<k}a_is^i$.

For all $n>0$ one has $sn>n$ (since $s>1$) so for every $m>0$ the quotient $\lfloor\frac ms\rfloor$ of the Eucliedean division of $m$ by $s$ is strictly smaller than $m$; this will allow us to do a strong induction on $a$ in which the induction hypothesis applies to $\lfloor\frac as\rfloor$.

The case $a=0$ needs separate consideration; the empty sequence ($k=0$) is a solution, and it is unique since for any sequence with $k>0$ the requirement $a_{k-1}\neq0$ implies $\sum_{0\leq i<k}a_is^i>0$. Now assume $a>0$ and by strong induction that the unique existence has been proved for $q=\lfloor\frac as\rfloor$. Writing $a=sq+r$ one has $r=a\bmod s$ (the remainder of Euclidean division) and for any solution $a=\sum_{0\leq i<k}a_is^i$, now obviously with $k>0$, one has $a\equiv a_0\pmod s$; therefore $a_0=r$ by the requirement $a_0\in\{0,\ldots,s-1\}$. Given that fact, the condition $a=\sum_{0\leq i<k}a_is^i$ is equivalent to $\sum_{1\leq i<k}a_is^{i-1}=\lfloor\frac as\rfloor=q$, which by the induction hypothesis has a unique solution $(a_{k-1},\ldots,a_1)$. If $k=1$ one has $a_{k-1}=a_0=a\neq0$ by assumption, and if $k>1$ then $a_{k-1}\neq0$ is part of the requirement for a solution for $q$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.