整数分拆同余性质毕业论文

100除以7的余数是2，意思就是说把100个东西七个七个分成一组的话最后还剩2个。余数有一个严格的定义：假如被除数是a，除数是b（假设它们均为正整数），那么我们总能够找到一个小于b的自然数r和一个整数m，使得a=bm+r。这个r就是a除以b的余数，m被称作商。我们经常用mod来表示取余，a除以b余r就写成a mod b = r。 如果两个数a和b之差能被m整除，那么我们就说a和b对模数m同余（关于m同余）。比如，100-60除以8正好除尽，我们就说100和60对于模数8同余。它的另一层含义就是说，100和60除以8的余数相同。a和b对m同余，我们记作a≡b(mod m)。比如，刚才的例子可以写成100≡60(mod 8)。你会发现这种记号到处都在用，比如和数论相关的书中就经常把a mod 3 = 1写作a≡1(mod 3)。 之所以把同余当作一种运算，是因为同余满足运算的诸多性质。比如，同余满足等价关系。具体地说，它满足自反性（一个数永远和自己同余）、对称性（a和b同余，b和a也就同余）和传递性（a和b同余，b和c同余可以推出a和c同余）。这三个性质都是显然的。 同余运算里还有稍微复杂一些的性质。比如，同余运算和整数加减法一样满足“等量加等量，其和不变”。小学我们就知道，等式两边可以同时加上一个相等的数。例如，a=b可以推出a+100=b+100。这样的性质在同余运算中也有：对于同一个模数m，如果a和b同余，x和y同余，那么a+x和b+y也同余。在我看来，这个结论几乎是显然的。当然，我们也可以严格证明这个定理。这个定理对减法同样有效。 性质：如果a≡b(mod m)，x≡y(mod m)，则a+x≡b+y(mod m)。 证明：条件告诉我们，可以找到p和q使得a-mp = b-mq，也存在r和s使得x-mr = y-ms。于是a-mp + x-mr = b-mq + y-ms，即a+x-m(p+r) = b+y-m(q+s)，这就告诉我们a+x和b+y除以m的余数相同。 容易想到，两个同余式对应相乘，同余式两边仍然相等： 如果a≡b(mod m)，x≡y(mod m)，则ax≡by(mod m)。 证明：条件告诉我们，a-mp = b-mq，x-mr = y-ms。于是(a-mp)(x-mr) = (b-mq)(y-ms)，等式两边分别展开后必然是ax-m(…) = by-m(…)的形式，这就说明ax≡by(mod m)。 现在你知道为什么有的题要叫你“输出答案mod xxxxx的结果”了吧，那是为了避免高精度运算，因为这里的结论告诉我们在运算过程中边算边mod和算完后再mod的结果一样。假如a是一个很大的数，令b=a mod m，那么(a * 100) mod m和(b * 100) mod m的结果是完全一样的，这相当于是在a≡b (mod m)的两边同时乘以100。这些结论其实都很显然，因为同余运算只关心余数（不关心“整的部分”），完全可以每一次运算后都只保留余数。因此，整个运算过程中参与运算的数都不超过m，避免了高精度的出现。 在证明Fermat小定理时，我们用到了这样一个定理： 如果ac≡bc(mod m)，且c和m互质，则a≡b(mod m) （就是说同余式两边可以同时除以一个和模数互质的数）。 证明：条件告诉我们，ac-mp = bc-mq，移项可得ac-bc = mp-mq，也就是说(a-b)c = m(p-q)。这表明，(a-b)c里需要含有因子m，但c和m互质，因此只有可能是a-b被m整除，也即a≡b(mod m)。

