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.

  • $\begingroup$ 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$. $\endgroup$ – 0XLR Oct 6 '15 at 17:59
  • $\begingroup$ 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. $\endgroup$ – Lundborg Oct 6 '15 at 18:00
  • $\begingroup$ Without justification, you can't just assume that your two expressions both have 'degree' n. $\endgroup$ – 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$.

  • $\begingroup$ Is there a way to do this without invoking modular arithmetic? $\endgroup$ – Lundborg Oct 6 '15 at 18:02
  • $\begingroup$ Well, you can certainly talk your way around it: "The RHS is divisible by $d^{j+1}$, so the LHS is as well, so...". $\endgroup$ – rogerl Oct 6 '15 at 18:03
  • $\begingroup$ 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. $\endgroup$ – 0XLR Oct 6 '15 at 18:05
  • $\begingroup$ 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? $\endgroup$ – Lundborg Oct 6 '15 at 18:07
  • 1
    $\begingroup$ @ZeroXLR Yes, it will. Since the entire sum is zero, what remains after removing the zero terms must also sum to zero. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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