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

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.这样就证完了.