给定整数，证明：存在n个互不相同的正整数组成的集合S，使得对S的任意两个不同的非空子集A，B，数 与 是互素的合数．（这里与分别表示有限数集的所有元素之和及元素

题型：不详难度：来源：

给定整数，证明：存在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元集合满足问题的全部要求．