题目内容
给定整数,证明:存在n个互不相同的正整数组成的集合S,使得对S的任意两个不同的非空子集A,B,数
与
是互素的合数.(这里与
分别表示有限数集
的所有元素之和及元素个数.)
见解析
解析:
我们用表示有限数集X中元素的算术平均.
第一步,我们证明,正整数的n元集合具有下述性质:对
的任意两个不同的非空子集A,B,有
.
证明:对任意,
,设正整数k满足
, ①
并设l是使的最小正整数.我们首先证明必有
.
事实上,设是A中最大的数,则由
,易知A中至多有
个元素,即
,故
.又由
的定义知
,故由①知
.特别地有
.
此外,显然,故由l的定义可知
.于是我们有
.
若,则
;否则有
,则
.
由于是A中最大元,故上式表明
.结合
即知
.
现在,若有的两个不同的非空子集A,B,使得
,则由上述证明知
,故
,但这等式两边分别是A,B的元素和,利用
易知必须A=B,矛盾.
第二步,设K是一个固定的正整数,,我们证明,对任何正整数x,正整数的n元集合
具有下述性质:对
的任意两个不同的非空子集A,B,数
与
是两个互素的整数.
事实上,由的定义易知,有
的两个子集
,满足
,
,且
. ②
显然及
都是整数,故由上式知
与
都是正整数.
现在设正整数d是与
的一个公约数,则
是d的倍数,
故由②可知,但由K的选取及
的构作可知,
是小于K的非零整数,故它是
的约数,从而
.再结合
及②可知d=1,故
与
互素.
第三步,我们证明,可选择正整数x,使得中的数都是合数.由于素数有无穷多个,
故可选择n个互不相同且均大于K的素数.将
中元素记为
,
则,且
(对
),
故由中国剩余定理可知,同余方程组
,
有正整数解.
任取这样一个解x,则相应的集合中每一项显然都是合数.结合第二步的结果,这一n元集合满足问题的全部要求.
