高中数学竞赛标准讲义：第十七章：整数问题新人教A版

用心 爱心 专心 第十七章第十七章 整数问题整数问题 一 常用定义定理 1 整除 设 a b Z a 0 如果存在 q Z 使得 b aq 那么称 b 可被 a 整除 记作 a b 且 称 b 是 a 的倍数 a 是 b 的约数 b 不能被 a 整除 记作 a b 2 带余数除法 设 a b 是两个给定的整数 a 0 那么 一定存在唯一一对整数 q 与 r 满 足 b aq r 0 r a 当 r 0 时 a b 3 辗转相除法 设 u0 u1是给定的两个整数 u1 0 u1 u0 由 2 可得下面 k 1 个等式 u0 q0u1 u2 0 u2 u1 u1 q1u2 u3 0 u3 u2 u2 q2u3 u4 0 u4 u3 uk 2 qk 2u1 uk 1 uk 0 uk uk 1 uk 1 qk 1uk 1 0 uk 11 且 n 为整数 则 k a k aa pppn 21 21 其中 pj j 1 2 k 是质数 或称素数 且在不计次序的意义下 表示是唯一的 6 同余 设 m 0 若 m a b 即 a b km 则称 a 与 b 模同 m 同余 记为 a b modm 也 称 b 是 a 对模 m 的剩余 7 完全剩余系 一组数 y1 y2 ys满足 对任意整数 a 有且仅有一个 yj是 a 对模 m 的剩余 即 a yj modm 则 y1 y2 ys称为模 m 的完全剩余系 8 Fermat 小定理 若 p 为素数 p a a p 1 则 ap 1 1 modp 且对任意整数 a 有 ap a modp 9 若 a m 1 则 m a 1 modm m 称欧拉函数 10 欧拉函数值的计算公式 若 k a k aa pppm 21 21 则 m 1 1 1 k i i p m 11 孙子定理 设 m1 m2 mk是 k 个两两互质的正整数 则同余组 x b1 modm1 x b2 modm2 x bk modmk 有唯一解 x 1 MM1b1 2 MM2b2 k MMkbk modM 其中 M m1m2mk i M i m M i 1 2 k iiM M 1 modmi i 1 2 k 二 方法与例题 1 奇偶分析法 例 1 有 n 个整数 它们的和为 0 乘积为 n n 1 求证 4 n 证明 设这 n 个整数为 a1 a2 an 则 a1 a2 an n a1 a2 an 0 用心 爱心 专心 首先 n 为偶数 否则 a1 a2 an均为奇数 奇数个奇数的和应为奇数且不为 0 与 矛盾 所以 n 为偶数 所以 a1 a2 an中必有偶数 如果 a1 a2 an中仅有一个偶数 则 a1 a2 an中还有奇数个奇数 从而 a1 a2 an也为奇数与 矛盾 所以 a1 a2 an中必 有至少 2 个偶数 所以 4 n 2 不等分析法 例 2 试求所有的正整数 n 使方程 x3 y3 z3 nx2y2z2有正整数解 解 设 x y z 为其正整数解 不妨设 x y z 则由题设 z2 x3 y3 所以 z2 x3 y3 但 x3 xz2 y3 yz2 因而 z nx2y2 2 33 z yx nx2y2 x y 故 x3 y3 z2 nx2y2 x y 2 所 以 n2x4y4 2nx2y2 x y x3 y3 所以 nxy 33 1111 2 nynxyx 若 x 2 则 4 nxy 33 1111 2 nynxyx 3 矛盾 所以 x 1 所以 nya1 2k b1 2k c1 从而 kkk cba 2 2 2 111 不是整数 矛盾 所以该方程仅有一组整数解 0 0 0 4 特殊模法 例 4 证明 存在无穷多个正整数 它们不能表示成少于 10 个奇数的平方和 证明 考虑形如 n 72k 66 k N 的正整数 若 22 2 2 1s xxxn 其中 xi为奇数 i 1 2 s 且 1 s 9 因为 n 2 mod8 又 2 i x 1 mod8 所以只有 s 2 所以 2 2 2 1 xxn 又因为 2 i x 2 或 0 mod3 且 3 n 所以 3 x1且 3 x2 所以 9 n 但 n 72k 66 3 mod9 矛盾 所以 n 不能表示成少于 10 个奇数的平方和 且这样的 n 有无穷 多个 用心 爱心 专心 5 最小数原理 例 5 证明 方程 x4 y4 z2没有正整数解 证明 假设原方程有一组正整数解 x0 y0 z0 并且 z0是所有正整数解 z 中最小的 因此 2 0 22 0 22 0 zyx 则 2 0 xa2 b2 2 0 y 2ab z0 a2 b2 其中 a b 1 a b 一奇一偶 假设 a 为偶数 b 为奇数 那么0 0 2 0 zx mod4 而3 222 0 bax mod4 矛盾 所以 a 为 奇数 b 为偶数 于是 由 222 0 abx 得 x0 p2 q2 b 2pq a p2 q2 这里 p q 1 p q 0 p q 为一奇一偶 从而推得 42 222 0 qppqaby 因为 p q p2 q2两两互质 因此它们必须都是某整数的平方 即 p r2 q s2 p2 q2 t2 从而 r4 s4 t2 即 r s t 也是原 方程的解 且有 t t2 p2 q2 a1 n 1 因为 1 1 33 mn nm 是整数 所以 1 1 1 1 1 33333 mn m mn nmnm 也是整 数 所以 m n 是对称的 不妨设 m n 若 m n 则 1 1 1 1 1 1 2 3 2 3 n n n nnn n n 为整数 所以 n 2 m 2 若 m n 因为 n3 1 1 modn mn 1 1 modn 所以 1 1 3 mn n 1 modn 所以存在 k N 使 kn 1 1 1 3 mn n 又 kn 1 1 1 1 1 1 1 2 3 2 3 n n n n mn n 所以 k 1 n 1 1 1 n 所以 k 1 所以 n 1 1 1 3 mn n 所以 1 2 1 1 1 2 n n n n m 所以 n 1 1 或 2 所以 m n 5 3 或 5 2 同理当 m n 时 有 m n 2 5 3 5 综上 m n 1 2 2 1 1 3 3 1 2 2 2 5 5 2 3 5 5 3 7 进位制的作用 例 7 能否选择 1983 个不同的正整数都不大于 105 且其中没有 3 个正整数是等差数列中的 用心 爱心 专心 连续项 证明你的结论 解 将前 105个自然数都表示为三进制 在这些三进制数中只选取含数字 0 或 1 而不含数 字 2 的数组成数集 T 下证 T 中的数符合要求 1 因为 310 10519