0

In the book "Algebra" by Gelfand, I have read a solution to a problem which assumes something that does not seem evident to me. Let's see:

Problem 2. In the addition example:

  A A A +
  B B B =
---------
A A A C

all A's denote some digit, all B’s denote another digit and C denotes a third digit. What are these digits?

Solution. First of all A denotes 1 because no other digit can appear as a carry in the thousands position of the result. [...]

How do the authors know that?

Eleno
  • 103
  • When adding two digits, and possibly a carried 1, the result can be no larger than 19. Therefore the largest digit which may carry is a 1. – David P Mar 20 '16 at 00:05
  • This is a consequence of having two summands. If we were adding more than two numbers, the carry could be greater than one. – hardmath Mar 20 '16 at 00:43

2 Answers2

3

Since $AAA \le 999$ and $BBB \le 999$, necessarily their sum is smaller or equal to $999+999 = 1998$. So the thousands digit must be at most $1$.

Crostul
  • 36,738
  • 4
  • 36
  • 72
0

In general, it might be easier to think of two digits as always having a carry digit when they are summed, where the carry digit is either $0$ or $1$. Let $a$, $b$, and $r$ be positive integers with $r>1$. Then the radix-$r$ expansions of $a$ and $b$ are $a=(a_{n-1}a_{n-2}...a_1a_0)_r$ and $b=(b_{n-1}b_{n-1}...b_1b_0)_r$, where initial digits of zero are added if necessary to make both expansions the same length of $n$ digits. Furthermore, $0\le a_j\le r-1$ and $0\le b_j\le r-1$ for $j = 0,1,...,n-1$. When we add $a$ and $b$ we obtain the sum $$a+b = \sum_{j=0}^{n-1}a_jr^j\ +\ \sum_{j=0}^{n-1}b_jr^j\ =\ \sum_{j=0}^{n-1}(a_j+b_j)r^j$$

By the division algorithm, there exist integers $C_0$ and $s_0$ such that $$a_0+b_0\ =\ C_0r+s_0,\ 0\le s_0\le r-1$$

To see that $C_0$, the carry digit to the next place, cannot exceed $1$, note that we can rewrite the previous inequality as $$-r+1\le -s_0\le0$$

Also, since $a_0$ and $b_0$ are non-negative integers not exceeding $r$, it follows that $$0\le a_0 + b_0 \le 2r-2$$ $$0\le C_0r + s_0 \le 2r-2$$

When adding two digits $a_j+b_j$, there are two cases to consider: $a_j+b_j<r$, and $a_j+b_j\ge r$. In the first case we have the following $$0\le C_0r+s_0\le r-1$$ $$-r+1\le C_0r\le r-1$$ $$-r<C_0r<r$$ $$-1<C_0<1$$ Since $C_0$ is an integer, we have $C_0=0$. In the case where $a_j+b_j\ge r$ we have the following $$r\le C_0r+s_0\le 2r-2$$ $$1\le C_0r\le 2r-2$$ $$1\le C_0r<2r$$ Since $r$ is a positive integer we have $1\le C_0<2$, and since $C_0$ is an integer it follows that $C_0=1$. Thus, $C_0=0$ or $C_0=1$. To prove that every carry digit $C_i$ is either $0$ or $1$ for $0\le i\le n-1$, we can use induction. The base case, where $i=0$, has already been proven. For the induction step, assume that the $C_{i-1}$ carry digit is $0$ or $1$. Because $0\le a_i\le r-1$ and $0\le b_i\le r-1$, and because $0\le C_{i-1}\le 1$ we have $$0\le a_i+b_i+C_{i-1}\le 2r-1$$ Again, using the division algorithm, we know there exist integers $C_i$ and $s_i$ such that $$a_i+b_i+C_{i-1}\ =\ C_ir+s_i,\ 0\le s_i\le r-1$$ When $a_i+b_i+C_{i-1}<r$ it follows that $$0\le C_ir+s_i\le r-1$$ $$-r+1\le C_ir\le r-1$$ $$-r<C_ir<r$$ $$-1<C_i<1$$ Since $C_i$ is an integer, $C_i$ must be equal to zero. When $a_i+b_i+C_{i-1}\ge r$ we have the following $$r\le C_ir+s_i\le 2r-1$$ $$1\le C_ir\le 2r-1$$ $$1\le C_ir<2r$$ Since $r$ and $C_i$ are integers with $r>1$, it follows that $C_i=1$. Thus, the carry digit $C_i$ is $0$ or $1$ for all $0\le i\le n-1$. $\square$

For a more intuitive explanation, consider any two digits of base-r. Since a digit in base-r can never exceed r (e.g. base 10 digits go up to 9, base 2 go up to 1, etc), adding two digits of base-r will always produce a value that is strictly less than 2r. That is $a+b<2r$, or $a+b\le 2r-1\ =\ (1)r+(r-1)$. You can think of the $(1)$ coefficient as the carry and the $(r-1)$ as the sum.

Display name
  • 829