数学竞赛中的数论问题

1、2-4 数学竞赛中的数论问题（09-10-28）数论是研究自然数的一个数学分支.一、数学竞赛中数论问题的基本内容主要有8个定义、15条定理.定义1 （带余除法）给定整数如果有整数满足 ，则和分别称为除以的商和余数特别的，时，则称被整除，记作，或者说是的倍数，而是的约数定义2 （最小公倍数）非零整数的最小公倍数是能被其中每一个所整除的最小正整数，记作定义3 （最大公约数）设整数中至少有一个不等于零，这个数的最大公约数是能整除其中每一个整数的最大正整数，记作定理1 对任意的正整数，有 定义4 如果整数 满足，则称与是互素的（以前也称为互质）定义5 大于1且除1及其自身外没有别的正整数因子的正整数，

2、称为素数（以前也称为质数）其余大于1的正整数称为合数；数1既不是素数也不是合数定理2 素数有无穷多个，2是唯一的偶素数定义6 对于整数，且，若，则称关于模同余，记作若则称关于模不同余，记作 定理3 （整除的性质）设整数为非零整数，（1） 若，则；（2） 若，则；（3） 若，则对任意整数，有；（4） 若，且，则；（5） 若，且，则（6） 若为素数，且，则或定理4 （同余的性质）设为整数，（1） 若且，则；（2） 若且，则且（3） 若，则对任意的正整数有，且；（4） 若，且对非零整数有，则定理5 设为整数，为正整数，（1） 若，则；（2） 若，则；（3） 若，则定义7 设为正整数，为大于2的正整数

3、, 是小于的非负整数，且若 ，则称数为的进制表示定理6 给定整数，对任意的正整数，都有唯一的进制表示定理7 任意一个正整数与它的十进制表示中的所有数字之和关于模9同余定理8 （分解唯一性）每个大于1的正整数都可分解为素数的乘积，而且不计因数的顺序时，这种表示是唯一的 .定理9 若正整数的素数分解式为 则的约数的个数为，的一切约数之和等于 定义8 对任意实数，是不超过的最大整数亦称为的整数部分，定理10 在正整数的素因子分解式中，素数作为因子出现的次数是 定理11 如果素数不能整除整数，则定理12 设为素数，对任意的整数，有定理13 设正整数，则不大于且与互素的正整数个数为 定理14 整系数二元

4、一次方程存在整数解的充分必要条件是定理15 若是整系数二元一次方程的一个整数解，则方程的一切整数解可以表示为 二. 数学竞赛中数论问题的重点类型主要出现8类问题.：1.奇数与偶数（奇偶分析法、01法）；2.约数与倍数、素数与合数；3.平方数；4.整除；5.同余；6.不定方程；7.数论函数、高斯函数、欧拉函数；8.进位制（十进制、二进制）.三. 例题选讲 例1 有100盏电灯，排成一横行，从左到右，我们给电灯编上号码1，2，99，100.每盏灯由一个拉线开关控制着.最初，电灯全是关着的.另外有100个学生，第一个学生走过来，把凡是号码为1的倍数的电灯的开关拉了一下；接着第2个学生走过来，把凡是号

5、码为2的倍数的电灯的开关拉了一下；第3个学生走过来，把凡是号码为3的倍数的电灯的开关拉了一下，如此等等，最后那个学生走过来，把编号能被100整除的电灯的开关拉了一下，这样过去之后，问哪些灯是亮的？讲解 （1）直接计算100次记录，会眼花缭乱.（2）拉电灯的开关有什么规律：电灯编号包含的正约数（学生）才能拉、不是正约数（学生）不能拉，有几个正约数就被拉几次.（3）灯被拉的次数与亮不亮（开、关）有什么关系：0123456789关开关开关开关开关开 灯被拉奇数次的亮！（4）哪些数有奇数个约数：平方数.（5）1100中有哪些平方数：共10个：1，4，9，16，25，36，49，64，81，100.答案

