主题:俺十岁时琢磨出来的一个算术方面的小规律... 看看哪位能给证明一哈? -- 煮酒正熟
符号:
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).
- 相关回复 上下关系8
花~~~~~~ 1 大懒虫1号 字0 2006-03-30 04:16:09
佩服啊佩服。除了上花,别的事我干不了…… 1 王外马甲 字0 2006-03-30 03:18:13
王兄的佩服令弟汗颜无已 1 煮酒正熟 字29 2006-04-03 00:52:43
😄煮酒二大定理对任意进制都成立! 普适证明如下:
这个太牛了! 1 静静 字0 2006-03-30 14:23:52
😜花!!!尽管没看懂这些公式。。。 1 大懒虫1号 字0 2006-03-30 04:17:40
比我厉害。我的直觉也是如此,不过没这个证明的能力。 1 电子赵括 字0 2006-03-30 02:54:28
😄比我厉害。我的直觉是这种证明我根本想不到也做不出。 非 字40 2006-03-30 04:48:03