剩余类与完全剩余系课件

初等数论课件初等数论课件-同余式同余式（导学设计）导学设计）灵台工作站灵台工作站张玉凤张玉凤初等数论课件-同余式（导学设计）前言前言本课件是以初等数论同余式内容的PPT课件为切入口，介绍了初等数论课程教学中，不断运用多媒体课件进行教学内容，体现了课件建设的好处以及其对数学思想的研究思维的拓展与教学的关系。前言(一一)课程的作用与任务课程的作用与任务“初等数论”课程是中央广播电视大学数学与应用数学专业的一门限选课。数学与应用数学专业的学生学习一些初等数论的基础知识可以加深对数的性质的了解与认识，便于理解和学习与其相关的一些课程。通过这门课的学习，使学生获得关于同余式的相关基本知识与性质，掌握数论中的最基本的理论和常用的方法，加强他们的理解和解决数学问题的能力，为今后的学习奠定必要的基础。(一)课程的作用与任务“初等数论”课程是中央广播电视大学数学（二）课程的目的（二）课程的目的通过本课程的学习，使学生加深对整数的性质的了解，更深入地理解初等数论与其它邻近学科的关系。通过本课程的学习，使学生较为系统的获得利用数学工具建立数学模型的基本知识、基本技能与常用技巧，培养学生的抽象概括问题的能力，用数学方法和思想进行综合应用与分析问题的能力，并着力导引实践理论实践的认识过程，培养学生辩证唯物主义的世界观。初等数论同余是研究整数性质的一门学科的重要部分，历史上遗留下来没有解决的大多数数论难题其问题本身容易搞懂，容易引起人的兴趣，但是解决它们却非常困难。本课程的目的是简单介绍在初等数论同余研究中经常用到的若干基础知识、基本概念、方法和技巧。（二）课程的目的通过本课程的学习，使学生加深对整数的性质的了（三）教学要求（三）教学要求（1）教学总要求有关定义、定理、性质等概念的内容按“知道、了解和理解”三个层次要求；有关计算、解法、公式和法则等方法的内容按“会、掌握、熟练掌握”三个层次要求。（2）教学基本要求1、理解整数同余的概念及同余的基本性质，熟练掌握整数具有素因子的条件，会利用同余简单验证整数乘积运算的结果。2、理解剩余系、完全剩余系的概念，熟练掌握判断剩余系的方法，理解欧拉函数的定义及性质。3、了解欧拉定理、Fermat小定理，掌握循环小数的判定方法。4、理解同余式的定义，掌握一次同余式有解的条件，熟练掌握求解一次同余式。5、理解中国剩余定理，掌握中国剩余定理的简单应用，掌握求解简单同余式方程组的方法。6、了解高次同余式解的个数的判断方法，知道解高次同余式的方法，了解模整数同余式与模素数同余式的关系，掌握求简单的（3、4次）同余式解的方法。7、了解素数模同余式的次数化简、Wilson定理，了解同余式的次数与解的个数的关系，知道n次同余式有n个解的条件。（三）教学要求（1）教学总要求（四）教学内容、重点及难点：四）教学内容、重点及难点：（1）教学内容：）教学内容：2.1.1同余的定义和基本性质2.1.2同余式性质2.2.1剩余类与剩余系2.2.2剩余类性质2.2.3剩余系及性质2.3.1欧拉定理2.3.2费马定理3.1一次同余方程3.2一次同余方程组 （2）重点及难点）重点及难点重点：剩余系的判定，欧拉函数的定义及性质，中国剩余定理，求解三次以下的同余式。难点：剩余系的判定，中国剩余定理，模整数同余式与模素数同余式的关系。（四）教学内容、重点及难点：（1）教学内容：2.1.1同余式定义同余式定义同余定义：若两个整数a、b被自然数m除有相同的余数，那么称a、b对于模m同余，用式子表示为：ab（modm）.（*）上式可读作：a同余于b，模m。同余式（*）意味着（我们假设ab）：a-b=mk，k是整数，即m（a-b）.例如：15365（mod7），因为365-15=350=750。5620（mod9），因为56-20=3694。900（mod10），因为90-090=109。由例以上3例我们得到启发，a可被m整除，可用同余式表示为：a0（modm）。例如，表示a是一个偶数，可以写a0（mod2）表示b是一个奇数，可以写b1（mod2）补充定义：若m（a-b），就说a、b对模m不同余，用式子表示是：ab（modm）我们书写同余式的方式，使我们想起等式，而事实上，同余式与等式在其性质上相似.同余式有如下一些性质（其中a、b、c、d是整数，而m是自然数）。2.1.1同余式定义同余定义：若两个整数a、b被自然数m除有2.1.2同余式性质同余式性质性质1：aa（modm），（反身性）这个性质很显然.因为a-a=0=m0。性质2：若ab（modm），那么ba（modm），（对称性）。性质3：若ab（modm），bc（modm），那么ac（modm），（传递性）。性质4：若ab（modm），cd（modm），那么acbd（modm），（可加减性）。性质5：若ab（modm），cd（modm），那么acbd（modm）（可乘性）。性质6：若ab（modm），那么anbn（modm），（其中n为自然数）。性质7：若acbc（modm），（c，m）=1，那么ab（modm），（记号（c，m）表示c与m的最大公约数）。注意同余式性质7的条件（c，m）1，否则像普通等式一样，两边约去，就是错的。例如610（mod4），而35（mod4），因为（2，4）1。请你自己举些例子验证上面的性质。同余是研究自然数的性质的基本概念，是可除性的符号语言。2.1.2同余式性质性质1：aa（modm），（反身性）例题解析（例题解析（1）例1判定288和214对于模37是否同余，74与20呢？解：288-214=74=372。288214（mod37）。74-20=54，而3754，7420（mod37）。例2求乘积4188141616除以13所得的余数。分析若先求乘积，再求余数，计算量太大.利用同余的性质可以使“大数化小”，减少计算量。解：4182（mod13），8148（mod13），16164（mod13），根据同余的性质5可得：41881416162846412（mod13）。答：乘积4188141616除以13余数是12。例题解析（1）例1判定288和214对于模37是否同余，7例题解析（2）例3求14389除以7的余数。分析同余的性质能使“大数化小”，凡求大数的余数问题首先考虑用同余的性质化大为小.这道题先把底数在同余意义下变小，然后从低次幂入手，重复平方，找找有什么规律。解法1：1433（mod7）14389389（mod7）8964+16+8+1而322（mod7），344（mod7），38162（mod7），3164（mod7），332162（mod7），3644（mod7）。38936431638344235（mod7），143895（mod7）。答：14389除以7的余数是5。解法2：证得14389389（mod7）后，363234241（mod7），384（36）141（mod7）。3893843431435（mod7）。143895（mod7）。例题解析（2）例3求14389除以7的余数。例题解析（3）例4四盏灯如图所示组成舞台彩灯，且每30秒钟灯的颜色改变一次，第一次上下两灯互换颜色，第二次左右两灯互换颜色，第三次又上下两灯互换颜色，这样一直进行下去.请问开灯1小时四盏灯的颜色如何排列？分析与解答经观察试验我们可以发现，每经过4次互换，四盏灯的颜色排列重复一次，而1小时=60分钟=12030秒，所以这道题实质是求120除以4的余数，因为1200（mod4），所以开灯1小时四盏灯的颜色排列刚好同一开始一样。例题解析（3）例4四盏灯如图所示组成舞台彩灯，且每30秒钟例题解析（4）例7求自然数210031014102的个位数字。分析求自然数的个位数字即是求这个自然数除以10的余数问题。解：210024256256（mod10），3101342531125313（mod10），4102（22）10042666（mod10），2100310141026365（mod10），即自然数210031014102的个位数字是5.例题解析（4）例7求自然数210031014102的个2.2.1剩余类与剩余系剩余类与剩余系定义：定义：定义：一个整数被正整数n除后，余数有n种情形：0，1，2，3，n-1，它们彼此对模n不同余。这表明，每个整数恰与这n个整数中某一个对模n同余。这样一来，按模n是否同余对整数集进行分类，可以将整数集分成n个两两不相交的子集。我们把（所有）对模n同余的整数构成的一个集合叫做模n的一个剩余类。确切地说，若x是一个给定的正整数,则全体整数可以分成n个集，记作x0,x1,xi.,xn-1,其中i=0,1,n-1xi是由一切形如axi(a=0,1,2,)的整数所组成的集2.2.1剩余类与剩余系剩余类与剩余系定义：2.2.2剩余类性质剩余类的性质剩余类的性质每一个整数必包含在而且仅包含在上述一个集合里。两个整数同在一个集合的充分必要条件是它们对模m同余。剩余类与完全剩余系剩余类与完全剩余系由此可引出抽象代数中重要的概念，如群论中的陪集，环论中的剩等。任取m，这m个数a0,a1,a2,am-1称为模m的一个完全剩余系。最常用的完全剩余系是0，1,m-1。如果(,)1，是任给的整数，,-1是模的一个完全剩余系，那么,+,+,-1+也是模的一个完全剩余系。但是,当0(mod2)时，如果，,-1和,-1分别是模的一个完全剩余系，那么+,+,-1+-1就不是模的一个完全剩余系。1948年，S.乔拉等人证明了:设2,如果,-1和,-1分别是模的一个完全剩余系,那么，,-1-1不是模的一个完全剩余系。2.2.2剩余类性质剩余类的性质2.2.3剩余系及性质（剩余系及性质（1）定义：所谓“剩余系”，就是指对于某一个特定的正整数n，一个整数集中的数模n所得的余数域。如果一个剩余系中包含了这个正整数所有可能的余数（一般地，对于任意正整数n，有n个余数：0,1,2,.,n-1），那么就被称为是模n的一个完全剩余系。剩余系剩余系:设模为设模为m,则根据余数可将所有的整数分成则根据余数可将所有的整数分成m类，分别记成类，分别记成0,1,2,m-1，这这m个数个数0,1,2,m-1称为一个完全剩余系，称为一个完全剩余系，每个数称为相应类的代表元。每个数称为相应类的代表元。当当m=10则则,0,1,2,3,4,5,6,7,8,9 最小非负完全最小非负完全 -5,-4,-3,-2,-1,0,1,2,3,4 绝对值最小绝对值最小 -4,-3,-2,-1,0,1,2,3,4,5 绝对值最小绝对值最小 1,2,3,4,5,6,7,8,9,10 2.2.3剩余系及性质（1）2.2.3剩余系及性质（剩余系及性质（2）当当m=5时则时则0,1,2,3,4 1,2,3,4,5 -2,-1,0,1,2 m为奇数为奇数-m/2,0,m/2 绝对值最小绝对值最小 m为偶数为偶数-m/2,0,.(m/2)-1 右端少右端少1个个 -m/2+1,0,m/2 左端少左端少1个个 简化剩余系简化剩余系:在每个剩余类选取至在每个剩余类选取至1个与个与m互素代表元构成简化剩余系。互素代表元构成简化剩余系。当当m=10则则,10,1,2,3,4,5,6,7,8,9 完全剩余系完全剩余系 1,3,7,9是简化剩余系是简化剩余系(?,10)=1 当素数当素数5的的0,1,2,3,4完全剩余系完全剩余系,其简化剩余系其简化剩余系 1,2,3,4除去余除去余0(正好是倍数正好是倍数)外，其它都互素。外，其它都互素。f(m)=欧拉函数欧拉函数=|t|0t60，所以，274604=34，就是所求的数。例2：有一个年级的同学，每9人一排多5人，每7人一排多1人，每5人一排多2人，问这个年级至少有多少人？（幸福123老师问的题目）题中9、7、5三个数两两互质。则7，5=35；9，5=45；9，7=63；9，7，5=315。为了使35被9除余1，用358=280；使45被7除余1，用455=225；使63被5除余1，用632=126。然后，280522511262=1877，因为，1877315，所以，18773155=302，就是所求的数例题例：一个数被3除余1，被4除余2，被5除余4，这个数最小2.3.1欧拉定理（欧拉定理（1）定理内容在数论中，欧拉定理（也称费马-欧拉定理）是一个关于同余的性质。欧拉定理表明，若n,a为正整数，且n,a互素，(a,n)=1，则a(n)1(modn)证明：首先证明下面这个命题：对于集合Zn=x1,x2,.,x(n),其中xi(i=1,2,(n)是不大于n且与n互素的数，即n的一个化简剩余系，或称简系，或称缩系)，考虑集合S=a*x1(modn),a*x2(modn),.,a*x(n)(modn)则S=Zn1)由于a,n互质，xi也与n互质，则a*xi也一定于n互质，因此任意xi，a*xi(modn)必然是Zn的一个元素2)对于Zn中两个元素xi和xj，如果xixj则a*xi(modn)a*xj(modn)，这个由a、n互质和消去律可以得出。所以，很明显，S=Zn2.3.1欧拉定理（1）2.3.1欧拉定理（欧拉定理（2）既然这样，那么（a*x1a*x2.a*x(n)）(modn)=（a*x1(modn)a*x2(modn).a*x(n)(modn)）(modn)=（x1x2.x(n)）(modn)考虑上面等式左边和右边左边等于(a*（x1x2.x(n)）)(modn)右边等于x1x2.x(n)）(modn)而x1x2.x(n)(modn)和n互质根据消去律，可以从等式两边约去，就得到：a(n)1(modn)推论：对于互质的数a、n，满足a(n)+1)a(modn)2.3.1欧拉定理（2）2.3.2费马定理a是不能被质数p整除的正整数，则有a(p-1)1(modp)证明这个定理非常简单，由于(p)=p-1，代入欧拉定理即可证明。同样有推论：对于不能被质数p整除的正整数a，有apa(modp当整数n2时，关于x,y,z的不定方程xn+yn=zn.的整数解都是平凡解，即当n是偶数时：(0,m,m)或(m,0,m)当n是奇数时：(0,m,m)或(m,0,m)或(m,-m,0)2.3.2费马定理a是不能被质数p整除的正整数，则有a(p费马大定理费马大定理：（：（1）设m,n属于非负整数，x，y，z是正整数。j表示“奇数”，k=2（m+1）j表示“偶数”。按奇数与偶数的加法形式讨论费马方程：1）偶数+偶数：k1n+k2n=k3n2n2m1nj1n+2n2m2nj2n=2n2m3nj3n2m1nj1n+2m2nj2n=2m3nj3n等式两边同时除以min(2m1n，2m2n，2m3n)，又分七种情况：A)m1=m2=m3得：j1n+j2n=j3n，偶数=奇数，产生矛盾。B)仅m1=m2j1n+j2n=2(m3-m1)nj3n，令m4=m3-m1若m40j1n+j2n=j3/2(-m4)n，j3/2(-m4)n为小数，j1n+j2n为整数，产生矛盾。可见，m40，j1n+j2n=j3n2(m4)n，n2若j3是j1n与j2n的公因数j1=j2=j3则有j4n+j5n=2(m4)n待证明2(m4)n不是j1n与j2n的公因数j1n/2(m4)n+j2n/2(m4)n=j3n费马大定理：（1）费马大定理费马大定理（2）若j1=j2则有2j1n/2(m4)n=j3n奇数/偶数=奇数，产生矛盾，j1不等于j2奇数/2n，为末尾为5的小数若要j1n/2(m4)n+j2n/2(m4)n等于整数，j1n/2(m4)n与j2n/2(m4)n的小数位数要相同j1/2(m4)与j2/2(m4)的小数位数也要相同通过计算观察，j1n/2(m4)n+j2n/2(m4)n要等于整数只能等于奇数，推出j3=奇数j1n/2(m4)n+j2n/2(m4)n=奇数j1n/2n+j2n/2n=奇数乘2(m4-1)n奇数乘2(m4-1)n不等于奇数，产生矛盾，可见，m1m3时，也不成立。所以，仅m1=m2，j1n+j2n=j3n2(m4)n不成立。同理:j4n+j5n=2(m4)n不成立。费马大定理（2）若j1=j2费马大定理费马大定理（3）C)再来看，仅m1=m3j1n+2（m2-m1）nj2n=j3n，令m4=m2-m1若m40j1n+j2n/2（-m4）n=j3n，j2n/2（-m4）n=j3n-j1n，j2n/2（-m4）n为小数，j3n-j1n为整数，产生矛盾，可见，m40则j3n-j1n=j2n2m4n若j2是j1n与j3n的公因数则j5n-j4n=2m4n待证明2(m4)n不是j3n与j1n的公因数j3n/2m4n-j1n/2m4n=j2n若j3=j1则0=j2n，产生矛盾，j1不等于j3j3n/2m4n-j1n/2m4n=j2n奇数/2n，为末尾为5的小数通过计算观察，j3n/2m4n-j1n/2m4n不等于整数，可见，m40时，不成立。所以，仅m1=m3时，j1n+j2n=j3n2(m4)n不成立。费马大定理（3）费马大定理费马大定理（4）D)仅m2=m3，同上，不成立。E)min(m1，m2，m3)仅为m1，m2，m3中的一个：得：j1n+2（m2-m1）nj2n=2(m3-m1)nj3n奇数=偶数，产生矛盾。F)2（m1-m2）nj1n+j2n=2(m3-m2)nj3n奇数=偶数，产生矛盾。G)2(m1-m3)nj1n+2(m2-m3)nj2n=j3n偶数=奇数，产生矛盾。所以：按奇数与偶数的加法形式讨论费马方程，偶数+偶数，不成立。2）奇数+奇数：j1n+j2n=knj1n+j2n=2（m+1)nj3n因为j1n+j2n=j3n2(m4)n不成立，所以：j1n+j2n=2（m+1)nj3n不成立。3)奇数+偶数：j1n+kn=j2nj2n-j1n=knj2nj1n=2n2mnj3n，因为：j3n-j1n=j2n2m4n不成立。所以：j2nj1n=2n2mnj3n不成立。所以：由1）2）3）可知，n2，“费马大定理”在正整数范围内成立。同理：应由1）2）3）可证，n2，“费马大定理”在整数范围内成立。费马大定理（4）费马大定理费马大定理（4）D)仅m2=m3，同上，不成立。E)min(m1，m2，m3)仅为m1，m2，m3中的一个：得：j1n+2（m2-m1）nj2n=2(m3-m1)nj3n奇数=偶数，产生矛盾。F)2（m1-m2）nj1n+j2n=2(m3-m2)nj3n奇数=偶数，产生矛盾。G)2(m1-m3)nj1n+2(m2-m3)nj2n=j3n偶数=奇数，产生矛盾。所以：按奇数与偶数的加法形式讨论费马方程，偶数+偶数，不成立。2）奇数+奇数：j1n+j2n=knj1n+j2n=2（m+1)nj3n因为j1n+j2n=j3n2(m4)n不成立，所以：j1n+j2n=2（m+1)nj3n不成立。3)奇数+偶数：j1n+kn=j2nj2n-j1n=knj2nj1n=2n2mnj3n，因为：j3n-j1n=j2n2m4n不成立。所以：j2nj1n=2n2mnj3n不成立。所以：由1）2）3）可知，n2，“费马大定理”在正整数范围内成立。同理：应由1）2）3）可证，n2，“费马大定理”在整数范围内成立。费马大定理（4）D)仅m2=m3，同上，不成立。2.4循环小数循环小数定义：循环小数英文名：circulating decimal两数相除，如果得不到整数商，会有两种情况：一种，得到有限两数相除，如果得不到整数商，会有两种情况：一种，得到有限小数。一种，得到无限小数。小数。一种，得到无限小数。从小数点后某一位开始不断地重复出现前一个或一节数字的十进制无限小数，叫做循环小数，如2.1666，35.232323等，被重复的一个或一节数码称为循环节。循环小数的缩写法是将第一个循环节以后的数码全部略去，而在第一个循环节首末两位上方各添一个小点。例如：0.34103103103缩写为0.34103（读作“零点三四一零三，一零三循环”）循环小数可以利用等比数列求和（附链接：等比数列）法化为分数。例如图中的化法。所以在数的分类中，循环小数属于有理数。2.4循环小数定义：循环小数英文名：circulating循环小数例题（循环小数例题（1）循环小数的问题中，最著名的是0.999是否等于1的问题代数方法为：证明:假设X=0.999.10X=9.999.0.999.即9x=9x=1以上的推理过程都是比较严密的，并不是所谓0.3=1/3而0.91（这个才是最高级的证明，大家都要学会这种紧扣定义的证明方法，而不是这个看似严谨，其实缺乏严谨的证明）。在我们所使用的数学中，0.9（9循环）=1。lichangbai1947评论：这个证明有问题。因为没有注意无穷的复杂性。其实上面的证明有两个结果，一个是：x=1即上面已经得出的结果。但是如果从：10 x=9.99.出发，把两边同时除以10，则得到的还是x=0.999.这两个结果中应该只有一个是正确的。很显然，x=0.999.的结果比x=1的结果更可信。没有仔细考察就对无穷进行推论是不合适的。我已经证明了1不等于0.999.。利用逻辑非常容易证明0.9。请比较下面的两个式子：-1/10(n)(1)-1/10+1/10(n)(2)这两个式子显然不完全相同，有差别。所以应该只有一个是正确的，不可能两个都是正确的。稍微细心一些，就会看出（1.1）式的右侧比（1.2）式的右侧少一个1/10。所以（1.2）式肯定是正确的，而（1.1）式就不成立。但是（1.1）式的右侧就是0.9.。而认为1/10=0会导致任何数都相等循环小数例题（1）循环小数的问题中，最著名的是0.999是循环小数例题（循环小数例题（2）如果认为1/10=0（它是认为0.9=的直接推论）（3）而且认为它是严格的相等，则由于“严格地相等”可以无穷递推，即得到：21/10=0，（4）31/10=0，（5）无穷地增加下去，总有一个时刻会得到：101/10=0。（6）但是一个显然的事实是：（1.2.4）式的右侧等于1，而不是0。再同样地推下去，则任意两个数都可以相等。这显然太荒谬了。还可以利用计算的数值的结果证明。但是需要微积分。故略。可以查看李长白数学网的有关文章。以上方法严格讲都是有缺陷的以上方法严格讲都是有缺陷的,真正的方法如下真正的方法如下:依照循环小数定义:如1/3在进行除法运算的时候,在用三除的时候余下的一位为1,这样继续进行下去的时候,根据归纳可知,这个小数后面会有无数个3,而且都是三,所以1/3=0.33循环然后我们看0.99循环我们用1/1来进行计算,不同的是,我们不要一次将1除尽,我们直接退位进行计算第一步就是得0.9余0.1,这个没有问题,也不违反任何运算规则,通过这样的方式计算,可以得出1/1通过除法运算的时候可以表示为0.99循环即0.99循环等于1。证毕循环小数例题（2）如果认为循环小数例题（循环小数例题（3）没有用到极限(根本和循环小数无关的),和循环小数运算法则!只用了分数除法,和循环小数定义!注意注意：无理数的定义是无限不循环小数，由此可以判定无限不循环小数是无理数（因为定义也是判定）。循环小数化分数将纯循环小数改写成分数，分子是一个循环节的数字组成的数；分母各位数字都是9，9的个数与循环节中的数字的个数相同.例如.0.1=1/90.1234=1234/9999混循环：将混循环小数改写成分数，分子是不循环部分与第一个循环节连成的数字组成的数，减去不循环部分数字组成的数之差；分母的头几位数字是9，末几位数字是0，9的个数跟循环节的数位相同，0的个数跟不循环部分的数位相同.例如：0.1234=(1234-1)/99900.558898=(558898-55)/999900这个概念是错的有限小数的小数位数是有限的循环小数的小数位数是无限的因此，有限循环小数这个说法本身就是错误的循环小数例题（3）3、同余式方程、同余式方程3.1一次同余方程3.2一次同余方程组3、同余式方程3.1一次同余方程3.1一次同余方程一次同余方程定义：相当于把一个方程式的等号换成了同余号。也就是把实数意义上的相等，换成了同余意义上的相等，或者说等价或等效，,。只是将一种等价关系（满足自反性，对称性（互反性）及传递性），换作了另一种。上面的5y=1mod4就是一个同余方程，也就是同余式。5y=4*y+y,故5y=y.得到y=1mod4就是求解了解。和方程的求解类似。3.1一次同余方程定义：相当于把一个方程式的等号换成了同余号3.2一次同余方程组一次同余方程组同余式组：类似于方程组。多个同余式，得到的结果(解)，因为同余式的数目多，也就是加了一些约束，得到更精确显然数量上也更少的解(甚至没有解)。例如，y=1mod4.y=1mod5，得到的同余式组的解无疑是y=1mod20.两个单独的同余式，解的出现频率是4个出现1个或5个出现1个，成组后，解的数量变少了，20个才出现1个。有些同余式组是无解的。如y=1mod4；y=3mod20.可以这样理解：y=3mod20可以等效于y=3mod4且y=3mod5,而y=3mod4与y=1mod4是不同时成立的。有些单个的同余式，也可以是无解的，如4y=1mod4.（因为，对于任意y,4y=0mod4）这里还看到，有些同余式有全解(所有整数均是它的解)，上面的4y=0mod4.上面说到的是一次同余式及一次同余式组。与方程及方程组类似，也有多元的，高次的。我们一般限于在整数范围内讨论。在学习更深入的数论知识后，还可以向其它代数结构中推广。此外，不排除类似微分或偏微分方程，积分方程，级数方程进行推广和研究。我相信随着研究的深入，还会出现更多的情况。3.2一次同余方程组作业设计：（作业设计：（1）一、选择题1、整数5874192能被(B)整除.A3B3与9C9D3或92、整数637693能被(C)整除.A3B5C7D93、模5的最小非负完全剩余系是(D).A-2,-1,0,1,2B-5,-4,-3,-2,-1C1,2,3,4,5D0,1,2,3,44、如果ab(modm),c是任意整数,则（A）A、acbc(modm)B、a=bC、acTc(modm)Dab二、解同余式（组）（1）45x21(mod132).解因为(45,132)=321,所以同余式有3个解.将同余式化简为等价的同余方程15x7(mod44).我们再解不定方程：15x-44y=7,得到一解(21,7).于是定理4.1中的的X0=21.因此同余式的3个解为x21(mod132),X21+132/3(mod132)65(mod132),X21+2132/3(mod132)109(mod132)（2）12x+150(mod45)解因为(12,45)=315,所以同余式有解,而且解的个数为3.又同余式等价于4x+50(mod15),即4x+515y.我们利用解不定方程的方法得到它的一个解是(10,3),即定理4.1中的x0=10.因此同余式的3个解为x10(mod45),x10+45(mod45)25(mod45),x10+245/3(mod45)40(mod45).（3）111x75(mod321)解因为(111,321)=375,所以同余式有3个解.将同余式化简为等价的同余方程37x25(mod107).作业设计：（1）一、选择题（2）12x+150(作业设计：（作业设计：（2）)我们再解不定方程:37x+107y=25,得到一解(-8,3).于是定理4.1中的x0=-8.因此同余式的3个解为：x-8(mod321),x-8+321/3(mod321)99(mod321),x-8+2321/3(mod321)206mod321).（4）x1(mod7x2(mod8).x3(mod9)解因为(7,8,9)=1,所以可以利用定理5.1.我们先解同余式72x1(mod7),63x1(mod8),56x1(mod9),得到X1=4(mod7),X2=-1(mod8),X3=-4(mod9).于是所求的解为X=7241+63(-1)2+56(-4)3(mod494)=-510(mod494)=478(mod494).（5）x1(mod2),x2(mod5),x3(mod7),x5(mod9(参考上题）三、证明题三、证明题1、如果整数a的个位数是5,则该数是5的倍数.证明设a是一正整数,并将a写成10进位数的形式:a=an10n+an-110n-1+.a0,0ai10,因为100(mod5),所以我们得到aa0(mod5)所以整数a的个位数是5,则该数是5的倍数.作业设计：（2）)我们再解不定方程:37x+107作业设计：（作业设计：（3）2、证明当n是奇数时，有3(2n+1).证明因为2-1(mod3),所以2n+1(-1)n+1(mod3).于是,当n是奇数时,我们可以令n=2k+1.从而有2n+1(-1)2k+1+10(mod3),n即3(2n+1).3、证明相邻两个整数的立方之差不能被5整除.（11分）证明因为,所以只需证明.3n2+3n+1T(mod5)而我们知道模5的完全剩余系由-2,-1,0,1,2构成,所以这只需将n=0,1,2代入3n2+3n+1分别得值1，7，1，19，7.对于模5,3n2+3n+1的值1，7，1，19，7只与1，2，4等同余,所以3n2+3n+1T(mod5)所以相邻两个整数的立方之差不能被5整除。4、求3364的末两位数码.解原题相当于求3364模100的余数.由Euler定理知3（100）1(mod100)，故有3401（mod100），从而33643481（mod100）.故3364末两位数码为81.作业设计：（3）2、证明当n是奇数时，有3(2n初等数论同余式这部分内容抽象、不容易理解，通过多媒体课件能更形象更具体的讲解，更利于学生对新内容的接受（2）xp-1-1(x-1)(x-2)(x-(p-1)(modp)，将x=0代入上式得-1呏(-1)(p-1)!(modp),这就证明了威尔森定理。威尔森定理的逆定理也是成立的，可用反证法简单证出。用拉格朗日定理还可证明：当p5是一个素数时,则有同余。这个定理是1862年，由J.沃斯顿霍姆证明的。设(x1,x2,xn)是n元整系数多项式,p是一个奇素数,对于同余式(x1,x2,xn)呏0(modp)的解(x1,x2,xn)(0 xj0)多项式(x)=nx+1x+0,m是一个正整数且不能整除n，则f(x)（modm）(1)叫做模m的n次同余式。如果整数是（1）的解且(modm)，那么也是(1)的解，因此,(1)的不同解是指满足(1)的模m互不同余的数。对于一次同余式x b)(modm)有解的充分必要条件是(,m)b)，若有解则有(,m)个解。一次同余式组是指xb1(modm1),xb2(modm2),(2)xbk(modmk).(2),xM1M1b1M2M2b2MkMkbk(modm).在中国古代孙子算经中，对某些具体的一次同余式组已有解法，把这一解法加以推广，就是著名的孙子剩余定理：设m1,m2,mk是k个两两互素的正整数:Mm1m2.mk,MiM/mi(i1,2,3k),则同余式组(2)的解是。式中。孙子剩余定理又被称之为中国剩余定理，是数论中一个重要的定理，除了数论本身，数学的许多其他分支以及一些应用学科都要用到它。例如,设mm1m2mk，m1,m2,mk两两互素,利用孙子剩余定理可将同余式(1)的求解问题化为同余式组(x)呏0(modmi)(i1，2,k)的求解问题，于是就只需要研究(1)中m是素数方幂的情形了。又如,可将0 xm中的一切整数表示，这叫做模系数记数法,这里mm1m2mk，m1,m2,mk两两互素，而x表示x模mi的最小非负剩余。如已知x的模系数记数法，就可用孙子定理找出x。这个记数法的优点是加法和乘法无须进位，它在计算机方面有应用。素数为模的同余式关于素数为模的同余式，1770年，J.-L.拉格朗日证明了如下定理：设p是素数，那么模p的n次同余式的解数不大于n（重解也计算在内）。人们称之为拉格朗日定理。由此立即可以得威尔森定理：如果p是素数，那么(p-1)!+10(modp)。因为x-10(modp)有p-1个解1,p-1，故由拉格朗日定理可得初等数论同余式这部分内容抽象、不容易理解，通过多媒体课件能更小结：多媒体课件能更形象更具体的讲解，更利于学生对新内容的接受因为人们不光在认识世界往往是通过视觉、知觉、听觉等感觉器官对外界进行事物感受，在感觉外界事物的时候，人们更偏向于通过视觉获得外界信息。因而，在感受外界事物时，注意会受到心理特性的影响。视觉心理学认为，人通过视觉认识事物的方式并不是根据视网膜上提供的影像，而是根据思维所提供的语言形式，正由于这种原因才能让学生清晰明快直接的接受课堂内容。另外文字教材是学生获得知识和能力的重要媒体，虽然教材中对概念的叙述要直观无误，论证清楚，但是要适合成人开放教育、以业余学习为主的特点，就必须借助于课件教学，这样就能使学生更形象更具体了解课本内容，从而利于学生对新内容的接受与思维的开阔。小结：多媒体课件能更形象更具体的讲解，更利于学生对新内容的接二、课件建设与多媒体教学的关系二、课件建设与多媒体教学的关系(一一)1.课件课件（courseware）是根据教学大纲的要求，经过教学目标确定，教学内容和任务分析，教学活动结构及界面设计等环节，而加以制作的课件。它与课程内容有着直接联系。所谓多媒体课件是根据教学大纲的要求和教学的需要，经过严格的教学设计，并以多种媒体的表现方式和超文本结构制作而成的课程软件。2.课件建设的常用制作方式课件建设的常用制作方式：现在应用最广泛的多媒体课件形式是PPT（用officePowerPoint制作的幻灯片），由于它编辑、播放，各种操作简单易学，但是严格来讲并不是为制作课件而开发。功能虽然强大，但使用烦琐，难以表达教育思想。尤其是PPT容纳文字量小，不能对图片作透明处理。二、课件建设与多媒体教学的关系(一)1.课件（coursew二、课件建设与多媒体教学的关系二、课件建设与多媒体教学的关系(二二)3.课件评价标准课件评价标准有价值的课件必须具备以下要素，也就是优秀课件的评价标准：（1）、教学设计精心的设计是优秀结果的保证，没有正确完整的设计后续一切都象散沙一样无法凝聚，缺少灵魂。（2）、生动性把教学内容的重点和多媒体手段充分地结合起来，带给学生最易理解的方式。（3）、交互性让学习者参与到学习过程中，充分调动学习积极性，加深理解和记忆。（4）、方便性好的导航可以扫除非教学因素的学习障碍，不让学习者迷失在技术障碍中，始终能便捷地访问。(5）、自由性自由学习是课件的一大特色，学员任何时候都清楚地知道自己所处位置和进度，控制自己的学习进程。(6)、个性化学习提供多种模式和习惯的选择，让每门课给每个学习者带来最贴心的学习感受。(7)、评估检查学习效果是必须的手段，没有评估可能会很容易放弃学习。更重要的是，一个优秀的课件，采用的形式其产生的效果应该是高于传统教材的，也就是说，如果连传统教材的效果都没有达到，那也就没有必要做成课件了。优秀的课件必须充分体现教授的教学思想，否则不仅普通教师和教学名师没有区别，而且教师和放映员没有区别了。二、课件建设与多媒体教学的关系(二)3.课件评价标准三、课件的建设使内容系统化从而有利于数学思想的研究与思维的拓展1.分步思想方法体现分步思想方法体现2.对比的思想方法的体现对比的思想方法的体现3.整体化思想方法体现整体化思想方法体现三、课件的建设使内容系统化从而有利于数学思想的研1.分步思想方法体现分步思想方法体现Fermat小定理的思想方法：Fermat小定理在数论和密码学中起着非常重要的作用。这里我们介绍这一定理的两种形式。1.第一种形式第一种形式认为如果p是一个素数，且a是一个不能被p整除的整数，那么。2.第二种形式第二种形式取消了对a的限制条件。如果p是素数，a为整数，那么。3.应用虽然我们在本章后面只了解了该定理在某些方面的应用，但该定理在解决其他一些问题时还是非常有用的。4.求幂Fermat小定理有时在快速求幂时也是很有用的，下面就是几个示例。1.分步思想方法体现Fermat小定理的思想方法：Ferma例题例题例9.12求mod11的结果。解答已知mod11=1。这是Fermat小定理的第一种形式，其中p=11。例9.13求mod11的结果。解答这里幂数(12)和模(11)是不同的。通过代换，这个问题可以运用Fermat小定理解决。乘法逆Fermat小定理的一个很有趣的应用就是，如果模是素数，那么可以用来快速求出某些乘法逆。如果p是素数，且a是一个整数，使得p不能整除，那么。如果用a同乘以等式的两边，并且运用Fermat小定理的第一种形式，我们很容易证明这一结论：这一应用淘汰了用扩展Euclidean算法求乘法逆的方法。例题例题例题例9.14答案是不用扩展Euclidean算法，我们也可以求出一个乘法逆模一个素数。Fermat定理的应用定理的应用：前主要应用在信息安全上。根据Euler-Fermat定理得到的RSA（公开密匙）体制是较为安全的加密方法。利用它可以实现数据加密、数字签名。RSA原理如下：设N=P1*P2.（P1、P2是两个非常大的素数，通常是一百多位).令e1*e2=1(mod(P1-1)*(P2-2).假设有需要加密的数据C(叫做原文)，作变换令B=Ce1(modN)，则将数据C加密成为密文B.这里把e1、e2叫做密匙.当接收数据的一方接到密文C后，根据Euler-Fermat定理、及预先知道的e2就可以解出原文C=Be2(modN).从上面可以知道，当第三方截获加密规则并到到密文B，也就是知道N、B、e1（这就是公开密匙的内涵），欲解出原文C，还必须知道e2，但要知道e2就必须解出P1-1、P2-1，也就是要知道P1及P2.这就牵涉到大数的分解问题，一般来说，按照现在的数学理论及其先进的计算工具，要分解这样的大数没有十来年是办不到的！这就是该算法的一种相对保密性.当然，不排除数学理论会有突飞猛进的时候，那时，这样的算法是否安全，值得商榷.但是这个理论却给出了一种加密的可行之道，就是加密函数的反函数非常不容易求出，所以现在在此原理上已经有另外的加密算法了.设传送密文的为甲方，接收密文的为乙方，那么甲、乙都有自己的一对密匙，甲传送时，按乙的密匙传送，并把自己的签名用自己的密匙加密，那么，只有拥有乙密匙的人才可以解读密文，并且从签名的加密可以知道，这个密文只有拥有甲的密匙的人才能发送.故对数据起到最大的保密效果.例题例9.14例题例题例9.15求mod35的结果。解答我们有mod35=mod35=1。例9.16求mod77的结果。解答如果在第二种形式中使k=1，我们有mod77=(20mod77)(mod77)mod77=(20)(20)mod77=15。乘法逆Euler定理可以用来求乘法逆模一个素数，也可以用来求一个乘法逆模一个复合数。如果n和a互素，那么。如果我们用a同乘以等式的两边，就可以很容易地证明：例9.17如果我们知道复合数的因数分解，不运用扩展Euclidean算法，也可以算出乘法逆模一个复合数的答案。例题例9.152.对比的思想方法的体现对比的思想方法的体现Euler定理可以认为是对Fermat小定理的一般化。在Fermat小定理中模是素数，Euler定理中模是整数。我们介绍该定理的两种形式。1.第一种形式Euler定理的第一种形式与Fermat小定理的第一种形式相似。如果a与n互素，那么。2.第二种形式Euler定理的第二种形式(我们这样称呼是因为没有更合适的词了)与Fermat小定理的第二种形式相似，它取消了a与n互素这个条件。如果且k为整数，那么。第二种形式是基于第一种形式的，我们给出第一种形式的正式证明。因为，三种情况都有可能：(1)如果a既不是p的倍数也不是q的倍数，那么a和n互素。(2)如果a是p(a=ip)的倍数，但a不是q的倍数，(3)如果a是的倍数，但a不是p的倍数，证明与第二种情况相同，但是p和q的作用改变了。Euler定理的第二个形式被运用在第10章中介绍的RSA加密系统中。3.应用虽然我们在本章的后面只了解一些有关Euler定理的应用，但该定理对某些问题的解决还是非常有用的4.求幂Euler定理有时候对快速求出一些求幂运算的结果是非常有帮助的，下面的例子就表明了这一概念2.对比的思想方法的体现3、整体化思想方法体现、整体化思想方法体现(1)欧拉定理：在数论中，欧拉定理欧拉定理（也称费马费马-欧拉定理欧拉定理）是一个关于同余的性质。欧拉定理表明，若n,a为正整数，且n,a互素，(a,n)=1，则a(n)1(modn)证明证明首先证明下面这个命题：对于集合Zn=x1,x2,.,x(n),其中xi(i=1,2,(n)是不大于n且与n互素的数，即n的一个化简剩余系，或称简系，或称缩系)，考虑集合S=a*x1(modn),a*x2(modn),.,a*x(n)(modn)则S=Zn1)由于a,n互质，xi也与n互质，则a*xi也一定于n互质，因此任意xi，a*xi(modn)必然是Zn的一个元素2)对于Zn中两个元素xi和xj，如果xixj则a*xi(modn)a*xj(modn)，这个由a、n互质和消去律可以得出。所以，很明显，S=Zn既然这样，那么（a*x1a*x2.a*x(n)）(modn)=（a*x1(modn)a*x2(modn).a*x(n)(modn)）(modn)=（x1x2.x(n)）(modn)3、整体化思想方法体现(1)3整体化思想方法体现整体化思想方法体现(2)考虑上面等式左边和右边左边等于(a*（x1x2.x(n)）)(modn)右边等于x1x2.x(n)）(modn)而x1x2.x(n)(modn)和n互质根据消去律，可以从等式两边约去，就得到：a(n)1(modn)推论：对于互质的数a、n，满足a(n)+1)a(modn)整体化思想方法就是把单个对象始终放在整体对象构成的系统中加以考察,通过系统对象之间的整体联系或整体特征,寻求原问题的解决途径。从以上的证明过程知道,欧拉定理整体性质:“由于a,n互质，xi也与n互质，则a*xi也一定于n互质，因此任意xi，a*xi(modn)必然是Zn的一个元素，和对于Zn中两个元素xi和xj，如果xixj则a*xi(modn)a*xj(modn)，这个由a、n互质和消去律可以得出的整体性质等。3整体化思想方法体现(2)小结：（小结：（1 1）初等数论解题过程中除了以上探讨的整体化、分步、对比数学思想方法,还涉及其它的数学思想方法(如:构造思想,分类思想等)。值得注意的是,初等数论解(证)题往往是多种数学思想方法相互交织、渗透、化归的综合应用过程。初等数论中包含了丰富的数学思想方法与思维拓展,其知识结构和数学思想方法形成一个经纬交织,融会贯通的知识网络,需要我们去挖掘、揭示。因此,在初等数论的教学过程中,应充分利用教材和习题的教育功能和多媒体课件的运用,注重展示解决问题的思路、思维过程,体现解决问题策略与方法的多样性,引导沟通知识间的内在联系,突出问题的背景和思想方法的阐述,注重数学思想方法的总结、提炼,把数学知识和相关数学思想方法有机联系起来,使学生从整体上把握初等数论的理论体系,理解数学思想方法的内涵,开阔思维视野,健全认知结构。小结：（1）初等数论解题过程中除了以上探讨的整体化、分步、小结：（小结：（2 2）“初等数论”课程是实践性很强的应用类学科，而教学时数有限。因此必须通过练习来加深对所学内容的理解和掌握，达到消化、掌握所学知识的目的。因此，独立完成作业是学好本课程的重要环节。根据“初等数论”课程的特点和远距离教育的特点，整个教学计划的内容安排，以及学生主要是成人、在职、业余学习的特点，教学中要遵循由浅入深，循序渐进的原则，通俗易懂的原则进行。同时该教材与辅导教材在编排上是同步的，便于自学。主教材是课上讲授用教材，辅导教材则主要用于教师辅导及学生自学参考，内容是对主教材的内容进行解释、归纳、总结，并通过典型例题理解学习内容，提高解题能力。但不给习题解答，而是给出答案和解题提示，在此基础上，在教学中要适当扩展习题加以练习巩固。小结：（2）四、多媒体课件建设的好处四、多媒体课件建设的好处(1)1、激发学生学习兴趣 传统的教学手段枯燥无味，没有直观的形态供学生了解,有了课件教学,使古板变生动了,抽象变形象了,深奥变浅显了,沉闷变愉悦了.不但激发了学生的学习兴趣，更有利的使学生理解其意义。2、使用课件可以提高学生的兴趣使用课件能把语言文字所描绘的情境直观形象逼真的展现出来,能够吸引学生注意力，提高学习情绪,从而诱发学生学习的兴趣。3、教师观念的转变 随着电教化教学普遍进入课堂，教育工作者树立了终身教育的观念。促使教师接受继续教育，对提高教师本身的教学水平也有很大帮助，有些老师尤其是多学科老师感到课件制作压力大，可以到找一些相关的课件进行修改。随着互联网的普及，努力创造各种条件，让教师有学习、实践、创新的机会，才能让学员接受更好的教育。四、多媒体课件建设的好处(1)1、激发学生学习兴趣四、多媒体课件建设的好处四、多媒体课件建设的好处(2)4、提高教师的教学水平 课件逐渐普及后，教师以生动的语言加上有声有色的课件，使学生对知识掌握更加容易，普通提高学生家长对教师的信任。5、节约时间可在最短的时间内，让学生清晰透彻的了解所需掌握的知识，并能灵活运用四、多媒体课件建设的好处(2)课课 程程 简简 介介初等数论研究数的规律，特别是整数性质的数学分支。是数论的一个最古老的分支。它以算术方法为主要研究方法，主要内容有整数的整除理论、不定方程、同余式等。古希腊毕达哥拉斯是初等数论的先驱。他与他的学派致力于一些特殊整数（如亲和数、完全数、多边形数）及特殊不定方程的研究。公元前4世纪，欧几里德的几何原本通过102个命题，初步建立了整数的整除理论。他关于“素数有无穷多个”的证明，被认为是数学证明的典范。初等数论已经有2000年的历史，2000年来，数论学的一个最重要的任务，就是寻找一个可以表示所有素数的统一公式，或者称为素数普遍公式，为此，人类耗费了巨大的心血。公元3世纪，丢番图研究了若干不定方程，并分别设计巧妙解法，故后人称不定方程为丢番图方程。17世纪以来，P.de费马、L.欧拉、C.F.高斯等人的工作大大丰富和发展了初等数论的内容。中国古代对初等数论的研究有着光辉的成就，周髀算经、孙子算经、张邱建算经、数书九章等古文献上都有记载。孙子定理比欧洲早500年，西方常称此定理为中国剩余定理，秦九韶的大衍求一术也驰名世界。初等数论不仅是研究纯数学的基础，也是许多学科的重要工具。它的应用是多方面的，如计算机科学、组合数学、密码学、信息论等。如公开密钥体制的提出是数论在密码学中的重要应用。初等数论就是用初等、朴素的方法去研究数论。另外还有解析数论（用解析的方法研究数论。）、代数数论（用代数结构的方法研究数论）。课程简介勤奋好学精益求精 剩余类与完全剩余系课件结束结束诚请大家提出宝贵意见！