Different Representations to Number Base represent Different Integers

From ProofWiki
Jump to: navigation, search

Theorem

Let $k \in \Z$ such that $k \ge 2$.

Let $a$ and $b$ be representations of integers in base $k$ notation:

$a = \displaystyle \sum_{j \mathop = 0}^r a_j k^j$
$b = \displaystyle \sum_{j \mathop = 0}^s b_j k^j$

such that either:

$r \ne s$

or:

$\exists j \in \set {0, 1, \ldots, r}: a_j \ne b_j$


Then $a$ and $b$ represent different integers.


Proof

First suppose that $r \ne s$.

Without loss of generality, suppose $r > s$.

Then from Bounds for Integer Expressed in Base k:

\(\displaystyle a_r k^r\) \(>\) \(\displaystyle b\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle a\) \(>\) \(\displaystyle b\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle a\) \(\ne\) \(\displaystyle b\)


Otherwise $r = s$.


Let $l$ be the largest such that $a_l \ne b_l$.

Without loss of generality, suppose $a_l > b_l$.

For all $j > l$, let $a_1 = a - a_j k_j$ and $b_1 = b - b_j k_j$.

As $a_j = b_j$ in this range, $a_j k_j = b_j k_j$ and so the same amount is being subtracted from both.

So consider $\paren {a_l - b_l} k_l$.

From Bounds for Integer Expressed in Base k:

$\paren {a_l - b_l} k_l > \displaystyle \sum_{j \mathop = 0}^{l - 1} a_j k^j$

and:

$\paren {a_l - b_l} k_l > \displaystyle \sum_{j \mathop = 0}^{l - 1} b_j k^j$

and so $a_1 > b_1$.

Hence:

$a_1 + a_j k_j > b_1 + b_j k_j$

Hence $a \ne b$ and the result.

$\blacksquare$



Sources