6、：编号为1，4，9，16，25，36，49，64，81，100共10个还亮.例2 用表示不大于的最大整数，求 .讲解 题目的内层有2004个高斯记号，外层1个高斯记号.关键是弄清的含义，进而弄清加法谁与谁加、除法谁与谁除：（1）分子是那些数相加，求出和来；由，知分子是05的整数相加，弄清加数各有几个 13650365个3667311366个73210972366个109814633366个146418294366个183020045175个（2）除法谁除以366，求出商的整数部分.原式 命题背景2004年有12个月、366天.例3 证明对任意正整数，分数不可约.证明1 （反证法）假若可约，则存

7、在， 使 从而存在，使消去，得 的 由（1）、（5）矛盾，得.解题分析：（1）去掉反证法的假设与矛盾就是一个正面证法（2）式是实质性的进展，表明 可见 .由此获得2个解法.证明2 设。存在，使消去，3-2，得 得 .证明3 由得 .证明4 . 解题分析：第 相当于 -；：第 相当于-2（-）=3-2；所以式与式的效果是一样的.例4 （1906，匈牙利）假设是的某种排列，证明：如果是奇数，则乘积 是偶数.解法1 （反证法）假设为奇数，则均为奇数，奇数个奇数的和还是奇数奇数=，这与“奇数偶数”矛盾. 所以是偶数. 评析 这个解法说明不为偶数是不行的，但没有指出为偶数的真正原因.体现了整体处理的优点

8、，但掩盖了“乘积”为偶数的原因.解法2 （反证法）假设为奇数，则均为奇数，与的奇偶性相反，中奇数与偶数一样多，为偶数但已知条件为奇数，矛盾. 所以是偶数.评析 这个解法揭示了为偶数的原因是“为奇数”.那么为什么“为奇数”时“乘积”就为偶数呢？ 解法3 中有个奇数，放到个括号，必有两个奇数在同一个括号，这两个奇数的差为偶数，得为偶数. 例4-1（1986，英国）设是整数，是它们的一个排列，证明是偶数. 例4-2 的前24位数字为，记为该24个数字的任一排列，求证必为偶数.例5 设与为正整数，满足 ，求证可被1979整除（1979） 有1979整除，从而1979整除，但1979为素数，得可被197

9、9整除例6 （1956，中国北京）证明对任何正整数都是整数，并且用3除时余2.讲解 只需说明为整数，但不便说明“用3除时余2”，应说明是3的倍数.作变形 命题得证. 证明 已知即， 因为相邻2个整数必有偶数，所以为整数.又可变为，因为相邻3个整数必有3的倍数，故能被3整除；又，所以能被3整除；得用3除时余2.例7设多项式的系数都是整数，并且有一个奇数及一个偶数使得及都是奇数，求证方程没有整数根 证明 由已知有 ， ， 若方程存在整数根，即.当为奇数时，有，与矛盾.有为偶数时，有，与矛盾.所以方程没有整数根例8 设是异于2，5，13的任一整数.求证在集合中可以找到两个不同元素，使得不是完全平方数

10、.证明 因为，所以不是完全平方数只能是.若结论不成立，则存在正整数，使同时成立，由知是奇数，设代入得 为奇数，代入、知均为偶数.设，代入、后相减，有 . 由于为偶数，故同奇偶，可被4整除，得为偶数.这与上证为奇数矛盾.所以，在集合中可以找到两个不同元素，使得不是完全平方数.例9 ()设为正整数，整除证明是完全平方数证明令是正整数式中是对称的，不妨设(l)若，则本题获证(2)若，由带余除法定理，可设（是整数)，则，易证此式大于且小于l(可用放缩法证)所以必有 化简得，于是，其中此时若，则，本题获证若，可继续令（是整数），仿上可推得，此时若，则，本题获证若，可如上法做下去因，且均为整数故总能得到某个，使，是完全平方综上本题获证解决这道世界级难题的这种巧妙的证明方法叫“无穷递降法”，是17世纪法国数学家费马(Fermat1601一1665)首创和应用的一种方法 作业1.求方程的整数解. 2、2009年9月9日的年、月、日组成“长长久久、永不分离”的吉祥数字20090909，而它也恰好是一个不能再分解的素数若规定含素因子的数为吉祥数，请证明最简分数的分子是吉祥数作业1. 设，证明对于不可能有某一正整数，使能被整除.（P.185，32）证明 由已知有，得