同余这个概念最初是由德国伟大的数学家高斯发现的，有这样的几个定理:对于两个整数A和B，如果他们除以同一个自然数M的余数相同，就说A、B对于模M同余。比如说:12除以5，47除以5，他们有相同的余数2，这时我们就说对于除数5，12和47同余。记作12≡47(mod5)同余的性质主要有:(1)对于同一个除数，两数的和(或差)于他们余数的和(或差)同余数。(2)对于同一个除数，两数的乘积与他们余数的乘积同余。(3)对于同一个除数，如果两个整数同余，那么他们的差就一定能被这个数整除。(4)对于同一个除数，如果两个整数同余，那么他们的乘方仍然同余。解答同余类型题目的关键是灵活运用性质，把求一个比较大的数字除以某数的余数问题转化为求一个较小数除以这个数的余数，使复杂的问题变得简单化。例1:求1992×59除以7的余数。根据性质2，不用计算两个数的乘积，可以转化位分别求出1992÷7和59÷7的余数的积，使计算简单化。第一个余数是4，第二个余数是3.余数的乘积是12，除以7后的余数是5，所以1992×59除以7的余数是5.简单记做因为1992×59≡4×3≡5(mod7),所以余数是5.例2:求2001的2003次方除以13的余数。根据性质4来解决。2001除以13的余数等于12，12除以13的余数也是12，可以说2001的2003次方与12的2003次方对于除数13同余。但是12的2003次方仍然是一个很大的数字，求余数仍然比较困难。这时的关键找出12的几次方对于13与1同余，经过试验知道12的平方≡1(mod13),而2003=2的1001次方+1，所以12平方的1001次方≡1的1001(mod13).根据同余的性质12的2002次方×12≡1×12=12(mod13),所以余数等于12。例3:自然数16520、14903、14177除以m得到相同的余数，m最大的数值等于多少?三个数字比较大，但是他们对于m同余，那么当中任意两个数字的差必然是m倍数，要求m的最大的数值可以转化位求他们的三个差的最大公约数，从而降低计算的难度。16520-14903=1617=3×7的平方×11，16520-14177=2343=3×11×71，14903-14177=726=2×3×11的平方，三个差的最大公约数是3×11=33,m的最大数字等于33.练习:1)879×4376×5283除以19的余数。2)已知2001年的国庆节是星期一，求2008年的国庆节是星期几?3)求16的200次方除以21的余数?4)一个整数除226、192、141都得到相同的余数，并且余数不等于0，这个整数最大是多少?

整数分拆理论，主要是研究各种类型的分拆函式的性质及其相互关系。早在中世纪，就有关于特殊的整数分拆问题的研究。18世纪40年代，L.欧拉提出了用母函式法（或称形式幂级数法）研究整数分拆，证明了不少有重要意义的定理，为整数分拆奠定了理论基础。解析数论中的圆法的引进，使整数分拆理论得到了进一步发展。整数分拆与模函式有密切关系，并在组合数学、群论、机率论、数理统计学及质点物理学等方面都有重要套用。

