加载中…
当正整数A与B互质时，用A和B表示不出的最大数为A*B-A-B
(2006-11-10 09:45:15)| 分类： 小学奥数专题讲解 |
当正整数A与B互质时，用A和B表示不出的最大数为A*B-A-B。(9:45:22)
证明：(9:45:29)
两个互质的数A、B（无论是否相差为1），最小公倍数为AB。(9:45:37)
设a(n)为使式子a(n)B mod A = n成立的最小正整数， (9:45:45)
其中n从1到A-1。可以证明，0<a(n)<A。(9:45:55)
显然a(n)不可能为A的倍数。(9:46:13)
如果a(n)>A，则有a(n)B mod A = (a(n)-A)B mod A = n， (9:46:42)
：即a(n)-A也是使以上式子成立的正整数，但显然比a(n)小，(9:46:54)
因此不是最小正整数。所以a(n)<A。(9:47:03)
令n从1到A-1，由于所有的a(n)都小于A且显然各不相同(9:47:19)
不可能同一个数除以A能得到两个不同的余数），(9:47:29)
所以a(1)到a(A-1)就是1到A-1的一个排列。(9:47:44)
这时，我们考察所有大于AB数X，(9:47:58)
X=AB+mA+n，n为X除以A的余数。(9:48:07)
我们先用B个A表示AB，m个A表示mA。(9:48:19)
这时我们将把其中一些A换成B，使得余数n消失。(9:48:29)
由上面的式子，a(n)B = pA + n，因此，可以用a(n)个B替换掉p个A。 (9:48:43)
而显然这时，pA=a(n)B-n<AB，即p<B，因此有足够的A被替换掉。(9:48:54)
就是说，凡是大于AB的数都可以用A与B表示。(9:49:13)
设A>B(9:49:23)
进一步考察X小于AB但大于AB-A时的情况。(9:49:31)
此时X=(B-1)A+n，n为X除以A的余数。(9:49:41)
先用B-1个A凑成(B-1)A。(9:49:53)
然后我们将把其中一些A换成B，使得余数n消失。(9:50:07)
由上面的式子，a(n)B = pA + n，因此，可以用a(n)个B替换掉p个A。 (9:50:23)
而显然这时，pA=a(n)B-n<AB，即p<B，因此有足够的A（B-1个足够了）被替换掉。(9:50:35)
因此，AB-A到AB之间的数可以用A、B表示。(9:50:50)
又显然AB-A是A的倍数，可以用A表示。(9:51:01)
由于a(n)>0，而小于AB且大于AB-A的数都可以用若干个A及至少1个B表示出来，(9:51:16)
因此将这些数都减掉一个B也能表示出来。(9:51:25)
即大于AB-A-B但小于AB-B的数都用A、B表示得出来。(9:51:34)
又由于A>B，所以AB-B>AB-A，即大于AB-A-B但小于AB-A的数都能表示出来。(9:51:48)
也就是说凡大于AB-A-B的数都能表示出来。(9:51:59)
假设AB-A-B可以用A和B表示，即AB-A-B=mA+nB，(9:52:17)
移项可得(B-m-1)*A=(n+1)*B，而n+1>0，(9:52:50)
也就是说等式两边不为0。(9:53:00)
根据n+1<=A且A、B互质，只能有A=n+1，B-m-1=B，得出m=-1，(9:53:22)
与前提矛盾。(9:53:28)
所以，AB-A-B无法用A、B表示。(9:53:37)
喜欢
0
赠金笔
前一篇：有趣的逻辑推理题：囚犯求生
后一篇：课间休息与孩子娱乐