数学竞赛中的数论问题.doc

智浪教育—普惠英才文库数学竞赛中的数论问题第二部分 数论题的范例讲解主要讲几个重要类型：奇数与偶数，约数与倍数（素数与合数） ，平方数，整除，同余，不定方程，数论函数等．重点是通过典型范例来分析解题思路、提炼解题方法和巩固基本内容．一、奇数与偶数整数按照能否被 2 整除可以分为两类，一类余数为 0，称为偶数，一类余数为 1，称为奇数．偶数可以表示为 ，奇数可以表示为 或 ．一般地，整数被正整数n21n去除，按照余数可以分为 类，称为模 的剩余类 ，从每类中mmmodiCxi各取出一个元素 ，可得模 的完全剩余系（剩余类派出的一个代表团） ，iiaC称为模 的非负最小完全剩余系.0,12,L通过数字奇偶性质的分析而获得解题重大进展的技巧，常称作奇偶分析，这种技巧与分类、染色、数字化都有联系，在数学竞赛中有广泛的应用． 关 于 奇 数 和 偶 数 ， 有 下 面 的 简 单 性 质 ： （ 1） 奇 数 偶 数 ．（ 2） 偶 数 的 个 位 上 是 0、 2、 4、 6、 8； 奇 数 的 个 位 上 是 1、 3、 5、 7、 9．（ 3） 奇 数 与 偶 数 是 相 间 排 列 的 ； 两 个 连 续 整 数 中 必 是 一 个 奇 数 一 个 偶 数 ； ．（ 4） 奇 数 个 奇 数 的 和 是 奇 数 ； 偶 数 个 奇 数 的 和 是 偶 数 ； 偶 数 跟 奇 数 的 和 是 奇 数； 任 意 多 个 偶 数 的 和 是 偶 数 ． （ 5） 除 2 外 所 有 的 正 偶 数 均 为 合 数 ；（ 6） 相 邻 偶 数 的 最 大 公 约 数 为 2， 最 小 公 倍 数 为 它 们 乘 积 的 一 半 ．（ 7） 偶 数 乘 以 任 何 整 数 的 积 为 偶 数 ．（ 8） 两 数 和 与 两 数 差 有 相 同 的 奇 偶 性 ， ．mod2ab（ 9） 乘 积 为 奇 数 的 充 分 必 要 条 件 是 各 个 因 数 为 奇 数 ．（ 10） 个 偶 数 的 积 是 的倍数．n2n（ 11） 的 充 分 必 要 条 件 是 为 偶 数 ， 的 充 分 必 要 条 件 是 为kk1kk奇 数 ．（ 12） ．2220mod4,1mod4,mod8nnn（ 13） 任 何 整 数 都 可 以 表 示 为 ．k……例 1 （1906，匈牙利）假设 是 的某种排列，证明：如果 是奇12,naL, n数，则乘积12n智浪教育—普惠英才文库是偶数．类似题： 例 1-1（1986，英国）设 是整数， 是它们的一个排列，证明127,aL127,bL是偶数．127abbL（ 中奇数与偶数个数不等）,例 1-2 的前 24 位数字为 ，记 为该3.145926873462124,aL24 个数字的任一排列，求证 必为偶数．2aaL（暗藏 中奇数与偶数个数不等）3,145,96,8,,,例 2 能否从 中选出 个数填入图的圆圈中，使得每两个有线相连的圈中1,25L10的数相减（大数减小数） ，所得的 14 个差恰好为 ？,214L智浪教育—普惠英才文库例 3 有一大筐苹果和梨分成若干堆，如果你一定可以找到这样的两堆，其苹果数之和与梨数之和都是偶数，问最少要把这些苹果和梨分成几堆？例 4 有 个数 ，它们中的每一个要么是 ，要么是 ．若n121,,nxxL1，求证 ．123 0nxL4|例 5 个整数 ，其积为 ，其和为 0，试证 ．n121,,naaLn4|n例 6 在数轴上给定两点 1 和 ，在区间 内任取 个点，在此 个点中，每相2(1,2)n2邻两点连一线段，可得 条互不重叠的线段，证明在此 条线段中，以一个有理点n1和一个无理点为端点的线段恰有奇数条．智浪教育—普惠英才文库二、约数与倍数最大公约数与最小公倍数的求法．（1）短除法．（2）分解质因数法．设，12,0,12,kiapkLL．12kib记 ，min,ax,iiii则 ，12,kapL．12kb（3）辗转相除法．121,,,,,0nnarrrL例 7 （1）求 ， ；83058305（2） ， ．4,4,例 8 正整数 分别除以 得到的余数依次为 ，n2,3456,789101,2345,6789则 的最小值为 ．n．例 9 有两个容器，一个容量为 27 升，一个容量为 15 升，如何利用它们从一桶油中倒出 6 升油来？智浪教育—普惠英才文库例 10 对每一个 ，求证存在 个互不相同的正整数 ，使2nn12,naL，对任意的 成立．ijija,1,,ijijL例 11 证明对任意正整数 ，分数 不可约．195,IMOn2143例 12 不存在这样的多项式，110mfnanaL使得对任意的正整数 ， 都是素数．f．智浪教育—普惠英才文库三、平方数若 是整数，则 就叫做 的完全平方数，简称平方数．a2a1．平方数的简单性质（1）平方数的个位数只有 6 个： ．0,145.69（2）平方数的末两位数只有 22 个：00，01，21，41，61，81，04，24，44，64，84，25，16，36，56，76，96，09，29，49，69，89． （3） ．220mod4,1mod4nn（ ４ ） ．18（6）凡是不能被 3 整除的数，平方后被 3 除余 1．（7）在两个相邻整数的平方数之间，不能再有平方数．（8）非零平方数的约数有奇数个．（9）直角三角形的三边均为整数时，我们把满足 的整数 叫做勾22abc,abc股数．勾股数的公式为22,,amnbc其中 为正整数， 且 一奇一偶．这个公式可给出全部素勾股数．,n1n,2．平方数的证明方法（1）反证法．（2）恒等变形法．（3）分解法．设 为平方数，且 ， ，则 均为平方数．aabc,1,bc（4）约数法．证明该数有奇数个约数．3．非平方数的判别方法（1）若 ，则 不是平方数．221nxx（2）约数有偶数个的数不是平方数．（3）个位数为 2，3，7，8 的数不是平方数．（4）同余法：满足下式的数 都不是平方数．n， modn， 234或， 5或，67od8n或 或 或 或智浪教育—普惠英才文库．2378mod10n或 或 或（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 整除的电灯的开关拉了一下，这样过去之后，问哪些灯是亮的？例 14 已知直角三角形的两条直角边分别为正整数 ，斜边为正整数 ，若 为素,abca数，求证 为平方数．21ab例 15 求证，任意 3 个连续正整数的积不是平方数．智浪教育—普惠英才文库例 16 设 是异于 2，5， 13 的任一整数．求证在集合231986,IMOd中可以找到两个不同元素 ，使得 不是完全平方数．2,513dab例 17 ( )设 为正整数， 整除 ．证明 是完全平方296IMO,ab1ab2b21ab数．四．整除整除的判别方法主要有 7 大类．1．定义法．证 ，有三种方式．baq（1）假设 ，然后证明 ． （定理 4）r0r（2）具体找出 ，满足 ．智浪教育—普惠英才文库（3）论证 的存在．q例 18 任意一个正整数 与它的十进制表示中的所有数码之差能被 9 整除．m2．数的整除判别法．（1）任何整数都能被 1 整除．（2）如果一个整数的末位能被 2 或５整除，那么这个数就能被 2 或５整除．（3）如果一个整数的末两位能被４或 25 整除，那么这个数就能被 4 或 25 整除．（4）如果一个整数的末三位能被 8 或 125 整除，那么这个数就能被 8 或 125 整除．（5）如果一个整数各数位上的数字之和能被 3 或 9 整除，那么这个数就能被 3 或 9 整除．证明 由 ，有10mod3,10od，10110mod3nnnaaaa LL1 9nn（6）如果一个整数的末三位数与末三位数以前的数字所组成的数的差能被 7 或 11 或13 整除，那么这个数就能被 7 或 11 或 13 整除．证明 由 120nmaL，313210naaL知 ，121032100n n 又由 ，而 均为素数知， 能被 7 或 11 或 13 整除．177,m（7）如果一个整数的奇位数字之和与偶位数字之和的差能被 11 整除，则这个数能被11 整除．证明 由 ，有0mod11010mod1.nnaaL3．分解法．主要用乘法公式．如．23221nnnnababab智浪教育—普惠英才文库． 212324232nnnnabaababL．1 1例 19 试证 ．5512929L例 20 设 与 为正整数，满足2197,IMOpq，13839pqL求证 可被 1979 整除（1979 ）例 20-1 2009 年 9 月 9 日的年、月、日组成“长长久久、永不分离”的吉祥数字20090909，而它也恰好是一个不能再分解的素数．若规定含素因子 的数为吉祥209数，请证明最简分数 的分子 是吉祥数．1208mnLm4． 余数分类法．例 21 试证 ．312n智浪教育—普惠英才文库例 22 个连续整数中必有一个能被 整除．kk例 23 个连续整数之积必能被 整除．k!k例 24 有男孩、女孩共 个围坐在一个圆周上（ ） ，若顺序相邻的 3 人中恰有一n3n个男孩的有 组，顺序相邻的 3 人中恰有一个女孩的有 组，求证 ．a bab智浪教育—普惠英才文库例 25 （1956，中国北京）证明 对任何正整数 都是整数，并且用321nn3 除时余 2．五、同余根据定义，同余问题可以转化为整除问题来解决；同时，同余本身有很多性质，可以直接用来解题．例 26 正方体的顶点标上 或 ，面上标上一个数，它等于这个面四个顶点处的数1的乘积，求证，这样得出的 14 个数之和不能为 0．．例 27 设多项式 的系数都是整数，并且有一nnaxxaxf 110L个奇数 及一个偶数 使得 及 都是奇数，求证方程 没有整数根． f 0f智浪教育—普惠英才文库六、不定方程未知数的个数多于方程个数的整系数代数方程，称为不定方程．求不定方程的整数解，叫做解不定方程． 解不定方程通常要解决 3 个问题，方程是否有解？有解时，有几个解，解数是有限还是无穷？求出全部解．例 28 解方程 ．7192xy例 29 求方程 的整数解．3209xy例 30 甲乙两队各出 7 名队员按事先排好的顺序出场参加围棋擂台赛，双方先由 1 号队员比赛，负者被淘汰，胜者再与负方 2 号队员比。