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

高中数学竞赛培训专题4---同余式与不定方程


竞赛培训专题 7---同余式与不定方程

同余式和不定方程是数论中古老而富有魅力的内容.考虑数学竞赛的需要,下面介绍 有关的基本内容. 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)如果



,则







特别地

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

解∵
n



则 2 +1 当 n 为偶数时,2 +1 不能被 3 整除.
n

n

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

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









∴ ∴2 的最后两位数字为 88. 例3 求证 3
1980 999

+4

1981

能被 5 整除.

证明 ∵



∴ 2.不定方程



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

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



若 x 为偶数,则

∴ ∵方程两边对同一整数 8 的余数不等, ∴x 不能为偶数.

② 若 x 为奇数,则 ∴x 不能为奇数.因则原方程无整数解.

但 5y +7

2

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

① 证明 如果有整数 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 整除得的 2 余数分别是 5,6,9,14,4,13,7,3,1,即在任何情况下(2x+3y) +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 对整数的平方和等于 13 即(5,12),(12,5),(-5,-12),(-12,-5),(5-,12),(12,-5),(-5,12),(-12,5).故原方程组 的解只能是下面的八个方程组的解
2

解得

例 7 (原民主德国 1982 年中学生竞赛题)已知两个自然数 b 和 c 及素数 a 满足方程 a +b =c . 证明:这时有 a<b 及 b+1=c. 证明(因式分解法)∵a +b =c , 又∵a 为素数,∴c-b=1,且 c+b=a .
2 2 2 2

2

2

2

∴a =(c-b)(c+b), 于是得 c=b+1 及 a =b+c=2b+1<3b,
2

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,得

分离整数部分得 ∴y-2=±1,±3,∴x=3,5,±1.

由 x 为整数知 y-2 是 3 的因数, ∴方程整数解为

例 11 求方程 x+y=x -xy+y 的整数解. 解(不等式法)方程有整数解 必须△=(y+1) -4(y -y)≥0,解得
2 2

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 (D)4 (E)7

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

得 当且仅当 1984x 是完全平方数时,y 是整数.而 1984=2 ·31,故当且仅当 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.


相关文章:
高中数学竞赛培训专题4---同余式与不定方程
高中数学竞赛培训专题4---同余式与不定方程_学科竞赛_高中教育_教育专区。竞赛培训专题 7---同余式与不定方程 同余式和不定方程是数论中古老而富有魅力的内容....
人教版高中数学竞赛讲座:同余式与不定方程
人教版高中数学竞赛讲座:同余式与不定方程_学科竞赛_高中教育_教育专区。竞赛讲座 03 --同余式与不定方程 同余式和不定方程是数论中古老而富有魅力的内容.考虑...
高中数学竞赛讲座 03同余式与不定方程
高中数学竞赛讲座 03同余式与不定方程_学科竞赛_高中教育_教育专区。竞赛讲座 03 --同余式与不定方程同余式和不定方程是数论中古老而富有魅力的内容.考虑数学竞赛...
竞赛讲座-同余式与不定方程
竞赛培训专题4---同余式... 7页 1下载券竞​赛​讲​座​-​同​...同余式与不定方程同余式和不定方程是数论中古老而富有魅力的内容.考虑数学竞赛...
竞赛讲座-同余式与不定方程.doc
竞赛讲座-同余式与不定方程.doc_学科竞赛_高中教育_教育专区。精品高中教育教学...同余式与不定方程 同余式和不定方程是数论中古老而富有魅力的内容.考虑数学竞赛...
竞赛数学 同余式与不定方程
竞赛数学 同余式与不定方程_其它_高等教育_教育专区...的不同 (A)0 (B)1 (C)3 (D)4 (E)7 ...
竞赛讲座+03同余式与不定方程
竞赛数学 同余式与不定方程... 26页 免费 竞赛培训专题4---同余式与... ...高中数学知识高中数学知识隐藏>> 阳光家教网 全国最大家教平台 全国最大家教平台...
同余与不定方程
同余与不定方程_数学_自然科学_专业资料。竞赛讲座 03 --同余式与不定方程同余式和不定方程是数论中古老而富有魅力的内容.考虑数学竞赛的需要,下面介绍 有关的基...
高中数学竞赛辅导-初等数论(不定方程)
高中数学竞赛辅导-初等数论(不定方程)_学科竞赛_...4.不定方程 xy ? zt 这是个元二次方程,此...y3 ? 1 1 ,从同余的角度看有 a ? ky ? 1,...
更多相关标签:
同余特性解不定方程 | 同余解不定方程公务员 | 不定方程同余 | 高中数学初等数论同余 | 同余定理 | 同余方程 | 线性同余法 | 同余问题 |