Expanding Base 2B representation of an integer

46 Views Asked by At

Consider an integer$L$ written in Base 2B which digits

$$a_n a_{n-1} a_{n-2} ... a_1 B$$

Where $a_i$ are arbitrary constants such that $9 \le a_i < 2B$.

I am attempting to prove that the square of this integer $L$ will have ending digits equal to

$$\frac{B}{2}, 0$$ if B is even and:

$$\frac{B-1}{2}, B $$ when B is odd

and furthermore the leading chunk of digits will be equivalent to those of

$$\frac{L}{2m} \left(\frac{L}{2m} + 1\right)$$

Where the division is integer division (no remainders)

Naturally I opted to begin by considering $L^2$ modulo $(2B)^2$ to generate a solution to the initial clause involving even and odd $B$.

I proceeded by noting

$$L^2 = B^2 + 2Ba_1(2B)+ ... + a_n^2(2B)^{2n} $$

When expanding the multiplicands

Thus we can consider

$$B^2 + (2B)a_1 \mod 4B^2$$

So my first challenge is to absorb the $a_1$ and have it dissappear when considering this expression $\mod 4B^2$ No clue how to do this

Any suggestions where to take it from here?

1

There are 1 best solutions below

8
On BEST ANSWER

Hint. I would suggest using congruence notation from the start. We have $$L\equiv a_1(2B)+B\pmod{4B^2}$$ and so $$L^2\equiv a_1^2(4B^2)+2a_1(2B)B+B^2\equiv B^2\pmod{4B^2}\ .$$ Since $B^2<4B^2$, the last two digits of $L^2$ are $b_1,b_0$ where $$B^2=b_1(2B)+b_0\ .$$ We know that there will be only one possibility for $b_1,b_0$ within the range $0,1,\ldots,2B-1$, so if you can find by trial and error something that works, it must be the correct answer.


Edit... after a bit of clarifying the question. First note that any integer $n\ge1$ has a unique expansion in any base $m\ge2$. So if we check that the digits we want give the number we want, there is no need to spend any time showing that they are the only possibility.

So, what it comes down to is this: if $L$ has digits $a_n\cdots a_1B$ in base $2B$, you want to show that the digits of $L^2$ are the digits of $$\Bigl\lfloor\frac{L}{2B}\Bigr\rfloor\left(\Bigl\lfloor\frac{L}{2B}\Bigr\rfloor+1\right)\ ,$$ followed by two more digits as specified. Now $$L=a_n(2B)^n+\cdots+a_1(2B)+B$$ and so $$\frac{L}{2B}=a_n(2B)^{n-1}+\cdots+a_1+\frac{1}{2}$$ and $$\Bigl\lfloor\frac{L}{2B}\Bigr\rfloor=\frac{L}{2B}-\frac{1}{2}\ .$$ So, doing the case where $B$ is even, if we have the "leading chunk" followed by $B/2$ and $0$ we get $$\Bigl(\frac{L}{2B}-\frac{1}{2}\Bigr) \Bigl(\frac{L}{2B}-\frac{1}{2}+1\Bigr)(2B)^2 +\frac{B}{2}(2B)+0\ ,$$ which simplifies to $L^2$, and this is all you need.