# Special avatar of Division Algorithm

Definition Given integer $$a$$ and $$b$$, with $$a>1$$, there exist integer $$r$$

Let W be the function , function define as follows

$$W(a,b)=r$$

Where $$r=r_1+r_2+...+r_{m+1}$$ And

$$a\cdot q_1=b+r_1$$ $$a\cdot q_2=q_1+r_2$$ $$a\cdot q_3=q_2+r_3$$ $$\vdots$$ $$a\cdot q_{m+1}=q_m+r_{m+1}=a$$ Up to $$q_{m+1}=1$$

And

$$0\leq r_i for $$i={1,2,...,m+1}$$.

More simply

$$a^{m+1}=b+r_1+ar_2+a^2r_3+...+a^mr_{m+1}$$

For example $$W(5,17)=4$$.

Here are some More interesting properties which I already proved

$$r+b=1 \mod a-1$$

$$W(odd,odd)=even$$

$$W(odd,even)=odd$$

I want more information on such type of function/algorithm. Properties of this type of function which deep connection with number theory. its really helpfull for me.

• Could you be more precise please. Like what are the lines $aq = b + r$ Euclidean division ? PS : For Tex use {} and not () for $q_{m+1}$ Commented Mar 1, 2019 at 18:22
• @Bleuderk now is it ok Commented Mar 1, 2019 at 18:57
• For the case of $a=2$, this seems highly related to 2's complement: en.wikipedia.org/wiki/Two%27s_complement where in your case the equation is $-b = r_1+ar_2+a^2r_3+...+a^mr_{m+1} - a^{m+1}$. Commented Mar 1, 2019 at 19:14
• @antkam thanks, But not getting the expected results Commented Mar 1, 2019 at 19:58
• perhaps you can explain where 2's complement do not give expected results (when $a=2$)? then i can perhaps understand the differences between that and what you're looking for... Commented Mar 1, 2019 at 20:02

This answer assumes $$b>0$$. Also, while this does not give useful references, it does map the original problem into a very well-known related problem.

Take $$m$$ to be the smallest integer s.t. $$a^{m+1} \ge b$$, i.e. $$m = \lceil \log{b}/\log{a} \rceil - 1$$.

As you said, $$a^{m+1}=b+r_1+ar_2+a^2r_3+...+a^mr_{m+1}$$.

Rearranging, we get: $$(a^{m+1} - b) = r_{m+1} a^m + ... + r_3 a^2 + r_2 a^1 + r_1 a^0$$.

In other words, the sequence of $$m+1$$ digits $$(r_{m+1}, ..., r_3, r_2, r_1)$$ is the representation of the non-negative integer $$(a^{m+1} - b)$$ in base $$a$$, and so $$W(a,b) =r=$$ the digit sum in this base-$$a$$ representation.

E.g. for $$a=5, b=17$$ we have:

• $$m+1 = 2$$ since $$5^2 > 17$$

• $$a^{m+1} - b = 5^2 - 17 = 25-17 = 8 = 13_5$$ (i.e. $$13$$ in base $$5$$).

• Sum of digits $$W(5,17) = r = 1+3 = 4$$ as desired.

E.g. proof that $$b + r = 1 \mod (a-1)$$:

• $$a^k \mod (a-1) = 1^k \mod (a-1) = 1$$ for any $$k$$

• So $$\mod (a-1)$$ we have: $$r = \sum r_k = r_{m+1} a^m + ... + r_3 a^2 + r_2 a^1 + r_1 a^0 = (a^{m+1} - b) = 1 - b$$.

You can probably prove many more interesting things about $$W(a,b)$$ based on understanding it as the digit sum of $$(a^{m+1} - b)$$ in base $$a$$.

• Actually I know this information. But I'm looking more Deep reference Commented Mar 2, 2019 at 2:19
• haha, oh well. so you're really looking for references on the digit sum (for any given base $a$)? interesting... Commented Mar 2, 2019 at 2:48