高中数学竞赛讲义-同余 新人教A 版

用心 爱心 专心 1 27 27 同余同余 1 设 m 是一个给定的正整数 如果两个整数 a 与 b 用 m 除所得的余数相同 则称 a 与 b 对模同余 记作 modmba 否则 就说 a 与 b 对模 m 不同余 记作 modmba 显然 modbamZkbkmamba 每一个整数 a 恰与 1 2 m 这 m 个数中的某一个同余 2 同余的性质 1 反身性 modmaa 2 对称性 mod modmabmba 3 若 modmba modmcb 则 modmca 4 若 mod 11 mba mod 22 mba 则 mod 2121 mbbaa 特别是 mod modmkbkamba 5 若 mod 11 mba mod 22 mba 则 mod 2121 mbbaa 特别是 mod modmbkakZkmba 则 mod modmbaNnmba nn 则 6 mod macabcba 7 若 mod1 modmbamcmbcac 时 则当 mod mod mod mbamcbcac d m badmc 特别地 时 当 8 若 mod 1 mba mod 2 mba mod 3 mba mod n mba 且 mod 21 MbammmM n 则 例题讲解 1 证明 完全平方数模 4 同余于 0 或 1 2 证明对于任何整数0 k 1532 61616 kkk 能被 7 整除 用心 爱心 专心 2 3 试判断 282726 197319721971 能被 3 整除吗 4 能否把 1 2 1980 这 1980 个数分成四组 令每组数之和为 4321 SSSS 且满足 101010 342312 SSSSSS 5 在已知数列 1 4 8 10 16 19 21 25 30 43 中 相邻若干数之和 能被 11 整除 的数组共有多少组 6 设 nn nnn axaxaxaxaxf 1 1 2 2 1 10 是整系数多项式 证明 若没有整数根 整除 则都不能被 1992 1992 1 0 xffff 7 试求出一切可使12 n n被 3 整除的自然数n 8 在每张卡片上各写出 11111 到 99999 的五位数 然后把这些卡片按任意顺序排成一列 证明所得到的 444445 位数不可能是 2 的幂 9 设 21n aaa是任意一个具有性质 1 1 kaa kk 的正整数的无穷数列 求证可以 把这个数列的无穷多个 m a用适当的正整数 qpayaxayx qpm 表示为 用心 爱心 专心 3 例题答案 1 证明 122Zkknknn 或者是任一整数 则设 4 mod042 22 knkn时 当 4 mod1 1212 22 knkn 时 当 所以原命题成立 153322 1532 2 666 61616 kkk kkk M M证 令 7 mod0 7 mod1132 117373272 1 122327 11047 3 197 2 1156257293642 CBA kkk kkk 0Zkk 且对于1532 61616 kkk 都能被 7 整除 注 Zkbaba k mod1 mod1 整除 不能被 又 即 解 3197319721971 3 mod2 21 3 mod142 3 mod21 197319721971 3 mod210 197319721971 3 mod21973 3 mod11972 3 mod01971 3 282726 281428 28282726 282726282726 不能这样分组 产生矛盾 又 解 依题意可知 4 mod21981990 2 19811980 1980321 4 mod0604 302010 4 1 11114321 T ST SSSSSSSST 组 则满足条件的数组有 时 相邻项之和 且当是数列由于 由此可得 除的余数依次为 它们被 依次为 并记解 记数列各对应项为 7313 11 11 mod 11 mod 11 mod 11 mod 11 mod 11 mod 125236125111 177134104795839231351 10 2 1 5 973821041 1021 21 jk jkijk kki SS SSaSS SSSSSSSS SSS aaaSia 用心 爱心 专心 4 没有整数根产生矛盾 又 则 整除 不能被由题意 且有整数根证 假设 1992 321 1992 mod0 321 1992 mod 1992 mod 0 1992 19920 1992 mod 6 1 11 10 xf rfmfrf nirm nirm rm mramramramfrf rfmfrfmf rf rrmmxf ii ii n nnnn 整除 能被时 由上可知当且仅当 时 当 时 当 时 当 时 当 时 当 时 当 则及考虑到 则解 若 322616 3 mod02 66 2 210 66 3 mod1 13 160326 2 56 2 210 56 3 mod1 13 6496 2 46 2 210 46 3 mod02 36 2 210 36 3 mod2 13 824 2 26 2 210 26 3 mod2 13 212 2 16 2 210 16 2 3 mod22n12n 3 7 66 56 46 36 26 16 nn n kn kkn kkn kn kkn kkn n nkkn kn kkn kkn kkn kkn kkn kn kkn kkn kkn kkn kkn n 的幂 不可能是 即 又 注意到 则 排成的数为 证 记由 2 11111 mod0 88889511111 88889 2 9999911111 999991111211111 11111 mod 11111 mod110 11111 mod110 10101010 999991111211111 999991111211111 8 888898888821 888898888821 888898888821 55 88889 5 88888 444430 3 444435 2 444440 1 8888921 A A aaaa aaaa aaaaA Zk aaaaaA aaaaA A k i 用心 爱心 专心 5 是无限多个是满足题意的要求 且 令 属于该子数列 且 同时还有无限多个小的该子数列中必有一个最 为严格递增的