课间休息时，n个学生围着老师坐成一圈做游戏，老师按顺时针方向并按下列规则给学生们发糖：他选择一个学生并给一块糖，隔一个学生给下一个学生一块，再隔2个学生给下一个学生

Question

课间休息时，n个学生围着老师坐成一圈做游戏，老师按顺时针方向并按下列规则给学生们发糖：他选择一个学生并给一块糖，隔一个学生给下一个学生一块，再隔2个学生给下一个学生一块，再隔3个学生给下一个学生一块…．试确定n的值，使最后(也许绕许多圈)所有学生每人至少有一块糖．

Answer 1

解析：
问题等价于确定正整数n，使同余式1＋2＋3＋…＋x＝a(modn)                        (1)对任意正整数a都有解．我们证明当且仅当n是2的方幂时，(1)式总有解．若n不是2的方幂，则n有奇素因数p．由于1，1＋2，1＋2＋3，…，1＋2＋…＋(p－1)，1＋2＋…＋p至多表示mod p的p－1个剩余类(最后两个数在同一个剩余类中)，所以1＋2＋…＋x也至多表示mod p的p－1个剩余类，从而总有a使1＋2＋…＋x≡a(mod p)无解，这时(1)也无解．若n＝2k(k≥1)，考察下列各数：0×1，1×2，2×3，…，(2k－1)2k                                 (2)设x(x＋1)≡y(y＋1)、(mod 2k＋1)，其中0≤x，y≤2k－1，则x2－y2＋x－y≡(x－y)(x＋y＋1)≡0(mod 2k＋1)因为x－y，x＋y＋1中，一个是奇数，一个是偶数，所以x－y≡0(mod2k＋1)或x＋y＋1≡0(mod 2k＋1)由后者得：2k＋1≤x＋y＋1≤2k－1＋2k－1＋1＝2k＋1－1矛盾．故  x≡y(mod 2k＋1)，即x＝y．因此(2)中的2k个偶数mod 2k＋1互不同余，从而对任意整数a，方程x(x＋1)≡2a(mod 2n)有解，即(1)有解．