Unique représentation of number.

Number representation in some system is given below:

$x = a_0 + a_1 m_0 + a_2 m_0 m_1 + ....a_l m_0 m_1 \cdots m_l$

where $m_0,m_1,\cdots, m_l $ are positive prime numbers grater than equal to 2.

For the sake of contradiction, assume that $x = b_0 + b_1 m_0 + b_2 m_0 m_1 + ....b_l m_0 m_1 \cdots m_l$ is a different representation of $x$.

subtract the above two equations, we will get

$0=(a_0-b_0) + (a_1-b_1)m_0 + \cdots (a_l-b_l)m_0m_1...m_l$ but we know that $0=0 + 0m_0 + 0m_0m_1 + ...+0m_0m_1..m_l$

so each $a_i = b_i$ and this prove that there will be unique representation for number $x$.

Question : Is the above proof correct?

  • $\begingroup$ Actually no. It is true that $0=0 + 0m_0 + 0m_0m_1 + ...+0m_0m_1..m_l$, but what you need to show is that this is the only solution to the equation $c_0 + c_1 m_0 + c_2 m_0m_1 + ...+c_{l+1} m_0m_1..m_l=0$. $\endgroup$ – Phil. Z Nov 24 '17 at 8:26

It is not a proof, and it is not in fact true. For example, taking $m_1=2, m_2=3$ we have:

For example $15=1+1\cdot 2+2\cdot 2\cdot 3=3+3\cdot 2+1\cdot 2 \cdot 3$

For uniqueness you need also to specify $0\le a_r \lt m_{r+1}$

Then you have $a_0+m_1 d=b_0+m_1e$ and $a_o-b_0$ is a multiple of $m_1$ and cannot be as large as $m_1$ or s small as $-m_1$ so must be zero. Then divide through by $m_1$ to get also $d=e$. Repeat the argument with $a_1, b_1, m_2$ or construct an induction.


Your Answer

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