Adding in different bases proof

[pendesu]

Homework Statement

Given that b>1,b\in\mathbb{Z},c_{0},c_{1},...,c_{m}\in\{0,...,b-1\}, 0\leq c_{m+1}\leq b-1, and
c_{m+1}b^{m+1}=(\sum\limits _{k=0}^{m+1}c_{k}b^{k})\text{mod }b^{m+2}-c_{0}-c_{1}b-c_{2}b^{2}-...-c_{m}b^{m}, show that c_{m+1}\in\mathbb{Z}.

Also,

\sum\limits _{k=0}^{n}c_{k}p^{k}=(\sum\limits _{k=0}^{n}(a_{k}+b_{k})p^{k})\text{mod }p^{n+1} where \{a_{k}\},\{b_{k}\}\subseteq\{0,...,b-1\} for n=0,1,2,...,m+1

Homework Equations

This problem was taken from adding numbers in a base other than 10. Some of the above in the case of what I am trying to prove holds n=0,1,2,... in terms of the upper limit of the sum. But, this is the core of what I am trying to show right now in order to complete a proof.

The Attempt at a Solution

Any help would be appreciated. I understand that given that this is true that b_(m+1) must divide the right hand side.

Been thinking about how to show this in general and even with specific examples, adding numbers in different bases as it relates to this, I have not yet been able to figure out exactly how this works out.

Came up with that I know that (\sum\limits _{k=0}^{m+1}c_{k}b^{k})\text{mod }b^{m+2}\geq c_{0}+c_{1}b+...+c_{m}b^{m} so I am thinking I could at least show this and maybe in doing so it may help me to come up with a way to show that c_(m+1) is in Z.

 

[chiro]

Hey pendesu and welcome to the forums.

The way to interpret this is that they are masking out the first m+1 digits from the base point (i.e. the . so since everything is an integer the first m+1 digits in some base from the right if it was written down the way we usually write numbers down).

By taking it mod the b^m+2 you are returning the part corresponding to m+1 digits.

So the first thing you need to do is show that by taking something mod the m+2, you get the expression corresponding to the first m+1 digits.

For the second one, I'm assuming you are adding two numbers and then creating a base decomposition of the result.

Again the identity is doing the same sort of thing with respect to the right digit.

This is a standard number theory problem where instead of say mod 10, you are doing mod 10^m+2. You can show this through the division theorem x = bq + r where r < 10^m+2 and that the r will always correspond to this.

Then the rest of isolating the term correspoding to b^m+1 is shown by subtracting the rest of the terms. You can show an inductive argument corresponding to isolating every single digit and even formalize this through the division theorem of x = bq + r for every appropriate r of b^g for g going from 1 to m if you want.

Then by subtracting out the terms you are left with only the digit at the 'm+1'th place which is your identity.

You can think of it as doing the following:

1) Start with a number x
2) Put it in some base (see DIV/MOD algorithm for how computers do this to give you more insight: it's exactly the same thing and has the same interpretation)
3) Remove the lowest digit by calculating z = x MOD b and then doing x = x - z, and x = x / b. This will create a new integer with 1 less digit with everything 'shifted' to the right.
4) Do this enough times until you get the lower digit to be the m+1'th digit.

Now if you simply do the MOD thing first to mask out the first m+1 digits, then you can apply the above until you have 1 digit left (you do the steps 2 to 4 m times). The expression you have is exactly what this algorithm is doing.

 

[pendesu]

I realized I typed my question incorrectly.

Given the following:

c_{0},c_{1},...,c_{m}\in\{0,...,b-1\} and \{a_{k}\},\{b_{k}\}\subseteq\{0,...,b-1\} and \sum\limits _{k=0}^{m+1}c_{k}b^{k}=(\sum\limits _{k=0}^{m+1}(a_{k}+b_{k})b^{k})\text{mod }b^{m+2} and 0\leq c_{m+1}\leq b-1, show that c_{m+1}\in\mathbb{Z}.

