~/writing/数学/数论 $ cat digit-sum-divisibility.md

数字之和的整除规律:从 3、9 到 N 进制

一个小学时发现、上了大学才会证明的规律

DATE
TAGS
数学 · 数论 · 证明
READ
5 分钟
NO.
004

前言

小学学数论时了解到了一个挺有意思的数论规律:

3 的倍数的各个位上的数字之和能被 3 整除。

那时小学正在学除法,了解这个规律以后我如获至宝,在一些涉及余数的选择题上所向披靡 (比如,我现在还记得的,给定一些数字,问从中选出哪些数的组合能被某个给定的数整除)。此后时常琢磨,还有没有哪些数也有类似的规律。

就这样从 1 开始一个个排除之后,我惊讶地发现,9 的倍数各个位上的数字之和能被 9 整除!

我拿着这个规律兴奋地找教数学的杨老师,她试了几个数发现确实如此,很是欣喜,却又无法满足我的好奇心:"也许你上初中就能解释了。"

同样的问题,初中数学老师研究了一晚上告诉我:"高中应该会讲这个内容,我有些忘了。"

高中时学进制系统,我在经验尝试后进一步把规律扩展为:

举些例子,在我们常用的十进制系统 下,比如 12331233 是 99 倍数,那么 S=1+2+3+3=9S = 1 + 2 + 3 + 3 = 9 正好能被 99 整除。

在一个七进制系统 下,比如 435(7)435_{(7)} 是 66 的倍数 (在十进制 下 435(7)435_{(7)} 为 222(10)222_{(10)} ),那么 S(7)=4(7)+3(7)+5(7)=15(7)=12(10)S_{(7)} = 4_{(7)} + 3_{(7)} + 5_{(7)} = 15_{(7)} = 12_{(10)} 正好能被 66 整除。这里要注意,一个数能否被另一个数整除是这个数固有的性质,与进制表示无关。

高中时数学不是特别好,数学老师劝我多把时间放在考纲内容里,这个规律就这样又被晾在了一边。

证明

叨逼叨逼这么多,这个规律的证明其实很简单(这也可能是为什么以前搜不出证明的原因),学习过 模运算 的相关知识就行了。

先把这个数按位展开:

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}

关键在于 N≡1(modN−1)N \equiv 1 \pmod{N-1},所以对任意 i≥1i \ge 1 都有 Ni−1≡1(modN−1)N^{i-1} \equiv 1 \pmod{N-1}。于是:

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}

因此,若 n(N)n_{(N)} 是 (N−1)(N-1) 的倍数(换句话说,n(N)≡0(modN−1)n_{(N)} \equiv 0 \pmod{N-1}),那么 ∑i=1kdi≡0(modN−1)\sum_{i=1}^{k} d_i \equiv 0 \pmod{N-1} 一定成立。

通过这个证明,我们可以进一步把规律总结为:

尾声

虽然是个很简单的定理证明,但是自己想出思路填完小学的坑感觉还是很满足。

PS: Hexo + MathJaX 真的很难用,我排版成这样已经尽力了…… 如果大家有什么问题可以留言。

2026-11-22 更新:用 Lean 4 形式化

最近 AI 在数学上的不少突破都借助了 Lean:证明写成代码,交给 Lean 逐步检查。最轰动的是这个月 Anthropic 的 Levent Alpöge 借助 Claude 给出了黎曼猜想的 Lean 4 证明1,并通过了 Lean 和 Mathlib 社区的验证2。

我也好奇,这样一个小学生都能发现的规律写成 Lean 是什么样子。下面的代码不依赖 Mathlib,思路和上面的手写证明一样:把 nn 拆成 b⋅⌊n/b⌋+(n mod b)b \cdot \lfloor n / b \rfloor + (n \bmod b);因为 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},再对 ⌊n/b⌋\lfloor n / b \rfloor 做归纳就行了。

LEAN
/-- n 在 b 进制下各位数字之和:每次取出最低位 n % b,再对 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)

/-- 关键一步:(m + 1) ≡ 1 (mod m),所以 (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]

/-- 定理:n 与它在 b 进制下的数字之和对 (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)

/-- 推论:n 是 (b - 1) 的倍数,当且仅当它的数字之和是 (b - 1) 的倍数。 -/
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₍₇₎,4 + 3 + 5 = 12

digitSum 就是正文里的 S(N)S_{(N)},dvd_iff_dvd_digitSum 就是最开始那条规律,最后两行算的是正文里的两个例子。把代码粘贴到 Lean 在线编辑器,下方只输出 9 和 12、没有报错,证明就通过了检查。

注释

  1. Levent Alpöge 于 2026-11-20 发布的说明:https://alpo.ge/remark.pdf;Lean 源码分卷压缩包(第一卷):https://alpo.ge/lean.tar.gz.part01。 ↩

  2. Lean 和 Mathlib 社区的联合声明(Lean FRO 与 Mathlib Initiative 背书,2026-11-21):Lean verification of the Riemann Hypothesis;社区的独立验证配置:leanprover-community/riemann-hypothesis;被证明的命题是 Mathlib 中的 RiemannHypothesis。 ↩

引用本文

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
}