《竞赛讲义例题版：第四讲：数论中的解题策略》由会员分享，可在线阅读，更多相关《竞赛讲义例题版：第四讲：数论中的解题策略（4页珍藏版）》请在金锄头文库上搜索。
1、 交交 流流 知知 识识 共共 享享 智智 慧慧 第四讲第四讲 初等数论解题策略初等数论解题策略 主讲人主讲人：文武光华数学工作室文武光华数学工作室 田开斌田开斌 基本概念基本概念： 1 1、整除整除、倍数倍数、约数约数：若? ?是整数，则称 a 能被 b 整除，记作b|a。其中 a 称为 b 的倍 倍 数数，b 称为 a 的约数约数。 2 2、唯一分解定理唯一分解定理：任一自然数n皆可唯一地表示为素数之积：n = p? p? p?，其中p?p? p?为素数，?、?、?为自然数。 3 3、约数个数定理约数个数定理：设n = p? p? p?，用d(n)表示大于n的所有正约数的个 数，则d(n)
2、 = (1 + ?) (1 + ?) (1 + ?)。 4 4、约数和定理约数和定理：设n = p? p? p?，用(n)表示大于n的所有正约数的个数， 则(n) = ? ? ? ? ? ? 。 5 5、辗转相除法辗转相除法：辗转相除法, 又名欧几里德算法，是求两个正整数之最大公因子的算 法。设两数为 a、b（ab），求它们最大公约数(a，b)的步骤如下：用 b 除 a，得 a = b qr?（0 r?b）。若r?= 0，则(a，b) = b；若r? 0，则再用r?除 b，得 b = r? qr? （0 r?r?)。若r?= 0，则(a，b) = r?；若r? 0，则继续用r?除 r?，如此下
3、去，直到能整除为止。其最后一个非零余数即为(a，b)。其理论依据即 为(a，b) = (a b，b)。 6 6、同余同余：两个整数a、b，若它们除以整数m所得的余数相等，则称a与b关于模m同余， 记作a b (mod m)。 完全平方数中，我们经常考虑模 3、4 和 8。（1）m? 0，1（mod 3）；（2） m?= 0，1（mod 4）；（3）m? 0，1，4（mod 8）。 7 7、费马小定理费马小定理：若p为质数，且?a，p? = 1，则a? 1 (mod p)。 8 8、欧拉定理欧拉定理：对于任意正整数n，(n)表示不大于n且与n互素的正整数的个数，称为 欧拉函数。设n = p? p
4、? p?，则(n) = n?1 ? ? ?1 ? ? ?1 ? ?。 若?a，n? = 1，则a?(?) 1(mod n)。这称为欧拉定理。显然，费马小定理是欧拉定理 的特殊形式。 9 9、阶数与原根阶数与原根：当?a，n? = 1时，存在最小的正整数使得a? 1(mod n)，则称为a 关于n的阶数。显然 (n)，且|(n)。如果 = (n)，则称a为n的原根。 阶数的性质：（）a?、a?、a?、a?中的任何两个数对n不同余；（） a? 1(mod n) |t。 1010、中国剩余定理中国剩余定理：设m?、m?、m?是k个两两互质的正整数，则同余组： ? x b?(mod m?) x b?(
5、mod m?) x b?(mod m?) ? 有唯一解x M?M?b?+ M?M?b?+ + M?M?b? (M)。其中M = m? m? m?， M?= ? ?， M?M? 1(mod m?)，i = 1、2、k。 例题选讲例题选讲： 例例 1 1、所有小于n 3 的正整数均整除正整数 n，求 n 的最大值。 例例 2 2、求最小的正整数 a，使得存在正奇数 n，满足2001|(55?+ a 32?)。（2001 年爱 尔兰数学奥林匹克） 交交 流流 知知 识识 共共 享享 智智 慧慧 例例 3 3、设有四个正整数，其中任何两数的平方和都可以被其余两个数的乘积整除。证 明：其中至少有三个数彼
6、此相等。（1999 年俄罗斯数学奥林匹克试题） 例例 4 4、求所有正整数 n，使得对于 n 的任意两个互素的约数a、b，a + b 1也是 n 的约 数。（2001 年俄罗斯数学奥林匹克试题） 例例 5 5、已知正整数a、b，?a，b? = 1，使得a|b?+ 5，b|a?+ 5，求所有满足条件的正 整数有序数对?a、b?。 例例 6 6、设a为给定的任意大于1的自然数，数列a?：a?= a?+ a? 1，求证：数列 a ?中存在无穷多个项，使得其中任意两项都互素。 例例 7 7、证明：存在无穷多个正整数n，使得n、n + 1、n + 2均可写成两个正整数的平方 和。 例例 8 8、求证：方
7、程x?+ x?+ x?+ + x?= x?有无穷多组正整数解。 （费振鹏老师题） 交交 流流 知知 识识 共共 享享 智智 慧慧 例例 9 9、设n N?，证明：n?+ 7不是完全平方数。 例例 1010、求使得? ? ?是整数的所有数对?p，n?，其中p是素数，n是正整数。（2012 年 APMO 试题） 例例 1111、假设函数f：N? N?满足f?(m)+ f(n)|(m?+ n)?，证明：f(n) = n，n N?。 （蕴秀斋高中数学联赛模拟题二试第三题） 例例 1212、若m、n N?，使得A = (?)? ? N?，证明：A 为奇数。 例例 1313、求所有正整数数列?x?，x?，
8、x?，x?，使得对于每个正整数 n，都存 在一个正整数 a，使得x? j ? ? = a?+ 1。（2011 年 IMO 预选题） 典型练习题典型练习题： 1 1、已知p为素数，x、y、z均为正整数，且满足xyzp。若x?、y?、z?被p除所得 的余数相同，求证：x + y + z|x?+ y?+ z?。（2003 年第 54 届波兰数学奥林匹克试题） 交交 流流 知知 识识 共共 享享 智智 慧慧 2 2、证明：存在无穷多个正整数 n，使得n?+ 1|n!。 3 3、求最小的正整数 m，使得对于任意素数p3，都有105|9? ? 29?+ m。（2012 年 西部数学奥林匹克试题） 4 4、
9、求所有函数f:N? N?，使得对任意x、y R?，均有f(y) + x?|?f(x)? ? + y。（2012 年广东省高中数学联赛预选题压轴题） 5 5、记f(n) = n + ?n?，定义数列a?：a?= m，a?= f(a?)。证明：对每个m Z?， 数列a?中，有无穷多个完全平方数。 6 6、正整数 a 与 b，使得ab + 1|a?+ b?，求证：? ? ?是某个正整数的平方。（1988 年 第 29 届 IMO 试题） 7 7、证明：（1）存在正实数x，对于任意的正整数 n，x?与 n 奇偶性相同。（1983 年 美国第 44 届普特南大学生数学竞赛试题） （2）存在正实数x，对于
10、任意的正整数 n，x?与 n 奇偶性不同。 8 8、是否存在三个大于10?的两两不同的正整数 a、b、c，使得它们的乘积可被它们中 的任何一个数与2012的和整除？（2012 年俄罗斯数学奥林匹克十年级试题） 9 9、求满足a?b?= 4a?+ b?的整数对?a，b?。（2007 年日本数学奥林匹克预赛试题） 1010、设f(n)是正整数 n 的所有正约数之和，求所有的质数 p，使得p|f(p 1)。 1111、求所有素数 p，使得p? p + 1为完全立方数。（2005 年巴尔干地区数学奥林匹克 试题） 1212、求所有素数p，使得p|2? ? 1。 1313、设 p 是奇素数，如果存在正整数a，使得p!|a?+ 1，证明：（1）?a + 1， ? ? ? = p；（2）? ? ? 没有小于p的素因子；（3）p!|a + 1。（2012 年第 8 届北方数学奥林匹克试 题）