I am still having a hard time showing this. I realize that c_m+1 must at least be rational, I am just having a hard time getting a contradiction out the denominator of c_m+1 not being 1. This is related to research (undergraduate) that I am starting to do with p-adic integers. Any tips? Sorry I just don't know what else to really do right now.

 

[chiro]

I realized I typed my question incorrectly.

Given the following:

c_{0},c_{1},...,c_{m}\in\{0,...,b-1\} and \{a_{k}\},\{b_{k}\}\subseteq\{0,...,b-1\} and \sum\limits _{k=0}^{m+1}c_{k}b^{k}=(\sum\limits _{k=0}^{m+1}(a_{k}+b_{k})b^{k})\text{mod }b^{m+2} and 0\leq c_{m+1}\leq b-1, show that c_{m+1}\in\mathbb{Z}.

I am still having a hard time showing this. I realize that c_m+1 must at least be rational, I am just having a hard time getting a contradiction out the denominator of c_m+1 not being 1. This is related to research (undergraduate) that I am starting to do with p-adic integers. Any tips? Sorry I just don't know what else to really do right now.

Again this is just the DIV/MOD algorithm.

You can show that if the original quantity is an integer and the bases at each power are integers then the coeffecient weights of those bases are also integers.

You can formalize this through the division theorem where n = pq + r where q is some quotient and r is the remainder and p is the coeffecient when divided by q.

In terms of the modulus, we can write n MOD q = r if the above definition is to be used. In other words dividing q into n and getting the remainder is the modulus.

So whenever you see the modulus, think of the above expression. I've outlined the intuitive algorithmic explanation above, but just to clarify we are dealing with multiple modulus expression. So for example if our total number was 12345 = n then n MOD 10 = 5, n MOD 100 = 45, n MOD 100000 = 12345.

 

[pendesu]

Thought for a moment this morning that the following would be true but I don't think that it could be true for this case since a_{m+1}+b_{m+1} could be greater than b-1. The following is along the lines I was thinking but again I don't think in this case it would work out this way for the reason I gave above:

c_{0}+c_{1}b+...+c_{m}b^{m}+c_{m+1}b^{m+1}=((\sum _{k=0}^{m+1}(a_{k}+b_{k})b^{k})\text{mod }b^{m+2} =r where
\sum\limits _{k=0}^{m+1}(a_{k}+b_{k})b^{k}=b^{m+2}\cdot q+r from the division theorem so
r=\sum\limits _{k=0}^{m+1}(a_{k}+b_{k})b^{k})-b^{m+2}\cdot q.

c_{0}+c_{1}b+...+c_{m}b^{m}+c_{m+1}b^{m+1}=(a_{0}+b_{0})+...+(a_{m+1}+b_{m+1})b^{m+1}+(-q)b^{m+2}

Then, two polynomials are equal iff their coefficients are equal so c_{m+1}=a_{m+1}+b_{m+1}\in\mathbb{Z}

-------------
I think this would be adequate to show that it is in Z but there is the possibility of contradicting that c_{m+1} must be less than or equal to b-1.

--------------

I did go through the steps 1-4 you gave for an arbitrary number and I see how it cuts out the ending digit one at a time but in this case I am thinking since I would have to take c_{0}c_{1}...c_{m}c_{m+1} to be a number in base b that this would be presupposing that c_{m+1}\in\mathbb{Z}.

I might be too naive to understand how to do this.

I am open to suggestions or if my thinking is wrong somewhere.

 

[chiro]

Regarding the results for addition (i.e. a + b = c), the thing you need to factor is known as the carry. The carry is basically the number you carry over for each digit addition.

With regards to the carry, the maximum overflow you can have is one extra digit. So if I add say two 6 digit numbers, the maximum I will get is a 7 digit number.

Now with regard to your a0+b0, a1+b1, etc, if its respect to the same base b for a+b and for c, then this is incorrect in general, and the reason is the carry.

It's only correct when am+bm < b and it's incorrect otherwise because the moment there is some kind of overflow, you get the carry effecting some portion which needs to be taken into account.