# Uniqueness of an integer representation in an integer base

I'm trying to prove the uniqueness of representations of integers in integer bases and I'm doing so by contradictions. Let $a,d$ be natural numbers where $d>1$. A representation of $a$ in base $b$ is an expression of the form $a = a_0 d^0 + a_1 d^1 + \dots a_n d^n$ where $a_0, a_1 \dots a_n \in \mathbb{N}_0$ and $0 \leq a_i \leq d$ for all $i \leq n$ and $a_n \neq 0$.

I've assumed that there exists 2 such expressions and get the following

$$a = q_0 d^0 + q_1 d^1 \dots q_n d^n = p_0 d^0 + p_1 d^1 \dots p_n d^n$$ $$\iff (q_0 - p_0)d^0 + (q_1 - p_1) d^1 \dots (q_n - p_n) d^n = 0$$

Let $j$ be the first time that $p_j \neq q_j$ then

$$(q_j - p_j)d^j + (q_{j+1} - p_{j+1}) d^{j+1} \dots (q_n - p_n) d^n = 0$$

Now I need a contradiction here and I just can't see it. Any help would be appreciated.

• If $j$ is the first time that $p_j \neq q_j$, you can only conclude that $(q_0 - p_0)d^0 + \ldots + (q_{j - 1} - p_{j-1})d^{j-1} = 0$. – 0XLR Oct 6 '15 at 17:59
• Hm... maybe this is the wrong way to approach it then. Got any suggestions? I was thinking of dividing through by $d^j$ and maybe manipulating with that but not sure if it leads to anything. – Lundborg Oct 6 '15 at 18:00
• Without justification, you can't just assume that your two expressions both have 'degree' n. – CopyPasteIt May 7 '17 at 13:53

If $j=n$, you are done. Otherwise, consider your equation modulo $d^{j+1}$, getting $$(q_j-p_j)d^j \equiv 0\pmod{d^{j+1}}.$$ It follows that $q_j-p_j\equiv 0\pmod{d}$, which, given that $0\le p_j, q_j\lt d$, implies that $p_j = q_j$ (if the distance between two points in an interval is equal to the length of the interval then the interval is closed).

Edit in response to a question in the comments:

To do this without explicitly using modular arithmetic, something like this: since the RHS is zero, it is divisible by $d^{j+1}$, so the left-hand side must be as well. All terms on the left except the first are obviously divisible by $d^{j+1}$, so the first one must be as well. But for $(q_j-p_j)d^j$ to be divisible by $d^{j+1}$, it must be the case that $q_j-p_j$ is divisible by $d$; given that $0\le p_j, q_j\lt d$, this implies that $p_j = q_j$.

• Is there a way to do this without invoking modular arithmetic? – Lundborg Oct 6 '15 at 18:02
• Well, you can certainly talk your way around it: "The RHS is divisible by $d^{j+1}$, so the LHS is as well, so...". – rogerl Oct 6 '15 at 18:03
• I want to point out that before this answer works, @Neutronic needs to fix his equation by letting $j$ be the last time (instead of the first time) that $p_j \neq q_j$. Only then can he conclude his equation. – 0XLR Oct 6 '15 at 18:05
• rogerl I will give it a shot but I'm not entirely sure I see how that would go @ZeroXLR How does that make a difference? – Lundborg Oct 6 '15 at 18:07
• @ZeroXLR Yes, it will. Since the entire sum is zero, what remains after removing the zero terms must also sum to zero. – rogerl Oct 6 '15 at 18:12

Here is another proof by contradiction.

If there are whole numbers with two representations, then we are interested in the smallest such whole number $a$.

Represent $a$ in two different ways,

$a = q_0 d^0 + q_1 d^1 + \dots + q_n d^n = p_0 d^0 + p_1 d^1 + \dots + p_m d^m$

with both $q_n$ and $p_m$ not equal to zero and some coefficients not equal.

If you apply Euclidean division and divide by $d$, right off the bat you see that $q_0 = p_0$. So, you can write

$(a - q_0)/d = q_1 d^0 + q_2 d^1 + \dots + q_n d^{n-1} = p_1 d^0 + p_2 d^1 + \dots + p_m d^{m-1}$.

We know that $(a - q_0)/d$ is being represented in two different ways. But this number is also strictly less than $a$ since $d > 1$. This contradicts our assumption about $a$ being the smallest whole number without a unique representation.