# Why is the carry of any n base system equal to the radix in arithmetic?

In binary the carry/borrow is 2, in hex the carry is 16. What's the reason for this?

Background

Writing a number in base $$r$$ means to write it in the form

$$a_0+a_1r+a_2r^2+\ldots+a_nr^n$$

where $$0\leq a_i< r$$, for all $$i=0,1,\ldots,n$$. The positional notation that we use consists in just writing the digits $$a_i$$ from right to left

$$(a_na_{n-1}\ldots a_2a_1a_0)_r$$

Some people write parentheses and maybe the radix as a subscript. Some people write a bar over the digits, and in the decimal positional system, which is the most popular, we just write the digits.

You can think of the digits as buckets that can only be filled up to the value $$r-1$$.

The carry actually depends on the position of the digit, only that when you compute you imagine that it is the degree zero position, the units. Actually, when you are inside algorithms like adding or converting numbers from one radix to another in each iteration you have already divided enough by $$r$$ such that the digit that you are treating has become the degree zero position or you are treating it as such.

The carry at the $$k$$-th position

For example, suppose that you are looking at position $$k$$ and the digits at that position and the one that follows are

$$a_kr^k+a_{k+1}r^{k+1}$$

You can divide by $$r^k$$ to get $$a_k+a_{k+1}r$$, which implicitly is what happened if we just write the two digits $$(a_ka_{k+1})_r$$.

Now, the maximum carry will happen when $$a_k$$ is as full as it can be and we add to it the maximum digit that we can add. This is $$a_k=r-1$$ and we add $$r-1$$. Then we get

\begin{align} (a_k+a_{k+1}r)+(r-1)&=(r-1)+a_{k+1}r+(r-1)\\ &=(r-2)+\mathbf{r}+a_{k+1}r\\ &=(r-2)+(a_{k+1}+1)r \end{align}

As you can see, it is $$\mathbf{r}$$ the amount that we have to move out of the $$k$$-th position to re-write the number as a sum of powers of $$r$$ in which the coefficients are all between $$0$$ and $$r-1$$. Well, it is really $$r\cdot r^k$$, because we divided by $$r^k$$. In terms of the contribution to the next ($$k+1$$-th) digit the carry contributes $$1$$, when carry over happens. Otherwise it contributes $$0$$ to the next digit.

Potentially, $$a_{k+1}+1$$ is larger than $$r-1$$, so $$(a_{k+1}+1)r$$ will have to spit out an $$r^2$$ (actually $$r^2\cdot r^k$$), but well that's the carry generated by the $$(k+1)$$-th position.