MO讲稿之同余（2）

1 MO 讲稿之同余 2 例例 1 设 设 n 是一个使是一个使不能被不能被 5 整除的自然数 求整除的自然数 求 333 21n 除以除以 5 的余数的余数 222 21n 解 设 有 333 12An 222 12An tZ 544 333 111 5 5 0 mod5 iii titii 544 222 111 5 5 0 mod5 iii titii 而当时 1 2 3r 333 111 5 5 0 mod5 rrr iii titii 因此当 或 时不能被 5 整除 5ntr tN 0t 1 2 3r A 对于或 通过计算 当时 tN 0t 51nt 1 mod5 B 当时 当时 52nt 0 mod5 B 53nt 4 mod5 B 故当 是使不能被 5 整除的自然数时 除以 5 的余数为 1 0 4 nAB 例例 2 证明 若 证明 若且且 则 则2 a nN 22 1 mod2 n n a 证明 对 作数学归纳法 设 n21ak 当时有 命题成立 1n 222 21 4 1 11 mod2 akk k 假设时 则由此可得 nk 22 1 mod2 k k a 22 12 k k aq qZ 故 1 2222222 12 121 mod2 kk kkk aaqQ QZ 所以时命题成立 1nk 2 例例 3 试求不大于 试求不大于 100 且使 且使成立的自然数成立的自然数 n 的和的和 11 374 nn 解 23 33 mod11 39 mod11 35 mod11 45 35 34 mod11 34 31 mod11 则通项为的数列的项的最小非负剩余系构成周期为 5 的周期数列 3n 3 9 5 4 1 3 9 5 4 1 1 类似的 通项为的数列的项的最小非负剩余系构成周期为 10 的周7n 期数列 7 5 2 3 10 4 6 9 8 1 2 于是由 1 和 2 可知 通项为的数列的项的最小非负剩374 nn 余构成了周期为 1 与 2 周期的最小公倍数 10 的周期数列 3 7 0 0 4 0 8 7 5 6 3 这说明 时 当且仅当时 110n 3 4 6n 3740 mod11 nn 由于 3 是模 11 的以 10 为周期的数列 故时满10110 1 knk 足条件的 有三个 则当时 其和为 n103 104 106kkk 1100n 999 000 103 104 106 3013 3013 10 1480 kkk kkkkk 例例 4 设 设 若 若是模是模 m 的一个简化剩余系 则证明 的一个简化剩余系 则证明 2m 12 m a aa mod0 21 maaa m 证明 因为模的任意互质的剩余类中的两个数对模同余 从而仅mm 需要对每一个都属于集合来进行讨论 不妨 1 i aim 1 2 1 m 设 首先 当时 不是 12 1 2 1 m a aam 2m 2 m 3 中的一个 这是因为当为奇数时 则 当为偶 12 m a aa m 2 m Z m 数时 此时 其次 若存在 使 且2m 1 22 mm m i1 2 i m a 则有 1 i a m 且 从而存在 使得 反过来也 1 i ma m 1 2 i m mam j ji ama 成立 这说明可以将两两配对 使得每一对的和为 便 12 m a aa m 得 12 0 mod m aaam 注 这个例子说明 当时 时偶数 2m m 例例 5 26 IMO 设 设 为正整数 为正整数 且且 令 令n 1n k 0kn 1 2 1 nM 给给中的每个数染上黑 白两种颜色中的一种 染法如下 中的每个数染上黑 白两种颜色中的一种 染法如下 M 1 对 对中每个中每个 与与同色 同色 Miini 2 对 对中的每个中的每个 与与同色同色Miik iik 证明 证明 中所有数必同色中所有数必同色 M 证明 为模 的一个完全剩余系 而 故可知0 1 2 1n n 1k n 也是模 的一个完全剩余系 设 0 2 1 kknk n mod i aikn 则必有 从而0 i an 011 0 1 2 1 n a aan 11 1 2 1 n aanM 对任意有 又知 12in 1 1 mod ii aaikikkn 1 0 ii a an 故可得 A 或 B 1ii aak 1ii aank 4 对于 A 由条件 2 与同色 故 11 iii aakak 1i a 1 i ak 有与同色 i a 1i a 对于 B 由条件 2 知 111 iiii aaknaknkna 与同色 再由条件 1 知与 即与同色 i a 1i na 1i a 1i na i a 1i a 因此 对任意 与同色 取 问题得证 12in i a 1i a 1 2 2in 例例 6 设 设 证明 证明 Zm d m dm 证明 设的标准分解为 则对的正约数 均可m 12 12 k k mp pp md 唯一的写成的形式 其中 故可得 12 12 k k dp pp 0 ii 12 12 00011 jj k iiiiii kk kjj d mjj dp pppp 1 11 1 1 j ii kk iiij jj ppppm 说明 1 这个证明使用了 若是互质的正整数 则 12 m m 1212 m mmm 2 累加 累乘符号的转换应很好的把握体会 例例 7 IMO 备选题 求备选题 求 8 个数个数具有性质 对于每个具有性质 对于每个 821 nnn Zkk 存在 存在 8 个整数个整数 每个数都属于 每个数都属于 使得 使得19851985 k 821 aaa 1 0 1 882211 nananak 证明 令是一切形如 1 M 2 012 333n n kaaaa 5 的数组成的集合 此处 显然有 1 0 1 i a 0 1 2 in 1 2 31 max 1 333 2 n n MH 1 2 31 min 1 333 2 n n MH 故中的每一个数都在与之间 MH H 又 1 中的每一个系数可取 3 个值 根据乘法原理 中共1 01 M 有个数公个数 因为中任意两数之差的绝对值不超过 1 3n 21H M2H 所以他们对模不同余 由定理 个整数是模的一个完全剩21H mm 余系的充要条件是 当时 中的数恰好是模ij mod ij aam M 的一个绝对最小完全剩余系 因此满足的任一整数都21H HkH 属于集合 因而可以唯一的表示为 的M 2 012 333n n kaaaa 形式 令 则 因此取7n 32801985H 7 128 1 3 3nnn 例例 8 IMO 以 以 A 表示表示 44444444的各位数字之和 的各位数字之和 B 表示表示 A 的各位的各位 数字之和 数字之和 C 表示表示 B 的各位数字之和 求的各位数字之和 求 C 分析 一个整数与它的各位数字之和模 9 同余 12k Na aa S N 事实上 12 121 101010 kk kk Naaaa 12 k S Naaa 而 12 121 101 101 10 1 kk k NS Naaa 1 1010 mod9 k 因此 本题可逐步求 A B C 对模 9 的余数进行估计 4444 4444 解 先估计 C 的位数 因为 而有位数 每位数字 44444444 444410000 4444 100004 4444 117777 6 不超过 9 故 A 故 A 最多有 6 位数字 且首位不超9过 1 于是 B 从而 B 最多有两位数字 且首位不超过1 5 946 4 于是 C 在计算 C 对模 9 的余数 4913 4444444444433 14811481 444477 77 7 7 9 38 1 7 mod9 而 C 故 C 7 44444444 44447ABC7 mod9 13 例例 9 设 设 n 是自然数 它不能被是自然数 它不能被 17 整除 求证整除 求证与与有且仅有有且仅有 8 1n 8 1n 一个数被一个数被 17 整除整除 证明 因 17 是素数 且 故 有费马小定理17 n 17 1n 即 则 即 17 1 1 mod17 n 16 10 mod17 n 88 1 1 0 mod17 nn 或者 而不能被 17 整 8 10 mod17 n 8 10 mod17 n 88 1 1 2nn 除 故与有且仅有一个数被 17 整除 8 1n 8 1n 例例 10 设 设 n 为正奇数 证明 存在为正奇数 证明 存在 2n 个整数个整数 使使 12 n a aa 12 n b bb 得对于任意的得对于任意的 下列 下列个数个数构成构成 kNkn 3n 1 1 nibbbaaa kiiiiii 模模 3n 的一个完全剩余系的一个完全剩余系 证明 令 则 均有 32 i ai 31 i bi 1 2 in kNkn 1 12 mod3 ii aa 0 mod3 ii ab 1 mod3 ii k bb 于是令 1 1 ii Aaain 1 ii Babin 1 ii k