当前位置: 首页 > >

竞赛讲座03-同余式与不定方程

发布时间:

教学视频-公开课,优质课,展示课,课堂实录(http://www.sp910.com/)

竞赛讲座 03 --同余式与不定方程
同余式和不定方程是数论中古老而富有魅力的内容.考虑数学竞赛的需要,下面介绍 有关的基本内容. 1. 同余式及其应用

定义:设 a、b、m 为整数(m>0),若 a 和 b 被 m 除得的余数相同,则称 a 和 b 对模 m 同余.记为 或

一切整数 n 可以按照某个自然数 m 作为除数的余数进行分类, n=pm+r r=0, …, 即 ( 1, m-1),恰好 m 个数类.于是同余的概念可理解为,若对 n1、n2,有 n1=q1m+r,n2=q2m+r, 那么 n1、n2 对模 m 的同余,即它们用 m 除所得的余数相等. 利用整数的剩余类表示,可以证明同余式的下述简单性质: (1) 若 ,则 m|(b-a).反过来,若 m|(b-a),则 ;

(2) (3) (4) ①

如果 a=km+b(k 为整数),则

;

每个整数恰与 0,1,…,m-1,这 m 个整数中的某一个对模 m 同余; 同余关系是一种等价关系: 反身性 ;



对称性

,则

,反之亦然.



传递性



,则



(5)如果



,则

教师之家-免费中小学教学资源下载网(http://www.teacher910.com/)

教学视频-公开课,优质课,展示课,课堂实录(http://www.sp910.com/)







特别地

应用同余式的上述性质,可以解决许多有关整数的问题. 例 1(1898 年匈牙利奥林匹克竞赛题)求使 2 +1 能被 3 整除的一切自然数 n.
n

解∵



则 2 +1 ∴当 n 为奇数时,2 +1 能被 3 整除; 当 n 为偶数时,2 +1 不能被 3 整除. 例2 求 2 最后两位数码.
999 999 n n

n

解 考虑用 100 除 2 所得的余数.











∴2 的最后两位数字为 88.
教师之家-免费中小学教学资源下载网(http://www.teacher910.com/)

999

教学视频-公开课,优质课,展示课,课堂实录(http://www.sp910.com/)

例3

求证 3

1980

+4

1981

能被 5 整除.

证明 ∵





∴ 2.不定方程 不定方程的问题主要有两大类:判断不定方程有无整数解或解的个数;如果不定方 程有整数解,采取正确的方法,求出全部整数解. (1) 不定方程解的判定

如果方程的两端对同一个模 m(常数)不同余,显然,这个方程必无整数解.而方程如 有解则解必为奇数、偶数两种,因而可以在奇偶性分析的基础上应用同余概念判定 方程有无整数解. 例4
2

证明方程 2x -5y =7 无整数解.
2

2

2

证明 ∵2x =5y +7,显然 y 为奇数.



若 x 为偶数,则



∵方程两边对同一整数 8 的余数不等,
教师之家-免费中小学教学资源下载网(http://www.teacher910.com/)

教学视频-公开课,优质课,展示课,课堂实录(http://www.sp910.com/)

∴x 不能为偶数.



若 x 为奇数,则

但 5y +7 ∴x 不能为奇数.因则原方程无整数解. 说明:用整数的整除性来判定方程有无整数解,是我们解答这类问题的常用方法. 例5 (第 14 届美国数学邀请赛题)不存在整数 x,y 使方程

2

① 证明 如果有整数 x,y 使方程①成立,



=

知(2x+3y )+5 能被 17 整除.

2

设 2x+3y=17n+a,其中 a 是 0,±1,±2,±3,±4,±5,±6,±7,±8 中的某 2 2 2 2 2 个数,但是这时(2x+3y) +5=(17n) +34na+(a +5)=a +5(mod17),而 a +5 被 17 整除得的余数分别是 5,6,9,14,4,13,7,3,1,即在任何情况下(2x+3y) 2 +5 都不能被 17 整除,这与它能被 17 整除矛盾.故不存在整数 x,y 使①成立. 例 7 (第 33 届美国数学竞赛题)满足方程 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 2 3 2 2 2 2 3

为方程的一组通解.由于自然数有无限多个,故满足方程的正整数对 (x,y)有无限多个,应选(D). 说明:可用写出方程的一组通解的方法,判定方程有无数个解. (2) 不定方程的解法

教师之家-免费中小学教学资源下载网(http://www.teacher910.com/)

教学视频-公开课,优质课,展示课,课堂实录(http://www.sp910.com/)

不定方程没有统一的解法,常用的特殊方法有:配方法、因式(质因数)分解法、不 等式法、奇偶分析法和余数分析法.对方程进行适当的变形,并正确应用整数的性质 是解不定方程的基本思路.

例6

求方程
2 2 2

的整数解.

解(配方法)原方程配方得(x-2y) +y =13 . 在勾股数中,最大的一个为 13 的只有一组即 5,12,13,因此有 8 对整数的*方和等于 2 13 即(5,12),(12,5),(-5,-12),(-12,-5),(5-,12),(12,-5),(-5,12),(-12,5).故 原方程组的解只能是下面的八个方程组的解

解得

例7 (原民主德国 1982 年中学生竞赛题)已知两个自然数 b 和 c 及素数 a 2 2 2 满足方程 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 2

教师之家-免费中小学教学资源下载网(http://www.teacher910.com/)

教学视频-公开课,优质课,展示课,课堂实录(http://www.sp910.com/)

于是得 c=b+1 及 a =b+c=2b+1<3b,

2





.而 a≥3,∴

≤1,∴

<1.∴a<b.

例 9(第 35 届美国中学数学竞赛题)满足联立方程

的正整数(a,b,c)的组数是( (A)0 (B)1 (C)2 (D)3

). (E)4

解(质因数分解法)由方程 ac+bc=23 得 (a+b)c=23=1×23. ∵a,b,c 为正整数,∴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),应选(C). 例 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 的整数解.

2

2

教师之家-免费中小学教学资源下载网(http://www.teacher910.com/)

教学视频-公开课,优质课,展示课,课堂实录(http://www.sp910.com/)

解(不等式法)方程有整数解

必须△=(y+1) -4(y -y)≥0,解得

2

2

≤y≤

.

满足这个不等式的整数只有 y=0,1,2. 当 y=0 时,由原方程可得 x=0 或 x=1;当 y=1 时,由原方程可得 x=2 或 0;当 y=2 时,由原方程可得 x=1 或 2. 所以方程有整数解

最后我们来看两个分式和根式不定方程的例子.

例 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 及 的整数对(x,y)的个数是( (A)0 (B)1 (C)3 ). (E)7

的不同

(D)4

解法 1 根据题意知,0<x<1984,由

教师之家-免费中小学教学资源下载网(http://www.teacher910.com/)

教学视频-公开课,优质课,展示课,课堂实录(http://www.sp910.com/)

得 当且仅当 1984x 是完全*方数时, 是整数.而 1984=2 ·31, y 故当且仅当 x 具有 31t 形式时,1984x 是完全*方数.
6 2

∵x<1984,∵1≤t≤7.当 t=1,2,3 时,得整数对分别为(31,1519)、(124, 1116)和(279,775).当 t>3 时 y≤x 不合题意,因此不同的整数对的个数是 3, 故应选(C).

解法 2 ∵1984=
2



由此可知:x 必须具有 31t 形式,y 必须

2

具有 31k 形式,并且 t+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.

[文章来源:教师之家 http://www.teacher910.com/ 转载请保留出处] [相关优质课视频请访问:教学视频网 http://www.sp910.com/]

教师之家-免费中小学教学资源下载网(http://www.teacher910.com/)




友情链接: