Math Core

Digit problems look like puzzles, but they are really algebra and modular arithmetic in disguise. The trick is always to write the number out as a polynomial in its base, $\underline{a}\,\underline{b}\,\underline{c} = 100a + 10b + c$ , and then use two facts: the digit sum controls the remainder mod $b - 1$ , and digits are small, which gives tight bounds.

Base $b$ as a polynomial

A number written $\underline{d_k} \cdots \underline{d_1}\,\underline{d_0}$ in base $b$ means

$N = d_k b^k + \cdots + d_1 b + d_0, \qquad 0 \le d_i \le b - 1, \quad d_k \ne 0.$

This representation exists and is unique: $d_0$ is forced to be $N \bmod b$ , then repeat with $\lfloor N / b \rfloor$ . A number $N$ has exactly $k + 1$ digits in base $b$ when $b^k \le N < b^{k+1}$ , i.e. $k = \lfloor \log_b N \rfloor$ .

Problems like " $\underline{3}\,\underline{5}\,\underline{2}_b = 2 \cdot \underline{1}\,\underline{6}\,\underline{5}_b$ " become polynomial equations in $b$ . Remember that every digit must be less than $b$ .

Digit sums and remainders

Digit sums

Let $s_b(N)$ be the sum of the base- $b$ digits of $N$ . Then

$N \equiv s_b(N) \pmod{b - 1}, \qquad N \equiv d_0 - d_1 + d_2 - \cdots \pmod{b + 1}.$

In base $10$ : $N \equiv S(N) \pmod 9$ and $N \equiv$ alternating digit sum $\pmod{11}$ .

Why. $b \equiv 1 \pmod{b-1}$ , so every $b^i \equiv 1$ and $N = \sum d_i b^i \equiv \sum d_i$ . Similarly $b \equiv -1 \pmod{b+1}$ , so $b^i \equiv (-1)^i$ .

Two consequences you will use constantly:

$N - S(N)$ is always a multiple of $9$ .
$S(N)$ is small. A number below $10^k$ has digit sum at most $9k$ . So in an equation like $n + S(n) = 2026$ , you know $n$ is within $28$ or so of $2026$ .

Carries

When you add two numbers digit by digit, each carry replaces $10$ in one column by $1$ in the next, so it lowers the total digit sum by $9$ :

$S(a + b) = S(a) + S(b) - 9 \cdot (\text{number of carries}).$

For doubling, a digit $d$ produces a carry exactly when $d \ge 5$ (and a carry never causes a second one, since $2d + 1 \le 19$ ). So $S(2n) = 2S(n) - 9c$ , where $c$ is the number of digits of $n$ that are at least $5$ . The same carry counting in base $p$ is the heart of Kummer's theorem in the $p$ -adic module.

Trailing zeros in base $b$

The number of trailing zeros of $N$ in base $b$ is the largest $k$ with $b^k \mid N$ . For $b = p_1^{e_1} \cdots$ , that is the minimum over primes $p_i \mid b$ of $\left\lfloor v_{p_i}(N) / e_i \right\rfloor$ , where $v_p(N)$ is the exponent of $p$ in $N$ . For factorials, $v_p(n!)$ comes from Legendre's formula.

Worked example: An equation in the base

Is there a base $b$ in which $\underline{2}\,\underline{4}\,\underline{1}_b = 3 \cdot \underline{5}\,\underline{2}_b$ ?

$2b^2 + 4b + 1 = 3(5b + 2) = 15b + 6$ , so $2b^2 - 11b - 5 = 0$ , $(2b + 1)(b - 5) = 0$ , $b = 5$ . But the digit $5$ is not allowed in base $5$ . So there is no such base. Always check the digit constraint.

Worked example: Digit algebra

A two-digit number is $4$ times the sum of its digits. What can it be?

$10a + b = 4(a + b) \Rightarrow 6a = 3b \Rightarrow b = 2a$ . So the numbers are $12, 24, 36, 48$ .

Worked example: Digit sum plus bounding

Find all $n$ with $n + S(n) = 1000$ .

Mod $9$ : $n + S(n) \equiv 2n \equiv 1000 \equiv 1$ , so $n \equiv 5 \pmod 9$ . Also $n < 1000$ has $S(n) \le 27$ , so $n \ge 973$ . The numbers $\equiv 5 \pmod 9$ from $973$ to $999$ are $977, 986, 995$ . Check: $977 + 23 = 1000$ ✓, $986 + 23 = 1009$ , $995 + 23 = 1018$ . So $n = 977$ only.

Worked example: How many digits

How many digits does $2^{100}$ have?

$\log_{10} 2^{100} = 100 \log_{10} 2 \approx 30.103$ , so $10^{30} \le 2^{100} < 10^{31}$ : it has $31$ digits.

Common mistake

The mod- $9$ trick only gives a necessary condition. It narrows the candidates; you still have to check each one, as in the $n + S(n) = 1000$ example, where two of the three candidates failed.

Practice

Practice 1

Find the base $b$ for which $\underline{3}\,\underline{5}\,\underline{2}_b = 2 \cdot \underline{1}\,\underline{6}\,\underline{5}_b$ .