酥 初等数论中的一个猜测 ( I) I 单 J夺 民 柯召 、 孙琦川猜测任意的 Zn一1个数(木文中的数均指整数) 中必有 n 个数的和为 n 整除 . 单蹲 证明 了这一猜测是正确的 . 这里的2 n 一1不能改成更小的数 , 因为在任意的2 n 一2 个数中未必能找到 n 个数 , 其和为 n 整除 . 例如在 n一 1 个 O与 n 一1 个 l (或与 n 互素的数 a )组成 的Zn 一2 个数 中 , 任意 n 个的和不被 n 整除 . 有趣的是 , 如果2 n 一2 个数中没有 n 个数的 和被 n 整除 , 那么这2 n 一2 个数基本上 就是上面所举的反例 . 这结论较柯召 、 孙琦的猜测 强 , 由它可得到柯召 、 孙琦猜侧的又 一证 明 . 确切地说 , 本文特证明下面的定理 及其推论 : 定理如果在 Zn一2个数中( n1) , 任 n 个数的和不被 n 整除 , 那么这Zn 一2个数 可分成两组 , 每组 : 一1 个数 , 分别同余于模 n 的 两个数 a , 乙 . 并且 ( 。 一吞 , n ) 一1 . 为了证明这个定理 , 需要几条引理 引理 i (K e mp e r m an 与 S e h e r k)设有 了 个不 同的剩余类 a。= 0 , a , a: , a , 一: (m o d n )及 个不 同的剩余类 b 。 二0 , b , , 乙 2 b :一, (m o d n ) , 并且在 i , j不同为0 日寸a ; +西 , 等 0(m o d 牡 ) , 则 a+ b , i0 , .1 二 : 一1 , 夕 二O , 1 , : 一1 . 中至少有mi n ( : , : 十:一l ) 个不同的剩余类( m o d n ) . 证明 : 这就是H . H a l b e rs a t m 与K . F . RO th t3 第一章的 T h . 巧 , 引理 2 如果 : 一1个数中任意个数的 和 (包括 仅一个数的情况 , 下同)不被 。 整 除 , 则这些数属于同一剩余类 a (m o d 儿 ) , 并且a ( , 。 )二1 . 证明 : 设 a , , a。 为其中二数 , 我们断定 a: 三 a: (m o d n ) , 事实上 卜 失 亡 、 0 , az , a l + a : , al + aZ + a 3 , , a一+a Z + a ,一 1 这 ” 个数互不同余(m ” d : ) , 否则它们的差同余于 0(m “ d n )与已知矛盾 因此它们是 、 mod 。 的完系 , 从而 。 2 必与其中之一同余 , 显然只能是 a Z 二 。: (m o d 。 ) 、 丫r 、 这就证明了 。一 1个数属于同一剩余类 : (m 。“: ) . 若 (。 , 。 ,一“, , 奋 ( :一 , , 这 。 一1 个数中的 子 个数的和为 n 整除矛盾 , 因此a ( , : )- 月月 一 色 l 弓1理 3 任意的 , 个数中一定可选出若干个数 , 它们的和被 。 整除 . 证明 : 即2中引理 2 . 由本文引理 2亦不难推出 . 引理 4 将 n一 1个数按照mo d 九 分类 , 设每一类至多有k个数 . 如果这 卜 1个数 中有若干个数的和被 n 整除 , 那么必可从这 : 一1 个数中选出( k十1个数 , 它们的和必 被 。 整除 . , 证明 : 考虑这 。一 1个数中的数所组成的被 n 整除的和 , 设其中最短的(即加数个 数最少的 )长为k : (即有k : 个加数) , 我们要证明k : 簇k十1 . 将这 。 一1 个数写成 x二x:x 3 x 止互 x工 x 2 x 3” . x IZ x上尤2 X3” x l 其 中每一列表示一个剩余类 , 并且同一类中的元素(至多k个)用同一字母表示 . l:l:夕l。 . 显然 八十l : 十十儿= n 一1 若 x: , “ 2, , x ,; 中有数属于零类 , 结论显然 , 故可设 x ; , x: 为 , 均不属于零类 . 令 x。= 0 , 如果有 x、: 十x 、: +十为 、 被 , 整除( 0 (i , 镇z , , 二1 , . 2 二 k ) , 并且 i , , i : 不全为0 , 那 么结论成立 , 因此可设“ , 十x : 十十: ,* 仅在i ; 二i:一 一 i*=。时被 : 整除 . 根据引理 1 . x ;: +: : (i ,= 0 , 1 , , l ; , i : 0 , J , l : ) 中至少有 l:十l : +1 个剩余类 (m od九 ) . 于是 x: + x: + :, (0(艺 。簇l: , t= 1 , 2 , 3) 中至少有l , +12+l。+1个剩余类(mod , ) . 依此类推 , x:+x: + , + x * (o( i ,成 l : , t二1 , 2 , k)中有 l:+1 2 +l+1 ,: 个剩余类( m od n ) , 即它们组成完系(m o d 。 ) . 于是 一x , 必与其中之一同余 , 设 一x , 三x , : 十 x ,: 十十羌 * (m odn ) 则上式右边必有 l , 个 x, (否则 x: + x * + x,三 0 (m o d n ) 从而 k 2( 几+1 , 结论成 立) . 我们把这样的和为 , +戈 : +十i x 称为(对 x , 是)满 的 . 今 现在考虑 魏 个数 0 , x l , x: 2x l , Zxf : 王z Zx r: (1) 无 x , , kx : kx z* 其中若有两类同余 : ,花x三 m x , ( m o d n ) 而m ,成 , , 那么在与 一x , 同余的剩余类“ : + x : 一卜 + x ;: 中可将 仇个x,换为 耐个 x , 化为对 x , 不满的和 , 而添上 x , 被 m整除 , 所以 花 2镇k + 1成立 . 假定(1)中两两不同余 , 那 么(1)构成完系(m o d n ) , 这时 x ,: + x,: (i ,沪 j Z) 必与 (1 ) 中某一类同余 , 若有 x s , + x,: 兰优 x , (m o d n ) 而 执)2 , 则仍可将与 一戈, 同余的 , (对义 , 是)满的和 x : + x, 换成不满的 , 导出结 论 . 假设对所有夕 : 举八 , 均有 x s: + 劣s:兰xs (m o d 。 ) 那么考虑和被 n 整除的无 : 个数 , 这时有三种情况 : (” 这和对所有 x , 都不是满的 , 则将其中两项之和 : ,: + x ,: 改为 x , 得到更短的 和被 : 整除 , 与k : 定义矛盾 . ( 2)这和仅对某个 x ,、 是满的 , 若 k Z )k月 一 1 , 则存在加数 x , : 子 x ,: , 和仍可缩短 , 矛 盾 。 ( 3)这和对 x ,: , :,: , , x ,。 是满的 , 则应用上面的方法将 x ,: 十x ,: 十 一卜 : , : 尽量缩 短 . 如摹其中出现x 2 ;:, 则将 x , 与另一项相加 , 即 2万 , + x ,: 兰x , 。十写, 三州 (m “ d 。 ) 最后化为一项 , 或者三项 x ,+ 城十川 , : , , 拼 , 群互不同余 , 并且 丫,十式= 丫; (m od” ) 但这时可先加出 x,+ x , , 若又有 戈,+x 梦 “ x: (m o d , ) 则 叉,+ 式+ 丫才= Zx丫兰 2斌 (m o d , ) 矛盾 , 所以幻+对二式 等式 (m o d n ) x , 十丫;+ 城二丫 + 式二丫扩 (m o d : ) 仍化为一项 . 总之 , 和的长k : 可以缩短 , 与k Z 定义矛盾 . 引理 4证毕 . 定理的证明 : 将 2。一2个数按 : 的剩余类分类 , 设其中最多的一类含k 。 个数 , 不 妨设这类为零类 (如果这一类为 a , 将 每一个数减去 a , 即化为这种情形)显 然 k o ( ” 一 1 . 若 k 。= 。一1, 则剩下的 。一1 个数中 , 任意个数的和不被 , 整除(否则添上若干 零 , 得 : 个数的和被 , 整除) , 由引理 2 , 结论成立 . 若k 。 ,一 1 , 则剩下的数的个数为 2刀一2一k 。 ) 2”一2一(卜2)书旅 所以其 一 中必有个数提 。 个数 , 其和为 n 整除(引理3) , 设长镇 : 的 、 被 n 整除的和中 最长的长为k : , 则 k l +k o n (否则有 , 个数的和为 , 整除)除去这k , +l 。 个数后剩下 2”一2一(k 工+ k 。 ) 犯一 1 个数 , 联其 中 。 一1个数 , 若这 , 一1个数中不存在被 , 整除的和 , 则由引理 2 , 它们在 同一类 , 与 k 。 , 一1矛盾 . 所以其中存在着被 。 整除的和 , 由引理 4 , 这种和的最短 长度k : ( k 。 +z , 于是 k , +k Z毛 k l +k o+ 1 刀 . 但这时有k ; +k:个数的和被 儿整 除 , 与k l 的定义矛盾 , 证毕 . 推论任意的 2 , 一 1个数中必有 , 个数的 和为 。 整除 . 证明 : 若在其中的 2 , 一2个数中 , 每 : 个数的和不为 杯整除 , 则由定理 , 这些数属 于两个剩余类 a , . b , 每个剩余类有 , 一1个数 . 将这 2”一2个数中任一数换为剩下的 一个数l如果这2 n 一2个数中有 n 个数的和为 九 整除 , 则结论成立 , 否则它们仍属于剩 余类 。 , b . 于是云类和 b类中有一类含 。 个数 , 它们的和显然为 。 整除 一 , “ 川 参考文狱 1 柯召 、 孙琦初等数论 10 0 例上海教育出版社 . 1979年版 . 2 单蹲 , 初等数论中的一个猜测 , 数学进展1 2卷 , 4(1983)p . 29 9一30 1 . 3H H a l be r s tam an dK . F . R o th , S e口u e旅c e s . V sl . l . (O x fo rd, 1966) P . 50一51 。