Question

初等数论题 剩余类 同余 整除





Answer 1

T6得用抽屉原理。因为m的剩余类为[0],[1]...[m-1]共m个。如果m 个整数都不属于[0]。那么把m个数放入[1].[2]...[m-1]。必定有两个数在同一个剩余类里面。此时取在同一个剩余类里面的那两个数。这两个数的差必然在[0]里面。
T7同样用到抽屉原理: 考虑10的剩余类[0],[1]...[9].把55个数放入这10个剩余类里面。必然每个剩余类里面至少有5个数。必然存在一个剩余类，其至少有6个数。考虑极端情况;如果每个剩余类里面都没有两个数差为10，则任意剩余类里面两个数的差至少为20。又在1~100内。每个剩余类的数个数上限为10个。每个剩余类里面至少有5个。考虑[k]。(k是0~9中任意给定的整数)。其中至少有如下5个整数：s.s+20.s+40.s+60.s+80.那么此时如果再有一个数n在这个剩余类里面。n必然介于上面5个整数之间。那么n与这两个数的差必为10。这样，在某个含有6个数的剩余类中。必然存在两个数的差为10。用同样的方法考虑差为12的情况。12的剩余类为[0].[1]...[11]。 把55个数放入其中。每个剩余类必然有4个数，必然存在一个剩余类，其至少有5个数。。在1~100里面。[1]~[4]个剩余类的数的个数上限为9,其余的上限为8。考虑[k](k是0~11的任意给定整数)同样用上面的方法把差不是12的4个数摆出; s,s+24,s+48,s+72,s+96.此时再加一个数n进来。必然与其中两个数的差为12。
上面这种做法得到的是更强的结论：在(1,2...100)里面任取55个数。必然存在三个数。使得它们成公差为10或12的等差数列。
最后一个问题有点难。不过必然能整除n(n+1).
我想到了：记原来的合式为m,考虑2m=(2^1987+n^1987)+3^1987+(n-1)^1987+....+(n^1987+2^1987).+(1^1987+1^1987).我们知道: (n+2)|k^1987+(n+2-k)^1987.(这可直接由因式分解: 得出.)那么(n+2)|2m-2.又n+2＞2.必有n+2|m-1,那么必有n+2不整除m。这样就证完了。