主题:俺十岁时琢磨出来的一个算术方面的小规律... 看看哪位能给证明一哈? -- 煮酒正熟
其实只要不“降”到10以内,“降”到20以内,适用范围就无限啦。
现在是在十进制下讨论问题。如果当年你考虑考虑二进制,就有点LRC的感觉了,那就真是天才的发现了。
等于满足了结合律。比如定义这个运算为P,X Y为任意两个自然数,
P(X+Y) = P(X) + P(Y)
如果满足,那么一切问题都简单了。比如自然数A,B总能分解为一个9的倍数和一个小于9的自然数之和,
A = a*9 + p, p<9
B = b*9 + q, q<9
A*B = C
P(A)*P(B) = P(a*9 + p) * P(b*9 + q)
= (P(a*9) + P(p)) * (P(b*9) + P(q))
计算过程比较复杂,这里忽略。但是P(p) = p, P(q) = q, 而且任何9的倍数算到底都是9。这个运算有个容易被忽略的性质,不自觉地就在继续。很容易得出
= 9 + pq
注意,这仅仅是个中间结果。这个结果实际等同于
= P(9 + pq)
回头看C,显然,
C = a*b*9*9 + a*9 + b*9 + pq
P(C) = P(a*b*9*9 + a*9 + b*9 + pq) = P(a*b*9*9 + a*9 + b*9) + P(pq) = 9 + P(pq)
= P(9 + pq)
两边一起接着算下去,当然相等了。
符号:
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).
繁琐, 一点都不优美了.
秋水龙泉的证明倒是会的。
只限于十进制。
看你说的这么郑重,我特地多看了两遍,还是没看出这运算中有什么问题啊。。。
西河三年某月某日,赵括成功地邀请到小非侠共进晚餐。
把一个数的各位相加(然后再相加、再相加……),最后的结果就是它被9除的余数。这可以用高斯开创的同余理论容易证明(关键是10^n-1总可以被9除尽)。
所以你的算术规律可以表示为:余数之和等于和的余数,余数之差等于差的余数,余数之积等于积的余数。
证明总是(相对)容易的,发现才是最难最难的啊!