《同余的概念及其基本性质》由会员分享，可在线阅读，更多相关《同余的概念及其基本性质（10页珍藏版）》请在金锄头文库上搜索。
1、 学院学 术 论 文题 目: 同余的概念及其基本性质学号： 学校： 专业： 班级： 姓名： 指导老师： 时间： 摘要：初等数论是研究数的规律，特别是整数性质的数学分支。它以算术方法为主要研究方法，在日常生活中，我们所要注意的常常不是某些整数，而是这些数用某一固定的数去除所得的余数。同余概念的产生可以说大大丰富了数学的内容。同余是数论中的一个基本概念，同余的应用，一 ：检查因数的一些方法；二 ：弃九法。在本专题的学习中，培养我分析推理解决问题的能力，理解问题的实质。关键字：同余 整数 算术Summary：The number of elementary number theory is to s
2、tudy 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
3、 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 th
4、e essence of the problem.Keyword ：Congruence Integer Arithmetic 引言数论是研究整数性质的一门学科，它是数学中最古老的分支之一，内容极为丰富，曾被数学家说成是数学的皇后。历史表明，每一个重大的数论课题；都是在吸收了当时最新的数学成果，创造成了极深刻地新方法之后，才获得进展的，反过来，数论研究的进展也促进了数学其他分支的发展，因此数论中的许多问题都受到了大批杰出的数学家的重视。初等数论已经有2000年的历史，公元前300年，欧几里得发现了素数是数论的基石，他自己证明了有无穷多个素数。公元前250年古希腊数学家埃拉托塞尼发明了一种筛法。
5、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，记为ab (mod m)。3由定义立刻可以得到下列三个性质：甲 ab (modm)乙 若ab（modm），则b a(modm)，丙 若a b(modm) ，b c(mo
6、dm) ，则 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+，b=m+，0m ，0m ，若a b(modm) ，则=,因此a-b=m(-).反之若ma-b，则mm(-)+(-)，因此m -.但-m，故=.4 同余及其性质 设m为自然数,若整数a与b之差a-b为m的倍数,则称a与b对模m同余,记做 (mod m)否则记为 (mod m)表示a与b对
7、模m不同余. 同余具有下列性质: 1 (mod m) (自反性) 2 若(mod m),则(mod m) (对称性) 3 若,(mod m),则(mod m) (传递性) 4 若,(mod m),则 (mod m) (mod m) (mod m)证明：4a=b+m，=+m，因此a+=b+m（+）,即得(mod m)同理可证 (mod m)若a=b+m，=+m.因此a=b+m(b+m).故 (mod m)参考文献5定理2:设a、b、c、d为整数，m为正整数，若ab(mod m)，cd(mod m)，则： (1)axcybxdy(mod m)，x、y为任意整数，即同余式可以相加；(2)acbd(m
8、od m)，即同余式可以相乘；(3)anbn(mod m)，n0；(4)f(a)f(b)(mod m)，f(x)为任一整系数多项式。证明 ： (1)因为ab(mod m)，cd(mod m)，所以m|(ab)，m|(cd)，于是m|(ab)x(cd)y)，即m|(axcy)(bxdy)，故axcybxdy(mod m)。(2)因为ab(mod m)，cd(mod m)，所以m|(ab)，m|(cd)，于是m|(ab)c(cd)b)，即m|(acbd)，故acbd(mod m)。(3)因为ab(mod m)，则存在整数q使得abmq。于是：anbn(bmq)nbn(bnbn-1(mq)1b1(m
9、q)n-1(mq)n)bnmp，其中p是一整数。所以anbn(mod m)。(4)由(1)和(3)可证定理3若acbc(mod m)，且(c，m)d，则ab(mod m/d)证明 ： 由 (c，m)d 得(c/d，m/d)1。 由 acbc(mod m) 得 m|(acbc)，于是 (m/d)|(ab)(c/d)。 又 (c/d，m/d)1， 从而 (m/d)|(ab)。 故 ab(mod m/d)定理4 设ai，bi（0 i n）以及x，y都是整数，并且x y (mod m)，ai bi (mod m)，0 i n则(mod m)。同余在算术里的两个应用：. 检查因数的一些方法A 一整数能被
10、3（9）整除的必要且充分的条件是它的十进位数码的和能被3（9）整除.证 显然我只须讨论任一正整数a就够了.按照通常方法.把a写成十进位数的形式；a=+ ，010.因101（modm3）,故由定理2得a+（modm3）.由已知性质，即知3a当且仅当3.同法可得9a当且仅当9.B 设正整数a=+，01000，则7（或11，或13）整除a的必要且充分的条件是7（或11或13）整除（+）-（+）=（-1）a证明：因为1000与-1对模7（或11或13）同余，故由定理知a与（-1）a对模7（或11或13）同余.由已知性质，7（或11或13）整除a当且仅当7（或11或13）整除（-1）a.1闵嗣鹤、严士健
11、，初等数论.第三版M，高等教育出版社，2003.12，51-1 弃九法 （假设我们由普遍乘法的运算方法求出整数a，b的乘积是P，并令 a=+，010，b=+，010，P=+，010.我们说：如果（）（）不同余（mod9），那么所求得的乘积是错误的.因为由定理2及性质戊，ab()(）（mod9），P（mod9）.若()(）不同余（mod9），则ab不同余P（mod9），故ab不是P.2闵嗣鹤、严士健，初等数论.第三版M，高等教育出版社，2003.12，52-3闵嗣鹤、严士健，初等数论.第三版M，高等教育出版社，2003.12，48-定义4闵嗣鹤、严士健，初等数论.第三版M，高等教育出版社，200
12、3.12，48-定理15闵嗣鹤、严士健，初等数论.第三版M，高等教育出版社，2003.12，49-丁2同余理论是初等数论中最核心的内容之一，由同余定义可知，若ab(modm)，则 a 和 b被 m除后有相同的余数。这里m 为正整数，一般要求 m大于1，称为模，同余这一思想本质上是将整数按模m 分类，然后讨论每一个类中整数所具有的共性及不同类之间的差异。第一章用带余除法定理将整数分类解决一些问题的方法只不过是同余理论中的一个特殊例子，从同余的定理上看，同余和整除实际上是同一回事，故同余还有两个等价的定义：用整除来定义即ma-b。用等号来定义a=b+mt。值得注意a和 b关于m同余个相对的概念。即它是相对于模 m来讲，两个整数 a和 b关于一个整数模m 同余。则对于另一个整数模，a 和 b未必会同余。从定义上看，同余和整除是同一个事情，但引进了新的符号“ ”后，无论从问题的叙述上，还是解决问题的方法上都有了显著的变化，同时也带来了一些新的知识和方法。在引进了同余的代数性质和自身性质后，同余符号“ ”和等号“ =”相比，在形式上有几乎一致的性质，这便于我们记忆。
