小木虫 --- 600万学术达人喜爱的学术科研平台
热门搜索：
&&求助，怎么下载MOD17A3的产品
求助，怎么下载MOD17A3的产品
用NPP计算生物质量，有谁知道在哪里下载EOS/MODIS 的MOD17A3啊？？？？？？？？？？？？？？
学术必备与600万学术达人在线互动！
扫描下载送金币数学竞赛中的数论问题题型全_伤城文章网
数学竞赛中的数论问题题型全
数学竞赛中的数论问题定理 4a, b 是两个不同时为 0 的整数，若 ax0 ? by0 是形如 ax ? by （ x, y 是任意整数）的数中的最小正数，则（1） ax0 ? by0 | ax ? by ； （2） ax0 ? by0 ? ? a , b ? ． 证明 得 （1）由带余除法有 ax ? by ? ? ax0 ? by0 ? q ? r ， 0 ? r ? ax0 ? by0 ，r ? a ? x ? qx0 ? x ? b ? y ? qy0 ? ? ax0 ? by0 ，知 r 也是形如 ax ? by 的非负数，但 ax0 ? by0 是形如 ax ? by 的数中的最小正数，故 r ? 0 ，即 ax0 ? by0 | ax ? by ． （2）由（1）有 ax0 ? by0 | a? ? b? ? a ， ax0 ? by0 | a? ? b? ? b ， 1 0 0 1 得 ax0 ? by0 是 a, b 的公约数．另一方面， a, b 的每一个公约数都可以整除 ax0 ? by0 ，所以 ax0 ? by0 是 a, b 的最大 公约数， ax0 ? by0 ? ? a , b ? ． 推论 定理 5 若 ? a, b ? ? 1 ，则存在整数 s, t ，使 as ? bt ? 1 ． （很有用） 互素的简单性质： （1） ?1, a ? ? 1 ． （2） ? n, n ? 1? ? 1 ． （3） ? 2n ? 1, 2n ? 1? ? 1 ．（4）若 p 是一个素数， a 是任意一个整数，且 a 不能被 p 整除，则 ? a, p ? ? 1 ． 推论 若 p 是一个素数， a 是任意一个整数，则 ? a, p ? ? 1 或 ? a, p ? ? p ．（6）若 ? a, b ? ? 1, ? a, c ? ? 1 ，则 ? a, bc ? ? 1 ． 证明 由 ? a, b ? ? 1 知存在整数 s, t ，使 as ? bt ? 1 ．有 a ? cs ? ? bct ? c ，得? a, bc ? ? ? a, c ? ? 1 ．（7）若 ? a, b ? ? 1 ，则 ? a ? b, a ? ? 1 ， ? a ? b, b ? ? 1 ， 证明? a ? b, ab ? ? 1 ．? a ? b, a ? ? ? ?b, a ? ? ? b, a ? ? 1 ， ? a ? b, b ? ? ? a, b ? ? 1，由（6） ? a ? b, ab ? ? 1 ．（8）若 ? a, b ? ? 1 ，则 a , bm?n? ? 1 ，其中 m, n 为正整数．?m证明 定理 7 证明m n 据（6） ，由 ? a, b ? ? 1 可得 a , b ? 1 ．同样，由 a , b ? 1 可得 a , b ? 1 ．m?????素数有无穷多个，2 是唯一的偶素数． 假设素数只有有限多个，记为 p1 , p2 ,?, pn ，作一个新数p ? p1 ?p2 ? pn ? 1 ? 1 ． ??若 p 为素数，则与素数只有 n 个 p1 , p2 ,?, pn 矛盾． 若 p 为合数，则必有 pi ? ? p1 , p2 ,? , pn ? ，使 pi | p ，从而 pi |1 ，又与 pi ? 1 矛盾． 综上所述，素数不能只有有限多个，所以素数有无穷多个． 2 是素数，而大于 2 的偶数都是合数，所以 2 是唯一的偶素数．1注：这个证明中，包含着数学归纳法的早期因素：若假设有 n 个素数，便有 n ? 1个素数． （构造法、反证法） 定理 8（整除的性质）整数 a, b, c 通常指非零整数 （1） 1 a ， ?1| a ；当 a ? 0 时， a | a ， a | 0 ． （2）若 b a ， a ? 0 ，则 b ?若 b a ， b ? a ，则 a ? 0 ;若 ab ? 0 ，且 b a , a b ，则 a ? b ． 证明 由 b a ， a ? 0 ，有 a ? bq ，得 a ? b q ? b ．逆反命题成立“若 b a ， b ? a ，则 a ? 0 ”;由 b ? a 且 b ? a 得 a ? b ，又 ab ? 0 ，得 a ? b ． （7）若 ? a, b ? ? 1 ，且 a bc ，则 a c ． 证明 由 ? a, b ? ? 1 知存在整数 s, t ，使 as ? bt ? 1 ，有 a ? cs ? ? ? bc ? t ? c ，因为 a a ， a bc ，所以 a 整除等式的左边，进而整除等式的右边，即 a c ． （8）若 ? a, b ? ? 1 ，且 a c , b c ，则 ab c ． 证明 由 ? a, b ? ? 1 知存在整数 s, t ，使 as ? bt ? 1 ，有 acs ? bct ? c ，又由 a c , b c 有 c ? aq1 , c ? bq2 代入得 ab ? q2 s ? ? ab ? q1t ? ? c ，所以 ab c ． 注意 不能由 a c 且 b c 得出 ab c ．如不能由 6 30 且 10 | 30 得出 60 | 30 ． （9）若 a 为素数，且 a bc ，则 a b 或 a c ． 证明 若不然，则 a ? b 且 a ? c ，由 a 为素数得 ? a, b ? ? 1, ? a, c ? ? 1 ，由互素的性质（6）得 ? a, bc ? ? 1 ，再由 | || a 为素数得 a ? bc ，与 a bc 矛盾．定义 6| 对于整数 a, b, c ，且 c ? 0 ，若 c ( a ? b) ，则称 a, b 关于模 c 同余，记作 a ? b(mod c) ；若 c ? ?a ?b ? ，则称 a, b 关于模 c 不同余，记作 ab(mod c) ．定理 9（同余的性质）设 a, b, c, d , m 为整数， m ? 0, 若 a ? b(mod m) 且 c ? d (mod m) ，则 a ? c ? b ? d (mod m) 且 ac ? bd (mod m) ． 证明 由 a ? b(mod m) 且 c ? d (mod m) ，有 a ? b ? mq1 , c ? d ? mq2 ， ①对①直接相加 ，有 ? a ? c ? ? ? b ? d ? ? m ? q1 ? q2 ? ，得a ? c ? b ? d (mod m) . ac ? bd (mod m) ．对①分别乘以 c, b 后相加，有 ac ? bd ? ? ac ? bc ? ? ? bc ? bd ? ? m ? cq1 ? bq2 ? ，得n n（3）若 a ? b(mod m) ，则对任意的正整数 n 有 a ? b (mod m) 且 an ? bn(mod mn) .2（4）若 a ? b(mod m) ，且对非零整数 k 有 k (a, b, m) ，则a b? m? ? ? mod ? ． k k? k?证明由 a ? b(mod m) 、 ，有 a ? b ? mq ，又 k (a, b, m) ，有a b m , , 均为整数，且 k k ka b m ? ? q ，得 k k k定理 10 设 a, b 为整数， n 为正整数， （1）若 a ? b ，则 ? a ? b ? a ? bna b? m? ? ? mod ? ． k k? k??n?．? b 2 n ?1 ? ．a n ? b n ? ? a ? b ? ? a n ?1 ? a n ? 2b ? a n ?3b 2 ? ? ? ab n ? 2 ? b n ?1 ? ．（2）若 a ? ?b ，则 ? a ? b ? a?2 n ?1a 2 n ?1 ? b 2 n ?1 ? ? a ? b ? ? a 2 n ? 2 ? a 2 n ?3b ? a 2 n ? 4b 2 ? ? ? ab 2 n ?3 ? b 2 n ? 2 ? ．（3）若 a ? ?b ，则 ? a ? b ? a?2n? b2n ? ．a 2 n ? b 2 n ? ? a ? b ? ? a 2 n ?1 ? a 2 n ? 2b ? a 2 n ?3b 2 ? ? ? ab 2 n ?2 ? b 2 n ?1 ? ．定义 7 设 n 为正整数， k 为大于 2 的正整数, a1 , a2 , ?, am 是小于 k 的非负整数，且 a1 ? 0 ．若n ? a1k m?1 ? a2 k m?2 ? ? ? am?1k ? am ，则称数 a1a2 ? am 为 n 的 k 进制表示．定理 11 给定整数 k ? 2 ，对任意的正整数 n ，都有唯一的 k 进制表示．如n ? a110m?1 ? a210m?2 ? ? ? am?110 ? am ， 0 ? ai ? 9, a1 ? 0 （10 进制） n ? a1 2m?1 ? a2 2m? 2 ? ? ? am?1 2 ? am ． 0 ? ai ? 1, a1 ? 0 （２进制）定理 12 （算术基本定理）每个大于 1 的正整数都可分解为素数的乘积，而且不计因数的顺序时，这种表示是 唯一的n ? p1?1 p2?2 ? pk ?k ，其中 p1 ? p2 ? ? ? pk 为素数， ?1 , ? 2 ,?, ? k 为正整数． （分解唯一性）定 理 13 若 正 整 数 n 的 素 数 分 解 式 为n ? p1?1 p2?2 ? pk ?k 则 n 的 正 约 数 的 个 数 为d ? n ? ? ? a1 ? 1?? a2 ? 1? ?? ak ? 1? ，n 的一切正约数之和为 S ? n ? ?证明?p ? k ?1 ? 1 p1?1 ?1 ? 1 p2? 2 ?1 ? 1 ? ?? ? k ． p1 ? 1 p2 ? 1 pk ? 1? ?k对于正整数 n ? p1 1 p2 2 ? pk，它的任意一个正约数可以表示为 ①m ? p1?1 p2 ?2 ? pk ?k ， 0 ? ?i ? ? i ，由于 ? i 有 0,1, 2,? , ? i 共 ? i ? 1 种取值，据乘法原理得 n 的约数的个数为 d ? n ? ? ? a1 ? 1?? a2 ? 1? ?? ak ? 1? ．3考虑乘积 p1 ? p1 ? ? ? p10 1??1?? p02? p21 ? ? ? p2? 2 ?? pk 0 ? pk1 ? ? ? pk ? k ，??展开式的每一项都是 n 的某一个约数（参见①） ，反之， n 的每一个约数都是展开式的某一项，于是， n 的一 切约数之和为 S ? n ? ? p1 ? p1 ? ? ? p10 1??1?? ? p0k? pk1 ? ? ? pk ?1 ? ?p ? k ?1 ? 1 p1?1 ?1 ? 1 p2? 2 ?1 ? 1 ? ?? ? k ． p1 ? 1 p2 ? 1 pk ? 1注构造法．定义 8 （高斯函数）对任意实数 x ，? x ? 是不超过 x 的最大整数．亦称 ? x ? 为 x 的整数部分，? x ? ? x ? ? x ? ? 1 ． 定理 14 在正整数 n ! 的素因子分解式中，素数 p 作为因子出现的次数是 ? 证明?n? ? n ? ? n ? ? ? ? 2 ? ? ? 3 ? ? ?． ? p? ? p ? ? p ?由于 p 为素数，故在 n ! 中 p 的次方数是 1, 2,?, n 各数中 p 的次方数的总和（注意，若 p 不为素数，这句话不成立） 1, 2,?, n 中，有 ? ．在? n ? ? n ? ?n? ?n? 2 ? 个 p 的倍数；在 ? p ? 个 p 的倍数的因式中，有 ? p 2 ? 个 p 的倍数；在 ? p 2 ? ? ? ? ? ? p? ? ?个 p 的倍数的因式中，有 ?2?n ? 3 个 p 的倍数；?，如此下去，在正整数 n ! 的素因子分解式中，素数 p 作为因子出 3? ?p ?现的次数就为 ??n? ? n ? ? n ? ? ? ? 2 ? ? ? 3 ? ? ? ．注 省略号其实是有限项之和． ? p? ? p ? ? p ?定理 15 （费玛小定理）如果素数 p 不能整除整数 a ，则 p a 证明 2p?p ?1? 1? ．改证等价命题：如果素数 p 不能整除整数 a ，则 a ? a ? mod p ? ．只需对 a ? 1, 2,?, p ? 1 证明成立，用数学归纳法． （1） a ? 1 ，命题显然成立． （2）假设命题对 a ? k ?1 ? k ? p ? 1? 成立，则当 a ? k ? 1 时，由于 p | C p ? i ? 1, 2,? , p ? 1? ，故有i? k ? 1?pp ? k p ? C 1 k p ?1 ? ? ? C p ?1k ? 1 ? k p ? 1 ? k ? 1? mod p ? ． （用了归纳假设） p这表明，命题对 a ? k ? 1 是成立． 由数学归纳法得 a ? a ? mod p ? ．p又素数 p 不能整除整数 a ，有 ? a, p ? ? 1 ，得 p a 定义 9?p ?1? 1? ．（欧拉函数）用 ? ? n ? 表示不大于 n 且与 n 互素的正整数个数．? ? ?k定理 16 设正整数 n ? p1 1 p2 2 ? pk 推论 ．，则 ? ? n ? ? n ? 1 ?? ?1 ?? 1 ? ? 1 ? ? ?1 ? ?? ?1 ? ? ． p1 ? ? p2 ? ? pk ?对素数 p 有 ? ? p ? ? p ? 1, ? p? ?? p??? p? ?1 ．4第二讲2数论题的范例讲解2 2（12） ? 2n ? ? 0 ? mod 4 ? , ? 2n ? 1? ? 1 ? mod 4 ? , ? 2 n ? 1? ? 1 ? mod 8 ? ． （13）任何整数都可以表示为 n ? 2m? 2k ? 1? ．b 例 1-1 （1986， 英国） a1 , a2 ,? , a7 是整数， 1 , b2 ,? , b7 是它们的一个排列， 设 证明 ? a1 ? b1 ?? a2 ? b2 ?? ? a7 ? b7 ?是偶数． a1 , a2 ,? , a7 中奇数与偶数个数不等） （ 例 1-2? 的前 24 位数字为 ? ? 3. ，记 a1 , a2 ,?, a24 为该 24 个数字的任一排列，求证 ? a1 ? a2 ?? a3 ? a4 ?? ? a23 ? a24 ? 必为偶数． （暗藏 3,1, 4,1,5,9, 2,6,5,3,5,8,9,7,9,3, 2,3,8, 4, 6, 2,6, 4 中奇数与偶数个数不等） 例 2 能否从 1, 2,?,15 中选出 10 个数填入图的圆圈中，使得每两个有线相连的圈中的数相减（大数减小数） ， 所得的 14 个差恰好为 1, 2,?,14 ？ 解 考虑 14 个差的和 S ，一方面S ? 1 ? 2 ? ? ? 14 ? 105 为奇数．另一方面，每两个数 a, b 的差与其和有相同的奇偶性 a ? b ? a ? b(mod 2) ，因此，14 个差的和 S 的奇偶性 与 14 个相应数之和的和 S 的奇偶性相同， 由于图中的每一个数 a 与 2 个或 4 个圈中的数相加， S 的贡献为 2a 或 对/ /4a ，从而 S / 为偶数，这与 S 为奇数矛盾，所以不能按要求给图中的圆圈填数．评析：用了计算两次的技巧．对同一数学对象，当用两种不同的方式将整体分为部分时，则按两种不同方式所 求得的总和应是相等的，这叫计算两次原理成富比尼原理．计算两次可以建立左右两边关系不太明显的恒等式．在 反证法中，计算两次又可用来构成矛盾． 例 3 有一大筐苹果和梨分成若干堆，如果你一定可以找到这样的两堆，其苹果数之和与梨数之和都是偶数， 问最少要把这些苹果和梨分成几堆？ 解 （1）4 堆是不能保证的．如 4 堆的奇偶性为： （反例） （奇奇）（偶偶）（奇偶）（偶奇） ， ， ， ． （2）5 堆是可以保证． 因为苹果和梨数的奇偶性有且只有上述 4 种可能，当把这些苹果和梨分成 5 堆时，必 有 2 堆属于同一奇偶性，其和苹果数与梨数都是偶数． 例 4, , 1 有 n 个 数 x1 , x 2? xn ? xn , ， 它 们 中 的 每 一 个 要 么 是 1 ， 要 么 是 ?1 ． 若n?x1 x2 ?证明x2 x3 ? ? ? ?? xn1x ? 0x，求证 4 | n ． x n 1 ?由 xi ? ?1, ?1? ，有 xi xi ?1 ? ?1, ?1? ，再由 x1 x2 ? x2 x3 ? ? ? ? ? xn ?1 xn ? xn x1 ? 0 ，知 n 个 xi xi ?1 中有一半是 1，有一半是 ?1 ， n 必为偶数，设 n ? 2k ．现把 n 个 xi xi ?1 相乘，有(?1)k (?1) k ? x1 x2 ?x2 x3 ? xn?1 xn ?xn x1 ? x12 x2 2 ? xn?12 xn 2 ? 1 ， ?? ??5可见， k 为偶数，设 k ? 2m ，有 n ? 4m ，得证 4 | n ． 例6 在数轴上给定两点 1 和 2 ，在区间 (1, 2) 内任取 n 个点，在此 n ? 2 个点中，每相邻两点连一线段，可得 n ? 1条互不重叠的线段，证明在此 n ? 1条线段中，以一个有理点和一个无理点为端点的线段恰有奇数条． 证明 将 n ? 2 个点按从小到大的顺序记为 A1 , A2 , …, An ? 2 ，并在每一点赋予数值 ai ，使? 1, 当Ai为有理数点时， ai ? ? 与此同时，每条线段 Ai Ai ?1 也可数字化为 ai ai ?1 （乘法） ?1, 　当Ai为无理数点时. ? ??1, 　当Ai , Ai ?1一为有理数点，另一为无理数时， ai ai ?1 ? ? ? 1, 　 当Ai , Ai ?1同为有理数点或无理数点时,记 ai ai ?1 ? ?1 的线段有 k 条，一方面 (a1a2 )(a2 a3 )(a3a4 )…(an ?1an ? 2 ) ? (?1) (?1)k 2 n ? k ?1? (?1) k另一方面 (a1a2 )(a2 a3 )(a3a4 )…(an ?1an ? 2 ) ? a1 (a2 a3…an ?1 ) an ? 2 ? a1an ? 2 ? ?1 ， 得 ? ?1? ? ?1，故 k 为奇数．评析 用了数字化、奇偶分析的技巧．k二、约数与倍数 最大公约数与最小公倍数的求法． （1） 短除法． （2）分解质因数法．设a ? p1?1 p2? 2 ? pk ? k , ? i ? 0, i ? 1, 2,?, k ， b ? p1?1 p2 ?2 ? pk ?k , ?i ? 0, i ? 1, 2,?, k ．记? i ? min ?? i , ?i ? , ? i ? max ?? i , ?i ? ，则（3）辗转相除法? a, b ? ? p1?1p2? 2 ? pk ? k ， ? a, b ? ? p1?1 p2? 2 ? pk ? k ．? a, b ? ? ? b, r ? ? ? r1 , r2 ? ? ? ? ? rn?1 , rn ? ? ? rn , 0 ? ? rn ．例 7 （1）求 ?
? ， ?? ； （2） ?144,180,108 ? ， ?144,180,108? ． 解（1）方法 1 分解质因数法．由8381 ? 17 2 ? 29, 1015 ? 5 ? 7 ? 29,得?? ? 29 ， ?? ? 5 ? 7 ?17 2 ? 29 ? 293335 ．方法 2 辗转相除法． 或?? ? ? 261,1015? ? ? 261, 232 ? ? ? 29, 232 ? ? ? 29, 0 ? ? 29 ．81?1015 ? ? 8381? 35 ? 293335 ． 29 ??2 144 180 108 2 72 90 30 10 5 54 27 9 3 3 36 3 12 4?? ?（2） 方法 1 短除法． 由得?144,180,108? ? 22 ? 32 ? 36 ，6?144,180,108? ? 24 ? 33 ? 5 ? 2160 ．方法 2 分解质因数法．由144 ? 2 4 ? 32 , 180 ? 2 2 ? 32 ? 5, ， 108 ? 2 2 ? 33 ,得?144,180,108? ? 22 ? 32 ? 36 ， ?144,180,108? ? 24 ? 33 ? 5 ? 2160 ．．例 8 正整数 n 分别除以 2,3, 4,5,6,7,8,9,10 得到的余数依次为 1, 2,3, 4,5,6,7,8,9 ，则 n 的最小值为 解 依题意，对最小的 n ，则 n ? 1是 2,3, 4,5,6,7,8,9,10 的公倍数 n ? 1 ? 2 ? 3 ? 5 ? 7 ，得 n ? 2519 ．3 2例 9 有两个容器，一个容量为 27 升，一个容量为 15 升，如何利用它们从一桶油中倒出 6 升油来？ 解 相当于求不定方程 15 x ? 27 y ? 6 的整数解．由 ?15, 27 ? ? 3 知，存在整数 u, v ，使15u ? 27v ? 3 ，可得一个解 u ? 2, v ? ?1 ，从而方程 15 ? 4 ? 27 ? ? ?2 ? ? 6 ．即往小容器里倒 2 次油，每次倒满之后就向大容器里倒，大容器倒满时，小容器里剩有 3 升油；再重复一次， 可得 6 升． 例 10 对 每 一 个 n ? 2 ， 求 证 存 在 n 个 互 不 相 同 的 正 整 数 a1 , a2 ,? , an ， 使 ai ? a j ai ? a j， 对 任 意 的i, j ? ?1, 2,? , n? , i ? j 成立．证明 用数学归纳法．当 n ? 2 时，取 a1 ? 1, a2 ? 2 ，命题显然成立．假设 n ? k 时，命题成立，即存在 a1 , a2 ,? , ak ，使 ai ? a j ai ? a j ，对任意的 i, j ? ?1, 2,? , k ? , i ? j 成立． 现取 b 为 a1 , a2 ,? , ak 及它们每两个数之差的最小公倍数，则 k ? 1 个数b, a1 ? b, a2 ? b,?, ak ? b 满足?? at ? b ? ? b ? at ? b ? ? b, ? ? ?? ai ? b ? ? ? a j ? b ? ? ai ? b ? ? ? a j ? b ? , ?即命题对 n ? k ? 1 时成立．由数学归纳法知命题对 n ? 2 成立． 例 11 证明 1?1959, IMO1?1 ? 证明对任意正整数 n ，分数（反证法）假若d ? 1，使21n ? 4 可约，则存在 14n ? 321n ? 4 不可约． 14n ? 3①? 21n ? 4,14n ? 3? ? d ，?21n ? 4 ? dp, ?14n ? 3 ? dq, ② ③④7从而存在 p, q, ? p, q ? ? 1 ，使 ? 消去 n ， ? 3? ? 3 ? ? 2 ? ? 2 ，得1 ? d ? 3q ? 2 p ? ，的d ? 1．⑤由（1）（5）矛盾，得 d ? 1 ． 、 解题分析： （1）去掉反证法的假设与矛盾就是一个正面证法． （2）式④是实质性的进展，表明 可见 证明 21 ? 3 ?14n ? 3? ? 2 ? 21n ? 4 ? ，? 21n ? 4,14n ? 3? ? 1 ．由此获得 2 个解法．设 ? 21n ? 4,14n ? 3? ? d ．存在 p, q, ? p, q ? ? 1 ，使?21n ? 4 ? dp, ? ?14n ? 3 ? dq,消去 n ，②×3-①×2，得① ②1 ? d ? 3q ? 2 p ?得 d ? 1． 证明 3 得 证明 4 由 1 ? 3 ?14n ? 3? ? 2 ? 21n ? 4 ?③? 21n ? 4,14n ? 3? ? 1 ． ? 21n ? 4,14n ? 3?? ? 7n ? 1,1? ? ? 7n ? 1,14n ? 3?⑤ ④?1．解题分析：第④ 相当于 ①-②；第⑤ 相当于②-2（①-②）=②×3-①×2；所以③式与⑤式的效果是一样的． 例 12 不存在这样的多项式f ? n ? ? am n m ? am?1n m?1 ? ? ? a1n ? a0 ，使得对任意的正整数 n ， f ? n ? 都是素数． 证明 假设存在这样的多项式,对任意的正整数 n ， f ? n ? 都是素数，则取正整数 n ? b ，有素数 p 使f ? b ? ? amb m ? am?1b m?1 ? ? ? a1b ? a0 ? p ，进而对任意的整数 k , 有 f ? b ? kp ? ? am ? b ? kp ? ? am ?1 ? b ? kp ?m m ?1? ? ? a1 ? b ? kp ? ? a0? ? amb m ? am ?1b m ?1 ? ? ? a1b ? a0 ? ? Mp （二项式定理展开） ? P ?1 ? M ? ，其中 M 为整数，这表明f ? b ? kp ? 为合数．这一矛盾说明，不存在这样的多项式,对任意的正整数 n ， f ? n ? 都是素数．三、平方数 若 a 是整数，则 a 就叫做 a 的完全平方数，简称平方数． 1．平方数的简单性质 （1）平方数的个位数只有 6 个： 0,1, 4,5.6.9 ． （2）平方数的末两位数只有 22 个：00，01，21，41，61，81，04，24，44，64，84，25，16，36，56，76，8296，09，29，49，69，89． （3） ? 2n ? ? 0 ? mod 4 ? , ? 2n ? 1? ? 1? mod 4 ? ．（４） ? 2n ? 1? ? 1? mod 8 ． ?2 2 2（6）凡是不能被 3 整除的数，平方后被 3 除余 1． （7）在两个相邻整数的平方数之间，不能再有平方数． （8）非零平方数的约数有奇数个． （9）直角三角形的三边均为整数时，我们把满足 a ? b ? c 的整数 ? a , b, c ? 叫做勾股数．勾股数的公式为2 2 2?a ? m 2 ? n 2 , ? ?b ? 2mn, ?c ? m2 ? n2 , ?其中 m, n 为正整数， ? m, n ? ? 1 且 m, n 一奇一偶．这个公式可给出全部素勾股数． 2．平方数的证明方法 （1）反证法． （2）恒等变形法． （3）分解法．设 a 为平方数，且 a ? bc ， ? b, c ? ? 1 ，则 b, c 均为平方数． （4）约数法．证明该数有奇数个约数． 3．非平方数的判别方法2 （1）若 n ? x ? ? n ? 1? ，则 x 不是平方数． （2）约数有偶数个的数不是平方数． 2（3）个位数为 2，3，7，8 的数不是平方数． （4）同余法：满足下式的数 n 都不是平方数．n ? 2 ? mod 3? ， n ? 2或3 ? mod 4 ? ， n ? 2或3 ? mod 5 ? ， n ? 2或3或5或6或7 ? mod8 ? ， n ? 2或3或7或8 ? mod10 ? ．（5）末两位数不是：00，01，21，41，61，81，04，24，44，64，84，25，16，36，56，76，96，09，29， 49，69，89．如 个位数与十位数都是都是奇数的数， 个位数是 6、而十位数是偶数的数． 例 13 有 100 盏电灯，排成一横行，从左到右，我们给电灯编上号码 1，2，?，99，100．每盏灯由一个拉线 开关控制着．最初，电灯全是关着的．另外有 100 个学生，第一个学生走过来，把凡是号码为 1 的倍数的电灯的开 关拉了一下；接着第 2 个学生走过来，把凡是号码为 2 的倍数的电灯的开关拉了一下；第 3 个学生走过来，把凡是 号码为 3 的倍数的电灯的开关拉了一下，如此等等，最后那个学生走过来，把编号能被 100 整除的电灯的开关拉了 一下，这样过去之后，问哪些灯是亮的？ 讲解 （1）直接统计 100 次拉线记录，会眼花缭乱． （2）拉电灯的开关有什么规律：电灯编号包含的正约数（学生）才能拉、不是正约数（学生）不能拉，有几 个正约数就被拉几次． （3）灯被拉的次数与亮不亮（开、关）有什么关系： 0 关 1 开 2 关 3 开 4 关 5 开 6 关 7 开 8 关 9 开灯被拉奇数次的亮！ （4）哪些数有奇数个约数：平方数． （5）1～100 中有哪些平方数：共 10 个： 1，4，9，16，25，36，49，64，81，100． 答案：编号为 1，4，9，16，25，36，49，64，81，100 共 10 个灯还亮．9例 14已知直角三角形的两条直角边分别为正整数 a, b ，斜边为正整数 c ，若 a 为素数，求证 2 ? a ? b ? 1? 为平方数．证明 由勾股定理 c 2 ? a 2 ? b2 ，有? c ? b ?? c ? b ? ? a 2 ，b?2但 a 为素数，必有?c ? b ? a 2 , 解得 ? ?c ? b ? 1,1 2 ? a ?1? ， 2从而 例 152 ? a ? b ? 1? ? 2a ? ? a 2 ? 1? ? 2 ? ? a ? 1? ，为平方数．求证，任意 3 个连续正整数的积不是平方数． 证明 设存在 3 个连续正整数 n ? 1, n, n ? 1 （ n ? 1 ）的积为平方数，即存在整数 m ，使? n ? 1? n ? n ? 1? ? m2 ，即?n2? 1? n ? m 2 ，?n 2 ? 1 ? a 2 , ? 2 2 2 但 ? n ? 1, n ? ? 1 ，故 n ? 1, n 均为平方数，有 ?n ? b , ?m ? ab, ?得1 ? n 2 ? a 2 ? n 2 ? ? n ? 1? ? 2n ? 1 ? 1， （注意 n ? 1 ）2这一矛盾说明，3 个连续正整数的积不是平方数． 四．整除 整除的判别方法主要有 7 大类． 1．定义法．证 b a ? a ? bq ，有三种方式． （1）假设 a ? qb ? r ，然后证明 r ? 0 ． （定理 4） （2）具体找出 q ，满足 a ? bq ． （3）论证 q 的存在． 例 18 证明 任意一个正整数 m 与它的十进制表示中的所有数码之差能被 9 整除． 设 m ? an ?10 ? an ?1 ?10n n ?1? ? ? a1 ?10 ? a0 ，其中 0 ? ai ? 9, an ? 0 ，则m ? ? an ? an ?1 ? ? ? a1 ? a0 ?? an ?10n ? 1? ? an ?1 ?10n ?1 ? 1? ? ? ? a1 ?10 ? 1? ? ? ? 9 ? an ? 11?1 ? ? an ?1 ? 11?1 ? ? ? a2 ?11 ? a1 ? , ? ? n个1 n ?1个1 ? ?按定义 9 m ? ? an ? an ?1 ? ? ? a1 ? a0 ? ． 2．数的整除判别法． （1）任何整数都能被 1 整除．（2）如果一个整数的末位能被 2 或５整除，那么这个数就能被 2 或５整除． （3）如果一个整数的末两位能被４或 25 整除，那么这个数就能被 4 或 25 整除． （4）如果一个整数的末三位能被 8 或 125 整除，那么这个数就能被 8 或 125 整除． （5）如果一个整数各数位上的数字之和能被 3 或 9 整除，那么这个数就能被 3 或 9 整除． 证明 由 10 ? 1? mod 3? ,10 ? 1? mod 9 ? ，有an ?10n ? an ?1 ?10n ?1 ? ? ? a1 ?10 ? a0 ? an ? an ?1 ? ? ? a1 ? a0 ? mod 3? ，10an ?10n ? an ?1 ?10n ?1 ? ? ? a1 ?10 ? a0 ? an ? an ?1 ? ? ? a1 ? a0 ? mod 9 ?（6） 如果一个整数的末三位数与末三位数以前的数字所组成的数的差能被 7 或 11 或 13 整除， 那么这个数就能 被 7 或 11 或 13 整除． 证明 由 m ? an an ?1 ? a2 a1a0 知? an an ?1 ? a3 ? 1001 ? an an ?1 ? a3 ? a2 a1a0 ，??1001 an an ?1 ? a3a2 a1a0 ? 1001 an an ?1 ? a3 ? ?a2 a1a0 ，又由 1001 ? 7 ?11?13 ，而 7,11,13 均为素数知， m 能被 7 或 11 或 13 整除． （7）如果一个整数的奇位数字之和与偶位数字之和的差能被 11 整除，则这个数能被 11 整除． 证明 由 10 ? ?1? mod11? ，有??an ?10n ? an?1 ?10n?1 ? ? ? a1 ?10 ? a0 ? an ? ?1? ? an?1 ? ?1?n n ?1? ? ? a1 ? ?1? ? a0 ? mod11? .3．分解法．主要用乘法公式．如a n ? b n ? ? a ? b ? ? a n ?1 ? a n ? 2b ? a n ?3b 2 ? ? ? ab n ? 2 ? b n ?1 ? ． a 2 n ?1 ? b 2 n ?1 ? ? a ? b ? ? a 2 n ? 2 ? a 2 n ?3b ? a 2 n ? 4b 2 ? ? ? ab 2 n ?3 ? b 2 n ? 2 ? ．a 2 n ? b 2 n ? ? a ? b ? ? a 2 n ?1 ? a 2 n ? 2b ? a 2 n ?3b 2 ? ? ? ab 2 n ? 2 ? b 2 n ?1 ? ．例 19 证明 试证 ?1 ? 2 ? ? ? 9 ? 1 ? 2 ? ? ? 95 5?5?．5改证 45 1 ? 2 ? ? ? 95 5?5? ．设 S ? 1 ? 25? ? ? 95 ，则S ? ?15 ? 85 ? ? ? 25 ? 75 ? ? ? 35 ? 65 ? ? ? 45 ? 55 ? ? 95 ? ?1 ? 8 ? m1 ? ? 2 ? 7 ? m2 ? ? 3 ? 6 ? m3 ? ? 4 ? 5 ? m4 ? 95 ? 9 ? m1 ? m2 ? m3 ? m4 ? 94 ? ,得 9 S ．又S ? ?15 ? 95 ? ? ? 25 ? 85 ? ? ? 35 ? 75 ? ? ? 45 ? 65 ? ? 55得5 S ．? ?1 ? 9 ? m1 ? ? 2 ? 8? m2 ? ? 3 ? 7 ? m3 ? ? 4 ? 6 ? m4 ? 55 ? 5 ? 2m1 ? 2m2 ? 2m3 ? 2m4 ? 54 ? ,但 ? 9,5 ? ? 1 ，得 45 S ，即 ?1 ? 2 ? ? ? 9 ? 1 ? 2 ? ? ? 95 5?5?．例 20?1979, IMO21?1 ? 设 p 与 q 为正整数，满足p 1 1 1 1 ，求证 p 可被 1979 整除（1979 p ） ? 1? ? ?? ? ? q 2 3 证明p 1 1 1 1 ?1 ? ? ? ? ? ? q 2 3 1 1 ? ?1 1 1 ? ? 1 1 ? ?1 ? ? ? ? ? ? ? ? 2 ? ? ?? ? ?
? ? 2 4 1318 ? ? 2 3111 1 ? ? 1 1 1 ? ? 1 1 ? ?1 ? ? ? ? ? ? ? ? ?1 ? ? ? ? ? ?
? ? 2 3 659 ? ? 2 31 1 1 1 ? ??? ? 660 661 0 ?
? 990 ? ? ??? 660 ?8 989 ? 990 ?M 660 ? 661? ? ? ! M ? 1979 ? 1319! ? 1979 ?得 1979 整除 1319! p ，但 1979 为素数， ?!? ? 1 ，得 p 可被 1979 整除． 例 20-1 2009 年 9 月 9 日的年、月、日组成“长长久久、永不分离”的吉祥数字 ，而它也恰好是一个不能再分解的素数． 若规定含素因子
的数为吉祥数， 请证明最简分数 子 m 是吉祥数． 证明：由m 1 1 的分 ? 1? ??? n 2 m 1 1 ? 1? ??? n 2 1 1 1 1 ?1 ? ?1 ? ? ? ?? ? ? ??? ? ? ?? ? ? ? ? 1
? ? 45455 ? 09 ? ? ?? ? 1?
? , 1? 2 ?? ?
? 其中 p 为正整数，有
? n ? p ? 1? 2 ???
? m ， 这 表 明 ，
整 除 1? 2 ? ? 2 0 0 9 0 9 ? 7 2 0 0 9 0， 0
为 素 数 ， 不 能 整 除 ? 0 m 9但 ? ，所以
整除 m ，得 m 是吉祥数． 1? 2 ? ? 2 0 0 9 0 9 ? 7 2 0 0 9 0 9 0 8 ? 0 4． 余数分类法． 例 21 证明 1 试证 3 n ? n ? 1?? 2n ? 1? ． 任何整数 n 被 3 除其余数分为 3 类n ? 3k , n ? 3k ? 1, n ? 3k ? 2, k ? Z ，（1） n ? 3k 时，有n ? n ? 1?? 2n ? 1? ? 3 ? k ? 3k ? 1?? 6k ? 1? ? , ? ?有 3 n ? n ? 1?? 2n ? 1? ． （2） n ? 3k ? 1 时，有 n ? n ? 1?? 2n ? 1? ? 3 ?? 3k ? 1?? 3k ? 2 ?? 2k ? 1? ? , ? ? 有 3 n ? n ? 1?? 2n ? 1? ． （3） n ? 3k ? 2 n ? n ? 1?? 2n ? 1? ? 3 ?? 3k ? 2 ?? k ? 1?? 6k ? 5 ? ? , ? ? 有 3 n ? n ? 1?? 2n ? 1? ．综上得， 3 n ? n ? 1?? 2n ? 1? ．证明 2n ? n ? 1?? 2n ? 1? ?2n ? 2n ? 2 ?? 2n ? 1? 4，得3 2n ? 2n ? 2 ?? 2n ? 1? ， 又 ? 3, 4 ? ? 1 ， 得123 n ? n ? 1?? 2n ? 1? ．5．数学归纳法．6．反证法．7．构造法． 例 22 k 个连续整数中必有一个能被 k 整除． 证明 设 k 个连续整数为 a, a ? 1, a ? 2,?, a ? k ? 1 ，若这 k 个数被 k 除没有一个余数为 0，则这 k 个数的余数只能取 1, 2,?, k ? 1，共 k ? 1种情况，必存在两个数a ? i, a ? j,0 ? i ? j ? k ，使其中 q1 ? q2 ，相减 i ? j ? k ? q1 ? q2 ? ，有 即a ? i ? kq1 ? r , a ? j ? kq2 ? r ,i ? j ? k q1 ? q2 ? k ，i ? j ? k 与 i ? j ? k 矛盾．故 k 个连续整数中必有一个能被 k 整除．0 ? i ? j ? k ? q1 ? q2 ? ? k ，推出 0 ? q1 ? q2 ? 1 ，与 q1 ? q2 为整数矛盾．也可以由 i ? j ? k ? q1 ? q2 ? 得 例 23 证明k 个连续整数之积必能被 k !整除．设 k 个连续整数为 n, n ? 1, n ? 2,?, n ? k ? 1 ，（1）若这 k 个连续整数为正整数，则n ? n ? 1?? n ? 2 ?? ? n ? k ? 1? k!?n! k !? n ? k ? !? ?C ?k n只须证明，对任何一个素数 p ，分子中所含 p 的方次不低于分母中所含 p 的方次，由高斯函数的性质? x ? y? ? ? x? ?? y? ，有?? p得? k ? ?n ? k ? ? ?n? ?k ? ?n ? k ? ? ?? ? ? ?? s ???? s ? s ? s p ? ? ?p ? ? p ? ? ?Ck n为整数（证实了组合数的实际意义）（2）若这 k 个连续整数中有 0，则连乘积为 0，必能被 k ! 整除． （3）若这 k 个连续整数为负整数，则n ? n ? 1?? n ? 2 ?? ? n ? k ? 1? ? ? ?1? ? ? ?1?由（1）知 例 24kk! ? ?n ?? ?n ? 1?? ?n ? 2 ??? ?n ? k ? 1? k!kCk ?n,n ? n ? 1?? n ? 2 ?? ? n ? k ? 1? k!为整数．Ck为整数，故 ?n有男孩、女孩共 n 个围坐在一个圆周上（ n ? 3 ） ，若顺序相邻的 3 人中恰有一个男孩的有 a 组，顺序相邻的 3 人中恰有一个女孩的有 b 组，求证 3 a ? b ． 证明 现将小孩记作 ai (i ? 1, 2, …, n) ，且数字化13?1, 　ai 表示男孩时 ai ? ? ??1, ai 表示女孩时则“3 人组”数值化为Ai ? ai ? ai ?1 ? ai ? 2?3, 　　 ai , ai ?1 , ai ? 2均为男孩 ? ??3, 　　ai , ai ?1 , ai ? 2均为女孩 ?? ?1, 　　 ai , ai ?1 , ai ? 2 恰有一个女孩 ??1, 　　a , a , a 恰有一个男孩 i i ?1 i?2 ?其中 an ? j ? a j ．又设取值为 3 的 Ai 有 p 个，取值为 ?3 的 Ai 有 q 个，依题意，取值为 1 的 Ai 有 b 个，取值为 ?1 的Ai 有 a 个，得3 ( 1 ? a 2 ? … ? an ) a 1 a ? a 3 ) a (?2a ? a ? 4) ? an ? a ? a1 a ? (? 2 ? … ( 32)? 3 p ? (?3)q ? (?1)a ? b ? 3( p ? q) ? (b ? a) ，可见 3 a ? b ． 例 25 （1956，中国北京）证明 n ?33 2 1 n ? n ? 1对任何正整数 n 都是整数，并且用 3 除时余 2． 2 2分析只需说明n ? 3n ? 1? 3 2 1 为 整 数 ， 但 不 便 说 明 “ 用 3 除 时 余 2 ”， 应 说 明 n ? n? 2 2 2n ? n ? 1?? 2n ? 1? 2n ? 2n ? 2 ?? 2n ? 1? 3 1 3 2 1 3 是 3 的倍数．作变形 n ? n ? n ? 1 ? n3 ? n 2 ? n ? ? 1, ? 3,8 ? ? 1 ， 2 2 2 2 2 8命题可证． 证明 已知即 n ?3n ? n ? 1?? 2n ? 1? 3 2 1 n ? n ?1 ? ?1 ， 2 2 23①因为相邻 2 个整数 n, ? n ? 1? 必有偶数，所以 n ?3 2 1 n ? n ? 1为整数．又①可变为 2 22n ? 2n ? 2 ?? 2n ? 1? 3 1 n3 ? n 2 ? n ? 1 ? ? 1， 2 2 8因为相邻 3 个整数 2n, ? 2n ? 2 ? , ? 2n ? 1? 必有 3 的倍数，故 2n ? 2n ? 2 ?? 2n ? 1? 能被 3 整除；又 ? 3,8 ? ? 1 ，所以2n ? 2n ? 2 ?? 2n ? 1? 8能被 3 整除；得 n ?33 2 1 n ? n ? 1用 3 除时余 2． 2 2五、同余 根据定义，同余问题可以转化为整除问题来解决；同时，同余本身有很多性质，可以直接用来解题． 例 26 正方体的顶点标上 ?1 或 ?1 ，面上标上一个数，它等于这个面四个顶点处的数的乘积，求证，这样得 出的 14 个数之和不能为 0． 证明 记 14 个数的和为 S ，易知，这 14 个数不是 ?1 就是 ?1 ，若八个顶点都标上 ?1 ，则 S ? 14 ，命题成立． 对于顶点有 ?1 的情况，我们改变 ?1 为 ?1 ，则和 S 中有 4 的数 a, b, c, d 改变了符号，用 S 表示改变后的和，/由14a ? b ? c ? d ? 0 ? mod 2 ? 知S ? S / ? 2 a ? b ? c ? d ? 0 ? mod 4 ? ，这表明，改变一个 ?1 ，和 S 关于模 4 的余数不变，重复进行，直到把所有的 ?1 都改变为 ?1 ，则S ? S / ? 1 ? 1 ? ? ? 1 ? 14 ? 2 ? mod 4 ? ，所以， S ? 0 ．例 27 设多项式 f ?x ? ? a0 x ? a1 xn n ?1? ? ? a n?1 x ? a n 的系数都是整数，并且有一个奇数 ? 及一个偶数 ? 使得 f ?? ? 及 f ?? ? 都是奇数，求证方程 f ?x ? ? 0 没有整数根． 证明 由已知有 f ?? ? ? 1? mod 2 ? ? a0 ? a1 ? a2 ? ? ? an ? 1? mod 2 ? ， ①f ? ? ? ? 1? mod 2 ? ? an ? 1? mod 2 ? ，若方程 f ?x ? ? 0 存在整数根 x0 ，即 f ? x0 ? ? 0 ．当 x0 为奇数时，有②f ? x0 ? ? 0 ? mod 2 ? ? a0 ? a1 ? a2 ? ? ? an ? 0 ? mod 2 ? ，与①矛盾．有 x0 为偶数时，有 f ? x0 ? ? 0 ? mod 2 ? ? an ? 0 ? mod 2 ? ，与②矛盾．所以方程 f ?x ? ? 0 没有整数根． 六、不定方程 未知数的个数多于方程个数的整系数代数方程，称为不定方程．求不定方程的整数解，叫做解不定方程． 解 不定方程通常要解决 3 个问题，方程是否有解？有解时，有几个解，解数是有限还是无穷？求出全部解． 例 28 解方程 7 x ? 19 y ? 213 ． 解法 1 由 ? 7,19 ? ? 1 知方程有整数解．观察特解，列表y x12 253 ?得一个特解 ?? x0 ? 25, 从而通解为 ? y0 ? 2,197 7? x ? 25 ? 19t , ? ? y ? 2 ? 7t .方法总结：第 1 步，验证 ? a , b ? c ，经常是 ? a, b ? ? 1 ．第 2 步，求特解（观察、列举、辗转相除等） ． 第 3 步，代入公式． 方法总结： ax ? by ? c ? ax ? c ? mod b ? 或 by ? c ? mod a ? ． 例 29 解 求方程 x ? 2 x y ? 2009 的整数解．3 2由 2009 的分解式，有x 2 ? x ? 2 y ? ? 1 ? 2009 ? 7 2 ? 41 ，2有? x 2 ? 1, ? x ? 1, ? x ? ?1, ?? ? ? ? x ? 2 y ? 2009, ? y ? 1004, ? y ? 1005, ? x2 ? 72 , ? x ? 7, ? x ? ?7, ?? ? ? ? x ? 2 y ? 41, ? y ? 17, ? y ? 24.15例 30 甲乙两队各出 7 名队员按事先排好的顺序出场参加围棋擂台赛，双方先由 1 号队员比赛，负者被淘汰， 胜者再与负方 2 号队员比赛，?直到有一方队员全被淘汰为止，另一方获得胜利，形成一种比赛过程，那么所有可 能出现的比赛过程的种数为 ． （1988，高中联赛） 解法 1 设甲、乙两队的队员按出场顺序分别为 A1 , A2 , A3 , A4 , A5 , A6 , A7 和 B1 , B2 , B3 , B4 , B5 , B6 , B7 ．如果甲方 获胜，设 Ai 获胜的场数是 xi ，则 0 ? xi ? 7,1 ? i ? 7 而且x1 ? x2 ? ? ? x7 ? 7，①容易证明以下两点：在甲方获胜时 （i）不同的比赛过程对应着方程①的不同非负整数解； （ii）方程①的不同非负整数解对应着不同的比赛过程，例如，解（2，0，0，1，3，1，0）对应的比赛过程为：A1 胜 B1 和 B2 ； B3 胜 A1 、和 A3 ； A4 胜 B3 后负于 B4 ； A5 胜 B4 、 B5 和 B6 但负于 B7 ；最后 A6 胜 B7 结束比赛．下面求方程①的非负整数解个数，设 yi ? xi ? 1 ，问题等价于方程y1 ? y2 ? y3 ? y4 ? y5 ? y6 ? y7 ? 14 ，正整数解的个数，将上式写成1 ?1 ?1 ?1 ?1 ?1 ?1 ?1 ?1 ?1 ?1 ?1 ?1 ?1 ? 14 ，从 13 个加号取 6 个的方法数 C13 种．得甲方获胜的不同的比赛过程有 C13 种． 同理，乙方获胜的不同的比赛过程也有 C13 种，合计 2C13 ? 3432 种比赛过程7 6 66例 31（1989，高中）如果从数 1，2，?，14 中按由小到大的顺序取出 a1 , a2 , a3 ，使同时满足a2 ? a1 ? 3, a3 ? a2 ? 3 ，那么，所有符合上述要求的不同取法有多少种？a1 ? 1 ? 0,解 由已知得a2 ? a1 ? 3 ? 0 a3 ? a2 ? 3 ? 0, 14 ? a3 ? 0,4 项均为非负数，相加得 ? a1 ? 1? ? ? a2 ? a1 ? 3? ? ? a3 ? a2 ? 3? ? ? 14 ? a3 ? ? 7 ，于是 a1 , a2 , a3 的取法数就是不定方程x1 ? x2 ? x3 ? x4 ? 7 y1 ? y2 ? y3 ? y4 ? 11的非负整数解的个数，作一一对应 y1 ? xi ? 1 ，问题又等价于不定方 的正整数解．由 七．数论函数 主要是 ? x ? 高斯函数， ? ? n ? 欧拉函数． 例 323 3 1 ?1 ???1 ? 11 ，得 C10 个解，即符合要求的不同取法有 C10 种．某学校要召开学生代表大会， 规定各班每 10 人推选一名代表， 当各班人数除以 10 的余数大于 6 时再增 ．．．选一名代表．那么，各班可推选代表人数 y 与该班人数 x 之间的函数关系用取整函数 y ? ? x ? （ ? x ? 表示不大于 x 的 最大整数）可以表示为16(A) y ? ??x? ?10 ? ?(B) y ? ?? x ? 3? ? 10 ? ?(C) y ? ?? x ? 4? ? 10 ? ?(D) y ? ?? x ? 5? ? 10 ? ?（2010 年全国高考数学陕西卷理科第 10 题） 解法 1 选（B）（求解对照） ． ．规则是“六舍七入” ，故加 3 即可进 1． 选 y ? ?? x ? 3? ． ? 10 ? ?解法 2 选（B）（特值否定） ． ．取 x ? 56 ，按规定应选 5 人，可否定(C)、(D)；再取 x ? 57 ，按规定应选 6 人，可否定(A)． 注：主要错误选(C) ，误为“五舍六入” ． 例 33 用 ? x ? 表示不大于 x 的最大整数，求?? 1 ? ? 2 ? ? 2004 ? ? ? ? 366 ? ? ? 366 ? ? ? ? ? 366 ? ? ? ? ? ? ?? ． ?? 366 ? ? ? ? ? ?讲解 题目的内层有 2004 个高斯记号，外层 1 个高斯记号．关键是弄清 ? x ? 的含义，进而弄清加法谁与谁加、除法谁与谁除： （1）分子是那些数相加，求出和来； 由 366 ? 5 ? 1830 ? 2004 ? 2196 ? 366 ? 6 ，知分子是 0～5 的整数相加，弄清加数各有几个1～365 366～731 732～～～～20040 1 2 3 4 5365 个 366 个 366 个 366 个 366 个 175 个（2）除法谁除以 366，求出商的整数部分． 原式 ? ?? 0 ? 365 ? 366 ?1 ? 2 ? 3 ? 4 ? ? 5 ? 175 ? ? 366 ? ??10 ? 366 ? 875 ? ?? ? 366 ? ? 143 ? ? ? ?10 ? 2 ? 366 ? ? ? ? 12.命题背景 2004 年有 12 个月、366 天． 例 34 解50! 的标准分解式中 2 的指数．50! ? 2?1 3?2 5?3 7?411?513?617?719?8 23?9 29? ? ? ? ? 31 37 41 43 472 的指数为17? 50 ? ? 50 ? ? 50 ? ? 50 ? ? 50 ? ? 2 ? ? ? 22 ? ? ? 23 ? ? ? 24 ? ? ? 25 ? ? 25 ? 12 ? 6 ? 3 ? 1 ? 47 ． ? ? ? ? ? ? ? ? ? ?图示（5 条横线，25 个偶数中 2 的方次，按横线求和） 八、综合练习 例 35 整数勾股形中，证明 （1）必有一条直角边长是 3 的倍数； （2）必有一条直角边长是 4 的倍数； （3）必有一条边长是 5 的倍数； （4）三角形的面积是 6 的倍数． 证明 当整数勾股形的三边有公约数时，可以先约去，使三边长 x, y, z 互素，且满足x2 ? y 2 ? z 2 .这时，若 x, y 两个均为偶数，则 z 也为偶数，与 x, y, z 互素矛盾；若 x, y 两个均为奇数，有x 2 ? 1? mod 4 ? , y 2 ? 1? mod 4 ? ，得z 2 ? x 2 ? y 2 ? 2 ? mod 4 ? ，这与平方数模 4 只能取 0，1 矛盾.所以， x, y 中有且只有一个为偶数，不妨设 x 为偶数. （1）设 x, y 中无一为 3 的倍数，则x 2 ? 1? mod 3? , y 2 ? 1? mod 3? ，得z 2 ? x 2 ? y 2 ? 2 ? mod 3? ，这与平方数模 3 只能取 0，1 矛盾，故 x, y 中有一个为 3 的倍数. （2）由 x 为偶数.，必有 y, z 均为奇数，记x ? 2m, y ? 2 p ? 1, z ? 2q ? 1 有则4m 2 ? x 2 ? z 2 ? y 2 ? ? 2q ? 1? ? ? 2 p ? 1? ? 4 ? q 2 ? q ? p 2 ? p ?2 2m2 ? q ? q ? 1? ? p ? p ? 1? 右边是两个偶数的差，必为偶数，从而 x 为 4 的倍数.（3）若 x, y 中有 5 的倍数，命题已成立. 若 x, y 均不是 5 的倍数，则若 x, y 只能是形如 5k ? 1 或 5k ? 2 的正整 数.若 x, y 均为 5k ? 1 型，则 z ? x ? y ? 1 ? 1 ? 2 ? mod 5 ?2 2 2这与平方数模 5 只能取 0，1，4 矛盾若 x, y 均为 5k ? 2 型，则 z ? x ? y ? 4 ? 4 ? 3 ? mod 5 ?2 2 2这与平方数模 5 只能取 0，1，4 矛盾.所以， x, y 只能分别取 5k ? 1 与 5k ? 2 型，有z 2 ? x 2 ? y 2 ? 4 ? 1 ? 0 ? mod 5 ? 得 5 z 2 ，但 5 是素数，得 5 z .（4）由上证（1）（2）及 ? 3, 4 ? ? 1 知， xy 是 12 的倍数，则 、 例 361 xy 是 6 的倍数，得三角形的面积是 6 的倍数． 2已知 ? ABC 内有 n 个点，连同 A, B, C 共有 n ? 3 个点，以这些点为顶点，把 ? ABC 分割为若干个互不重叠的小三角形，现把 A, B, C 分别染上红色、蓝色、黄色，而其余 n 个点，每点任意染上红、蓝、黄三色之一， 证明三顶点都不同色的小三角形的总数必是奇数． （斯潘纳定理） 证明 1 给这些小三角形的边赋值：当边的两端点同色时，记为 0；当边的两端点异色时，记为 1； 再用三边之和给小三角形赋值：当三角形的三顶点同色时，和值为 0，记这样的小三角形有 a 个；当三角形的 三顶点中仅有两点同色时，和值为 2，记这样的小三角形有 b 个；当三角形的三顶点两两异色时，和值为 3，记这 样的小三角形有 c 个.下面用两种方法计算所有三角形赋值的总和 S ，一方面 ① S ? 0 ? a ? 2 ? b ? 3? c ? 2b ? 3c . 另方面， AB, BC, CA 的赋值均为 1，和为奇数；而 ? ABC 内的每一条连线，在上述 S 的计算中都被计算了两18次，和为偶数；这两者之和得 S 为奇数，记为 ② S ? 2k ? 1 由①，②得 2k ? 1 ? 2 ? 3可见 c 为奇数，即三顶点都不同色的小三角形的总数必是奇数． （ b c 证明：n 个连续整数的乘积一定能被 n!整除设 a 为任一整数，则式： (a+1)(a+2)...(a+n) =(a+n)!/a! =n!*[(a+n)!/(a!n!)] 而式中[(a+n)!/(a!n!)]恰为 C(a+n,a),也即是从 a+n 中取出 a 的组合数，当然为整数。 所以(a+1)(a+2)...(a+n)一定能被 n!整除同余式与不定方程例：求使 2 +1 能被 3 整除的一切自然数 n. 解∵n n∴则 2 +1nn∴当 n 为奇数时，2 +1 能被 3 整除；当 n 为偶数时，2 +1 不能被 3 整除. 例 2 求 2 最后两位数码. 解 考虑用 100 除 2 所得的余数.∵ ∴ ∴ ∴ ∴2 的最后两位数字为 88. 例3 证明 ∴ 2．不定方程 不定方程的问题主要有两大类：判断不定方程有无整数解或解的个数；如果不定方程有整数解，采取正确 的方法，求出全部整数解. (1) 不定方程解的判定 求证 3 ∵ ∴ ∴ 999又+41981能被 5 整除.19如果方程的两端对同一个模 m(常数)不同余,显然,这个方程必无整数解.而方程如有解则解必为奇数、偶 数两种，因而可以在奇偶性分析的基础上应用同余概念判定方程有无整数解. 例4 证明方程 2x -5y =7 无整数解.2 2证明∵2x =5y +7，显然 y 为奇数.① 若 x 为偶数，则22∴∵方程两边对同一整数 8 的余数不等，∴x 不能为偶数.②若 x 为奇数，则但 5y +72∴x 不能为奇数.因则原方程无整数解.说明:用整数的整除性来判定方程有无整数解,是我们解答这类问题的常用方法. 例5 不存在整数 x,y 使方程①证明 如果有整数 x，y 使方程①成立，则=知（2x+3y ）+5 能被 17 整除.2设 2x+3y=17n+a，其中 a 是 0，±1，±2，±3，±4，±5，±6，±7，±8 中的某个数，但是这时（2x+3y）2+5=（17n） +34na+（a +5）=a +5（mod17），而 a +5 被 17 整除得的余数分别是 5，6，9，14，4，13，7，222223，1，即在任何情况下（2x+3y） +5 都不能被 17 整除，这与它能被 17 整除矛盾.故不存在整数 x，y 使 ①成立. 例 7 满足方程 x +y =x 的正整数对（x，y）的个数是（ （A）0 （B）1（C）2（D）无限个（E）上述结论都不对 解由 x +y =x 得 y =x （x-1），所以只要 x-1 为自然数的平方，则方程必有正整数解.令 x-1=k (k 为自然2 2 3 2 2 2 2 2 3）.数),则为方程的一组通解.由于自然数有无限多个,故满足方程的正整数对(x,y)有无限多个,应选(D).说明:可用写出方程的一组通解的方法,判定方程有无数个解.20(2)不定方程的解法不定方程没有统一的解法,常用的特殊方法有:配方法、因式（质因数）分解法、不等式法、奇偶分析法和 余数分析法.对方程进行适当的变形,并正确应用整数的性质是解不定方程的基本思路.例6求方程2 2 2的整数解.解(配方法)原方程配方得(x-2y) +y =13 . 在勾股数中,最大的一个为 13 的只有一组即 5,12,13,因此有 8 对整数的平方和等于 13 即 (5,12),(12,5),(-5,-12),(-12,-5),(5-,12),(12,-5),(-5,12),(-12,5).故原方程组的解只能是下面的 八个方程组的解2解得例 7 已知两个自然数 b 和 c 及素数 a 满足方程 a +b =c .证明:这时有 a＜b 及 b+1=c. 证明（因式分解法）∵a +b =c ，∴a =（c-b）（c+b），又∵a 为素数，∴c-b=1，且 c+b=a .2 2 2 2 2222于是得 c=b+1 及 a =b+c=2b+1＜3b，即2＜.而 a?3,∴?1，∴＜1.∴a＜b.21例 9 满足联立方程的正整数（a，b，c）的组数是（）.解（质因数分解法）由方程 ac+bc=23 得（a+b）c=23=1×23. ∵a， c 为正整数， b， ∴c=1 且 a+b=23.将 c 和 a=23-b 代入方程 ab+bc=44 得(23-b)b+b=44,即(b-2)(b-22)=0, ∴b1=2,b2=22.从而得 a1=21,a2=1.故满足联立方程的正整数组(a,b,c)有两个,即(21,2,1)和(1,22,1) 例 10 求不定方程 2(x+y)=xy+7 的整数解.解 由(y-2)x=2y-7,得分离整数部分得 由 x 为整数知 y-2 是 3 的因数, ∴y-2=±1，±3，∴x=3，5，±1. ∴方程整数解为例 11求方程 x+y=x -xy+y 的整数解. 必须△=（y+1） -4（y -y）?0，解得2 222解（不等式法）方程有整数解?y?.满足这个不等式的整数只有 y=0，1，2. 当 y=0 时，由原方程可得 x=0 或 x=1；当 y=1 时，由原方程可得 x=2 或 0；当 y=2 时，由原方程可得 x=1 或 2.22所以方程有整数解最后我们来看两个分式和根式不定方程的例子.例 12求满足方程且使 y 是最大的正整数解（x，y）.解将原方程变形得 由此式可知，只有 12-x 是正的且最小时，y 才能取大值.又 12-x 应是 144 的约数，所以， 12-x=1，x=11，这时 y=132. 故 满足题设的方程的正整数解为（x，y）=（11，132）.例 13（第 35 届美国中学生数学竞赛题）满足 0＜x＜y 及 数是（ （A）0 ）. （B）1 （C）3 （D）4 （E）7的不同的整数对（x，y）的个解法 1 根据题意知，0＜x＜1984，由得 当且仅当 1984x 是完全平方数时，y 是整数.而 ，故当且仅当 x 具有 31t 形式时，1984x 是完 全平方数. ∵x＜1984，∵1?t?7.当 t=1，2，3 时，得整数对分别为（31，1519）、（124，1116）和（279，775）. 当 t＞3 时 y?x 不合题意，因此不同的整数对的个数是 3，故应选（C）.236 2解法 2 ∵1984=∴由此可知：x 必须具有 31t 形式，y 必须具有 31k 形式，并且22t+k=8（t，k 均为正整数）.因为 0＜x＜y，所以 t＜k.当 t=1，k=7 时得（31，1519）；t=2，k=6 时得（124， 1116）；当 t=3，k=5 时得（279，775）.因此不同整数对的个数为 3. (1)方程 x -y =105 的正整数解有( （A） 一组 （B）二组2 2).（C）三组 （D）四组 ）.(2)在 0,1,2,?，50 这 51 个整数中，能同时被 2，3，4 整除的有（ （A） 2．填空题 （1）的个位数分别为_________及_________. 3 个 （B）4 个 （C）5 个 （D）6 个(2)满足不 (3) (4)等式 10 ?A?10 的整数 A 的个数是 x×10 +1，则 x 的值________.3454已知整数 y 被 7 除余数为 5,那么 y 被 7 除时余数为________. 求出任何一组满足方程 x -51y =1 的自然数解 x 和 y_________.2 23.求三个正整数 x、y、z 满足. 4．（1985 年上海数学竞赛题）在数列 4，8，17，77，97，106，125，238 中相邻若干个数之和是 3 的倍 数，而不是 9 的倍数的数组共有多少组？5．求的整数解.6．求证可被 37 整除.7．（全俄 1986 年数学竞赛题）求满足条件的整数 x，y 的所有可能的值.248．（1985 年上海初中数学竞赛题）已知直角三角形的两直角边长分别为 l 厘米、m 厘米，斜边长为 n 厘 米，且 l，m，n 均为正整数，l 为质数.证明：2（l+m+n）是完全平方数.9.(1988 年全国初中数学竞赛题)如果 p、q、 练习二十、都是整数，并且 p＞1，q＞1，试求 p+q 的值.1.D.C.2.(1)9 及 1.2(2)9.2(3)4.(4)原方程可变形为 x =(7y+1) +2y(y-7),令 y=7 可得 x=50.3.不妨设 x?y?z,则,故 x?3.又有故 x?2.若 x=2,则,故 y?6.又有,故 y?4.若 y=4,则 z=20.若 y=5,则 z=10.若 y=6,则 z 无整数解.若 x=3,类似可以确定 3?y?4,y=3 或 4,z 都不能是整数.4.可仿例 2 解.5.先求出 方数,?,解得,然后将方程变形为 y=5+x-2要使 y 为整数,5x-1 应是完全平6.8888≡8(mod37),∴≡7(mod37),777733332222≡8 (mod37).33332≡7 (mod37),88882 232222+7777≡(8 +7 )(mod37),而 8 +7 =407,37|407,∴37|N.23237.简解:原方程变形为 3x -(3y+7)x+3y -7y=0 由关于 x 的二次方程有解的条件△?0 及 y 为整数可得 0?y ?5,即 y=0,1,2,3,4,5.逐一代入原方程可知,原方程仅有两组解(4,5)、(5,4). 8.∵l +m =n ,∴l =(n+m)(n-m).∵l 为质数,且 n+m＞n-m＞0,∴n+m=l ,n-m=1.于是 l =n+m=(m+1)+m=2m+1,2m=l -1,2(l+m+1)=2l+2+2m=l +2l+1=(l+1) .即 2(l+m+1)是完全平方数.2 2 2 2 2 2 2 2 29.易知 p≠q,不妨设 p＞q.令 p、q 之值.=n,则 m＞n 由此可得不定方程(4-mn)p=m+2,解此方程可得25赛题精讲 例 1：数 1978 与 1978 的最末三位数相等，试求正整数 m 和 n，使得 n+m 取最小值，这里 n ? m ? 1. （第 20 届 IMO 试题）n m【解】由已知 1978 ? 1078 (mod 1000 ), 而 5，所以n m n m 1 9 7 8 ? 1 0 7 8 ( m o 8) d① ②－1978 n ? 1078 m (mod 125)因 n ? m ? 1 ，且（1978m，125）=1，则由②式知 1978n m≡1（mod125）③ 又直接验证知，1978 的各次方幂的个位数字是以 8、4、2、6 循环出现的，所以只有 n－m 为 4 的倍数时，③ 式才能成立，因而可令 n－m=4k.由于. n+m=（ n－m）+2m=4k+2m，因而只需确定出 k 和 m 的最小值. 先确定 k 的最小值：因为 19784=（79×25+3）4≡34≡1（mod5） ，1（mod25）.故可令 ， 而 5 t，从而 0≡1978n－m－1=19784k－1=（5k+1）k－1≡k (k ? 1) ? (5t ) 2 2+ k ? 5t (mod 125 ) ，显然，使上式成立的 k 的最小值为 25. 再确定 m 的最小值：因 1978≡2（mod8） ，则由①式知， 2 ? 2 (mod 8)n m④由于 n ? m ? 1, ④式显然对 m=1，2 不成立，从而 m 的最小值为 3. 故合于题设条件的 n+m 的最小值为 106. 【评述】比例中我们用了这样一个结论：1978 的各次方幂的个位数字是以 8，4，2，6 循环出现，即，当 r=1， 2，3，4 时， 1978 义： 整数列 ?x n ? 各项除以 m（m?2，m∈N*）后的余数 a n 组成数列 ?a n ?.若 ?a n ?是一个周期数列，则称 ?x n ? 是关 于模 m 的周期数列，简称模 m 周期数列.满足 a n ?T ? a n （或 a n ?T ? x n （modm） ）的最小正整数 T 称为它的周期. 例如， （1） 1978p? 1978 4 q ?r ? 8,4,2,6(mod 10). 这种现象在数学上称为“模同期现象”.一般地，我们有如下定?n?是模 10 周期数列，周期为 4； （2）自然数列{n}是一个模 m（m?2，m∈N*）周期数列，周期为 m； （3）任何一个整数等差数列都是一个模 m（m?2，m∈N*）周期数列，周期为 m. 例 2：设 a 是方程 x 3 ? 3x 2 ? 1 ? 0 的最大正根，求证：17 可以整除[a1788]与[a1988].其中[x]表示不超过 x 的最大 整数. （第 29 届 IMO 预选题）【证明】根据如下符号表可知，若设三根依次为 ? ? ? ? a ，则 ? 1 ? ? ? ?1 1 , ? ? ? 1, 2 2x f(x)符号－1 －－1 21 2+1 －2 3－3 ++2 2 ? a,由于f (?? ) ? ?2? 3 ? (? 3?2? 2 ? 1) ? ?2? 3 ? 0, 于是 ? ? ? ? , | ? |? ? .26另一方面，由韦达定理知，? 2 ? ? 2 ? (? ? ? ) 2 ? 2?? ? (3 ? a) 2 ?2 2 ? 6a 2 ? a 3 ? 2a 3 ? a 3 ?9? ?9? ? 1 ? (8 ? a 2 ) a a a? a 2 ? (2 2 ) 2 ? 8,?? 2 ? ? 2 ? 1.为了估计[ a 1788 ]、[ a 1988 ]，先一般考察[an]，为此定义：u n ? ? n ? ? n ? a n .( n ? 0,1,2,?)直接计算可知： u 0 ? 3, u1 ? 2 ? ? ? a ? 3.u 2 ? ? 2 ? ? 2 ? a 2 ? 9,以及u n?3 ? 3u n? 2 ? n(n ? 0). 又 因0 ? ? n ? ? n ? 1(?| ? |? ? ,即? n ? ? n ? 0, 又? ? ? ? 3 ? ? ? 2 ? 2 2 ? 1,当n?2时，? n ? ? n ?| ? | n ? ? n ? ? 2 ? ? 2 ? 1), 则a n ? u n ? (? n ? ? n ) ? u n ? 1 ? [1 ? (? n ? ? n )].?[a n ] ? u n ? 1.( n ? 1,2,?)由此知，命题变为证明： u1788 ? 1和u1988 ? 1 能被 17 整除. 现考察 ?u n ? 在模 17 的意义下的情况：u 0 ? 3, u1 ? 3, u 2 ? 9,u 3 ? 7, u 4 ? 1, u5 ? 11, u 6 ? 9,u 7 ? 9, u8 ? 16, u9 ? 5, u10 ? 6,u 11? 2,u12 ? 1, u13 ? 14, u14 ? 6,u 15 ? 0, u16 ? 3, u17 ? 3, u18 ? 9,??可见，在模 17 意义下， ?u n ? 是 16 为周期的模周期数列，即 u n ?16 ? u n (mod 17 ). 由于 1788 ? 12(mod 16),1988 ? 4(mod 16), 故u1788 ? u12 ? 1(mod 17 ), u1988 ? u 4 ? 1(mod 17 ), 故u 1788?1 ? 0, u1988 ? 1 ? 0(mod 17 ). 命题得证.例 3：求八个整数 n1 , n2 ,?, n8 满足：对每个整数 k（－1985&k&1985） ，有八个整数 a1，a2，?，a8∈{－1，0， 1}，使得 k ? a1 n1 ? a 2 n2 ? ? ? a8 n8 . （第 26 届 IMO 预选题）【解】令数集 G ? k | k ? a1 ? a 2 ? 3 ? a3 ? 32 ? ? ? a n?1 ? 3n , ai ? {?1,0,1}, i ? 1,2,?, n ? 1 .??显然m a x ? 1 ? 3 ? 32 ? ? ? 3n ? G3n ?1 ? 1 2记H， mixG ? 1 ? 3 ? 32 ? ? ? 3n ? ? H .且 G 中的元素个数有 3n?1 ? 2H ? 1 个.又因 G 中任意两数之差的绝对值不超过 2H，所以 G 中的数对模 2H+1 不同 余.因此，G 的元素恰好是模 2H+1 的一个绝对值最小的完系，于是，凡满足 ? H ? k ? H 的任意整数都属于 G，且 可惟一地表示为： a1 ? a 2 ? 3 ? a3 ? 32 ? ? ? a n?1 ? 3n 形式. 当 n=7 时，H=，而 n=6 时，H=.故 n1=1，n2=3，?，n8=37 为所求. 例 4：设 n 为正整数，整数 k 与 n 互质，且 0&k&n.令 M={1，2，?，n－1}，给 M 中每个数染上黑、白两种颜27色中的一种，染法如下： （i）对 M 中每个 i，i 与 n－i 同色； （ii）对 M 中每个 i，i≠k,i 与|k－i|同色.求证：M 中所 有的数必为同色. （第 26 届 IMO 试题） 【证明】因 (k , n) ? 1, 又 0，1，?n－1 是模 n 的一个完全剩余系，所以 0，k，2k，?， （n－1）k 也是模 n 的 一个完全剩余系.若设 jk ? r j (mod n)(其中 ? r j ? n ? 1, j ? 1,2,?, n ? 1), 1 则 M= {r1 , r2 ,?, rn ?1 }. 下只需证 r j ?1与r j (1 ? j ? n ? 2). 因为，若如此，当 r1 的颜色确定后，M 中所有都与 r1 同色. 由于 ( j ? 1)k ? r j ?1 (mod n), 则r j ? k ? r j ?1 (mod n) ，因此， （1）若 r j ? k ? n,则r j ?1 ? r j ? k ，于是，由条件（i）知，k ? r j ?1 ? n ? r j 与n ? (n ? r j ) ? r j 同色.又由条件（ii） 知， k ? r j ?1与 | k ? r j ?1 ? k |? r j ?1 同色，故 r j ?1与r j 同色.综上所述可知， r j ?1与r j 同色.命题得证. 例 5：设 a 和 m 都是正整数，a&1.证明： m | ? (a ? 1).m【证明】实上，显然 a与a ? 1 互素，且 a模a ? 1 的阶是 m，所以由模阶的性质③导出 m | ? (a ? 1).m mm例 6：设 p 是奇素数，证明：2p－1 的任一素因了具有形式 2 px ? 1, x 是正整数. 【证明】设 q 是 2p－1 的任一素因子，则 q≠2.设 2 模 q 的阶是 k，则由 2 ? 1(mod q) 知 k|p，故 k=1 或 p（因pp 是素数，这是能确定阶 k 的主要因素）.显然 k≠1，否则 2 ? 1(mod q), 这不可能，因此 k=p.1现在由费马小定理 2 证毕.q ?1? 1(mod q) 推出 k | q ? 1,即p | q ? 1. 因 p、q 都是奇数，故 q－1=2px（x 是个正整数） ，例 7：设 m,a,b 都是正整数，m&1，则 m ? 1, m ? 1) ? ma b a b( a ,b )? 1.( a ,b )【证明】记 d ? (m ? 1, m ? 1). 由于（a,b）|a 及（a,b）|b，易知 m?1 | ma ?1及m ( a ,b ) ? 1 | m b ? 1 ，故 m ( a ,b ) ? 1 | d ，另一方面设 m 模 d 的阶是 k，则由m a ? 1(mod d ), m b ? 1(mod d ) 推出，k|a 及 k|b，故 k|（a，b）.因此 m ( a ,b ) ? 1(mod d ), 即d | m ( a ,b ) ? 1.综合两方面可知， d ? m ( a ,b ) ? 1. 证毕. 例 8： n， 是给定的整数， 设 k n&0， k 且 （n－1） 是偶数.证明： 存在 x, y, 使得( x, n) ? ( y, n) ? 1, 是 x ? y ? k (mod n). 【证明】我们先证明，当 n 为素数幂 p 时结论成立.实际上，我们能证明，存在 x,y，使 p xy，且 x ? y ? k .如 p=2，则条件表明 k 为偶数，可取 x ? 1, y ? k ? 1; 如p ? 2, 则x ? 1, y ? k ? 1或x ? 1, y ? k ? 2 中 有一对满足要求.一般情形下，设 n ? p1 1 ? p r r 是 n 的标准分解，上面已证明，对每个 p i ，均有整数 x i ， y i ，使 pi xiyi，且 xi ? yi ? k (1,2,?, r ). 现在孙子定理表明，同余方程组28? ??? x ? x1 (mod p1 1 ), ?, x ? xr (mod prar ) 有解 x，同样? y ? y1 (mod p1 1 ), ?, y ? y r (mod prar )也 有 解 y. 现 在 易 证 x,y 符 合 问 题 中 的 要 求 ： 因 pixiyi ， 故 pixy（ i=1 ， ? ， r ） 于 是 （ xy， n ） =1. 又 ，x ? y ? xi ? yi ? k (mod pi?1 )(i ? 1,?, r ), 故x ? y ? k (mod n).例 9：设 n 为任意的正整数.证明：一定存在 n 个连续的正整数解，使其中任何一个都不是质数的整数幂. （第 30 届 IMO 试题） 【证明】取 2n 个两两不同的质数 p1 , p2 ,?, pn 和q1 , q2 ,?, qn . 同余方程组 x ? ?i(mod pi qi ),i ? 1,2,?, n .由于 p1q1 , p2 q2 ,?, pn qn 两两互质，根据孙子定理必有解，取为正整数 N，则 n 个连续正整数 N+1，N+2，?，N+n 都至少含有两个不同的质因数，因而它们中的任一个都不是质数的整数幂.证毕. .、数论素有“数学皇后”的美称。由于其形式简单，意义明确，所用知识不多而又富于技巧性，千 姿百态，灵活多样。有人曾说： “用以发现数学天才，在初等数学中再也没有比数论更好的课程了。 ” 因此在理念的国内外数学竞赛中，几乎都离不开数论问题，使之成为竞赛数学的一大重要内容。 例 1 证明无穷数列 1001，??中没有素数。 证明：设 an ?
，则 an ? 1 ? 10 ? 10 ? ? ? 10 ?? ??? ? ?4 8 4( n ?1)n个1104 n ? 1 = 4 10 ? 1当 n 为偶数，设 n ? 2k ， an =108k ? 1 (108 ) k ? 1 108 ? 1 ? ? 104 ? 1 108 ? 1 104 ? 1所以 an 为合数。当 n 为奇数，设 n ? 2k +1 ，an =（ 104 2 k +1）? 1 （ 2）k ?1 ? 1（ 2）k ?1 ? 1 10 2 10 2 = ? 所以 an 为合数。 104 ? 1 102 ? 1 102 ? 1评析：对 n 分奇偶，分情况讨论，问题变得清晰易证。同时注意，若 n 为奇数时， x n ? y n 可分解因式。 例 2 证明对任意整数 n ? 1 ， n4 ? 4n 不是素数。 证明：当 n 为偶数时， n4 ? 4n 为偶数，所以 n4 ? 4n 为合数；(2 当 n 为奇数，设 n ? 2k ? 1 ，则 n4 ? 4n =n4 ? 42 k ?1 ? n4 ? 4? k )4=n4 ? 4n2 (2k ) 2 ? 4? k ) 4 ? 4n2 (2k ) 2 (2 ? [n 2 ? 2(2k ) 2 ]2 ? 4n2 (2k ) 2 ? [n 2 ? 2(2k ) 2 ? 2n ? 2k ]? n 2 ? 2(2 k ) 2 ? 2n ? 2 k ] [所以 n4 ? 4n 为合数。29例 3 设正整数 a, b, c, d 满足 ab ? cd 。证明： a ? b ? c ? d 不是素数。 证明：由于 ab ? cd ，则设a ? pu, c ? pv d ? qu, b ? qva d u ? ? ，其中 (u, v) ? 1 ，则 c b v故 a ? b ? c ? d =pu ? qv ? pv ? qu ? p(u ? v) ? q(u ? v) ? ( p ? q)(u ? v) 所以为合数。a d ? ，不妨设 gcd(a, c) ? s,gcd(d , b) ? t ,则 c ba1s d1t a d ，所以 1 ? 1 ，即 a1b1 =c1d1 ? c1s b1t c1 b1评析：此题中采用方法可扩展如下：若a ? a1s, c ? c1s b ? d1t , b ? b1t，且 gcd(a1 , c1 ) ? gcd(d1 , b1 ) ? 1 由于所以 a1 d1 c1 , gcd(a1 , c1 ) ? 1 ，故 a1 d1 。同理可证 d1 a1 ，所以 a1 =d1 同理可得 c1 =b1 例 4 证明：若正 整数 a, b 满足 2a 2 ? a ? 3b2 ? b ，则 a ? b 和 2a ? 2b ? 1都是完全平方数。 证明： 因 2a 2 ? 2b2 ? a ? b ? b2 ，即 (a ? b)(2a ? 2b ? 1) ? b 2 故只需证 a ? b 和 2a ? 2b ? 1互质。 设 gc d (a ? b, 2a ? 2b ? 1) ? d ,即证 d ? 1 则 d a ? b, d 2a ? 2b ? 1 由于 d 2 b 2 ，所以 d b ，又 d a ? b ，则 d a 。所以 d 1 ，故 d ? 1 得证。 故 a ? b 和 2a ? 2b ? 1互质，所以 a ? b 和 2a ? 2b ? 1都是完全平方数。 评析：有时，适当的因式分解可以使问题简化，以证得结论。 例 5 一个正整数，加上 100 为一个完全平方数，若加上 168 则为另一个完全平方数，求这个数。 解：设这个数为 x ，则? x ? 100 ? a 2 ? ? 2 ? x ? 168 ? b ?其中 a, b ? N （注：限定正的可减少讨论） 。故 (b ? a)(b ? a) ? 22 ?17 ，从而 b ? a 与 b ? a 则等于把 22 ?17 拆开的因数 1、2、4、17、34、68.这样就 有六种情形。又由于 b ? a ? b ? a ，且 b ? a 与 b ? a 同奇偶性，故?b ? a ? 2 ? ?b ? a ? 34所以 b ? 18, a ? 16 。则 x ? 162 ? 100 ? 156 。 例 6 求方程 x 4 ? y 4 ? z 4 ? 2 x 2 y 2 ? 2 x 2 z 2 ? 2 y 2 z 2 ? 24 的全部整数解。 解：对原方程进行变形、因式分解30(? x 2 ? y 2 ? z 2 ) 2 ? 4 y 2 z 2 ? 24x 4 ? y 4 ? z 4 ? 2 x 2 y 2 ? 2 x 2 z 2 ? 2 y 2 z 2 ? 4 y 2 z 2 ? 24 (? x 2 ? y 2 ? z 2 ? 2 yz )(? x 2 ? y 2 ? z 2 ? 2 yz ) ? 24 ( y ? z ? x)( y ? z ? x )( y ? z ? x )( y ? z ? x ) ? 24? 左边四个括号内奇偶性相同，而 24 ? 23 ? 3 为偶数，故括号内每个都为偶数，则应出现 24 ，矛盾。所以原方程无整数解。 例 7 证明：两连续正整数之积不能是完全平方数，也不能是完全立方数。 证明：1? 若有两连续正整数之积为完全平方数，设 x( x ? 1) ? t 2 （ x ? 1, t ? 2 ） ，则 ( x, x ? 1) ? ( x,1) ? 1 ， 则 x 与 x ? 1均为完全平方数。 故存在正整数 a, b 使得 x ? a 2 , x ? 1 ? b2 ，从而 b2 ? a 2 ? (b ? a)(b ? a) ? 1 这与 b ? a ? 2 矛盾。所以两连续正整数不能是完全平方数。 设 ， 则 2? 若有两连续正整数之积为完全立方数， x( x ? 1) ? t 3（ x ? 1, t ? 2 ） 则 ( x, x ? 1) ? ( x,1) ? 1 ， x 与x ? 1均为完全立方数。故存在正整数 a, b 使得 x ? a3 , x ? 1 ? b3 ，从而b3 ? a3 ? (b ? a)(b2 ? ba ? a 2 ) ? 1这与 b2 ? ba ? a 2 ? 3 矛盾。所以两连续正整数不能是完全平方数。例 9 在两个相邻的完全平方数 n 2 与 (n ? 1)2 之间任取若干个不同的整数， 证明它们中两两乘积互不相 同。证明：只需证明若 n2 ? a ? b ? c ? d ? (n ? 1)2 则 ad ? bc 若 ad ? bc ，则设a ? pu , b ? qu c ? pv, d ? qv（见例 3） ，则 q ? p, v ? u ，即 q ? p ? 1, v ? u ? 1d ? qv ? ( p ? 1)(u ? 1) ? pu ? p ? u ? 1? pu ? a ? n2 ? ?? ? p ? u ? 2 pu ? 2 a ? 2n ?? d ? n2 ? 2n ? 1 ? (n ? 1)2 ，矛盾故在两个相邻的完全平方数 n 2 与 (n ? 1)2 之间任取若干个不同的整数，它们中两两乘积互不相同。 评析：与例三的思想方法大同小异，因为它们都利用 ad ? bc 的结论。例 10 求不定方程 (n ? 1)! ? nk ? 1 的全部正整数解。 解：当 n ? 1 时，无解； 当 n ? 2 时， 1 ? 2k ? 1 ，有 k ? 1 ； 当 n ? 2 是， (n ? 1)! 为偶数， n 必为奇数 1? 当 n ? 3 时， 2 ? 3k ? 1 ， k ? 1312? 当 n ? 5 时， 24 ? 5k ? 1, k ? 2 3? 当 n ? 5 时，n ?1 n ?1 n ?1 (n ? 2)!( ? n ? 2) ， 2? (n ? 2)! 2 2 21 故 (n ? 1) (n ? 2)! ，则 (n ? 1) 2 n k ? 1 而 nk ? 1 ? (n ? 1 ? 1)k ? 1 ? (n ? 1) k ? Ck (n ? 1) k ?1 ? ? ? Ckk ?1 (n ? 1)所以 (n ? 1) 2 Ckk ?1 (n ? 1) ，则 ? n ? 1? k ， n ? 1 ? k 故 nk ? 1 ? nn?1 ? 1 ? (n ? 1)! ，与 (n ? 1)2 n k ? 1 矛盾，则无 解。综上，不定方程的正整数解为（2，1）（3，1）（5，2） 、 、 。 评析：通过分析估计归纳，对 n 分类讨论，一一得出结果。不等式的应用I．排序不等式（又称排序原理） 设有两个有序数组 a1 ? a 2 ? ? ? a n 及 b1 ? b2 ? ? ? bn . 则 a1b1 ? a 2 b2 ? ? ? a n bn （同序和） ? a1b j1 ? a 2 b j 2 ? ? ? a n b jn （乱序和） ? a1bn ? a 2 bn ?1 ? ? ? a n b1 （逆 序和）其中 j1 , j 2 ,?, j n 是 1，2，?，n 的任一排列.当且仅当 a1 ? a 2 ? ? ? a n 或 b1 ? b2 ? ? ? bn 时等号（对任 一排列 j1 , j 2 ,?, j n ）成立. IV．利用排序不等式还可证明下述重要不等式. 切比雪夫不等式：若 a1 ? a 2 ? ? ? a n ， b1 ? b2 ? ? ? bn ，则a1b1 ? a 2 b2 ? ? ? a n bn a1 ? a 2 ? ? ? a n b1 ? b2 ? ? ? bn ? ? . n n n证明：由题设和排序不等式，有 a1b1 ? a 2 b2 ? ? ? a n bn = a1b1 ? a 2 b2 ? ? ? a n bn ，a1b1 ? a2 b2 ? ? ? an bn ? a1b2 ? a2 b3 ? ? ? an b1 ，?? a1b1 ? a 2 b2 ? ? ? a n bn ? a1bn ? a2 b1 ? ? ? an bn?1 . 将上述 n 个不等式叠加后，两边同除以 n2，即得欲证的不等式.赛题精讲I．排序不等式的应用 应用排序不等式可以简捷地证明一类不等式，请看下述例题. 例 1：对 a, b, c ? R ，比较 a ? b ? c 与a b ? b c ? c a 的大小.3 3 3 2 2 2?取两组数a, b, a 2 , b 2 , c 2 .不管a, b, c的大小顺序如何，a 3 ? b 3 ? c 3都是同序和a 2 b ? b 2 c ? c 2 a都是乱序和，故 a 3 ? b 3 ? c 3 ? a 2 b ? b 2 c ? c 2 a .例 2： a, b, c ? R ，求证 a ? b ? c ??a2 ? b2 b2 ? c2 c2 ? a2 a2 b2 c2 ? ? ? ? ? . 2c 2a 2b bc ca ab32【思路分析】 应先将 a 、 b 、 c 三个不失一般性地规定为 a ? b ? c ? 0. 【略解】由于不等式关于 a 、 b 、 c 对称，可设 a ? b ? c ? 0. 于是 a ? b ? c ,2 2 21 c?1 b?1 a.由排序不等式，得 a 2 ?1 1 1 1 1 1 ? b 2 ? ? c 2 ? (逆序和) ? a 2 ? ? b 2 ? ? c 2 ? a b c b c a（乱序和）.及 a 2 ?1 1 1 1 1 1 ? b2 ? ? c2 ? ? a2 ? ? b2 ? ? c2 ? . a b c c a b以上两个同向不等式相加再除以 2，即得原式中第一个不等式.再考虑数组1 1 1 ，仿上可证第二个不等式，请读者自己完成. ? ? bc ca ab 1 1 1 例 6：设正数 a, b, c 的乘积 abc ? 1 ，试证： (a ? 1 ? )(b ? 1 ? )(c ? 1 ? ) ? 1. b c a a 3 ? b 3 ? c 3 ? 0, 及【略解】设 a ?x y z , b ? , c ? ，这里 x, y, z 都是正数，则原需证明的不等式化为 y z x( x ? y ? z )( y ? z ? x)( z ? x ? y) ? xyz, 显然x ? y ? z, y ? z ? x, z ? x ? y 中 最 多 只 有 一 个 非 负 数 . 若x ? y ? z, y ? z ? x, z ? x ? y 中恰有一个非正数，则此时结论显然成立.若 x ? y ? z, y ? z ? x, z ? x ? y 均为正数， 则 x, y, z 是某三角形的三边长.容易验证 1 ( x ? y ? z )( y ? z ? x)( z ? x ? y) ? [( x 2 ( y ? z ? x) ? y 2 ( z ? x ? y) ? z 2 ( x ? y ? z )]. 3故得 ( x ? y ? z )( y ? z ? x)( z ? x ? y) ? xyz. 【评述】 利用上述换元的方法可解决同类的问题.见下题：设正数 a 、 b 、 c 的乘积abc ? 1, 证明1 1 1 3 ? 2 ? 2 ? . a (b ? c) b (c ? a) c (a ? b) 22证明：设 a ?1 1 1 , b ? , c ? , 则xyz ? 1 ，且所需证明的不等式可化为 x y zx2 y2 z2 3 x y z ? ? ? ，现不妨设 x ? y ? z ，则 ? ? ，据排序不等式 y?z z?x x? y 2 y?z z?x x? y得x2 y2 z2 x y z ? ? ? z? ? x? ? y? y?z z?x x? y y?z z?x x? yx2 y2 z2 x y z ? ? ? y? ? z? ? x? 及 两式相加并化简可得 y?z z?x x? y y?z z?x x? y 2( x2 y2 z2 ? ? ) ? x ? y ? z ? 33 xyz ? 3. y?z z?x x? y例 7：设实数 x1 ? x2 ? ? ? xn , y1 ? y 2 ? ? ? y n , z1 , z 2 ,?, z n 是 y1 , y 2 , ?, y n 的一个置换，证明：? (xi ?1ni? y i ) 2 ?? ( xi ? z i ) 2 .i ?1n33【略解】 显然所需证不等式等价于? xi yi ?? xi z i , 这由排序不等式可直接得到.i ?1 i ?1nn【评述】 应用此例的证法可立证下题： 设 a k 是两两互异的正整数（ k ? 1,2,?) ，证明对任意正整数 n ，均有?ki ?1nak2n 1 ?? . i ?1 k证明：设 b1 , b2 , ?, bn 是 a1 , a 2 ,?, a n 的一个排列，使 b1 ? b2 ? ? ? bn ，则从条件知对每个1 ? k ? n, bk ? k ， 于是由排序不等式可知n a k n bk 1 ?? 2 ?? . ? k 2 i?1 k i?1 k i ?1 n求不定方程 x1 ? x2 ? x3 ? 3x4 ? 3x5 ? 5 x6 ? 21 的正整数解的组数． 解 令 x1 ? x2 ? x3 ? x ， x 4 ? x5 ? y ， x6 ? z ，则 x ? 3, y ? 2, z ? 1 ．先考虑不定方程 x ? 3 y ? 5z ? 21 满足x ? 3, y ? 2, z ? 1 的正整数解．? x ? 3, y ? 2, z ? 1 ，? 5z ? 21 ? x ? 3 y ? 12 ，?1 ? z ? 2 ．当 z ? 1 时，有 x ? 3 y ? 16 ，此方程满足 x ? 3, y ? 2 的正整数解为 ( x, y) ? (10, 2), (7, 3), (4, 4) ． 当 z ? 2 时，有 x ? 3 y ? 11 ，此方程满足 x ? 3, y ? 2 的正整数解为 ( x, y ) ? (5, 2) ． 所以不定方程 x ? 3 y ? 5z ? 21 满足 x ? 3, y ? 2, z ? 1 的正整数解为( x, y, z ) ? (10, 2, 1), (7, 3, 1), (4, 4, 1), (5, 2, 2) ．又方程 x1 ? x 2 ? x3 ? x( x ? N , x ? 3) 的正整数解的组数为 C x ?1 ， 方程 x 4 ? x5 ? y ( y ? N , x ? 2) 的正整数解2的组数为 C y ?1 ，故由分步计数原理知，原不定方程的正整数解的组数为2 2 2 C 9 C1 ? C 6 C1 ? C 3 C1 ? C 2 C1 ? 36 ? 30 ? 9 ? 6 ? 81 ． 1 2 3 4 11例题选讲 例 1 100 个正整数之和为 101101，则它们的最大公约数的最大可能值是多少?证明你的结论. 注：看上去不好处理，实际比较容易， 101101 ? 101?1001 ，这样就好处理了，此时 101 为质数，比较好讨论了，101为质数，可以取 a1 ? a2 ? a3 ? ? ? a99 ? 1001, a100 ? 2例 2 证明：对一切整数 n , n ? 2n ? 12 不是 121 的倍数.2注解： n ? 2n ? 12 ? (n ? 1) ? 11 ，分析可以得到2 2例 3 能否有正整数 m 、 n 满足方程 m ? 2009 ? n22注解： 2009 ? 41? 49 例 4 一个正整数不是 42 的正整数倍和合数（不为零）之和，这个数的最大值是多少？34解析：这个整数必定可以写成 42n ? p ，其中 p 为 1 或素数，其中 p ? 1, 2,3,5,7,11,13,17,19, 23, 29,31,37, 41 ， 因为可以从 42(n ? 1) ? p ? 42 ，所以先排除p ? 2,3, 7,13, 23, 再者，有 42(n ? 2) ? p ? 84 ，所以可以排除 p ? 1,11,17,31,37, 41 ，最后 42(n ? 3) ? p ? 126 ，所以可以排除 p ? 19, 29, ，只有 p ? 5 ，n 可以较大，通过尝试，可以得到 n ? 5 例 5 设 a, b, c 是三个互不相等的正整数。求证：在 a b ? ab ， b c ? bc ， c a ? ca 三个数中,至少有一个能被 103 3 3 3 3 3整除。 注：比较好考虑，分如下几类。 （1）三者中有 10 的倍数，则自然可以考虑。 （2）若无 10 的倍数，则 当三者均为偶数时，因为偶数的平方其个位数为 4，6， a , b , c 中必定有两个个位数相同，命题得证。 当三者均为奇数时， 如果有个位数为 5， 则显然成立。 如果没有 5， a , b , c 中必定有两个个位数相同 则 （为 1， ， 9） 命题得证。 当三者为 1 偶 2 奇，或 2 偶 1 奇时， a b ? ab ， b c ? bc ， c a ? ca 均为偶数，只要考虑三个数中必定有 5 的倍3 3 3 3 3 32 2 2 2 2 2数即可。 a , b , c 除以 5 的余数只有两种情形：1，4，所以其中必定有一个为 10 的倍数。 例 6 证明： T ? 1 ?a2221 1 1 ? ? ? ? (n ? 1) 不是整数 2 3 n? ? ?1 注： k ? 2 k pk ，其中 pk 为奇数，令 2 ? n 的最大正整数为 ? ，则 2 ? n 。这样在 1, 2,3, 4,5,?, n 中，有且仅有一个 k 其标准分解式中有 2 。从而 2?? ?11? ? 1 1 p1 ?? ? pnT ? 2? p1 ?? ? pn ?1 ? ? ? ? ? ? ，毫无疑问，有 n? ? 2 32? p1 ?? ? pnT ? 整数＋1 p1 p2 ? pn ，矛盾。 28 11 n例 7 求所有这样的自然数 n ，使得 2 ? 2 ? 2 是一个自然数的平方. 解析： （1）当 n ? 8 时， N ? 2 ? 2 ? 2 ? (28 11 n 8? n? 211?n ? 1) ，因（?）为奇数，所以要使 N 为平方数， n 必为偶数.逐一验证 n ? 2,4,6,8 知，N 都不是平方数. （2）当 n ? 9 时， N ? 2 ? 2 ? 2 ? 2 ? 11 不是平方数.8 11 9 8（3） n ? 10 时，N ? 2 (9 ? 2 当8n ?82 n ?8 ) ， N 为平方数，9 ? 2 n ?8 应为奇数的平方， 要 不妨假设 9 ? 2 = (2k ? 1) ,则2n ?10? (k ? 1) ? (k ? 2). 由于 k ? 1 和 k ? 2 是一奇一偶，左边为 2 的幂，因而只能 k ? 1 =1，于是得 k ? 2 ，由2 n?10 ? 2 2 知 n ? 12 为所求.35例1．求不定方程 解：先求的整数解。 的一组特解，为此对37，107运用辗转相除法： ，， 将上述过程回填，得：由此可知，是方程的一组特解，于是，是方程的一组特解，因此原方程的一 例2．求不定方程切整数解为：。的所有正整数解。解：用原方程中的最小系数7去除方程的各项，并移项得：因为是整数，故也一定是整数，于是有，再用5去除比式的两边，得，令 经观察得为整数，由此得。 ，所是最后一个方程的一组解，依次回代，可求得原方程的一组特解：以原方程的一切整数解为： 例3．求不定方程。 的正整数解。 的取值范围，因为 的最小值为1，所以解：显然此方程有整数解。先确定系数最大的未知数。当时，原方程变形为，即，由上式知是 偶 数且故方程组有5组正整数解，分别为，，，，；当时， 原方程变形为， 即， 故方程有3组正整数解， 分别为：，，；当时，原方程变形为，即，故方程有2组正整数解，分别为：，；36当时，原方程变形为，即 8 4 1 10 1 1，故方程只有一组正整数解，为 2 9 2 4 6 2 6 3 2 2 5 3 4 2 3 2 1 4。故原方程有11组正整数解（如下表） ： 2 4 6 13 10 7 1 1 1例5．在直角坐标平面上，以（199，0）为圆心，以199为半径的圆周上的整点的个数为多少个？ 解：设 显然 但当 时， 为圆 上任一整点，则其方程为： 为方程的4组解。 （因为199是质数） ，此时， 。因为 这与199为 。 ，可设 型的质数矛盾！ 是一组勾股数，故199可表示为 ， ；两个正整数的平方和，即 则 因而圆 O 上只有四个整点 于是 。例8．求证：边长为整数的直角三角形的面积不可能是完全平方数。 证明：假设结论不成立，在所有的面积为平方数勾股三角形中选取一个面积最小的，设其边长为 ，则是平方数，则必有 是偶数）。因为，故存在整数 。中一奇一偶，，使得（不妨设由于 即 因为 是奇数， 易知是完全平方数，而知 ，所以 ， 于是 得 与 即两两互素，故它们是平方数，中有一个是， 另一个是， 而；另一方面，所以，以为边的三角形都是直角三角形，其面积等于是平方数，37但是，于是构造出了一个面积更小的勾股三角形，矛盾！3839例 3．设 k 证明： n? 1是一个奇数，证明 L 对于任意正整数 n ，数 1k ? 2 k ? ? ? n k 不能被 n ? 2 整除。? 1时，结论显然成立。设 n ? 2 ，记所说的和为 A，则：2 A ? 2 ? (2 k ? n k ) ? (3k ? (n ? 1) k ) ? ? ? (n k ? 2 k ) 。由 k 是正奇数，从而结于每一个 i? 2 ，数 i k ? (n ? 2 ? i) k 被 i ? (n ? 2 ? i) ? n ? 2 整除，故 2 A 被 n ? 2 除得余数为 2，从而。 2）A 不可能被 n ? 2 整除（注意 n ? 2 ? 例 4．设 m, n 是正整数， m ?（ （ 。 2 ，证明： 2 m ? 1） 2 n ? 1 ）n证明：首先，当 n ? m 时，易知结论成立。事实上， m ? n 时，结论平凡；当 n ? m 时，结果可由 2 出来（注意 m ? 。 2）? 1 ? 2 m?1 ? 1 ? 2 m ? 1 推最后， n ? m 的情形可化为上述特殊情形：由带余除法 n 而由若 n 是正整数，则 xn? mp ? r ,0 ? r ? m 而 q ? 0 ，由于 2 n ? 1 ? (2 mq ? 1)2 r ? 2 r ? 1 ，从? y n ? ( x ? y)( x n?1 ? x n?2 y ? ? ? xy n?2 ? y n?1 ) 知 (2 m ? 1) | (2 mq ? 1) ；而 0 ? r ? m ，故由上面证明了的结论知(2 m ? 1)m n ，从而当 n ? m 时，也有（ 2 ? 1 ） 2 ? 1 ） （ 。这就证明了本题的结论。 (2 r ? 1) （注意 r ? 0 时结论平凡）例 5．设正整数 a, b, c, d 满足 ab ? cd ，证明： a ? b ? c ? d 不是质（素）数。 证法一：由 ab ? cd ，可设 约分数a d m a m a ? ? 其中 (m, n) ? 1 。由 ? 意味着有理数 c b n c n c① ②的分子、分母约去了某个正整数 u 后得既m n，因此， a? mu, c ? nu? nv, d ? mv同理，存在正整数 v 使得 b因此， a ? b ? c ? d ＝ (m ? n)(u ? v) 是两个大于 1 的整数之积，从而不是素数。 注：若正整数 a, b, c, d 适合 ab ? cd ，则 a, b, c, d 可分解为①及②的形式，这一结果在某些问题的解决中很有作用。 证法二：由 ab ? cd ，得 b?(a ? c)( a ? d ) 也是整数。 a若它是一个素数，设为 可见cd a，因此 a ? b ? c ? d?a?cd (a ? c)( a ? d ) ，因为 a ? b ? c ? d 是整数，故 ?c?d ? a ap ，则由 (a ? c)(a ? d ) ? ap③p 整除 (a ? c)( a ? d ) ，从而素数 p 整除 a ? c 或 a ? d 。不妨设 p ｜ a ? c ，则 a ? c ? p ，结合③推出 a ? d ? a ，而。 ? 1）这是不可能的（因为 d例 6．求出有序整数对（m, n）的个数，其中1 ? m ? 99，1 ? n ? 99，(m ? n) 2 ? 3m ? n是完全平方数。（1999 年美国数学邀请赛试题） 解：由于 1 ?m ? 99 ， 1 ? n ? 99 可得：(m ? n) 2 ? 3m ? n ＜ (m ? n) 2 ? 4(m ? n) ? 4 ? (m ? n ? 2) 2 。又 ( m ? n)2? (m ? n) 2 ? 3m ? n ，于是 (m ? n) 2 ? (m ? n) 2 ? 3m ? n ? (m ? n ? 2) 240若 ( m ? n) 然而2? 3m ? n 是完全平方数，则必有 (m ? n) 2 ? 3m ? n ＝ (m ? n ? 1) 2 。(m ? n) 2 ? 3m ? n ＝ (m ? n ? 1) 2 ? n ? m ? 1 ， 于 是 必 有 n ? m ? 1 ? 0 ， 即 m ? n ? 1 ， 此 时 n ? 2,3,?,99 ，m ? 1,2,?,98 。所以所求的有序整数对（ m, n ）共有 98 对： (m, n) ? (1,2), (2,3), (3,4),?, (98,99) 。例 7．证明：若正整数 a, b 满足 2a2? a ? 3b 2 ? b ，则 a ? b 和 2a ? 2b ? 1 都是完全平方数。（2006 年山东省第二届夏令营试题）证法一：已知关系式即为 2a2? a ? 3b 2 ? b ? 2(a 2 ? b 2 ) ? (a ? b) ? b 2①（ ? （ a ? b ） 2a ? 2b ? 1 ）＝ b 2 若a ，结论显然。 ? b ? 0 （或者说 a, b 中有一个为 0 时）不妨设 a? b 且 ab ? 0 ，令 (a, b) ? d ，则 a ? a1d , b ? b1d ， (a1 , b1 ) ? 1? b1 )d，将其代入①得 2a12从而 a ? b ＝ (a1 因为 d2d ? a1 ? b1 ? 3b1 d2②| 2a1 d ，所以 d | (a1 ? b1 ) ，从而 d ? a1 ? b1 ；? b1 ) (2a1 ? 2b1 ? 1) ? b1d 2 ；? 1 ，所以 (a1 ? b1 , b1 ) ? 1 ? (a1 ? b1 )而②式又可写成 (a1 因为 (a, b) 所以 (a1 所以 d?d且 ( a1 , b1 )? b1 ) | d ，从而 a1 ? b1 ? d 。? a1 ? b1 ，所以 a ? b ＝ (a1 ? b1 )d ? d 2 ，从而 a ? b 为完全平方数。b2 b ? ( ) 2 也是完全平方数。 2 d d2所以 2a ? 2b ? 1 ?证法二：已知关系式即为 2a? a ? 3b 2 ? b ? 2(a 2 ? b 2 ) ? (a ? b) ? b 2①（ ? （ a ? b ） 2a ? 2b ? 1 ）＝ b 2 论证的关键是证明正整数 a ? b 与 2a ? 2b ? 1 互素。 记d 知。若 ? （ a ? b ， 2a ? 2b ? 1 ） d ? 1 ，则 d 有素因子 p ，从而由①知 p | b 2 。因为 p 是素数，故 p | b ，结合 p | (a ? b)p | a ，从而由 p | 2a ? 2b ? 1 得 p | 1，这是不可能的。故 d ? 1 ，从而由①推知正整数 a ? b 与 2a ? 2b ? 1 都是完全平方数。例 8．证明不存在正整数 n ，使 2n2+1，3n2+1，6n2+1 都是完全平方数。 证明：假设存在这样的正整数 n ，使 2n2+1，3n2+1，6n2+1 都是完全平方数，那么 （2n2+1） （3n2+1） 2+1）也必定是完全平方数。 （6n 而（2n2+1） （3n2+1） 2+1）＝36n6+36n4+11n2+1； （6n 41(6n 3 ? 3n) 2 ? 36n6+36n4+9n2； (6n 3 ? 3n ? 1) 2 ? 36n6+36n4+12n3+9n2+6n+1；所以 (6n3（3n （6n （3n （6n ? 3n) 2 ? （2n2+1） 2+1） 2+1）＜ (6n 3 ? 3n ? 1) 2 与（2n2+1） 2+1） 2+1）为完全平方数矛盾。1．证明：如果 证明：因为 于是 6 是p 和 p ? 2 都是大于 3 的素数，则 6 是 p ? 1 的因子。p 是奇数，所以 2 是 p ? 1 的因子。又因为 p ， p ? 1 ， p ? 2 除以 3 的余数各不相同，而 p 与 p ? 2 都不能被 3 整数。p ? 1 的因子。2n2．设 m ? n ? 0 ，证明： ( 2 解：由 2 又因为 2n? 1) | (2 2 ? 1) ；m n ?1 m ? n ?12m?1 ? (2 2n ?1? 1)[( 2 2 ) 2n? ? ? 22nn ?1? 1] ，故 (2 2n ?1n ?1? 1) ｜（ 2 2 ? 1 ） 。m2n ?1? 1 ? (2 2 ? 1) (2 2 ? 1) ，从而 (2 2 ? 1) ｜ (2 2n m? 1) ，于是由整除的性质知(2 2 ? 1) | (2 2 ? 1) 。3．证明：对于任意正整数 n ，数 1 证明：只需证 2（ n ? 2 ）2（ 1 因为若 n 是正整数，则 x 若 n 是正奇数，则 x 故 n ? 2｜ 205? 22005 ? ? ? n2005不能被 n ? 2 整除。? 22005 ? ? ? n2005 ）即可。n? y n ? ( x ? y)( x n?1 ? x n?2 y ? ? ? xy n?2 ? y n?1 ) ；n? y n ? ( x ? y)( x n?1 ? x n?2 y ? ? ? xy n?2 ? y n?1 ) ；? n2005 ； n ? 2 ｜ 32005 ? (n ? 1)2005 ，??， n ? 2 ｜ n 2005 ? 2 20052005所以 n ? 2 ｜2（ 2。 ?? ? n 2005 ） 2，所以 n ? 2 2（ 22005又因为 n ? 2 ? 3 ? 2 ，所以 n ? 2 即（ n ? 2 ）2（ 12005?? ? n 2005 ）＋2? 22005 ? ? ? n2005 ）命题得证。n4．已知 n 为正奇数，求证： 60 | 6 证明：因为若 n 是正整数，则 x 若 n 是正奇数，则 x 所以 3 | 6n n? 3n ? 2 n ? 1 。? y n ? ( x ? y)( x n?1 ? x n?2 y ? ? ? xy n?2 ? y n?1 ) ； ? y n ? ( x ? y)( x n?1 ? x n?2 y ? ? ? xy n?2 ? y n?1 ) ；n? 3n ， 3 | 2 n ? 1 ，从而 3 | 6 n ? 3n ? 2 n ? 1 ；4 | 6 n ? 2 n ， 4 | 3 n ? 1 ，从而 4 | 6 n ? 3n ? 2 n ? 1 ；5 | 6 n ? 1， 5 | 3n ? 2 n ，从而 5 | 6 n ? 3n ? 2 n ? 1 ；又 (3,4,5)? 1 且 3 ? 4 ? 5 ? 60 ，所以 60 | 6 n ? 3n ? 2 n ? 1 。42例 1． 设 x, y 是正整数， x 解：设 ( x, y)? y 且 x ? y ? 667 ，它们的最小公倍数是最大公约数的 120 倍，求 x, y 。? d ，则 x ? md , y ? nd ，其中 (m, n) ? 1 且 m ? n ，于是 [ x, y] ? mnd 。(1) ( 2)?md ? nd ? 667 ?(m ? n)d ? 23 ? 29 ? mnd 即? 3 ? 120 ? mn ? 2 ? 3 ? 5 ? d ? 由 m ? n 及（2）可得：所以 ?? m ? 1 ? m ? 2 ? m ? 3 ? m ? 4 ? m ? 5 ? m ? 6 ? m ? 8 ?m ? 10 ;? ;? ;? ;? ;? ;? ;? 。 ? n ? 120 ?n ? 60 ?n ? 40 ?n ? 30 ?n ? 24 ?n ? 20 ?n ? 15 ? n ? 12 ?由（1）可知只能取 ?? m ? 5 ?m ? 8 ;? ; ?n ? 24 ?n ? 15从而 d? 23 或 29，故 x ? 115, y ? 552 或 x ? 232, y ? 435 。? 0 ， mn | (m 2 ? n 2 ) ，则 m ? n 。例 2．设 m, n证明：设 (m, n)2 2?d，则 m? m1d，n2? n1 d ，其中 (m1 , n1 ) ? 1 。于是，已知条件转化为 m1 n1 | (m1 ? n1 ) ，故更有2 2m1 | (m1 ? n1 ) ，从而转化为 m1 | n1因此 m ? n 。，但是 (m1 , n1 )? 1 ，故 (m1 , n1 ) ? 1 ，结合 m1 | n122，知必有 m1? 1 ，同时 n1 ? 1 ，例 3．设正整数 a, b, c 的最大公约数是 1，并且 证明：设 (a, b) 化为 da1b1ab ? c ，证明 a ? b 是一个完全平方数。 a?b?d，则 a? a1 d ， b ? b1 d ，其中 (a1 , b1 ) ? 1 ，由于 (a, b, c) ? 1 ，故 (b, c) ? 1 ，现在问题中的等式可以转①? ca1 ? cb1由此可见 a1 整除 cb1 。因为 ( a1 , b1 )? 1 ，故 a1 | c ，同样可得 b1 | c ，再由 (a1 , b1 ) ? 1 便可以推出 a1b1 | c 。设 c ? a1b1k ，其中 k 是一个正整数。一方面，显然 k 整除 c ；另一方面，结合①式，得 d 故k? k (a1 ? b1 ) ，故 k | d ，从而 k | (c, d ) ，但 (c, d ) ? 1 ，? 1。? a1 ? b1 ，故 a ? b ? d (a1 ? b1 ) ? d 2 ，这样就证明了 a ? b 是一个完全平方数。因此， d 例 4．a, b 都是正整数，是否存在整数 p, q 使得对任意的正整数 n ， p ? na 与 q ? nb 互质？? [a, b] ， r ?解：令 L 令L L , s ? ，则 (r , s) ? 1，于是存在整数 x, y 使得 rx ? sy ? 1 ， a bp ? x, q ? ? y ，则对任意的正整数 n ，设 dn ? ( p ? na, q ? nb) ，有 dn | (r ( p ? na) ? s(q ? nb))所以 即对任意的正整数 n ， p ? na ， （ ? L ? sb ， dn | 1 ? dn ? 1，即 dn | (rp ? sq ? n(ra ? sb)) ， rp ? sq ? rx ? sy ? 1 ，ra 而q ? nb ）＝1。43例 6．求出所有的正整数对 (m, n) ，使得n3 ? 1 是一个整数。 mn ? 1（2006 年山东省第二届夏令营试题）解：由于 (m3, mn ? 1) ? 1 且 mn ? 1 | n 3 ? 1 ? mn ? 1 | m 3 (n 3 ? 1) ? mn ? 1 | m 3 n 3 ? 1 ? m 3 ? 1? mn ? 1 | m 3 ? 1，所以 m, n 是对称的。不妨设 m ? n 。n3 ? 1 n2 ? n ? 1 1 当 m ? n 时，则 2 ? ? n? ? N * ? n ? 2 ，从而 m ? n ＝2； n ?1 n ?1 n ?1当 m ? n 时，若 n? 1时，则有 m ? 1 | 2 ，所以 m ? 2 或 3；若n?2时 ， 由 于n3 ? 1 mn ? 1是 一 个 整 数 ， 从 而?k ? N *使 得n 3 ? 1 ? (kn ? 1)(mn ? 1)即kn ?1 ?又由于 nn3 ? 1 n3 ? 1 1 1 ，所以 kn ? 1 ＜ 1 ? 。 ? n? ? 2 n ?1 mn ? 1 n ? 1 n ?1? 2 ， k ? N * ，所以 k ? 1 。n2 ?1 2 所以 ? n ?1? ? N * 得 n ? 2 或 3， m ? 5 ； n ?1 n ?1所以 n3从而 ? 1 ? (n ? 1)(mn ? 1) ? mn3 ? n ? mn ? 1 }