西西河

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

共:💬75 🌺99
全看树展主题 · 分页首页 上页
/ 5
下页 末页
家园 我觉得是我文中表述有点问题

其实只要不“降”到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除尽)。

所以你的算术规律可以表示为:余数之和等于和的余数,余数之差等于差的余数,余数之积等于积的余数。

证明总是(相对)容易的,发现才是最难最难的啊!

全看树展主题 · 分页首页 上页
/ 5
下页 末页


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河