同余的概念及其基本性质
- 格式：pdf
- 大小：496.25 KB
- 文档页数：10
学院
学 术 论 文
题 目: 同余的概念及其基本性质
学号：
学校：
专业：
班级：
姓名：
指导老师：
时间：
摘要：初等数论是研究数的规律，特别是整数性质的数学分支。它
以算术方法为主要研究方法，在日常生活中，我们所要注意的常
常不是某些整数，而是这些数用某一固定的数去除所得的余数。
同余概念的产生可以说大大丰富了数学的内容。同余是数论中的
一个基本概念，同余的应用，一 ：检查因数的一些方法；二 ：
弃九法。在本专题的学习中，培养我分析推理解决问题的能力，
理解问题的实质。
关键字：同余 整数 算术
Summary：The number of elementary number theory is to study the law, in particular
integer nature of the branch of mathematics. It arithmetic method as the main research
methods in their daily lives, we are often not to pay attention to some integer, but these numbers with a fixed a number of removal from the remainder. I created the concept of the same can be said to have greatly enriched the content of mathematics. Number theory congruence is a basic concept of the application with more than one: Check factor of some of the ways; 2: abandoned nine law. In the topic of study, training my analysis reasoning ability to
solve problems, understand the essence of the problem.
Keyword ：
Congruence Integer Arithmetic
引言
数论是研究整数性质的一门学科，它是数学中最古老的分支之一，内容极为丰富，曾被数学家说成是数学的皇后。历史表明，每一个重大
的数论课题；都是在吸收了当时最新的数学成果，创造成了极深刻地
新方法之后，才获得进展的，反过来，数论研究的进展也促进了数学
其他分支的发展，因此数论中的许多问题都受到了大批杰出的数学家
的重视。初等数论已经有2000年的历史，公元前300年，欧几里
得发现了素数是数论的基石，他自己证明了有无穷多个素数。公
元前250年古希腊数学家埃拉托塞尼发明了一种筛法。2000年来，
数论学的一个最重要的任务，就是寻找一个可以表示所有素数的
统一公式，或者称为素数普遍公式，为此，人类耗费了巨大的心
血。後来发现埃拉托塞尼筛法可以转换成为一个素数产生的公式：
同余的基本性质
定义1：给定正整数m
，如果整数a
与b
之差被m
整除，则称a
与
b
对于模m
同余，或称a
与b
同余，模m
，记为
a
b
(mod m
)，
此时也称b
是a
对模m
的同余。
如果整数a
与b
之差不能被m
整除，则称a
与b
对于模m
不同余，
或称a
与b
不同余，模m
，记为a
b
(mod m
)。
由定义立刻可以得到下列三个性质：
甲 a≡b (modm)
乙 若a≡b（modm），则b≡ a(modm)，
丙 若a ≡b(modm) ，b≡ c(modm) ，则 a ≡c(modm). 下面的三个叙述是等价的：
(ⅰ) a
a
(mod m
)；
(ⅱ) a
b
(mod m
) b
a
(mod m
)；
(ⅲ) a
b
，b
c
(mod m
) a
c
(mod m
)。
定理1 整数a ，b对模m同余的充分与必要条件是m ∣a-b ,即
a=b+mt， t是整数.
证明：设a=m
1q+
1r，b=m
2q+
2r，0≤
1r
2r
则
1r=
2r,因此a-b=m(
1q-
2q).反之若m∣a-b，则m∣m(
1q-
2q)+(
1r-
2r)，
因此m ∣
1r-
2r.但︱
1r-
2r︱
1r=
2r.
[同余及其性质] 设m
为自然数,若整数a
与b
之差a-b
为m
的倍
数,则称a
与b
对模m
同余,记做
(mod m
)
否则记为
(mod m
)
表示a
与b
对模m
不同余.
同余具有下列性质:
1 (mod m
) (自反性) 2 若(mod m
),则(mod m
) (对称性)
3 若,(mod m
),则(mod m
) (传递性)
4 若
,(mod m
),则
(mod m
)
(mod m
)
(mod m
)
证明：4 a=b+m
1t，
1a=
1b+m
2t，因此a+
1a=b+
1b+m（
1t+
2t）,
即得 (mod m
)
同理可证
(mod m
)
若a=b+m
1t，
1a=
1b+m
2t.因此a
1a=b
1b+m(b
2t+
1b
1t+m
2t
2t).
故
(mod m
)
定理2:设a
、b
、c
、d
为整数，m
为正整数，若a
≡b
(mod m
)，c
≡d
(mod
m
)，则：
(1)ax
＋cy
≡bx
＋dy
(mod m
)，x
、y
为任意整数，即同余式可以相加；
(2)ac
≡bd
(mod m
)，即同余式可以相乘；
(3)an
≡bn
(mod m
)，n
＞0； (4)f
(a
)≡f
(b
)(mod m
)，f
(x
)为任一整系数多项式。
证明 ： (1)因为a
≡b
(mod m
)，c
≡d
(mod m
)，所以m
|(a
－b
)，m
|(c
－d
)，于是m
|((a
－b
)x
＋(c
－d
)y
)，即m
|((ax
＋cy
)－(bx
＋dy
))，
故ax
＋cy
≡bx
＋dy
(mod m
)。
(2)因为a
≡b
(mod m
)，c
≡d
(mod m
)，所以m
|(a
－b
)，m
|(c
－d
)，于
是m
|((a
－b
)c
＋(c
－d
)b
)，即m
|(ac
－bd
)，故ac
≡bd
(mod m
)。
(3)因为a
≡b
(mod m
)，则存在整数q
使得a
－b
＝mq
。于是：
an
－bn
＝(b
＋mq
)n
－bn
＝(bn
＋bn-
1(mq
)1＋„＋b
1(mq
)n-
1＋(mq
)n
)
－bn
＝mp
，其中p
是一整数。
所以an
≡bn
(mod m
)。
(4)由(1)和(3)可证
定理3若ac
≡bc
(mod m
)，且(c
，m
)＝d
，则a
≡b
(mod m
/d
)
证明 ： 由 (c
，m
)＝d
得(c
/d
，m
/d
)＝1。 由 ac
≡bc
(mod m
) 得
m
|(ac
－bc
)，于是 (m
/d
)|(a
－b
)(c
/d
)。 又 (c
/d
，m
/d
)＝1， 从
而 (m
/d
)|(a
－b
)。 故 a
≡b
(mod m
/d
)
定理4 设a
i，b
i（0 i
n
）以及x
，y
都是整数，并且
x
y
(mod m
)，a
i
b
i (mod m
)，0 i
n