数学发展史 此书记录了世界初等数学的发展与变迁。可大体分为“数的出现”、“数字与符号的起源与发展”、“分数”、“代数与方程”、“几何”、“数论”与“名著录”七大项，跨度千万年。可让读者了解数学的光辉历史与发展。是将历史与数学结合出的趣味百科读物。数的出现一、数的概念出现 人对于“数”的概念是与身俱来的。从原始人开始，人就能分出一与二与三的区别，从而，就有了对数的认识。而为了表示数，原始人就创造并使用了一种古老却笨拙且不太实用的方法——结绳计数。通过在绳子上打结来表示所指物体的数量，而为了辨认数量，也就出现了数数这一重要的方法。这一方法如今看来十分笨拙，但却是人对数学的认识由零到一的关键一步。从这笨拙的一步人们也意识到：对数学的阐述必须要尽量得简洁清楚。这是一个从那时开始便影响至今的人类第一个数学方面的认识，这也是人类为了解数学而迈出的关键性一步。数字与符号的起源与发展一、数的出现 很快，人类就又迈出了一大步。随着文字的出现，最原始的数字就出现了。且更令人高兴的是，人们将自己的认识代入了设计之中，他们想到了“以一个大的代替多个小的”这种方法来设计，而在字符表示之中，就是“进位制”。在众多的数码之中，有古巴比仑的二十进制数码、古罗马字符，但一直流传至今的，世界通用的阿拉伯数字。它们告诉了我们：简洁的，就是最好的。 而现在，又出现了“二进制数”、“三进制数”等低位进制数，有时人们会认为它们有些过度的“简洁”，使数据会过多得长，而不便书写，且熟悉了十进制的阿拉伯数字后，改变进制的换算也十分麻烦。其实，人是高等动物 ，理解能力强，从古至今都以十为整，所以习惯了十进制。可是，不是所有的东西都有智商，而且不可能智商高到能明显区分1-10，却能通过明显相反的方式表达两个数码。于是，人类创造了“二进制数”，不过它们不便书写，只适用于计算机和某些智能机器。但不可否认的是，它又创造了一种新的数码表示方法。二、符号的出现 加减乘除〈＋、－、×(·)、÷(∶）〉等数学符号是我们每一个人最熟悉的符号，因为不光在数学学习中离不开它们，几乎每天的日常的生活也离不开它们。别看它们这么简单，直到17世纪中叶才全部形成。 法国数学家许凯在1484年写成的《算术三篇》中，使用了一些编写符号，如用D表示加法，用M表示减法。这两个符号最早出现在德国数学家维德曼写的《商业速算法》中，他用“＋”表示超过,用“－”表示不足。1、加号（+）和减号（-） 加减号“＋”，“－”，1489年德国数学家魏德曼在他的著作中首先使用了这两个符号，但正式为大家公认是从1514年荷兰数学家荷伊克开始。到1514年，荷兰的赫克首次用“＋”表示加法，用“－”表示减法。1544年，德国数学家施蒂费尔在《整数算术》中正式用“＋”和“－”表示加减，这两个符号逐渐被公认为真正的算术符号，广泛采用。2、乘号（×、·） 乘号“×”，英国数学家奥屈特于1631年提出用“×”表示相乘。英国数学家奥特雷德于1631年出版的《数学之钥》中引入这种记法。据说是由加法符号＋变动而来，因为乘法运算是从相同数的连加运算发展而来的。另一乘号“·”是数学家赫锐奥特首创的。后来，莱布尼兹认为“×”容易与“X”相混淆，建议用“·”表示乘号，这样，“·”也得到了承认。3、除号（÷） 除法除号“÷”，最初这个符号是作为减号在欧洲大陆流行，奥屈特用“：”表示除或比.也有人用分数线表示比，后来有人把二者结合起来就变成了“÷”。瑞士的数学家拉哈的著作中正式把“÷”作为除号。符号“÷”是英国的瓦里斯最初使用的，后来在英国得到了推广。除的本意是分，符号“÷”的中间的横线把上、下两部分分开，形象地表示了“分”。 至此，四则运算符号齐备了，当时还远未达到被各国普遍采用的程度。4、等号（＝） 等号“＝”，最初是1540年由英国牛津大学教授瑞柯德开始使用。1591年法国数学家韦达在其著作中大量使用后，才逐渐为人们所接受。分数一、分数的产生与定义 人类历史上最早产生的数是自然数（正整数），以后在度量和均分时往往不能正好得到整数的结果，这样就产生了分数。 一个物体，一个图形，一个计量单位，都可看作单位“1”。把单位“1”平均分成几份，表示这样一份或几份的数叫做分数。在分数里，表示把单位“1”平均分成多少份的叫做分母，表示有这样多少份的叫做分子；其中的一份叫做分数单位。 分子,分母同时乘或除以一个相同的数〔0除外〕,分数的大小不变.这就是分数的基本性质.分数一般包括:真分数,假分数,带分数. 真分数小于1. 假分数大于1,或者等于1. 带分数大于1而又是最简分数.带分数是由一个整数和一个真分数组成的。 注意 ：①分母和分子中不能有0，否则无意义。 ②分数中的分子或分母不能出现无理数（如2的平方根），否则就不是分数。 ③一个最简分数的分母中只有2和5两个质因数就能化成有限小数；如果最简分数的分母中只含有2和5以外的质因数那么就能化成纯循环小数；如果最简分数的分母中既含有2或5两个质因数也含有2和5以外的质因数那么就能化成混循环小数。（注：如果不是一个最简分数就要先化成最简分数再判断；分母是2或5的最简分数一定能化成有限小数，分母是其他质数的最简分数一定能化成纯循环小数）二、分数的历史与演变 分数在我们中国很早就有了,最初分数的表现形式跟现在不一样。后来,印度出现了和我国相似的分数表示法。再往后,阿拉伯人发明了分数线,分数的表示法就成为现在这样了。 在历史上，分数几乎与自然数一样古老。早在人类文化发明的初期，由于进行测量和均分的需要，引入并使用了分数。 在许多民族的古代文献中都有关于分数的记载和各种不同的分数制度。早在公元前2100多年，古代巴比伦人（现处伊拉克一带）就使用了分母是60的分数。 公元前1850年左右的埃及算学文献中，也开始使用分数。200多年前，瑞士数学家欧拉，在《通用算术》一书中说，要想把7米长的一根绳子分成三等份是不可能的，因为找不到一个合适的数来表示它．如果我们把它分成三等份，每份是3/7 米．像3/7 就是一种新的数，我们把它叫做分数． 为什么叫它分数呢？分数这个名称直观而生动地表示这种数的特征．例如，一只西瓜四个人平均分，不把它分成相等的四块行吗？从这个例子就可以看出，分数是度量和数学本身的需要——除法运算的需要而产生的． 最早使用分数的国家是中国．我国春秋时代（公元前770年～前476年）的《左传》中，规定了诸侯的都城大小：最大不可超过周文王国都的三分之一，中等的不可超过五分之一，小的不可超过九分之一。秦始皇时代的历法规定：一年的天数为三百六十五又四分之一。这说明：分数在我国很早就出现了，并且用于社会生产和生活。 《九章算术》是我国1800多年前的一本数学专著，其中第一章《方田》里就讲了分数四则算法． 在古代，中国使用分数比其他国家要早出一千多年．所以说中国有着悠久的历史，灿烂的文化 。几何一、公式1、平面图形正方形： S＝a² C＝4a三角形： S＝ah/2 a＝2S/h h＝2S/a平行四边形：S＝ah a＝S/h h＝S/a梯形： S＝(a＋b)h/2 h＝2S/(a＋b) a＝2S/h－b b＝2S/h－a圆形： S＝∏r² C＝2r∏＝∏d r＝d/2＝C/∏/2r²＝S/∏ d＝C/∏半圆： S＝∏r²/2 C＝∏r＋d＝ 顶点数＋面数－块数＝12、立体图形正方体： V＝a³＝S底·a S表＝6a² S底＝a² S侧＝4a² 棱长和＝12a长方体： V＝abh＝S底·h S表＝2(ab＋ac＋bc） S侧＝2(a＋b)h 棱长和＝4(a＋b＋h)圆柱： V＝∏r²h S表＝2∏r²＋∏r²h＝S底（h＋2） S侧＝∏r²h S底＝∏r² 其它柱体：V＝S底h锥体： V＝V柱体/3球： V＝4/3∏r³ S表＝4∏r²顶点数＋面数－棱数＝2数论一、数论概述 人类从学会计数开始就一直和自然数打交道了，后来由于实践的需要，数的概念进一步扩充，自然数被叫做正整数，而把它们的相反数叫做负整数，介于正整数和负整数中间的中性数叫做0。它们合起来叫做整数。（现在，自然数的概念有了改变，包括正整数和0） 对于整数可以施行加、减、乘、除四种运算，叫做四则运算。其中加法、减法和乘法这三种运算，在整数范围内可以毫无阻碍地进行。也就是说，任意两个或两个以上的整数相加、相减、相乘的时候，它们的和、差、积仍然是一个整数。但整数之间的除法在整数范围内并不一定能够无阻碍地进行。 人们在对整数进行运算的应用和研究中，逐步熟悉了整数的特性。比如，整数可分为两大类—奇数和偶数（通常被称为单数、双数）等。利用整数的一些基本性质，可以进一步探索许多有趣和复杂的数学规律，正是这些特性的魅力，吸引了古往今来许多的数学家不断地研究和探索。 数论这门学科最初是从研究整数开始的，所以叫做整数论。后来整数论又进一步发展，就叫做数论了。确切的说，数论就是一门研究整数性质的学科。 二、数论的发展简况 自古以来，数学家对于整数性质的研究一直十分重视，但是直到十九世纪，这些研究成果还只是孤立地记载在各个时期的算术著作中，也就是说还没有形成完整统一的学科。 自我国古代，许多著名的数学著作中都关于数论内容的论述，比如求最大公约数、勾股数组、某些不定方程整数解的问题等等。在国外，古希腊时代的数学家对于数论中一个最基本的问题——整除性问题就有系统的研究，关于质数、和数、约数、倍数等一系列概念也已经被提出来应用了。后来的各个时代的数学家也都对整数性质的研究做出过重大的贡献，使数论的基本理论逐步得到完善。 在整数性质的研究中，人们发现质数是构成正整数的基本“材料”，要深入研究整数的性质就必须研究质数的性质。因此关于质数性质的有关问题，一直受到数学家的关注。 到了十八世纪末，历代数学家积累的关于整数性质零散的知识已经十分丰富了，把它们整理加工成为一门系统的学科的条件已经完全成熟了。德国数学家高斯集中前人的大成，写了一本书叫做《算术探讨》，1800年寄给了法国科学院，但是法国科学院拒绝了高斯的这部杰作，高斯只好在1801年自己发表了这部著作。这部书开始了现代数论的新纪元。 在《算术探讨》中，高斯把过去研究整数性质所用的符号标准化了，把当时现存的定理系统化并进行了推广，把要研究的问题和意志的方法进行了分类，还引进了新的方法。 由于近代计算机科学和应用数学的发展，数论得到了广泛的应用。比如在计算方法、代数编码、组合论等方面都广泛使用了初等数论范围内的许多研究成果；又文献报道，现在有些国家应用“孙子定理”来进行测距，用原根和指数来计算离散傅立叶变换等。此外，数论的许多比较深刻的研究成果也在近似分析、差集合、快速变换等方面得到了应用。特别是现在由于计算机的发展，用离散量的计算去逼近连续量而达到所要求的精度已成为可能。三、数论的分类初等数论 意指使用不超过高中程度的初等代数处理的数论问题，最主要的工具包括整数的整除性与同余。重要的结论包括中国剩余定理、费马小定理、二次互逆律等等。解析数论 借助微积分及复分析的技术来研究关于整数的问题，主要又可以分为积性数论与加性数论两类。积性数论藉由研究积性生成函数的性质来探讨质数分布的问题，其中质数定理与狄利克雷定理为这个领域中最著名的古典成果。加性数论则是研究整数的加法分解之可能性与表示的问题，华林问题是该领域最著名的课题。此外例如筛法、圆法等等都是属于这个范畴的重要议题。我国数学家陈景润在解决“哥德巴赫猜想”问题中使用的是解析数论中的筛法。 代数数论 是把整数的概念推广到代数整数的一个分支。关于代数整数的研究，主要的研究目标是为了更一般地解决不定方程的问题，而为了达到此目的，这个领域与代数几何之间的关联尤其紧密。建立了素整数、可除性等概念。 几何数论是由德国数学家、物理学家闵可夫斯基等人开创和奠基的。主要在于透过几何观点研究整数（在此即格子点）的分布情形。几何数论研究的基本对象是“空间格网”。在给定的直角坐标系上，坐标全是整数的点，叫做整点；全部整点构成的组就叫做空间格网。空间格网对几何学和结晶学有着重大的意义。最著名的定理为Minkowski 定理。由于几何数论涉及的问题比较复杂，必须具有相当的数学基础才能深入研究。 计算数论 借助电脑的算法帮助数论的问题，例如素数测试和因数分解等和密码学息息相关的话题。 超越数论 研究数的超越性，其中对于欧拉常数与特定的 Zeta 函数值之研究尤其令人感到兴趣。 组合数论 利用组合和机率的技巧，非构造性地证明某些无法用初等方式处理的复杂结论。这是由艾狄胥开创的思路。四、皇冠上的明珠 数论在数学中的地位是独特的，高斯曾经说过“数学是科学的皇后，数论是数学中的皇冠”。因此，数学家都喜欢把数论中一些悬而未决的疑难问题，叫做“皇冠上的明珠”，以鼓励人们去“摘取”。 简要列出几颗“明珠”：费尔马大定理、孪生素数问题、歌德巴赫猜想、角谷猜想、圆内整点问题、完全数问题…… 五、中国人的成绩 在我国近代，数论也是发展最早的数学分支之一。从二十世纪三十年代开始，在解析数论、刁藩都方程、一致分布等方面都有过重要的贡献，出现了华罗庚、闵嗣鹤、柯召等第一流的数论专家。其中华罗庚教授在三角和估值、堆砌素数论方面的研究是享有盛名的。1949年以后，数论的研究的得到了更大的发展。特别是在“筛法”和“歌德巴赫猜想”方面的研究，已取得世界领先的优秀成绩。 特别是陈景润在1966年证明“歌德巴赫猜想”的“一个大偶数可以表示为一个素数和一个不超过两个素数的乘积之和”以后，在国际数学引起了强烈的反响，盛赞陈景润的论文是解析数学的名作，是筛法的光辉顶点。至今，这仍是“歌德巴赫猜想”的最好结果。名著录《几何原本》 欧几里得 约公元前300年 《周髀算经》 作者不详 时间早于公元前一世纪 《九章算术》 作者不详 约公元一世纪 《孙子算经》 作者不详 南北朝时期 《几何学》 笛卡儿 1637年 《自然哲学之数学原理》 牛顿 1687年 《无穷分析引论》 欧拉 1748年 《微分学》 欧拉 1755年 《积分学》（共三卷） 欧拉 1768－1770年 《算术探究》 高斯 1801年 《堆垒素数论》 华罗庚 1940年左右 任意选一段吧!!!

1 反身性 a≡a (mod m)2 对称性 若a≡b(mod m)，则b≡a (mod m)3 传递性 若a≡b (mod m)，b≡c (mod m)，则a≡c (mod m)4 同余式相加 若a≡b (mod m)，c≡d(mod m)，则a+-c≡b+-d (mod m)5 同余式相乘 若a≡b (mod m)，c≡d(mod m)，则ac≡bd (mod m)【证明】上述性质很容易证明,下面仅证明(3).∵a≡b(mod m)∴m|(a-b) 同理m|(b-c),∴m|[(a-b)+(b-c)]∴m|(a-c).故a≡c(mod m).4 线性运算如果a ≡ b (mod m)，c ≡ d (mod m),那么(1)a ± c ≡ b ± d (mod m)，(2)a * c ≡ b * d (mod m)【证明】(1)∵a≡b(mod m),∴m|(a-b) 同理 m|(c-d)∴m|[(a-b)±(c-d)]∴m|[(a±c)-(b±d)]∴a ± c ≡ b ± d (mod m)(2)∵ac-bd=ac-bc+bc-bd=c(a-b)+b(c-d)又 m|(a-b) , m|(c-d)∴m|(ac-bd)∴a * c ≡ b * d (mod m) 5 除法若ac ≡ bc (mod m) c≠0 则 a≡ b (mod m/gcd(c,m)) 其中gcd(c,m)表示c,m的最大公约数特殊地 ,gcd(c,m)=1 则a ≡ b (mod m)6 幂运算如果a ≡ b (mod m)，那么a^n ≡ b^n (mod m)7 若a ≡ b (mod m)，n|m,则 a ≡ b (mod n)8 若a ≡ b (mod mi) (i=1,2...n) 则 a ≡ b (mod [m1,m2,...mn]) 其中[m1,m2,...mn]表示m1,m2,...mn的最小公倍数9 欧拉定理设a,m∈N,(a,m)=1,则a^(φ(m))≡1(mod m)(注:φ(m)指模m的简系个数， φ(m)=m-1, 如果m是素数；φ(m=q1^r1 * q2^r2 * ...*qi^ri)=m (1-1/q1)(1-1/q2)...(1-1/qi))推论: 费马小定理: 若p为质数，则a^p ≡ a (mod p) 即a^(p-1) ≡ 1 (mod p)（但是当p|a时不等价）10 中国剩余定理设整数m1,m2,m3,......,mn 两两互素，令m=m1m2m3m4m5...mn（mi的连乘）。则对于任意的J在（1,n)整数，下列联立的同余式有解：{xj≡1(mod mj){xj≡0(mod mi) i不等于j令x为从1到najxj的和，则x适合下列联立同余式x≡aj（mod mj）, j=1,2,3,.....,n另：求自然数a的个位数字，就是求a与哪一个一位数对于模10同余