主题：俺十岁时琢磨出来的一个算术方面的小规律... 看看哪位能给证明一哈？ -- 煮酒正熟

符号:

A_{xyz}表示 xyz是A的下标.

∑ 求和标志

mod(a,b) a除以b所得的余数 ∈{0, 1, ..., b-1}. 例如, mod(107,5)=2, mod(18,9)=0

d^n d的n次方

===========================

d进制下, 任一整数x皆可表为

(x_{n} x_{n-1} x_{n-2} ... x_2 x_1)

= ∑_{k=1到n} [x_k * d^(k-1)],

其中 x_k 为 x 的k位数, 0≤x_k＜d.

例如, 在十进制下, x_1是x的个位数, x_2是x的十位数; 321 = 3*100 + 2*10 + 1

定义映射 S: x → S(x) = ∑_{k=1到n} x_k,

即S(x)是x的数位和.

---------

引理1: mod(x,d-1) = mod(S(x),d-1)

证:

mod(d^m, d-1) = mod(((d-1)+1)^m, d-1)

= mod(∑_{k=0到m}[C(m,k)*(d-1)^k], d-1), 其中C(m,k)为二项式系数.

上式中,只有k=0的项才可能给出非零余数, 其为1, 这是因为C(m,0)=1. 所以我们得出

mod(d^m, d-1) = 1

因是故,

mod(x, d-1) = mod(∑_{k=1到n}[x_k*d^(k-1)], d-1)

= mod(∑_{k=1到n}[x_k*1], d-1)

= mod(S(x), d-1)

证毕.

---------

譬如在十进制下,引理1说的是: 一个整数与它数位之和对9同余.

定义映射 W: x → W(x)=S(...S(S(x))), 即:S映射的迭代, 直至W(x)＜d.

重复运用引理1, 可得

引理2: mod(x,d-1) = mod(W(x),d-1) = W(x)

最后一个等式是由于0≤W(x)＜d.

所以事实上 W映射值就是对d-1的余数算子.

最后, 由余数算子的特性, 易证[1]

mod(a+b, n) = mod(mod(a,n)+mod(b,n), n)......(i)

mod(a*b, n) = mod(mod(a,n)*mod(b,n), n)......(ii)

故而

W(x+y) = W(W(x)+W(y))

W(x*y) = W(W(x)*W(y))

证毕!

-----------------------------------

[1] 譬如,令 a = k*n + ra, b = j*n + rb

那么 mod(a+b, n) = mod(ra+rb, n) = mod(mod(a,n)+mod(b,n), n).