清北学堂 2013 寒假数学 集训六数论导学-整除与同余.pdf

北京清北学堂教育科技有限公司 电话 010 88400806 010 88400903 网址 www topschool org 1 23 2013 寒假集训六数论导学 寒假集训六数论导学 数论是高考中没有要求 但数论是高考中没有要求 但是中学数学竞赛大纲中提出要求的内容 需要是中学数学竞赛大纲中提出要求的内容 需要 引起同学们注意 希望能提前做好预习和学习准备引起同学们注意 希望能提前做好预习和学习准备 一 整除和同余一 整除和同余 知识点知识点 1 整数的整除性整数的整除性 初等数论的基本研究对象是自然数集合及整数集合 我们知道 整数集合中可以作加 减 乘法运算 并且 这些运算满足一些规律 即加法和乘法的结合律和交换律 加法与乘法的分配律 但一般不能做除法 即 如 ba 是整除 0 b 则b a 不一定是整数 由此引出初等数论中第一个基本概念 整数的整除性 定义定义 1 带余除法 对于任一整数a和任一整数b 必有惟一的一对整数q r使得 rbqa br 0 并且整数q和r由上述条件惟一确定 则q称为b除a的不完全商 r称为b除a的余数 若 0 r 则称b整除a 或a被b整除 或称 ba是 的倍数 或称 ab是 的约数 又叫因子 记为 ab 否则 b a 任何a的非 1 a 的约数 叫做a的真约数 0 是任何整数的倍数 1 是任何整数的约数 任一非零的整数是其本身的约数 也是其本身的倍数 由整除的定义 不难得出整除的如下性质 由整除的定义 不难得出整除的如下性质 1 若 cacbba则 2 若 2 1 1 niZcbcaba i n i iii 其中则 3 若 ca 则 cbab 反之 亦成立 4 若 baba 则 因此 若 baabba 则又 5 a b互质 若 cabcbca则 6 p 为质数 若 21n aaap 则 p 必能整除 n aaa 21 中的某一个 特别地 若 p 为质数 apap n 则 7 如在等式 m k k n i i ba 11 中除开某一项外 其余各项都是c的倍数 则这一项也是c的倍数 8 n 个连续整数中有且只有一个是 n 的倍数 9 任何 n 个连续整数之积一定是 n 的倍数 北京清北学堂教育科技有限公司 电话 010 88400806 010 88400903 网址 www topschool org 2 23 定理定理 1 设大于 1 的整数a的标准分解式为 12 1212 n nn apppppp 为质数 i 均为非负整 数 则 a 的约数的个数为 n i i ad 1 1 所有的约数和为 n i i i p p a i 1 1 1 1 事实上 由算术基本定理的推论知 n i i ad 1 1 而各约数的和就是 n i ii i pap 1 1 展开后的各 项之和 所以 n i n i i ii p p ppa i i 11 1 1 1 1 例如 25200 24 32 52 7 所以 90 11 12 12 14 25200 d 99944 17 17 15 15 13 13 12 12 25200 2335 2 最大公约数和最小公倍数最大公约数和最小公倍数 定义定义 2 设a b是两个不全为 0 的整数 若整数 c 满足 bcac 则称 bac 为 的公约数 ba与 的所有 公约数中的最大者称为 ba与 的最大公约数 记为 ba 如果 ba 1 则称 ba与 互质或互素 定义定义 3 如果 ad是 b的倍数 则称 ad是 b的公倍数 ba与 的公倍数中最小的正数称为 ba与 的最小 公倍数 记为 ba 最大公约数和最小公倍数的概念可以推广到有限多个整数的情形 并用 21n aaa 表示 n aaa 21 的 最大公约数 21n aaa 表示 n aaa 21 的最小公倍数 若 1 21 n aaa 则称 n aaaa 321 互质 若 n aaa 21 中任何两个都互质 则称它们是两两互 质的 注意 n 个整数互质与 n 个整数两两互质是不同的概念 前者成立时后者不一定成立 例如 3 15 8 互质 但不两两互质 显然后者成立时 前者必成立 因为任何正数都不是 0 的倍数 所以在讨论最小公倍数时 一般都假定这些整数不为 0 同时 由于 baba与 有相同的公约数 且 baba 有限多个亦成立 因此 我们总限于在自然数集 合内来讨论数的最大公约数和最小公倍数 显然 若 ba 的标准分解式为 i n i i n i i ppbpa ii 11 为质数 ii a 为非负整数 则 1 ii n min i i a bp 北京清北学堂教育科技有限公司 电话 010 88400806 010 88400903 网址 www topschool org 3 23 1 ii n max i i a bp 例如 3960 23 32 5 11 756 22 33 7 则 3960 756 22 32 36 3960 756 23 33 5 7 11 83160 求最大公约数也可以用辗转相除法 其理论依据是 定理定理 2 设 a b c 是三个不全为 0 的整数 且有整数 t 使得 cbta 则 a b 与 b c 有相同的公约数 因而 cbba 即 btabba 因为 若 ad是 b 的任一公约数 则由 bdcdcbtabdad是即知和 c 的公约数 反之 若 bd是 c 的任一公约数 ad也是 b 的公约数 辗转相除法 设a bab N 且 由带余除法有 0 0 0 0 1111 112 12221 111 nnnnn nnnnnn rrqrr rrrqrr rrrqrb brrbqa 因为每进行一次带余除法 余数至少减 1 即 11 nn rrrb 而 b 为有限数 因此 必有一个最多 不超过 b 的正整数 n 存在 使得 0 n r 而 0 1 n r 故由定理二得 11211 babrrrrrrrr nnnnn 可得可得最大公约数和最小公倍数的如下性质 最大公约数和最小公倍数的如下性质 1 bambmamNm 则 2 设 bac 为 的公约数 则 c ba c b c a 特别地 若 1 c b c a bac则 3 设 n aaa 21 是任意 n 个正整数 如果 1222331 nnn a acc accac 则 nn caaa 21 因 21121111 nnnnnnnnnnnn ccacccacccac故而 如此类推得出 n c 能整除 nnn caaa于是 11 是它们的一个公约数 北京清北学堂教育科技有限公司 电话 010 88400806 010 88400903 网址 www topschool org 4 23 又设 n aaac 21 为 的任一公约数 则 21 acac 因而 2 cc 同理可推出 3 cc 如此类推最后可得 n cc 于是 n ccc 故 n c 是最大公约数 4 若 cba 则一定有整数 yx和 使得 cbyax 特别地 1 ba 存在 1 byaxyx使得 这可由辗转相除法的 式逆推而得 byaxrc n 5 若 1 bcbacba 则 6 a b N ak bkk a bk N bam 为 的任一公倍数 则 mba abbaba 特别地 若 abbaba 1 则 可由 直接得到 可由最小公倍数定义得 根据 式知 baba 11 ii nn iiii ii pminpab 7 设 n aaa 21 是任意n个正整数 若 1332221nn ammammaa mn 则 nn maaa 21 这是一个求多个整数的最小公倍数的方法 它可用证明 类似的方法来证明 3 方幂问题方幂问题 一个正整数n能否表成m个整数的k次方和的问题称为方幂和问题 特别地 当 1 m 时称为k次方问 题 当 2 k 时 称为平方和问题 能表为某整数的平方的数称为完全平方数 简称平方数 关于平方数 明显有如下一些简单的性质和结论 1 平方数的个位数字只可能是 0 1 4 5 6 9 2 偶数的平方数是 4 的倍数 奇数的平方数被 8 除余 1 即任何平方数被 4 除的余数只能是 0 或 1 3 奇数平方的十位数字是偶数 4 十位数字是奇数的平方数的个位数一定是 6 5 不能被 3 整除的数的平方被 3 除余 1 能被 3 整除的数的平方能被 3 整除 因而 平方数被 9 除的余数 为 0 1 4 7 且此平方数的各位数字的和被 9 除的余数也只能为 0 1 4 7 6 平方数的约数的个数为奇数 北京清北学堂教育科技有限公司 电话 010 88400806 010 88400903 网址 www topschool org 5 23 7 任何四个连续整数的乘积加 1 必定是一个平方数 定理定理 3 奇素数 p 能表示成两个正整数的平方和的充要条件是 14 mp 定理定理 4 设正整数 pmn 2 其中 p 不再含平方因数 n能表示成两个整数的平方的充要条件是 p 没有形 如 34 q 的质因数 定理定理 5 每个正整数都能表示成四个整数的平方和 这几个定理的证明略 这里重点是介绍有关k方幂的解法技巧 k方幂中许多问题实质上是不定方程的整 数解问题 比如著名的勾股数问题 4 除数函数除数函数 d n 正整数的正因数的个数称为除数函数 记为 d n 这里给出 d n 的计算公式 d n 为素数唯一分解定理中的指数 为了叙述地更加明确 我们给出素数唯一分解定理 算术基本定理 素数唯一分解定理 算术基本定理 素数唯一分解定理 任何一大于 1 的整数均可以分解为素数的乘积 若不考虑素数乘积的 先后顺序 则分解式是唯一的 例如 当一个整数分解成素数的乘积时 其中有些素数可以重复出现 例如在上面的分解 式中 2 出现了三次 把分解式中相同的素数的积写成幂的形式 我们就可以把大于 1 的正整数写成 1 此式称为的标准分解式 这样 算术基本定理也可以描述为大于 1 的整数的标准分解式是唯一的 不考虑 乘积的先后顺序 推论推论 1 若的标准分解式是 1 式 则是的正因数的充要条件是 2 应说明 2 不能称为是的标准分解式 其原因是其中的某些可能取零值 也有可能不含有某个素 因数 因而 推论推论 2 设 且 若是整数的次方 则也是整数的次方 特别地 若是整数的 北京清北学堂教育科技有限公司 电话 010 88400806 010 88400903 网址 www topschool org 6 23 平方 则也是整数的平方 5 5 同余同余 定义定义 4 4 设 m 是一个给定的正整数 如果两个整数 a 与 b 用 m 除所得的余数相同 则称 a 与 b 对模同余 记作 modmba 否则 就说 a 与 b 对模 m 不同余 记作 modmba 显然 有如下事实 1 若 mod0ma 则 m a 2 modbamZkbkmamba 每一个整数 a 恰与 1 2 m 这 m 个数中的某一个同余 同余的性质 同余的性质 1 反身性 modmaa 2 对称性 mod modmabmba 3 传递性 若 modmba modmcb 则 modmca 4 若 mod 11 mba mod 22 mba 则 mod 2121 mbbaa 特别是 mod modmkbkamba 5 若 mod 11 mba mod 22 mba 则 mod 2121 mbbaa 特别是 mod modmbkakZkmba 则 n k n k kk mba 11 mod n k n k kk mba 11 mod mod modmbaNnmba nn 则 若 mod mod 222121 mbambbaa 且1 2 ma 则 mod 11 mba 6 若 modmba 且mddba 则 d m d b d a mod 7 mod macabcba 8 若 mod1 modmbamcmbcac 时 则当 mod mod mod mbamcbcac d m badmc 特别地 时 当 9 若 mod 1 mba 北京清北学堂教育科技有限公司 电话 010 88400806 010 88400903 网址 www topschool org 7 23 mod 2 mba mod 3 mba mod n mba 且 mod 21 MbammmM n 则 10 设 是系数全为整数的多项式 若 则 定理定理 6 6 欧拉定理 1 2 1mm 中 与 m 互素的元素个数 定理 1 a m 则 m a 1 mod m 定理 m 素数 则 a m 1 1 1 m a mod m 定理 p 素数 1 1p mod p 5 5 完全剩余系和简化剩余系完全剩余系和简化剩余系 定义定义 5 同余类同余类 设 每一个这样的类为模的同余类 说明 整数集合可以按模来分类 确切地说 若和模同余 则和属同一类 否则不属于同 一类 每一个这样的类为模的一个同余类 由带余除法 任一整数必恰与 0 1 中的一个模 同余 而 0 1 这个数彼此模不同余 因此模共有个不同的同余类 即 例如 模 2 的同余类共有两个 即通常说的偶数类与奇数类 这两类中的数分别具有形式和 为任意整数 定义定义 6 剩余类 设是正整数 把全体整按对模的余数分成类 相应的个集合记为 其中 称为模的一个剩余类 以下是几条常用性质以下是几条常用性质 1 且 北京清北学堂教育科技有限公司 电话 010 88400806 010 88400903 网址 www topschool org 8 23 2 每一个整数仅在的一个里 3 对于任意 则的充要条件是 定义定义 7 7 完全剩余系 设 是使成立的最小正整 则称为对模的阶 显然 一组整数成为模的完全剩余系只需要满足两个条件 1 有个数 2 各数关于模两两不同 余 最常用的完全剩余系是最小非负完全剩余系及绝对值最小完全剩余系 模的最小非负完全剩余系是 0 1 2 即除数为时 余数可能取到的数的全部值 当为奇数时 绝对值最小的完全剩余系是 当为偶数时 绝对值最小的完全剩余系有两个 说明 在个剩余类中各任取一个数作为代表 这样的个数称为模的一个完全剩余系 简称模 的完系 换句话说 个数称为模的一个完系 是指它们彼此模不同余 例如 0 1 2 是模的一个完系 这称作是模的最小非负完系 简化剩余系简化剩余系 如果一个模m的剩余类里面的数与m互质 就把它叫做一个与模m互质的剩余类 在与模m互质的全部剩 余类中 从每一类各任取一个代表元所作成的数组 叫做模m的一个简化剩余系 或缩系 下面给出简化剩余系的判别方法和性质下面给出简化剩余系的判别方法和性质 若 12 m a aa 是 m 个与m互质的整数 并且两两对模m不同余 则 12 m a aa 是模m的一个 简化剩余系 若 1 a mx 通过模m的简化剩余系 则ax也通过模m的简化剩余系 设 N Z 1maa m 且 则称满足1 mod axm 的整数x为a对模m的数论倒数 记为 1 mod am 或简记为 1 a 由 知数论倒数的存在性 北京清北学堂教育科技有限公司 电话 010 88400806 010 88400903 网址 www topschool org 9 23 若 12 m m是两个互质的正整数 12 x x分别通过 12 m m的简化剩余系 则 2112 m xm x 通过模 12 m m的简化 剩余系 6 6 几个著名定理几个著名定理 1 1 欧拉 欧拉 EulerEuler 定理 设 定理 设a a m 是正整数 且 是正整数 且 a a m 1 1 则 则 1 mod 1 mod m m amam 证明 设 12 m x xx 是模 m 的一个简化剩余系 则由上一节简化剩余系质 12 m ax axax 也 是模 m 的简化剩余系 从而 1 2 i ax im 与且仅与 12 m x xx 中的一个数对模 m 同余 所以 12 12 mod mm axaxaxx xxm 即 1 2 1 2 mod m mm axx xxx xxm 由同余的性质 如果 12 1 m x xxm 那么 命题也就证完了 注意到 12 m x xx 是模 m 的简化剩 余系 故 1 1 2 i x mim 所以 12 m x xxm 1 综上所述 定理成立 2 2 费马 费马 FermatFermat 小定理 若 小定理 若P P是质数 是质数 a a是正整数 则是正整数 则 mod mod p p aapaap 证明 若 1p a 则p a 命题显然成立 若 1p a 则由 1pp 从而由欧拉定理有 1 1 mod p ap 当然也有 mod p aap 费马小定理的另一形式是 当 1p a 时 1 1 mod p ap 解题中经常运用这一形式 3 3 威尔逊 威尔逊 WilsonWilson 定理 设定理 设p p为质数 则为质数 则 1 1 mod 1 1 mod pppp 证明 当2p 时 命题显然成立 设p为奇质数 对11 ap 我们从下面的结论出发 1 1 11ap 这里 1 a 为a的模p的数论倒数 并且认为 1 01 ap 2 若11 abp 则 11 mod abp 如果已证好上述两个结论 我们可以将2 3 2p 中的数两两配对 将a与 1 a 配对 得到 1 1 1 1 mod ppp 从而命题获证 事实上 1 只需排除 1 1a 或1p 这两种可能 这是显然的 对 2 若 11 mod abp 则 1 1 mod abp 进而 mod bap 与条件矛盾 北京清北学堂教育科技有限公司 电话 010 88400806 010 88400903 网址 www topschool org 10 23 4 4 中国剩余定理 孙子定理 中国剩余定理 孙子定理 设设 1212 k k m mmm mm 为两两互质的正数 则对任意整数为两两互质的正数 则对任意整数 1212 k k c ccc cc 存在整数存在整数x x 使得 使得 mod 1 mod 1 iiii xcmikxcmik 同时成立 并且在模同时成立 并且在模 1212k k m mmm mm 的意义下 上述同余方程级的解是惟一的 可表示为的意义下 上述同余方程级的解是惟一的 可表示为 012012 mod mod k k xxmmmxxmmm 其中其中 0 0 x x可以这样确定 令可以这样确定 令 1 1 1 1 k k ijiiijii i i Mmm MMmm M 是是 i i MM关于模关于模 i i m m的数论倒数 则的数论倒数 则 1 1 0 0 1 1 k k iiiiii i i xM McxM Mc 这个定理说明了当模两两互质时 同余方程组 11 22 mod mod mod kk xcm xcm xcm 一定有解 其证明可参考以下思路 令 11 xc 则 1 x满足第一个方程 考虑数 1111121 2 xm xmxm m 它们构成模 2 m的一个完系 其中 必 有 一 个 数 为 模 2 m余 2 c的 数 记 为 2 x 则 2 x满 足 前 两 个 方 程 再 考 虑 2122122312 2 xmm xmmxm mm 依此类推可找到满足同余方程组的解 7 7 指数及其性质指数及其性质 设 1 mNaZa m 且称使得同余式1 mod d am 成立的最小正整数d为a模m的指数指数 或阶阶 记为 m a 指数有以下性质指数有以下性质 设1 mod n am nN 则 m a n 证明 设 0 mm na qrra 若0 r 则 1 mod m arrqn aa aam 这与 m a 的定义矛盾 故0 m ra n 即 根据上述性质及欧拉定理可知 m am 特别地 当 m 是质数 p 时 1 p a p 典型典型例题 例题 例例 1 1 求 2999最后两位数码 解 考虑用 100 除 2999所得的余数 北京清北学堂教育科技有限公司 电话 010 88400806 010 88400903 网址 www topschool org 11 23 又 2 999的最后两位数字为 88 例例 2 2 求证 31980 41981能被 5 整除 证明 例例 3 证明对于任何整数0 k 1532 61616 kkk 能被 7 整除 证明 61616 666 2351 2 23 351 kkk kkk M M 令 7 mod0 7 mod1132 117373272 1 122327 11047 3 197 2 1156257293642 CBA kkk kkk 0Zkk 且对于1532 61616 kkk 都能被 7 整除 注 Zkbaba k mod1 mod1 例例 4 44444444 44444444的十进位数的数字和是 A A 的数字和是 B B 的数字和是多少 解析 设B的数字和是C 显然 44444444 100004444 所以 4444 4444的位数不超过 20000144444 因为每一个数字都不大于 9 所以 9 20000180000199999A 而 199999 的数字和总比小于 199999 的数的数字和大 则 A 的数字和46 B 北京清北学堂教育科技有限公司 电话 010 88400806 010 88400903 网址 www topschool org 12 23 于是 B 的数字和 C 12 这是因为 12 是小于 46 的正整数中最大的数字和 39 的数字和是 12 由于一个正整数与其数字和关于模 9 同余 于是 9 mod44444444CBA 4 所以 1481344444444 2 2 2 4444 C 9 mod72 1 2 1481 因为在 C 12 的正整数中 只有 7 本身才能与 7 模 9 同余 所以 C 7 这就是说 B 的数字和是 7 例例 5 5 求最小的正整数a 使得存在正奇数n 满足2001 5532 nn a 解析 由于20013 23 29 若存在正奇数n 使得2001 5532 nn a 则1 1 0 m o d3 n a 既1 mod3 a 同样地 有5532990 mod23 nnnn aa 故1 mod23 a 而5532 3 3330 mod29 nnnnnn aaa 所以 1 mod29 a 同 时 满 足 同 余 式1 mod3 1 mod23 1 mod29 aaa 的 正 整 数a可 以 这 样 来 求 令 3 291871amm 由8711 mod23 5 mod23 mm 得 所以 满足条件的最小的87 5 1436a 例例 6 6 是否存在 4 个正整数使得其中任意两个的积都是平方数 解析 设存在这样的 4 个数 a b c d 其中 a b c d 中至少 3 个奇数 其中两个 mod 4 同余 设 mod4 ab 为奇 则1 mod4 ab 20103 mod4 ab 例例 7 7 P 是一个素数 0 pn 求证 1 1 nnpn mod p 解析 1 kpk mod p k 1 2 n 1 1 1 1 1 2 1 mod n npppnp 1 1 1 1 n npnp 1 mod n p 模拟模拟真题真题 题题 1 设 p 和q均为自然数 使得 1319 1 1318 1 3 1 2 1 1 q p 证明 p 可被 1979 整除 第 21 届 IMO 试题 证明 1318 1 4 1 2 1 2 1319 1 3 1 2 1 1 q p 659 1 2 1 1 1319 1 3 1 2 1 1 北京清北学堂教育科技有限公司 电话 010 88400806 010 88400903 网址 www topschool org 13 23 990 1 989 1 1318 1 661 1 1319 1 660 1 1979 990989 1 1318661 1 1319660 1 两端同乘以 1319 得 1319 1979Nmm q p 此式说明 1979 1319 p 由于 1979 为质数 且 1979 1319 故 1979 p 评述 把 1979 换成形如 23 k 的质数 1319 换成 12Nkk 命题仍成立 牛顿二项式定理和 nbabababa nnnn 为偶数 nbaba nn 为奇数 在整除 问题中经常用到 题题 2 求一对整数 ba 满足 1 baab 不能被 7 整除 2 777 baba 能被 77整除 第 25 届 IMO 试题美国普特南数学竞赛试题 解 777 baba 5 3 7 223355 bababaabbaab 7 222 abbabaab 根据题设要求 1 2 知 7 2226 abba 即 7 223 abba 令 73 22 abba 即 343 2 abba 即 19 ba 则 343192 ab 故可令 1 18 ba 即合要求 评述 数学归纳法在整除问题中也有广泛应用 题题 3 是否存在 1000000 个连续整数 使得每一个都含有重复的素因子 即都能被某个素数的平方所整除 解 存在 用数学归纳法证明它的加强命题 对任何正整数 m 存在m个连续的整数 使得每一个都含有重 复的素因子 当m 1 时 显然成立 这只需取一个素数的平方 假设当m k时命题成立 即有k个连续整数 knnn 2 1 它们分别含有重复的素因子 k ppp 21 任取一个与 k ppp 21 都不同的素数 1 k p 显然存在 当 2 1 2 1 k pt 时 1 22 2 2 1 knpptp k 这 2 1 k p 个数中任两个数的差是形如 11 2 1 22 2 2 1 kk pappap 的数 不能被 2 1 k p 整除 故这 2 1 k p 个数除以 2 1 k p 后 余数两两不同 但除以 2 1 k p 后的余数只有 0 1 2 1 k p 1 这 2 1 k p 个 从而恰有一个数 1 2 100 k ptt 使 1 22 2 2 10 knpppt k 能被 2 1 k p 整除 这时 1 k 个连续 整数 北京清北学堂教育科技有限公司 电话 010 88400806 010 88400903 网址 www topschool org 14 23 1 22 2 2 10 npppt k npppt k 22 2 2 10 2 npppt k 22 2 2 10 k npppt k 22 2 2 10 k 1 分别能被 2 1 22 2 2 1 kk pppp 整除 即 1 km 时命题成立 故题对一切正整数m均成立 题题 4 求证 22 accbba cba accbba cba 第 1 届美国数学奥林匹克竞赛试题 证明 设 111 n i i n i i n i i ipcipbipa 其中 i p 为质数 iii 为非负整数 则 1 iii n max i i a b cp 1 ii n max i i a bp 1 iii n min i i a b cp 1 ii n min i i a bp 因此只需证明 2 iiiiiiiii maxmaxmaxmax 2 iiiiiiiii minminminmin 上式关于 iii 对称 则不妨设 iii 于是上式变为 22 iiiiiiii 此式显然成立 故得证 题题 5 5 求设a和b是两个正整数 pba 1 为大于或等于 3 的质数 ba ba bac pp 试证 1 1 ac 2 1 c或 pc 1985 新加坡数学竞赛试题 证明 由已知得 Nstcs ba ba ctba pp 两式相乘得 1112 ctpatpactcactabastc ppppppppp 于是 12211 ppppp patpactccs 故 1 p pac 北京清北学堂教育科技有限公司 电话 010 88400806 010 88400903 网址 www topschool org 15 23 1 现用反证法来证明 1 ac 若 1 kac 令q是k的一个质因子 则有 aqcq 因 bac 则 baq 从而 bq 于是q是a b的一个公约数 这与 ba 1 矛盾 故 1 ac 2 因为 1 1 acpac p 所以 pc 而 p 为质数且 3 p 故 1 c 或 pc 题题 6 设 n k n kkS 1 75 求最大公约数 3nn SSd 第 26 届 IMO 预选题 解 能过具体计算可猜想 2 1 2 21 2 44 nn nSn 此式不难用数学归纳法获证 为求 3nn SSd 对n分奇偶来讨论 1 当 kn2 时 16 812 12 2 2 16 6 2 2 12 2 2 444444 kkkk kkkk d 由于 12 k 和 16 k 互质 所以 81 12 2 44 kkd 而当 13 tk 时 13 12 81 12 44 tktk 时 4 12 k 与 81 互质 故此时有 0 4666 8 1 2 26 8 81 2 812812 44 4 4 4 4 tttnnk tnn n k d 时或当 时当 2 当当 12 kn 时 23 12 3 2 1 12 2 44 kkkkd 1 1223 kkk与因 与质 所以 3 1 12 2 444 kkk 而当 23 tk 时 23 1 31 kktk 时 1 k 与 34 互质 故此时有 36162 12 2 56 162323 12 2 44 4444 时或当 时当 ttnnk tnnnk d 题题 7 m m盒子中各若干个球 每一次在其中 mnn 个盒中加一球 求证 不论开始的分布情况如何 总可 按上述方法进行有限次加球后使各盒中球数相等的充要条件是 1 nm 第 26 届 IMO 预选题 证明 设 1 nm 则有 Zvu 使得 1 1 1 vmvvmun 此式说明 对盒子连续加球u次 北京清北学堂教育科技有限公司 电话 010 88400806 010 88400903 网址 www topschool org 16 23 可使 1 m 个盒子各增加了v个 一个增加 1 v 个 这样可将多增加了一个球的盒子选择为原来球数最少的 那个 于是经过u次加球之后 原来球数最多的盒子中的球与球数最少的盒子中的球数之差减少 1 因此 经过有限次加球后 各盒球数差为 0 达到各盒中的球数相等 用反证法证明必要性 若 1 dnm 则只要在m个盒中放 1 m 个球 则不管加球多少次 例如 加球k次 则这时m个盒中共有球 knm 1 个 因为 1 dndmd 所以 knm 1 不可能是d的 倍数 更不是m的倍数 各盒中的球决不能一样多 因此 必须 1 nm 题题 8 8 1998 年匈牙利奥林匹克竞赛题 求使 2n 1 能被 3 整除的一切自然数 n 解 则 2n 1 当 n 为奇数时 2n 1 能被 3 整除 当 n 为偶数时 2n 1 不能被 3 整除 二 不定方程二 不定方程 知识点 知识点 1 1 一次不定方程一次不定方程 整系数方程 ax by c a 0 b 0 通常称为二元一次不定方程 对于二元一次不定方程 已经解决是否有解及如何求解的问题 定理定理 1 1 二元一次不定方程 ax by c a b c Z a 0 b 0 有整数解的充分必要条件是 a b c 显然 若 a b 1 方程 有解 定理定理 2 2 若 x0 y0是 的一组解 通常称为 的一组特解 则方程 的全部解 通常称为通解 为 Zt t ba a yy t ba b xx 0 0 特别地 若 a b 1 则方程 的通解为 Zt atyy btxx 0 0 定理定理 3 3 k 元一次不定方程 0 3 2 1 212211 kikk aaakkiZaccxaxaxa 有整数解的充分必要条件是caaa k 21 2 2 一次不定方程组一次不定方程组 一次不定方程组主要手段是通过消元的方法来求解 3 3 勾股数勾股数 对于不定方程 222 zyx 北京清北学堂教育科技有限公司 电话 010 88400806 010 88400903 网址 www topschool org 17 23 如果 x y d 则 d2 z2 即 d z 这样方程两边可约去 d 所以在讨论 的解时 仅需在 x y 1 时讨论 此时 x y z 是两两互素的 这样两两互素的解 x y z 称为方程 的本原解 定理定理 4 4 不定方程 满足 x y 1 x 0 y 0 z 0 2 y 的全部解可表示成 22 22 2 baz aby bax 其中 a b 是满足 a b 0 a b 一奇一偶 且 a b 1 的任意整数 4 4 沛尔方程沛尔方程 形如 1 22 dyx 或 1 22 dyx 的二元二次不定方程称为佩尔方程 其中 d Z d 0 且非平方数 定义定义 设正整数 1 x和 1 y是方程 的所有正整数解中使 11 ydx 最小的一组解 称 11 yx是方程 或 的 基本解 定理定理 5 5 设 11 yx是方程 或 的基本解 则对于 或 的任意一组正整数解 x y 必有 x1 x y1 y 定理定理 6 6 方程 有无穷多组正整数解 且全部正整数解由下式给出 1111 1111 1 2 1 2 nn n nn n xxd yxd y yxd yxd y d 其中 11 yx是 的基本解 n 1 2 公式 也可写成 n nn dyxdyx 11 由公式 可以推导出xn yn满足线性递推关系 2 2 111 111 nnn nnn yyxy xxxx 定理定理 7 7 方程 有无穷多组正整数解 且全部正整数解由下式给出 2121 1111 2121 1111 1 2 1 2 nn n nn n xxd yxd y yxd yxd y d 其中 11 yx是 的基本解 n 1 2 公式 也可写成 12 11 n nn dyxdyx 北京清北学堂教育科技有限公司 电话 010 88400806 010 88400903 网址 www topschool org 18 23 5 5 不定方程不定方程 不定方程的问题主要有两大类 判断不定方程有无整数解或解的个数 如果不定方程有整数解 采取正确 的方法 求出全部整数解 1 1 不定方程解的判定不定方程解的判定 如果方程的两端对同一个模 m 常数 不同余 显然 这个方程必无整数解 而方程如有解则解必为奇数 偶数两种 因而可以在奇偶性分析的基础上应用同余概念判定方程有无整数解 例例 1 1 证明方程 2x2 5y2 7 无整数解 证明 2x2 5y2 7 显然 y 为奇数 若 x 为偶数 则 方程两边对同一整数 8 的余数不等 x 不能为偶数 若 x 为奇数 则但 5y2 7 x 不能为奇数 因则原方程无整数解 说明 用整数的整除性来判定方程有无整数解 是我们解答这类问题的常用方法 2 2 不定方程的解法不定方程的解法 不定方程没有统一的解法 常用的特殊方法有 配方法 因式 质因数 分解法 不等式法 奇偶分析法和 余数分析法 对方程进行适当的变形 并正确应用整数的性质是解不定方程的基本思路 例例 2 2 求方程的整数解 解 配方法 原方程配方得 x 2y 2 y2 132 在勾股数中 最大的一个为 13 的只有一组即 5 12 13 因此有 8 对整数的平方和等于 132即 5 12 12 5 5 12 12 5 5 12 12 5 5 12 12 5 故原方程 组的解只能是下面的八个方程组的解 北京清北学堂教育科技有限公司 电话 010 88400806 010 88400903 网址 www topschool org 19 23 解得 例例 3 3 求不定方程 2 x y xy 7 的整数解 解 由 y 2 x 2y 7 得 分离整数部分得 由 x 为整数知 y 2 是 3 的因数 y 2 1 3 x 3 5 1 方程整数解为 例例 4 4 求方程 x y x2 xy y2的整数解 解 不等式法 方程有整数解 必须 y 1 2 4 y2 y 0 解得 y 满足这个不等式的整数只有 y 0 1 2 当 y 0 时 由原方程可得 x 0 或 1 当 y 1 时 由原方程可得 x 2 或 0 当 y 2 时 由原方程可得 x 1 或 2 北京清北学堂教育科技有限公司 电话 010 88400806 010 88400903 网址 www topschool org 20 23 所以方程有整数解 例例 5 5 求满足方程且使 y 是最大的正整数解 x y 解 将原方程变形得 由此式可知 只有 12 x 是正的且最小时 y 才能取大值 又 12 x 应是 144 的约数 所以 12 x 1 x 11 这时 y 132 故满足题设的方程的正整数解为 x y 11 132 模拟真题模拟真题 题题 1 1 不存在整数 x y 使方程12223 22 yxyx 成立 第 14 届美国数学邀请赛题 证明 如果有整数 x y 使方程 成立 则 2222 17 32 812448852917yyxyxyx 知 2x 3y 2 5 能被 17 整除 设 2x 3y 17n a 其中 a 是 0 1 2 3 4 5 6 7 8 中的某个数 但是这时 2x 3y 2 5 17n 2 34na a2 5 a2 5 mod17 而 a2 5 被 17 整除得的余数分别是 5 6 9 14 4 13 7 3 1 即在任何情况下 2x 3y 2 5 都不能被 17 整除 这与它能被 17 整除矛盾 故不存在整数 x y 使 成立 题题 2 2 证明不定方程1999 3333 tzyx有无穷多组整数解 证明 注意到 19990 1 1010 3333 因此 方程有整数解 由上可知 我们可寻找如下形式的整数解 x 10 k y 10 k z 1 m t m k m Z 代入方程并化简得 m m 1 20k2 即有180 12 22 km 这是佩尔方程 易知 m1 4 k1 1 是其基本解 全部正整数解为 2 1 809 809 802 1 809 809 2 1 12 n k m nn n nn n 所以原方程有无穷多组整数解 北京清北学堂教育科技有限公司 电话 010 88400806 010 88400903 网址 www topschool org 21 23 题题 3 3 试求所有的正整数 n 使方程 222333 zynxzyx 有正整数解 解析 设 x y z 是其正整数解 由对称性 不妨设 x y z 显然有 332 yxz 故 332 yxz 但 23 xzx 23 yzy 即 233 yxzyx 又 22 2 33 22 yxynx z yx ynxz 2 22442222233 yxynxyxnyxynxzyx 于是 3322442 2yxyxynxyxn 33 1111 2 nynxyx xy 若 x 2 则 xy 4 而3 4 1 2 1111 2 33 nnynxyx 与 矛盾 故 x 1 则 式转化为