~/writing/math/number theory $ cat digit-sum-divisibility.md

Digit Sums and Divisibility: From 3 and 9 to Base N

A pattern I found in elementary school and only learned to prove in college

DATE
READ
6 MIN
NO.
003

Preface

Back in elementary school, when we were first taught a bit of number theory, I came across a rather neat rule:

If a number is a multiple of 3, its digits add up to a multiple of 3.

We were learning division at the time, and this felt like a treasure. It made me unbeatable on multiple-choice questions involving remainders — one type I still remember: given a handful of digits, which combination of them forms a multiple of some given number? From then on I kept wondering which other numbers had rules like this.

Working through them one by one starting from 1, I was delighted to find that the digits of a multiple of 9 also add up to a multiple of 9!

I took the rule to Ms. Yang, my math teacher, all excited. She tried a few numbers, saw that it held, and was pleased — but she couldn't satisfy my curiosity: "Maybe you'll be able to explain it once you get to junior high."

I put the same question to my junior high math teacher, who spent a whole evening on it and came back with: "I think this comes up in high school. I've forgotten some of it."

In high school I learned about number bases, and after playing around with a few examples I extended the rule to:

For example, in the decimal system we use every day, 12331233 is a multiple of 99, and S=1+2+3+3=9S=1+2+3+3=9 is indeed divisible by 99.

Or take a base-7 system: 435(7)435_{(7)} is a multiple of 66 (435(7)435_{(7)} is 222(10)222_{(10)} in decimal), and S(7)=4(7)+3(7)+5(7)=15(7)=12(10)S_{(7)} = 4_{(7)} + 3_{(7)} + 5_{(7)} = 15_{(7)} = 12_{(10)} is divisible by 66. It is worth noting here that whether one number is divisible by another is an intrinsic property of the number itself, and has nothing to do with the base it happens to be written in.

My math wasn't particularly good in high school, and my teacher advised me to spend the time on what was actually in the college entrance exam syllabus — so the rule got shelved once again.

Proof

After all that rambling: the proof is in fact quite simple (which may well be why I could never find one written down anywhere). A little familiarity with modular arithmetic is all it takes.

First, expand the number digit by digit:

n(N)=dkdk−1⋯d1‾(N)=∑i=1kdi⋅Ni−1n_{(N)} = \overline{d_k d_{k-1} \cdots d_1}_{(N)} = \sum_{i=1}^{k} d_i \cdot N^{i-1}

The key is that N≡1(modN−1)N \equiv 1 \pmod{N-1}, so Ni−1≡1(modN−1)N^{i-1} \equiv 1 \pmod{N-1} for every i≥1i \ge 1. Therefore:

n(N)≡∑i=1kdi⋅Ni−1≡∑i=1kdi⋅1≡∑i=1kdi(modN−1)\begin{aligned} n_{(N)} &\equiv \sum_{i=1}^{k} d_i \cdot N^{i-1} \\ &\equiv \sum_{i=1}^{k} d_i \cdot 1 \\ &\equiv \sum_{i=1}^{k} d_i \pmod{N-1} \end{aligned}

So if n(N)n_{(N)} is a multiple of (N−1)(N-1) — in other words, n(N)≡0(modN−1)n_{(N)} \equiv 0 \pmod{N-1} — then ∑i=1kdi≡0(modN−1)\sum_{i=1}^{k} d_i \equiv 0 \pmod{N-1} must hold as well.

The proof also lets us state the rule in a more general form:

Epilogue

It's a simple proof of a simple theorem, but working it out for myself and finally filling in a hole left over from elementary school still feels pretty satisfying.

PS: Hexo + MathJax really is painful to work with. This layout is the best I could manage... If you have any questions, feel free to leave a comment.

Update, 2026-11-22: formalizing it in Lean 4

A lot of AI's recent breakthroughs in mathematics run through Lean: the proof is written as code and Lean checks every step. The headline example is this month's Lean 4 proof of the Riemann hypothesis by Anthropic's Levent Alpöge, developed with Claude1 and verified by the Lean and Mathlib communities2.

