初中数学竞赛精品标准教程及练习69：数的整除(三) (2).pdf

1 初 中数学竞赛精品标准教程及练习 69 数的整除 三 一 内容提要一 内容提要 在第 1 讲 数的整除 一 和 44 讲 数的整除 二 中 分别介绍了数的整除特征和 运用因式分解法解答数的整除问题 本讲介绍应用 同余 方面的知识 一 同余的概念 两个整数 a 和 b 被同一个正整数 m 除 所得的余数相同时 称 a b 关于模 m 同余 记作 a b mod m 如 8 和 15 除以 7 同余 1 记作 8 15 mod 7 读作 8 和 15 关于模 7 同余 2003 7 286 1 2003 1 mod 7 7 和 6 对于模 13 同余 6 余数是非负数 7 6 mod 13 35 和 0 除以 5 余数都是 0 即都能整除 35 0 mod 5 二 用同余式判定数的整除 若 a b mod m 则 m a b 即 a b 0 mod m m a b 例如 11 25 mod 7 7 25 11 或 7 11 25 25 35 2 3 0 mod 5 5 25 35 三 同余的性质 注意同余式与等式在变形中的异同点 1 传递性 mod mod mod mca mcb mba 2 可加可乘性 mod mod mod mod mbdac mdbca mdc mba 推论 可移性 a b c mod m a b c mod m 可倍性 a b mod m ka kb mod m k 为正整数 可乘方 a b mod m an bn mod m n 为正整数 3 当 d 是 a b m 的正公因数时 a b mod m d b d a mod d m 如 2 是 20 26 6 的正公因数 20 26 mod 6 1310 mod 3 四 根据抽屉原则 任给 m 1 个整数 其中至少有两个数对于模 m 同余 即至少有两个 其差能被 m 整除 例如 任给 5 个数 a b c d e 其中至少有两个 它们的差能被 4 整除 除以 4 的余数只有 0 1 2 3 四种 5 个数除以 4 至少有两个同余 2 二 例题二 例题 例 1 已知 69 90 125 除以正整数 n 有相同的余数 求 n 的值 解 69 90 mod n 90 125 mod n n 90 69 n 125 90 而 21 35 的最大公约数是 7 记作 21 35 7 7 是质数 n 7 例 2 求 388除以 5 的余数 解 38 3 mod 5 388 38 32 4 1 4 1 mod 5 注意 9 除以 5 余 4 1 除以 5 也是余 4 32 1 mod 5 例 3 求 9 9 7的个位数字 解 74k n与 7n的个位数字相同 且 9 1 mod 4 99 19 1 mod 4 9 9 7与 71的个位数字相同都是 7 例 4 求证 7 22225555 55552222 证明 22225555 55552222 22225 1111 55552 1111 2222 7 317 3 5555 7 793 4 2222 3 mod 7 5555 4 mod 7 22225 35 5 mod 7 55552 42 2 mod 7 22225 55552 5 2 0 mod 7 即 22225 55552 mod 7 22225 1111 55552 1111 55552 1111 mod 7 22225555 55552222 0 mod 7 7 22225555 55552222 例 5 求使 32n 1 能被 5 整除的一切自然数 n 解 32 1 mod 5 32 n 1 n mod 5 32n 1 1 n 1 mod 5 当且仅当 n 为偶数时 1 n 1 0 使 32n 1 能被 5 整除的一切自然数 n 是非负偶数 例 6 已知 a b c 是三个互不相等的正整数 求证 a3b ab3 b3c bc3 c3a ca3三个数中 至少有一个数能被 10 整除 证明 用同余式判定整除法证明 当正整数 n 的个位数是 0 1 4 5 6 9 时 n3 的个位数也是 0 1 4 5 6 9 这时 n3 n mod 10 当正整数 n 的未位数为 2 3 7 8 时 n3 的个位数分别是 8 7 3 2 8 与 2 7 与 3 3 与 7 2 与 8 除以 10 是同余数 这时 n3 n mod 10 把三个正整数 a b c 按个位数的情况 分为上述两类时 则至少有两个 3 属于同一类 设 a b 的末位数是同一类 那么 a3b ab3 ab ab 0 mod 10 或 a3b ab3 a b a b 0 mod 10 10 a3b ab3 三 三 练习练习 69 1 三个数 33 45 69 除以正整数 N 有相同余数 但余数不是 0 那么 N 2 求 7 7 7的个位数字 3 求37 92 45 除以 19 的余数 41989除以 9 的余数 4 求 19891990 1990 的余数 5 四个数 2836 4582 5164 6522 都被同一个正整数除 所得的余数都相同且不是 0 求除数和余数 6 求证 7 33334444 44443333 7 已知 正整数 n 2 求证 31111 个n mod 4 8 任给 8 个整数 其中必有两个 它们的差能被 7 整除 试证之 9 求使 2n 1 能被 3 整除的一切自然数 n 10 已知 69 90 125 除以 N N 1 有同余数 那么对于同样的 N 81 同余于 A 3 B 4 C 5 D 7 E 8 三 三 练习练习 69 参考答案 参考答案 1 N 12 6 2 舍去 3 余数是 0 解法仿例 1 2 个位数字是 3 7 1 mod 4 7 7 7 1 7 7 mod 4 仿例 3 3 余数是 18 和 1 37 1 mod 19 原式 1 18 mod 19 41989 43 663 64 1 mod 9 64663 1663 1 4 余数是 1 1989 1 mod 1990 19891990 1 1990 1 mod 1990 5 根据题意 2836 4582 5164 6522 r mod m 而且 4582 2836 1746 6522 5164 1358 m 1746 且 m 1358 1746 1358 2 97 m 194 97 2 2 不合题意 舍去 答 除数为 194 余数是 120 或除数为 97 余数是 23 6 33334444 44443333 14444 1 3333 0 mod 7 7 个个2 11111111 nn 00 11 11 3 mod 4 8 8 个正整数分别除以 7 必有两个或两个以上是同余数 9 2 1 mod 3 2n 1 n mod 3 2n 1 1 n 1 mod 3 当且仅当 n 奇数时 1 n 1 0 能被 3 整除的一切正整数 n 是奇数 4 10 B 。