# Conversion to other basis

#### evinda

##### Well-known member
MHB Site Helper
Hello!!! We consider the usual representation of non-negative integers, where the digits correspond to consecutive powers of the basis in a decreasing order.
Show that at such a representation, for the conversion of a number with basis $p$ to a system with basis $q$, where $p=q^n$ and $n$ positive integer, it suffices that each digit of the number is expressed from initial system of basis $p$ to the system of basis $q$, using $n$ digits of the system of basis $q$.
Also the rule should be stated and it should be proved at the reverse case, i.e. when the conversion is done from the system of basis $q$ to the system of basis $p$.

Could you give me a hint how we could show this? • Klaas van Aarsen

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Hey evinda !!

So we have a number like $p_0 + p_1\cdot p + p_2\cdot p^2 +\ldots$ yes?
And we have $p=q^n$ so that number is the same as $p_0 + p_1\cdot q^n + p_2\cdot q^{2n} +\ldots$.
That is a representation in the system with basis $q$ isn't it? So if we needed $m$ digits to represent the number in the system with basis $p$, we can represent the number with $m$ digits in the system with basis $q$ as well. • evinda

#### evinda

##### Well-known member
MHB Site Helper
Hey evinda !!

So we have a number like $p_0 + p_1\cdot p + p_2\cdot p^2 +\ldots$ yes?
And we have $p=q^n$ so that number is the same as $p_0 + p_1\cdot q^n + p_2\cdot q^{2n} +\ldots$.
That is a representation in the system with basis $q$ isn't it? Yes, it is... But how do we know that the coefficients $p_0,p_1, \dots$ are also based on the system of basis $q$ ? So if we needed $m$ digits to represent the number in the system with basis $p$, we can represent the number with $m$ digits in the system with basis $q$ as well. Yes, but we need to show that $n$ digits suffice, right? #### Klaas van Aarsen

##### MHB Seeker
Staff member
Yes, it is... But how do we know that the coefficients $p_0,p_1, \dots$ are also based on the system of basis $q$ ?
Didn't we just show that? We effectively wrote the same number with respect to the system with basis $q$, didn't we? Yes, but we need to show that $n$ digits suffice, right?
Could it be that's a mistake in the problem statement?

Consider for example that $p=100$ and $q=10$. So $n=2$.
We can represent the number $10203$ with respect to $p$ as $123$, and we can represent the same number with respect to $q$ as $10203$.
In this case we need $m=3$ digits to represent the number and $n=2$ digits does not suffice to represent the number. Last edited:
• evinda

#### evinda

##### Well-known member
MHB Site Helper
Didn't we just show that? We efectively wrote the same number with respect to the system with basis $q$, didn't we? Do we know that $p_0,p_1,p_2, \dots$ are also written in the system with basis $q$, since $p=q^n$ and so $p<q$ ?

Could it be that's a mistake in the problem statement?

Consider for example that $p=100$ and $q=10$. So $n=2$.
We can represent the number $10203$ with respect to $p$ as $123$, and we can represent the same number with respect to $q$ as $10203$.
In this case we need $m=3$ digits to represent the number and $n=2$ digits does not suffice to represent the number. We have that $\frac{10203}{100}=102 \cdot 100+3$ and so $10203=1023$ with respect to $100$ and $\frac{10203}{10}=1020 \cdot 10+3$ and so $10203=10203$ with respect to $10$, right? #### Klaas van Aarsen

##### MHB Seeker
Staff member
Do we know that $p_0,p_1,p_2, \dots$ are also written in the system with basis $q$, since $p=q^n$ and so $p<q$ ?
More or less. It means that the digits with respect to $q$ are the same - except that there are $n-1$ zeroes in between each of the digits. We have that $\frac{10203}{100}=102 \cdot 100+3$ and so $10203=1023$ with respect to $100$ and $\frac{10203}{10}=1020 \cdot 10+3$ and so $10203=10203$ with respect to $10$, right? More accurately, we have $10203=1\cdot 100^2+2\cdot 100^1+3\cdot 100^0$ with respect to $p=100$.
And we have $10203=1\cdot 10^4+0\cdot 10^3 + 2\cdot 10^2+0\cdot 10^1 + 3\cdot 10^0$ with respect to $q=10$. • evinda

