第 36 讲 同 余同余是数论中的重要概念，同余理论是研究整数问题的重要工具之一。设 m 是一个给定的正整数，如果两个整数 a 与 b 用 m 除所得的余数相同，则称 a 与 b 对模同余，记作，否则，就说 a 与 b 对模 m 不同余，记作，显然，；1、 同余是一种等价关系，即有自反性、对称性、传递性1).反身性：；2).对称性：；3). 传递性：若，则;2、加、减、乘、乘方运算若 （mod m） （mod m）则 （mod m），（mod m），（mod m）3、除法设 （mod m）则 （mod）。A 类例题 例 1．证明： 一个数的各位数字的和被 9 除的余数等于这个数被 9 除的余数。分析 20≡2(mod9)，500≡5(mod9)，7000≡7(mod9)，……，由于 10n－1=9M，则10n≡1(mod9)，故 an×10n≡an (mod9)。可以考虑把此数变为多项式表示 an×10n+ an-1×10n-1+…+ a1×10+a0后处理。证明 设 a==an×10n+ an-1×10n-1+…+ a1×10+a0， 10≡1(mod9)，∴10n≡1(mod9)，∴an×10n+ an-1×10n-1+…+ a1×10+a0≡an+ an-1+…+ a1+a0。说明 要熟练记忆并应用常见的数据模的特征。例 2．A，B 两人玩一种 32 张扑克牌的取牌游戏，A 先取，以后轮流进行，每次只能从剩下的牌中取 1 张，或者质数张牌，谁取到最后一张牌获胜，问：谁有必胜策略？分析 原有 32 张牌，如果 A 总取奇数张牌，B 只要取 1 张牌，使 A 面临偶数张牌就可以了，此时 A 总不能取完偶数张牌。但 2 是质数，A 可以取两张牌。注意到 32 是 4 的倍数，A 只能取奇数张牌或 2 张牌，B 的应对方案稍作调整，可以有必胜的策略。解 B 有必胜策略。由于 32≡0（mod 4），而 A 取的牌不能是 4 及其倍数，从而 A 取后，剩下的牌张数 x≡3（mod 4），或x≡2（mod 4），或 x≡1（mod 4），于是 B 可以通过取 1，2 或 3 张牌，使得剩下的牌的张数 y≡0（mod 4），用心 爱心 专心1所以，B 依次此策略，在 A 取后，剩下的牌张数不同余于 0（mod 4），总是有牌，而 B取后剩下的牌的张数 y≡0（mod 4），从而 B 能取到最后一张牌。例 3 在已知数列 1，4，8，10，16，19，21，25，30，43 中，相邻若干数之和，能被 11 整除的数组共有多少组。分析 相邻若干数之和可通过，中来实现。解 记数列各对应项为并记 依次 为 1 、 5 、 13 、 23 、 39 、 58 、 79 、 104 、 134 、 177 它 们 被...
