Algorithm 版 (精华区)

发信人: sino (茶水), 信区: Algorithm
标  题: 覆盖同余式系(zz)
发信站: 哈工大紫丁香 (2002年08月28日21:15:15 星期三), 站内信件

【覆盖同余式系】

   有没有这样的k个同余式
                    n=a1(mod n1)
                    n=a2(mod n2)
                    ......
                    n=ak(mod nk)
   使得任一整数n至少满足其中之一?这是可以办到的.例如,任一整数n至少满足下
列6个同余式之一:
   (1) n=1 (mod 2)     (2) n=1 (mod 3)      (3) n=2 (mod 4)
   (4) n=4 (mod 8)     (5) n=0 (mod 12)     (6) n=8 (mod 24)
   可以检验如下:
       如果n为奇数,则适合(1).
       如果 n为偶数,则n必为下列形式之一:
   n=24m,24m+2,24m+4,24m+6,24m+8,24m+10,24m+12,24m+14,24m+16,24m+18,
24m+20,24m+22.其中m为任意整数.
       当 24m+4,24m+16,24m+22 时,适合(2)
       当 24m+2,24m+6,24m+10,24m+14,24m+18, 时,适合(3)
       当 24m+20 时,适合(4)
       当 24m,24m+12 时,适合(5)
       当 24m+8, 时,适合(6)
   这样的一祖同余式,称为覆盖同余式系.覆盖同余式系在数论中有很重要的应用
.例如,我们可以用它证明:存在一个正整数 k,使得
N=k2n+1对于每一个正整数n都是合数.
   首先,对于正整数n按照上面的覆盖同余式系进行分类.
       当n适合(1)时,n=2m+1,m为整数,于是N=k2n+1=2k4m+1,但是 4m=1(mod 3),
从而 N=2k+1 (mod 3)
   只要适当选择k满足2k+1=0 (mod 3),就可以使 N 能被3整除,因而 N 为合数.解
同余式 2k+1=0 (mod 3)得到 k=1 (mod 3).
   当n 适合(2)时,n=3m+1,m为整数.N=k2n+1=2k8m+1,但是 8m=1 (mod 7),从而 
N=2k+1 (mod 7).
   只要适当选择k满足2k+1=0 (mod 7),就可以使 N 能被7整除,因而 N 为合数.解
同余式 2k+1=0 (mod 7)得到 k=3 (mod 7).
同理,对于n 满足其余四个式子之一时,分别得出 k 应满足
   k=1 (mod 5),k=1 (mod 17),k=-1 (mod 13),k=16(mod 241)
   综上所述,只要k 满足下列同余式组
   k=1 (mod 3)
   k=1 (mod 5)
   k=3 (mod 7)
   k=-1 (mod 13)
   k=1 (mod 17)
   k=16 (mod 241)
就能对于任意正整数 n ,使得 N 能被3,5,7,13,17,241之一整除,即 N 为合数.
利用中国剩余定理可以解出上述同余式组的解为 k = 1207426 (mod 5592405 ) 即
 k=5592405t+1207426 .其中 t 为任意整 数.
取t=0,k=1207426,则有 N=1207426*2n+1,对于任何正整数 n 都是合数.
   覆盖同余式系不是唯一的.例如,下面的12个同余式也组成覆盖同余式系:
   n=1 (mod 3), n=2 (mod 4), n=5 (mod 6)
   n=4 (mod 8), n=0 (mod 9), n=0 (mod 12)
   n=0 (mod 16), n=3 (mod 18), n=3 (mod 24)
   n=33 (mod 36), n=8 (mod 48), n=15 (mod 72).
   一般地,如果覆盖同余式系
   n=a1(mod n1)
   n=a2(mod n2)
   ......
   n=ak(mod nk)
中,c=n1<n2<...<nk,则 c 越大,找到覆盖同余式系的难度越大.已经找到了 c=3,
6,8,10,14,18,20 所对应的覆盖同余式系.数 学家厄特希猜想:对于任意大的正整
数 c 都有覆盖同余式系存在.并悬赏500美元征求这个猜想的解决-------证明它或
推翻 它!
   厄特希还认为:当模 n1,n2,...nk都是大于1的各不相同的奇数时,这样的覆盖同
余式系是不存在的.但是数学家赛尔弗里 奇(J.L.Selfridge)则宁愿悬赏500美元征
求这种覆盖同余式系存在的例子.究竟如何,尚待解决.


--

                御剑乘风来，除魔天地间。
                有酒乐逍遥，无酒我亦癫。
                一饮尽江河，再饮吞日月。
                千杯醉不倒，唯我酒剑仙。
                

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.239.224]