在集合{1,2,…,50}的子集S中,任意两个元素的平方和不是7的倍数,求|S|的最大值。
答案
将集合中的数按照对7取的余数分为7类,考虑余数为1~7的数的平方对7取余数,依次为1、4、2、2、4、1、0。
则两个元素的平方和为7的倍数要求两个数的平方各自对7取余数都为0,即两个数都是7的倍数。
所以S中不能出现2个对7取余为0的数。{1,2,…,50}中有7个7的倍数,所以S最多可以包含所有对7取余不为0的数以及1个对7取余为0的数,即|S|的最大值=50-7+1=44.
答案
将集合中的数按照对7取的余数分为7类,考虑余数为1~7的数的平方对7取余数,依次为1、4、2、2、4、1、0。
则两个元素的平方和为7的倍数要求两个数的平方各自对7取余数都为0,即两个数都是7的倍数。
所以S中不能出现2个对7取余为0的数。{1,2,…,50}中有7个7的倍数,所以S最多可以包含所有对7取余不为0的数以及1个对7取余为0的数,即|S|的最大值=50-7+1=44.