#### evinda

##### Well-known member
MHB Site Helper
Didn't we just show that? We effectively wrote the same number with respect to the system with basis $q$, didn't we? Could it be that's a mistake in the problem statement?

Consider for example that $p=100$ and $q=10$. So $n=2$.
We can represent the number $10203$ with respect to $p$ as $123$, and we can represent the same number with respect to $q$ as $10203$.
In this case we need $m=3$ digits to represent the number and $n=2$ digits does not suffice to represent the number. Is it maybe meant that each digit of the number is expressed with $n$ digits of the system $q$ ?

For example in this case $3$ is written as $03$, $2$ as $02$ and $1$ to $01=1$.

So since $p=q^n$ it means that each digit in the $p$-system corresponds to $n$ digits of the $q$-system.

But is this statement sufficient when we want to prove that for the conversion of a number from the $p$-system to the $q$-system that then it suffices that each digit of the number is expressed using $n$ digits of the $q$-system?

#### evinda

##### Well-known member
MHB Site Helper
Also the rule should be stated and it should be proved at the reverse case, i.e. when the conversion is done from the system of basis $q$ to the system of basis $p$.

Could you give me a hint how we could show this? For the reverse case, we begin from the end and we pick consecutively $n$-digits at the $q$-system that correspond to one digit of the $p$-system. At the beginning, we might need to add 0s to get $n$ digits. Right? How could this rule be proved? #### Klaas van Aarsen

##### MHB Seeker
Staff member
Is it maybe meant that each digit of the number is expressed with $n$ digits of the system $q$ ?

For example in this case $3$ is written as $03$, $2$ as $02$ and $1$ to $01=1$.

So since $p=q^n$ it means that each digit in the $p$-system corresponds to $n$ digits of the $q$-system.

But is this statement sufficient when we want to prove that for the conversion of a number from the $p$-system to the $q$-system that then it suffices that each digit of the number is expressed using $n$ digits of the $q$-system?
Ah right. That makes more sense. So we start with a number $p_0 + p_1 \cdot p^1 + p_2\cdot p^2 + \ldots$, which is equal to $p_0 + p_1 \cdot q^n + p_2\cdot q^{2n} + \ldots$.
We have that each $p_i$ is between $0$ and $p-1=q^n-1$.
So each of the $p_i$ can be written as an n-digit number with respect to $q$.
That is, we can write $p_i = q_{i0} + q_{i1} q^1 +\ldots + q_{i(n-1)} q^{n-1}$ with appropriate $q_{ij}$. For the reverse case, we begin from the end and we pick consecutively $n$-digits at the $q$-system that correspond to one digit of the $p$-system. At the beginning, we might need to add 0s to get $n$ digits. Right? How could this rule be proved?
We can start with the general number $q_0+q_1 \cdot q^1+q_2\cdot q^2+\ldots$.
Now we can group those terms in groups of $n$, can't we? And each group corresponds to a digit with respect to $p$. • evinda

#### evinda

##### Well-known member
MHB Site Helper
Ah right. That makes more sense. So we start with a number $p_0 + p_1 \cdot p^1 + p_2\cdot p^2 + \ldots$, which is equal to $p_0 + p_1 \cdot q^n + p_2\cdot q^{2n} + \ldots$.
We have that each $p_i$ is between $0$ and $p-1=q^n-1$.
So each of the $p_i$ can be written as an n-digit number with respect to $q$.
That is, we can write $p_i = q_{i0} + q_{i1} q^1 +\ldots + q_{i(n-1)} q^{n-1}$ with appropriate $q_{ij}$. I see! We can start with the general number $q_0+q_1 \cdot q^1+q_2\cdot q^2+\ldots$.
Now we can group those terms in groups of $n$, can't we? And each group corresponds to a digit with respect to $p$. I understand!!! Thank you very much!!! • Klaas van Aarsen