当前位置:首页 >> 学科竞赛 >>

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


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

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

一切整数 n 可以按照某个自然数 m 作为除数的余数进行分类, n=p

m+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)如果



,则







特别地

应用同余式的上述性质,可以解决许多有关整数的问题. 例 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. 例3 求证 3
1980

999

+4

1981

能被 5 整除.

证明 ∵





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

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

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

2

2

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



若 x 为偶数,则



∵方程两边对同一整数 8 的余数不等, ∴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) 不定方程的解法

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

例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

于是得 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

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

必须△=(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,由

得 当且仅当 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. 练习二十 1. 选择题
2 2

(1)方程 x -y =105 的正整数解有( (A)

).

一组 (B)二组 (C)三组 (D)四组 ).

(2)在 0,1,2,…,50 这 51 个整数中,能同时被 2,3,4 整除的有( (A) 2.填空题 (1)的个位数分别为_________及_________.
4 5 4

3 个 (B)4 个 (C)5 个

(D)6 个

(2)满足不 ________. (3)

等式 10 ?A?10 的整数 A 的个数是 x×10 +1,则 x 的值

已知整数 y 被 7 除余数为 5,那么 y 被 7 除时余数为________.
2 2

3

(4) (全俄第 14 届中学生数学竞赛试题)求出任何一组满足方程 x -51y =1 的自然 数解 x 和 y_________. 3.(第 26 届国际数学竞赛预选题)求三个正整数 x、y、z 满足

.

4.(1985 年上海数学竞赛题)在数列 4,8,17,77,97,106,125,238 中相邻 若干个数之和是 3 的倍数,而不是 9 的倍数的数组共有多少组?

5.求

的整数解.

6.求证

可被 37 整除.

7.(全俄 1986 年数学竞赛题)求满足条件 能的值.

的整数 x,y 的所有可

8.(1985 年上海初中数学竞赛题)已知直角三角形的两直角边长分别为 l 厘米、m 厘米,斜边长为 n 厘米,且 l,m,n 均为正整数,l 为质数.证明:2(l+m+n)是完 全平方数.

9.(1988 年全国初中数学竞赛题)如果 p、q、 q>1,试求 p+q 的值.



都是整数,并且 p>1,

练习二十 1.D.C. 2.(1)9 及 1. (2)9.
2

(3)4.
2

(4)原方程可变形为 x =(7y+1) +2y(y-7),令 y=7 可得 x=50.

3.不妨设 x?y?z,则

,故 x?3.又有

故 x?2.若 x=2,则

,

故 y?6.又有

,故 y?4.若 y=4,则 z=20.若 y=5,则 z=10.若 y=6,则 z 无整数

解.若 x=3,类似可以确定 3?y?4,y=3 或 4,z 都不能是整数. 4.可仿例 2 解.

5.先求出

,然后将方程变形为 y=5+x-2

要使 y 为整数,5x-1 应是

完全平方数,…,解得

6.8888≡8(mod37),∴8888
3333

2222

≡8 (mod37).
2222

2

7777≡7(mod37),7777 ≡7 (mod37),8888 2 3 8 +7 =407,37|407,∴37|N.
2 2

3

+7777

3333

≡(8 +7 )(mod37),而

2

3

7.简解:原方程变形为 3x -(3y+7)x+3y -7y=0 由关于 x 的二次方程有解的条件△?0 及 y 为整数可得 0?y?5,即 y=0,1,2,3,4,5.逐一代入原方程可知,原方程仅有两组 解(4,5)、(5,4). 8.∵l +m =n ,∴l =(n+m)(n-m).∵l 为质数,且 n+m>n-m>0,∴n+m=l ,n-m=1.于是 2 2 2 2 l =n+m=(m+1)+m=2m+1,2m=l -1,2(l+m+1)=2l+2+2m=l +2l+1=(l+1) .即 2(l+m+1)是 完全平方数.
2 2 2 2 2

9.易知 p≠q,不妨设 p>q.令 (4-mn)p=m+2,解此方程可得 p、q 之值.

=n,则 m>n 由此可得不定方程


相关文章:
竞赛讲座-同余式与不定方程
同余式与不定方程同余式和不定方程是数论中古老而富有魅力的内容.考虑数学竞赛的需要,下面介绍 有关的基本内容. 1. 同余式及其应用 定义:设 a,b,m 为整数(m...
竞赛讲座 03同余式与不定方程
竞赛讲座 03 --同余式与不定方程同余式和不定方程是数论中古老而富有魅力的内容.考虑数学竞赛的需要,下面介绍 有关的基本内容. 1. 同余式及其应用 定义:设 a...
竞赛讲座03-同余式与不定方程
教学视频-公开课,优质课,展示课,课堂实录(http://www.sp910.com/) 竞赛讲座 03 --同余式与不定方程同余式和不定方程是数论中古老而富有魅力的内容.考虑数学...
人教版高中数学竞赛讲座:同余式与不定方程
人教版高中数学竞赛讲座:同余式与不定方程_学科竞赛_高中教育_教育专区。竞赛讲座 03 --同余式与不定方程 同余式和不定方程是数论中古老而富有魅力的内容.考虑...
高中数学竞赛讲座 03同余式与不定方程
高中数学竞赛讲座 03同余式与不定方程_学科竞赛_高中教育_教育专区。竞赛讲座 03 --同余式与不定方程同余式和不定方程是数论中古老而富有魅力的内容.考虑数学竞赛...
高中数学奥林匹克竞赛讲座:03同余式与不定方程
高中数学奥林匹克竞赛讲座:03同余式与不定方程_高一数学_数学_高中教育_教育专区。高中数学奥林匹克竞赛讲座竞赛讲座 03 --同余式与不定方程 同余式与不定方程同余...
竞赛数学 同余式与不定方程
竞赛数学 同余式与不定方程_其它_高等教育_教育专区。竞赛数学 同余式与不定方程...竞赛讲座 03同余式与不定... 10页 免费 数学奥林匹克竞赛讲座 1... 2页 ...
同余与不定方程
同余与不定方程_数学_自然科学_专业资料。竞赛讲座 03 --同余式与不定方程同余式和不定方程是数论中古老而富有魅力的内容.考虑数学竞赛的需要,下面介绍 有关的基...
高中数学竞赛培训专题4---同余式与不定方程
高中数学竞赛培训专题4---同余式与不定方程_学科竞赛_高中教育_教育专区。竞赛培训专题 7---同余式与不定方程 同余式和不定方程是数论中古老而富有魅力的内容....
更多相关标签:
同余特性解不定方程 | 同余解不定方程公务员 | 不定方程同余 | 同余定理 | 同余方程 | 线性同余法 | 同余问题 | 同余式 |