同余与不定方程
余年寄山水
984次浏览
2021年01月23日 12:33
最佳经验
本文由作者推荐
-读书心得300字
竞赛讲座
03
--
同余式与不定方程
同余式和不定方程是数论中古老而富有魅力的内容
.
考虑数学竞赛的需要
,
下面介绍
有关的基本内容
.
1.
同余式及其应用
定义
:
设
a
、
b
、
m
为整数（< br>m
＞
0
），若
a
和
b
被
m
除得的余数相同，则称
a
和
b
对模
m
同余
.
记为
或
一切整数
n
可以按照某个自然数
m
作为 除数的余数进行分类，
即
n=pm+r
（
r=0
，
1
，
…，
m-1
）
，
恰好
m
个数类
.于是同余的概念可理解为
,
若对
n
1
、
n
2< br>，
有
n
1
=q
1
m+r
，
n
2
=q
2
m+r
，
那么
n
1
、
n
2
对模
m
的同余，即它们用
m
除所得的余数相等
.
利用整数的剩余类表示
,
可以证明同余式的下述简单性质
:
(1)
若
,
则
m|(b-a).
反过来
,
若
m| (b-a),
则
;
(2)
如果
a=km+b(k
为整数
),
则
;
(3)
每个整数恰与
0,1,…，
m-1
，这
m
个整数中的某一个 对模
m
同余；
(4)
同余关系是一种等价关系：
①
反身性
；
②
对称性
，则
，反之亦然
.
③
传递性
，
，则
；
（
5
）如果
，
，则
①
；
②
特别地
应用同余式的上述性质，可以解决许多有关整数的问题
.
例
1
（< br>1898
年匈牙利奥林匹克竞赛题）求使
2
+1
能被
3
整除的一切自然数
n.
n
解∵
∴
则
2
+1
n
n
∴当
n
为奇数时 ，
2
+1
能被
3
整除；
当
n
为 偶数时，
2
+1
不能被
3
整除
.
例
2
求
2
最后两位数码
.
解
考虑用
100
除
2
所得的余数
.
999
999
n
∵
∴
又
∴
∴
∴2
的最后两位数字为
88.
999
例
3
求证
3
1980
+4
1981
能被
5
整除
.
证明
∵
∴
∴
∴
2
．不定方程
< br>不定方程的问题主要有两大类：判断不定方程有无整数解或解的个数；如果不定方
程有整数解，采 取正确的方法，求出全部整数解
.
(1)
不定方程解的判定
如果方程的两端对同一个模
m(
常数
)
不同余
,
显然
,
这个方程必无整数解
.
而方程如
有解则解必为奇数、偶数两种，因而可以 在奇偶性分析的基础上应用同余概念判定
方程有无整数解
.
例
4
证明方程
2x
-5y
=7
无整数解
.
证明
∵2x
=5y
+7
，显然
y
为奇数
.
2
2
2
2
①
若
x
为偶数，则
∴
∵方程两边对同一整数
8
的余数不等，
∴x
不能为偶数
.
②
若
x
为奇数，则
但
5y
+7
2
∴x
不能为奇数
.
因则原方程无整数解
.
说明
:
用整数的整除性来判定方程有无整数解
,
是我们解答这类问题的常用方法
.
例
5 (
第
14
届美国数学邀请赛题
)
不存在 整数
x,y
使方程
①
证明
如果有整数
x
，
y
使方程①成立，
则
=
知（
2x+3y
）
+5
能被
17
整除< br>.
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< br>+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
为自然数
),< br>则
2
2
2
3
2
2
2
2
3< br>为方程的一组通解
.
由于自然数有无限多个
,
故满足方程的正整数对< br>(x,y)
有无限多个
,
应选
(D).
说明
:可用写出方程的一组通解的方法
,
判定方程有无数个解
.
(2)
不定方程的解法
不定方程没有统一的解法
,
常用的特殊方法有
:
配方法、因式（质因数）分解法、不
等式法、奇偶分析法和余数分 析法
.
对方程进行适当的变形
,
并正确应用整数的性质
是解不定方程 的基本思路
.
例
6
求方程
2
的整数解
. < br>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