I was curious what a rule simple enough for a kid to spot looks like in Lean. The code below doesn't use Mathlib and follows the handwritten proof above: write nn as b⋅⌊n/b⌋+(n mod b)b \cdot \lfloor n / b \rfloor + (n \bmod b); since b≡1(modb−1)b \equiv 1 \pmod{b-1}, n≡⌊n/b⌋+(n mod b)(modb−1)n \equiv \lfloor n / b \rfloor + (n \bmod b) \pmod{b-1}, and induction on ⌊n/b⌋\lfloor n / b \rfloor does the rest.

LEAN
/-- Sum of the digits of n in base b: take the last digit n % b, then recurse on n / b. -/
def digitSum (b n : Nat) : Nat :=
  if _h : 2 ≤ b ∧ 0 < n then n % b + digitSum b (n / b) else n
termination_by n
decreasing_by exact Nat.div_lt_self _h.2 (by omega)

/-- Key step: (m + 1) ≡ 1 (mod m), so (m + 1)·q + r ≡ q + r (mod m). -/
theorem step (m q r : Nat) : ((m + 1) * q + r) % m = (q + r) % m := by
  rw [Nat.add_mul, Nat.one_mul, Nat.add_assoc, Nat.mul_add_mod]

/-- Theorem: n and its base-b digit sum are congruent modulo (b - 1). -/
theorem digitSum_mod (b n : Nat) (hb : 2 ≤ b) :
    n % (b - 1) = digitSum b n % (b - 1) := by
  if hn : n = 0 then
    subst hn
    simp [digitSum]
  else
    have hpos : 0 < n := Nat.pos_of_ne_zero hn
    have ih := digitSum_mod b (n / b) hb
    rw [digitSum, dite_eq_left_of_eq_true (eq_true ⟨hb, hpos⟩)]
    obtain ⟨m, rfl⟩ : ∃ m, b = m + 1 := ⟨b - 1, by omega⟩
    simp only [Nat.add_sub_cancel] at ih ⊢
    calc n % m
        = ((m + 1) * (n / (m + 1)) + n % (m + 1)) % m := by rw [Nat.div_add_mod]
      _ = (n / (m + 1) + n % (m + 1)) % m := step m _ _
      _ = (digitSum (m + 1) (n / (m + 1)) + n % (m + 1)) % m := by
            rw [Nat.add_mod, ih, ← Nat.add_mod]
      _ = (n % (m + 1) + digitSum (m + 1) (n / (m + 1))) % m := by rw [Nat.add_comm]
termination_by n
decreasing_by exact Nat.div_lt_self hpos (by omega)

/-- Corollary: (b - 1) divides n if and only if it divides the digit sum of n. -/
theorem dvd_iff_dvd_digitSum (b n : Nat) (hb : 2 ≤ b) :
    (b - 1) ∣ n ↔ (b - 1) ∣ digitSum b n := by
  rw [Nat.dvd_iff_mod_eq_zero, Nat.dvd_iff_mod_eq_zero, digitSum_mod b n hb]

#eval digitSum 10 1233  -- 1 + 2 + 3 + 3 = 9
#eval digitSum 7 222    -- 222 = 435₍₇₎, and 4 + 3 + 5 = 12

digitSum is the S(N)S_{(N)} from the text, dvd_iff_dvd_digitSum is the original rule, and the last two lines compute the two examples above. Paste the code into the Lean online editor: if the only output is 9 and 12 with no errors, the proof checks out.

Notes

  1. Levent Alpöge's release note, 2026-11-20: https://alpo.ge/remark.pdf; the Lean source, as a split archive (first part): https://alpo.ge/lean.tar.gz.part01. ↩

  2. Joint statement by the Lean and Mathlib communities, endorsed by the Lean FRO and the Mathlib Initiative, 2026-11-21: Lean verification of the Riemann Hypothesis; the community's independent checking setup: leanprover-community/riemann-hypothesis; the theorem proved is Mathlib's RiemannHypothesis. ↩

Cite this post

BIBTEX
@misc{brandozhang2019college,
  title  = {Digit Sums and Divisibility: From 3 and 9 to Base N},
  author = {Brando ZHANG},
  year   = {2019},
  url    = {https://brando.dev/posts/digit-sum-divisibility/},
  month  = apr
}