计算数论和初等数论的区别

您好，初等数学研究是初等数论。初等数论就是用初等数学的方法来研究整数的整除、不定方程式、同余式等方面问题的数论分支。其内容包括辗转相除法、因数、倍数、公因数、公倍数、最大公因数、最小公倍数、素数、合数。素数个数是无限的，算数基本定理，二次剩余，完全数等。数论又称“整数论”。是研究数的性质，特别是整数性质的一门学科，它的主要分支有初等数论、代数数论、刁番都逼近论、数的几何、解析数论等。

初等数论是研究数的规律，特别是整数性质的数学分支。它是数论的一个最古老的分支。它以算术方法为主要研究方法，主要内容有整数的整除理论、同余理论、连分数理论和某些特殊不定方程。 换言之，初等数论就是用初等、朴素的方法去研究数论。另外还有解析数论（用解析的方法研究数论）、代数数论（用代数结构的方法研究数论）。初等数论有以下几部分内容：1.整除理论。引入整除、因数、倍数、质数与合数等基本概念。这一理论的主要成果有：唯一分解定理、裴蜀定理、欧几里德的辗转相除法、算术基本定理、素数个数无限证明。2.同余理论。主要出自于高斯的《算术研究》内容。定义了同余、原根、指数、平方剩余、同余方程等概念。主要成果：二次互反律、欧拉定理、费马小定理、威尔逊定理、孙子定理（即中国剩余定理）等等。3.连分数理论。引入了连分数概念和算法等等。特别是研究了整数平方根的连分数展开。主要成果：循环连分数展开、最佳逼近问题、佩尔方程求解。4.不定方程。主要研究了低次代数曲线对应的不定方程，比如勾股方程的商高定理、佩尔方程的连分数求解。也包括了四次费马方程的求解问题等等。5.数论函数。比如欧拉函数、莫比乌斯变换等等。6.高斯函数。初等数论是一个理论层次第一个层次叫做数学概念，是反映对象的本质属性的思维形式。人类在认识过程中，从感性认识上升到理性认识，把所感知的事物的共同本质特点抽象出来，加以概括，就成为概念。表达概念的语言形式是词或词组。科学概念，特别是数学概念要求更加严格，至少必须具备三个条件：专一性，精确性，可以检验。例如：”孪生素数“就是一个数学概念。第二个层次叫做数学命题，数学命题是对一系列数学概念之间的关系作出判断的句子。一个命题要么真，要么不真（这由逻辑中的排中律保证）。真命题包含定理，引理，推论，事实等。命题既可以是存在性命题（表述为”存在......."），也可以是全称命题（表述为“对于一切....."）。　　第三个层次叫做数学理论，把方法，公式，公理，定理，原理，组合成为一个体系叫做数学理论。例如“初等数论”，由公理（例如等量公理），定理（例如费马小定理），原理（例如抽屉原理，一一对应原理），公式等组成。　　在数学证明时，全称命题常常不能通过枚举法来判断真伪，这是因为数学有时面对的是无穷多个对象，永远不可能一一枚举出每一种情况。不完全归纳法在数学中是不可行的，数学只承认演绎逻辑（数学归纳法，超限归纳法等均属于演绎逻辑）。

初等数论不怎么需要高中知识，初等数论只要中学的知识作预备知识。学习解析数论和代数数论之前，你需要学完数学系本科到研究生的大部分专业课。代数数论的话，可能需要 本科的高等代数、抽象代数，研究生的交换代数，以及拓扑、代数拓扑、代数几何方向的内容，这些掌握之后就能开始看懂。初等数论是研究数的规律，特别是整数性质的数学分支。它是数论的一个最古老的分支。它以算术方法为主要研究方法，主要内容有整数的整除理论、同余理论、连分数理论和某些特殊不定方程。换言之，初等数论就是用初等、朴素的方法去研究数论。另外还有解析数论（用解析的方法研究数论）、代数数论（用代数结构的方法研究数论）。初等数论有以下几部分内容：1、整除理论。引入整除、因数、倍数、质数与合数等基本概念。这一理论的主要成果有：唯一分解定理、裴蜀定理、欧几里德的辗转相除法、算术基本定理、素数个数无限证明。2、同余理论。主要出自于高斯的《算术研究》内容。定义了同余、原根、指数、平方剩余、同余方程等概念。主要成果：二次互反律、欧拉定理、费马小定理、威尔逊定理、孙子定理（即中国剩余定理）等等。3、连分数理论。引入了连分数概念和算法等等。特别是研究了整数平方根的连分数展开。主要成果：循环连分数展开、最佳逼近问题、佩尔方程求解。4、不定方程。主要研究了低次代数曲线对应的不定方程，比如勾股方程的商高定理、佩尔方程的连分数求解。也包括了四次费马方程的求解问题等等。5、数论函数。比如欧拉函数、莫比乌斯变换等等。6、高斯函数。

包括：初等数论、解析数论、代数数论、几何数论、计算数论、超越数论、组合数论、算术代数几何。1、初等数论初等数论主要就是研究整数环的整除理论及同余理论。此外它也包括了连分数理论和少许不定方程的问题。本质上说，初等数论的研究手段局限在整除性质上。初等数论中经典的结论包括算术基本定理、欧几里得的质数无限证明、中国剩余定理、欧拉定理（其特例是费马小定理）、高斯的二次互反律， 勾股方程的商高定理、佩尔方程的连分数求解法等等。2、解析数论借助微积分及复分析（即复变函数）来研究关于整数的问题，主要又可以分为乘性数论与加性数论两类。乘性数论藉由研究积性生成函数的性质来探讨素数分布的问题，其中质数定理与狄利克雷定理为这个领域中最著名的古典成果。加性数论则是研究整数的加法分解之可能性与表示的问题，华林问题是该领域最著名的课题。解析数论的创立当归功于黎曼。他发现了黎曼zeta函数之解析性质与数论中的素数分布问题存在深刻联系。确切的说， 黎曼ζ函数的非平凡零点的分布情况决定了素数的很多性质。黎曼猜测， 那些零点都落在复平面上实部为1/2的直线上。这就是著名的黎曼假设—千禧年大奖难题之一。值得注意的是， 欧拉实际上在处理素数无限问题时也用到了解析方法。解析数论方法除了圆法、筛法等等之外， 也包括和椭圆曲线相关的模形式理论等等。此后又发展到自守形式理论，从而和表示论联系起来。3、代数数论代数数论，将整数环的数论性质研究扩展到了更一般的整环上，特别是代数数域。一个主要课题就是关于代数整数的研究，目标是为了更一般地解决不定方程求解的问题。其中一个主要的历史动力来自于寻找费马大定理的证明。代数数论更倾向于从代数结构角度去研究各类整环的性质， 比如在给定整环上是否存在算术基本定理等等。这个领域与代数几何之间的关联尤其紧密， 它实际上也构成了交换代数理论的一部分。它也包括了其他深刻内容，比如表示论、p-adic理论等等。4、几何数论主要在于通过几何观点研究整数（在此即格点， 也称整点）的分布情形。最著名的定理为Minkowski定理。这门理论也是有闵科夫斯基所创。对于研究二次型理论有着重要作用。5、计算数论借助电脑的算法帮助研究数论的问题，例如素数测试和因数分解等和密码学息息相关的课题。

你好，初等数论名词一般是数论的其中一个分支。而对于初等数论名词是以整数的整除性为中心的，其中包括整除性，不定方程，同余式，连分数，素数其实就是指整数还有分布及数论函数等关于数学理论的内容。关于初等数论，其实它是数论中某些问题的研究以此来促使形成新的数学分支。就像那些对不定方程和高次互反律的研究，促进了代数数论和类域论的形成和发展。不过随着时间的发展，初等数论在计算机科学，组合数学，代数编码和密码学还有计算方法以及那些信号的数字处理等领域内得到广泛的应用。

1.求有关初等数论的所有知识``` 初等数论 研究数的规律，特别是整数性质的数学分支。 是数论的一个最古老的分支。它以算术方法为主要研究方法，主要内容有整数的整除理论、不定方程、同余式等。 古希腊毕达哥拉斯是初等数论的先驱。他与他的学派致力于一些特殊整数（如亲和数、完全数、多边形数）及特殊不定方程的研究。 公元前4世纪，欧几里德的《几何原本》通过102个命题，初步建立了整数的整除理论。他关于“素数有无穷多个”的证明，被认为是数学证明的典范。公元3世纪，丢番图研究了若干不定方程，并分别设计巧妙解法，故后人称不定方程为丢番图方程。17世纪以来，P.de费马、L.欧拉、C.F.高斯 等人的工作大大丰富和发展了初等数论的内容。 中国古代对初等数论的研究有着光辉的成就，《周髀算经》、《孙子算经》、《张邱建算经》、《数书九章》等古文献上都有记载。孙子定理比欧洲早500年， 西方常称此定理为中国剩余定理，秦九韶的大衍求一术也驰名世界。 初等数论不仅是研究纯数学的基础，也是许多学科的重要工具。它的应用是多方面的，如计算机科学、组合数学、密码学、信息论等。 如公开密钥体制的提出是数论在密码学中的重要应用。 初等数论就是用初等、朴素的方法去研究数论。 另外还有解析数论（用解析的方法研究数论。）、代数数论（用代数结构的方法研究数论）。 素数 数论刚开始的时候是用朴素的推理方法去研究整数的性质，又以素数最令人神往。古今不知道多少数学家都为了它而呕心沥血！研究素数的性质是数论中一个非常重要的方面！ 所谓素数，就是一个正整数，它除了本身和 1 以外并没有任何其他因子。 素数就好象是正整数的原子一样，著名的高斯「唯一分解定理」说，任何一个整数。可以写成一串质数相乘的积。 但是至今仍然没有一个一般的特别使用的式子可以表示所有的素数。所以数论里关于素数的两个著名猜想非常困难：1哥德巴赫猜想 ：（Goldbach Conjecture） 内容为“所有的大于2的偶数，都可以表示为两个素数” 这个问题是德国数学家哥德巴赫（C.Goldbach,1690-1764）于1742年6月7日在给大数学家欧拉的信中提出的，所以被称作哥德巴赫猜想。 同年6月30日，欧拉在回信中认为这个猜想可能是真的，但他无法证明。从此，这道数学难题引起了几乎所有数学家的注意。 哥德巴赫猜想由此成为数学皇冠上一颗可望不可即的“明珠”。“用当代语言来叙述，哥德巴赫猜想有两个内容，第一部分叫做奇数的猜想，第二部分叫做偶数的猜想。 奇数的猜想指出，任何一个大于等于7的奇数都是三个素数的和。偶数的猜想是说，大于等于4的偶数一定是两个素数的和。” （引自《哥德巴赫猜想与潘承洞》） 哥德巴赫猜想貌似简单，要证明它却着实不易，成为数学中一个著名的难题。18、19世纪，所有的数论专家对这个猜想的证明都没有作出实质性的推进，直到 20世纪才有所突破。 直接证明哥德巴赫猜想不行，人们采取了“迂回战术”，就是先考虑把偶数表为两数之和，而每一个数又是若干素数之积。如果把命题"每一个大偶数可以表示成为一个素因子个数不超过a个的数与另一个素因子不超过b个的数之和"记作"a+b"，那么哥氏猜想就是要证明"1+1"成立。 1900年，20世纪最伟大的数学家希尔伯特，在国际数学会议上把“哥德巴赫猜想”列为23个数学难题之一。此后，20世纪的数学家们在世界范围内“联手”进攻“哥德巴赫猜想”堡垒，终于取得了辉煌的成果。 到了20世纪20年代，有人开始向它靠近。1920年，挪威数学家布爵用一种古老的筛选法证明，得出了一个结论：每一个比6大的偶数都可以表示为（9+ 9）。 这种缩小包围圈的办法很管用，科学家们于是从（9十9）开始，逐步减少每个数里所含质数因子的个数，直到最后使每个数里都是一个质数为止，这样就证明了“哥德巴赫猜想”。 1920年，挪威的布朗（Brun）证明了 “9+9 ”。 1924年，德国的拉特马赫（Rademacher）证明了“7+7 ”。 1932年，英国的埃斯特曼（Estermann）证明了 “6+6 ”。 1937年，意大利的蕾西（Ricei）先后证明了“5+7 ”, “4+9 ”, “3+15 ”和“2+366 ”。 1938年，苏联的布赫 夕太勃（Byxwrao）证明了“5+5 ”。 1940年，苏联的布赫 夕太勃（Byxwrao）证明了 “4+4 ”。 1948年，匈牙利的瑞尼（Renyi）证明了“1+c ”，其中c是一很大的自然数。 1956年，中国的王元证明了 “3+4 ”。 1957年，中国的王元先后证明了 “3+3 ”和 “2+3 ”。 1962年，中国的潘承洞和苏联的巴尔巴恩（BapoaH）证明了 “1+5 ”， 中国的王元证明了“1+4 ”。 1965年，苏联的布赫 夕太勃（Byxwrao）和小维诺格拉多夫（BHHopappB），及 意大利的朋比利（Bombieri）证明了“1+3 ”。 1966年，中国的陈景润证明了 “1+2 ”[用通俗的话说，就是大偶数=素数+素数*素数或大偶数=素数+素数（注：组成大偶数的素数不可能是偶素数，只能是奇素数。因为在素数中只有一个偶素数，那就是2。） ]。 其中“s + t ”问题是指： s个质数的乘积 与t个质数的乘积之和 20世纪的数学家们研究哥德巴赫猜想所采用的主要方法，是筛法、圆法、密率法和三角和。 2.关于数论的一些基础知识 如果只是限定在初等数论中，那么初等数论的研究对象就比较窄，一般就是整数，甚至是自然数。高级一点的研究连分数就突破这方面的限制。 从原则上来讲，初等数论是研究负整数的，比如丢番图方程。而如果只讲最基础的整除、素数，研究自然数就够了。 初等数论最基本的工具是整除和同余，整除就是6除以2是整数，就说6能被2整除；6除以4是分数，就说6不能被2整除。同余就是两个数用同一个数（称为模）去除，看是否得到一样的余数。比如对于模7,2和9同余，3和6不同余。 附带的概念包括最大公约数等等，欧几里德算法是求最大公约数的基本方法。 向较高方向发展可以包括，原根、二次剩余、Pell方程、数论函数、素数分布、图形格点等等。总之，初等数论所用的工具不会超过初等分析。 3.初等数论怎么学习 初等数论也称整数论，主要研究整数的性质和方程的整数解，是一门非常重要的数学基础理论分支.由于初等数论中的问题简明易懂，所以它比任何其它的数学分支更能引起人们的注意.近代数学中许多重要的思想、概念、方法和技巧都是从对整数性质的深入研究而不断丰富和发展起来的. 本课程3学分，学时为54。 本课程共分5章，分别介绍了整除理论、不定方程、同余理论和连分数，重点讲解了整数的整除性、不定方程、一元同余理论、平方剩余等四个模块。本课程的主要任务是一方面使学生加深对整数及其性质的理解，另一方面使学生能够掌握基本的初等数论的研究方法和技巧，有利于学生更好地进行初等数学的教学。 本课程的文字教材根据知识点的难易程度配备了一系列例题和练习题，还编制了20学时的IP课件供学生在网上学习，并编制了一系列网上辅导练习题. 整数的整除性模块要求掌握整数的整除、公因子、素数的概念及性质，熟练运用辗转相除法求两个整数的最大公因子，最小公倍数，深入理解剩余定理和算术基本定理.会用筛法求简单的素数表；会利用抽屉原理证明一些有关整数是某个特定整数的倍数的简单问题. 不定方程模块要求牢记二元一次不定方程有整数解的条件，二元一次不定方程整数解的形式，熟练掌握利用剩余定理（辗转相除法）求二元一次不定方程整数解的方法；知道多元一次不定方程有解的条件，会求解简单的多元（三元）一次不定方程的整数解；知道不定方程 的整数解的形式，会求形如 的整数解，并且能够证明一些简单的有关问题. 一元同余理论模块要求会利用同余的性质，简单验证整数乘积运算的结果；熟练掌握判断剩余系的方法，理解欧拉函数的定义及性质；了解欧拉定理、Fermat小定理，掌握循环小数的判定方法；掌握一次同余式有解的条件，熟练掌握求解一次同余式；掌握中国剩余定理的简单应用，掌握求解简单同余式方程组的方法；了解高次同余式解的个数的判断方法，知道解高次同余式的方法，了解模整数同余式与模素数同余式的关系，掌握求简单的（3、4次）同余式解的方法. 平方剩余模块要求理解二次同余式的一般形式、模整数同余与模素数幂同余的关系、平方剩余与平方非剩余的概念；理解单素数的平方剩余与平方非剩余的欧拉判定法，了解单素数的平方剩余与平方非剩余的个数；了解Legendre符号的定义、性质及Jacobi符号的定义、性质，熟练掌握利用Legendre和Jacobi符号判断同余式的解的存在性；掌握非素数模的二次同余式有解的条件及解的个数的有关结论；会对素数p讨论不定方程 有整数解的条件；掌握求原根的简单方法；会利用原根得到整数简化剩余系的方法；掌握指标的应用（讨论同余式有解的条件及解的个数）. 在许多数论问题的研究方面，我国都处于领先地位，如老一辈著名数学家华罗庚、柯召、闵嗣鹤等都曾取得过辉煌的成就，特别是华罗庚教授在解析数论方面的成果是举世公认的.60年代后，著名数学家陈景润、王元、潘承洞等在Goldbach猜想等问题上也取得了国际领先的成果. 怎样才能学好本课程？我们唯一的建议是去做，去实践.学习初等数论就像学习一门新的实践和实用技术课程一样，必须多练习，最好是一节一练，甚至是一定理（或一例题）一练习，如遇不懂之处，可反复看书或反复看举例题或反复做配套练习题，或许您会豁然开朗。学好本课程对有否本专业知识背景要求不高，只要你能花时间认真去学，有些公式需要去记去背，并会灵活应用，抓住关键点。 学习一门课程还需要有一定的技巧，学会分类和概括，抓住关节点，不知不觉就激起了您对学习和探讨本课程的兴趣和积极性，学起来就更加得心应手.。 4.初等数论的初等数论内容 初等数论有以下几部分内容： 1.整除理论。引入整除、因数、倍数、质数与合数等基本概念。这一理论的主要成果有：唯一分解定理、裴蜀定理、欧几里德的辗转相除法、算术基本定理、素数个数无限证明。 2.同余理论。主要出自于高斯的《算术研究》内容。定义了同余、原根、指数、平方剩余、同余方程等概念。主要成果：二次互反律、欧拉定理、费马小定理、威尔逊定理、孙子定理（即中国剩余定理）等等。 3.连分数理论。引入了连分数概念和算法等等。特别是研究了整数平方根的连分数展开。主要成果：循环连分数展开、最佳逼近问题、佩尔方程求解。 4.不定方程。主要研究了低次代数曲线对应的不定方程，比如勾股方程的商高定理、佩尔方程的连分数求解。也包括了四次费马方程的求解问题等等。 5.数论函数。比如欧拉函数、莫比乌斯变换等等。 6.高斯函数。 第一个层次叫做数学概念，是反映对象的本质属性的思维形式。人类在认识过程中，从感性认识上升到理性认识，把所感知的事物的共同本质特点抽象出来，加以概括，就成为概念。表达概念的语言形式是词或词组。科学概念，特别是数学概念要求更加严格，至少必须具备三个条件：专一性，精确性，可以检验。例如：”孪生素数“就是一个数学概念。 第二个层次叫做数学命题，数学命题是对一系列数学概念之间的关系作出判断的句子。一个命题要么真，要么不真（这由逻辑中的排中律保证）。真命题包含定理，引理，推论，事实等。命题既可以是存在性命题（表述为”存在。。."），也可以是全称命题（表述为“对于一切。.."）。 第三个层次叫做数学理论，把方法，公式，公理，定理，原理，组合成为一个体系叫做数学理论。例如“初等数论”，由公理（例如等量公理），定理（例如费马小定理），原理（例如抽屉原理，一一对应原理），公式等组成。 在数学证明时，全称命题常常不能通过枚举法来判断真伪，这是因为数学有时面对的是无穷多个对象，永远不可能一一枚举出每一种情况。不完全归纳法在数学中是不可行的，数学只承认演绎逻辑（数学归纳法，超限归纳法等均属于演绎逻辑）。 5.【求初等数论的基本概念,基本理论和定理等,越全越好,】 第一章 有关数论的算法1.1 最大公约数与最小公倍数1.2 有关素数的算法1.3 方程ax+by=c的整数解及应用1.4 求a^b mod n1.1最大公约数与最小公倍数 1.算法1：欧几里德算法求a,b的最大公约数 function gcd(a,b:longint):longint;beginif b=0 then gcdd:=aelse gcd:=gcd(b,a mod b);end;2.算法2：最小公倍数acm=a*b div gcd(a,b);3.算法3：扩展的欧几里德算法，求出gcd(a,b)和满足gcd(a,b)=ax+by的整数x和y function exgcd(a,b:longint;var x,y:longint):longint;vart:longint;beginif b=0 then beginresult:=a;x:=1;y:=0;endelsebeginresult:=exgcd(b,a mod b,x,y);t:=x;x:=y;y:=t-(a div b)*y;end;end；（理论依据：gcd(a,b)=ax+by=bx1+(a mod b)y1=bx1+(a-(a div b)*b)y1=ay1+b(x1-(a div b)*y1))1.2有关素数的算法1.算法4：求前n个素数：program BasicMath_Prime;constmaxn=1000;varpnum,n:longint; p:array[1..maxn] of longint;function IsPrime(x:longint):boolean;var i:integer;beginfor i:=1 to pnum doif sqr(p[i])0），现c筒装满水，问能否在c筒个量出d升水（c>d>0）.若能，请列出一种方案.算法分析：量水过程实际上就是倒来倒去，每次倒的时候总有如下几个持点：1.总有一个筒中的水没有变动；2.不是一个筒被倒满就是另一个筒被倒光；3.c筒仅起中转作用，而本身容积除了必须足够装下a简和b简的全部水外，别无其它限制.程序如下：program mw;typenode=array[0..1] of longint;vara,b,c:node;d,step,x,y:longint;function exgcd(a,b:longint;var x,y:longint):longint;var t:longint;beginif b=0 thenbeginexgcd:=a;;x:=1;y:=0;endelsebeginexgcd:=exgcd(b,a mod b,x,y);t:=x;x:=y;y:=t-(a div b)*yend;end;procedure equation(a,b,c:longint;var x0,y0:longint);var d,x,y:longint;begind:=exgcd(a,b,x,y);if c mod d>0 thenbeginwriteln("no answer");halt;end elsebeginx0:=x*(c div d);y0:=y*(c div d);end;end;procedure fill(var a,b:node);var t:longint;beginif a[1]0 thenrepeatif a[1]=0 then fill(c,a) elseif b[1]=b[0] then fill(b,c) else fill(a,b);inc(step);writeln(step:5,":",a[1]:5,b[1]:5,c[1]:5);until c[1]=delserepeatif b[1]=0 then fill(c,b) elseif a[1]=a[0] then fill(a,c) else fill(b,a);inc(step);writeln(step:5,":",a[1]:5,b[1]:5,c[1]:5);until c[1]=d;end.1.4 求a^b mod n 1.算法8：直接叠代法求a^b mod n function f(a,b,n:longint):longint; var d,i:longint; begin d:=a; for i:=2 to b do d:=d mod n*a; d:=d mod n; f:=d; end; 2.算法9：加速叠代法 function f(a,b,n:longint):longint; var d,t:longint; begin d:=1;t:=a; while b>0 do begin if t=1 then begin f:=d;exit end ; if b mod 2 =1 then d:=d*t mod n; b:=b div 2; t:=t*t mod n; end; f:=d end； 练习：1.熟记并默写以上算法.。 6.数学小知识 1、在生活中，我们经常会用到0、1、2、3、4、5、6、7、8、9这些数字。 那么你知道这些数字是谁发明的吗？ 这些数字符号原来是古代印度人发明的，后来传到 *** ，又从 *** 传到欧洲，欧洲人误以为是 *** 人发明的，就把它们叫做“ *** 数字”，因为流传了许多年，人们叫得顺口，所以至今人们仍然将错就错，把这些古代印度人发明的数字符号叫做 *** 数字。 现在， *** 数字已成了全世界通用的数字符号。 2、九九歌就是我们现在使用的乘法口诀。 远在公元前的春秋战国时代，九九歌就已经被人们广泛使用。 在当时的许多著作中，都有关于九九歌的记载。最初的九九歌是从“九九八十一”起到“二二得四”止，共36句。 因为是从“九九八十一”开始，所以取名九九歌。大约在公元五至十世纪间，九九歌才扩充到“一一得一”。 大约在公元十三、十四世纪，九九歌的顺序才变成和现在所用的一样，从“一一得一”起到“九九八十一”止。 现在我国使用的乘法口诀有两种，一种是45句的，通常称为“小九九”；还有一种是81句的，通常称为“大九九”。 3、圆形，是一个看来简单，实际上是很奇妙的圆形。 古代人最早是从太阳，从阴历十五的月亮得到圆的概念的。 就是现在也还用日、月来形容一些圆的东西，如月门、月琴、日月贝、太阳珊瑚等等。 是什么人作出第一个圆呢？ 十几万年前的古人作的石球已经相当圆了。 前面说过，一万八千年前的山顶洞人曾经在兽牙、砾石和石珠上钻孔，那些孔有的就很圆。 山顶洞人是用一种尖状器转着钻孔的，一面钻不透，再从另一面钻。 石器的尖是圆心，它的宽度的一半就是半径，一圈圈地转就可以钻出一个圆的孔。 以后到了陶器时代，许多陶器都是圆的。 圆的陶器是将泥土放在一个转盘上制成的。 当人们开始纺线，又制出了圆形的石纺缍或陶纺缍。 6000年前的半坡人（在西安）会建造圆形的房子，面积有十多平方米。 古代人还发现圆的木头滚着走比较省劲。 后来他们在搬运重物的时候，就把几段圆木垫在大树、大石头下面滚着走，这样当然比扛着走省劲得多。当然了，因为圆木不是固定在重物下面的，走一段，还得把后面滚出来的圆木滚到前面去，垫在重物前面部分的下方。 大约在6000年前，美索不达米亚人，做出了世界上第一个轮子--圆的木盘。 大约在4000多年前，人们将圆的木盘固定在木架下，这就成了最初的车子。 因为轮子的圆心是固定在一根轴上的，而圆心到圆周总是等长的，所以只要道路平坦，车子就可以平衡地前进了。 会作圆，但不一定就懂得圆的性质。 古代埃及人就认为：圆，是神赐给人的神圣图形。一直到两千多年前我国的墨子（约公元前468-前376年）才给圆下了一个定义："一中同长也"。 意思是说：圆有一个圆心，圆心到圆周的长都相等。这个定义比希腊数学家欧几里得（约公元前330-前275年）给圆下定义要早100年。 圆周率，也就是圆周与直径的比值，是一个非常奇特的数。 《周髀算经》上说"径一周三"，把圆周率看成3，这只是一个近似值。 美索不达来亚人在作第一个轮子的时候，也只知道圆周率是3。 魏晋时期的刘徽于公元263年给《九章算术》作注。 他发现"径一周三"只是圆内接正六边形周长和直径的比值。他创立了割圆术，认为圆内接正多连形边数无限增加时，周长就越逼近圆周长。 他算到圆内接正3072边形的圆周率，π= 3927/1250，请你将它换算成小数，看约等于多少？ 刘徽已经把极限的概念运用于解决实际的数学问题之中，这在世界数学史上也是一项重大的成就。 祖冲之（公元429-500年）在前人的计算基础上继续推算，求出圆周率在3.1415926与3.1415927之间是世界上最早的七位小数精确值，他还用两个分数值来表示圆周率：22/7称为约率，355/113称为密率。 请你将这两个分数换成小数，看它们与今天已知的圆周率有几位小数数字相同？ 在欧洲，直到1000年后的十六世纪，德国人鄂图（公元1573年）和安托尼兹才得到这个数值。 现在有了电子计算机，圆周率已经算到了小数点后一千万以上了。 4、数学除了记数以外，还需要一套数学符号来表示数和数、数和形的相互关系。 数学符号的发明和使用比数字晚，但是数量多得多。 现在常用的有200多个，初中数学书里就不下20多种。它们都有一段有趣的经历。 例如加号曾经有好几种，现在通用"+"号。 "+"号是由拉丁文"et"（"和"的意思）演变而来的。 十六世纪，意大利科学家塔塔里亚用意大利文"più"（加的意思）的第一个字母表示加，草为"μ"最后都变成了"+"号。 "-"号是从拉丁文"minus"（"减"的意思）演变来的，简写m，再省略掉字母，就成了"-"了。 也有人说，卖酒的商人用"-"表示酒桶里的酒卖了多少。以后，当把新酒灌入大桶的时候，就在"-"上加一竖，意思是把原线条勾销，这样就成了个"+"号。 到了十五世纪，德国数学家魏德美正式确定："+"用作加号，"-"用作减号。 乘号曾经用过十几种，现在通用两种。 一个是"*"，最早是英国数学家奥屈特1631年提出的；一个是"· "，最早是英国数学家赫锐奥特首创的。德国数学家莱布尼茨认为："*"。

是的。大学数学专业的学生需要学习的课程包括高等代数、数学分析、解析几何、概率论、高等几何、微分几何、复变函数、实变函数、微分方程、近世代数、初等数论等。《初等数论》可作为综合性大学数学专业，中、高等师范学校及教师进修院校的教材，也可供数学爱好者、中学数学教师阅读。

初等数论研究数的规律，特别是整数性质的数学分支。是数论的一个最古老的分支。它以算术方法为主要研究方法，主要内容有整数的整除理论、不定方程、同余式等。初等数论不仅是研究纯数学的基础，也是许多学科的重要工具。它的应用是多方面的，如计算机科学、组合数学、密码学、信息论等。如公开密钥体制的提出是数论在密码学中的重要应用。 代数学http://baike.baidu.com/view/556393.htm（太长了）

古希腊毕达哥拉斯是初等数论的先驱。他与他的学派致力于一些特殊整数（如亲和数、完全数、多边形数）及特殊不定方程的研究。公元前4世纪，欧几里德的《几何原本》通过102个命题，初步建立了整数的整除理论。他关于“素数有无穷多个”的证明，被认为是数学证明的典范。初等数论已经有2000年的历史，公元前300年，欧几里得发现了素数是数论的基石，他自己证明了有无穷多个素数。公元前250年古希腊数学家埃拉托塞尼发明了一种筛法。2000年来，数论学的一个最重要的任务，就是寻找一个可以表示所有素数的统一公式，或者称为素数普遍公式，为此，人类耗费了巨大的心血。后来发现埃拉托塞尼筛法可以转换成为一个素数产生的公式：公元前250年同样是古希腊的数学家埃拉托塞尼提出一种筛法：（一）“要得到不大于某个自然数n（不等于0）的所有素数，只要在2至n中将不大于 的素数的倍数全部划去即可”。（二）将上面的内容等价转换：“如果n是合数（非0自然数），则它有一个因子d满足 ”。 （三）再从（二）得到等价的逆否命题：“若自然数n不能被不大于 的任何素数整除，则n是一个素数”。 （四）上述的（三）可以用符号如此表达：其中 顺序地表示素数2，3，5，...。对以上的诸 （ ，即 为N被 相除所得之余数 ），有 （余数不为0）。即N不能是2m，3m，5m，...，pkm形。若 ，则N是一个素数。（五）可以把上述的式（1）用同余式组表示：例如，29不能够被以下的任何素数2，3，5整除，29=2x14+1=3x9+2=5x5+4。29≡1(mod2)，29≡2(mod3)， 29≡4(mod5)。29小于72=49 ，所以29是一个素数。由于（2）的模 两两互素，根据孙子定理（中国剩余定理）知，（2）式在 的意义上有唯一解。例如k=1时， ，解得N=3，5，7。求得了（3，32）区间的全部素数。k=2时， ，解得N=7，13，19； ，解得N=5，11，17，23。如此，求得了（5，52 ）区间的全部素数。仿此下去可以求得任意给定数以内的全部素数。(六)用程序方法求素数。“若一个自然数n，判断n/k是否整除，先判断其能否整除2，若不能再判断其能否整除3，依次向下判断，当k>(n/k)时，判断结束。”如果所有判断都不能整除，则自然数N为素数。公元3世纪，丢番图研究了若干不定方程，并分别设计巧妙解法，故后人称不定方程为丢番图方程。17世纪以来，费马、欧拉、高斯等人的工作大大丰富和发展了初等数论的内容。 中国古代对初等数论的研究有着光辉的成就，《周髀算经》、《孙子算经》、《张邱建算经》、《数书九章》等古文献上都有记载。孙子定理比欧洲早500年， 西方常称此定理为中国剩余定理，秦九韶的大衍求一术也驰名世界。初等数论不仅是研究纯数学的基础，也是许多学科的重要工具。它的应用是多方面的，如计算机科学、组合数学、密码学、信息论等。如公开密钥体制的提出是数论在密码学中的重要应用。

初等数论是大学本科小学教育专业理科类必修课程，教学总时数为48课时。本课程主要研究整数最基本的性质。整除理论是初等数论的基础，其中心内容是算术基本定理和最大公约数理论。

现在我们就开始为剩余系建立“ 坐标 ”，完全剩余系是连续的，剩余类本身就是很好的坐标，所以这里我们只需讨论既约剩余系。前面已经知道 时，总存 d 在使得 ，满足条件的最小的 称为a对模m的阶或指数，也可简记为 ，我们可以看出来当模 m 确定时， 由 a 唯一的确定，d 是 a 的函数。为了得到更进一步的结论，我们先整理一下指数的一些简单性质如下： （1）若 ，则 。从而有若 ，则 ； （2） ； 。 我们来继续研究指数的性质，首先考虑 ，由 知 ，故可容易有公式（1），你可以简单停留思考下，有了（1）式后我们就可以从 求 了。其次由定义显然有：若 ，则 。所以对互质分解 (分解模数)，总有 ，再根据模的性质就有公式（2）。再进一步，对任意的a1,a2,u22ef,an，考虑方程组 的 唯一解 a （ 剩余定理 ），显然有 ，再根据公式（2）可得 a 满足公式（3）。 　 　 再来研究 （分解底数），令 ，则显然有 （提示：可以结合(1)式进行思考）。先看各个 互素 的情况，这时 ，令 。因为 ，又因为 互素。故 ，从而有公式（4）。如果 不互素，一般并没有 。但反过来，对任意的 ，利用公式（1）和（4）构造满足公式（5）的 a 还是很容易的。 　 　 　 指数在研究 循环小数 时有个有趣的结论。对既约分数 ，如果有 ，则 是循环小数的充要条件是 。如果 ，则最小循环周期为 c，并且小数点后的非循环数长度为 。特别地，如果 ，则 是纯循环小数。证明过程不是难，可以作为练习，提示：使用关系式 由指数的性质（2）可知 是 个不同的数，特别地当 时，它们遍历 m 的既约剩余系。这种关系使得既约剩余系变得特别简单，我们也由此找到了合适的 坐标 。为此，当 时称 g称为模 m的 原根 ，它便是既约剩余系的 单位元 ，负责将剩余系串成一个线性空间。先来思考如下几个问题： 　 u2022 如果 ，则 遍历m的既约剩余系时， 也遍历既约剩余系; u2022 若 ，或 ，都有 2 是 的原根； u2022 的素因子有形式 或 。 我们自然会有问题：什么样的 模数 有原根？有多少个原根？如何判定？前面已经知道 ，而除了 这5种情况外（p为 奇素数 ），容易证明其它都有 ，它们肯定没有原根，因为当模数 m 不属于上面这五种情况时，必有 m 为 或 或 ，而这里的 由 给出。这里的 由下列式子给出： 　 又因为我们有式子， 故可以得到 ，可自行验证。 下面就需要论证那5种情况是否有原根，直接验算可知1,2,4有原根。对于模p的情况，由公式（5）知存在g使得 ，首先当然有 。另外因为 有全解，则 。从而 ，所以p有原根 g。 由 和 的等价性，并且 ，可知 和 有相同的原根，这样一来我们就只需要讨论模 是否有原根了。当g是 原根时，因为 ，故 为 或 。要想g也是 的原根，必须 ，即满足式子（6）。而如果该条件满足，用归纳法可以验算得它对一切 都满足，即g是所有 的原根。 　 　现在只要能证明以上条件对 成立（即 ），我们就找到了所有模 的原根，研究证明了 原根的存在性。对模 p 的原根 g，考察 和式子（7）中的变形。 中有且仅一个是 p 的倍数，取其它任何一个值都能得到了满足条件的原根，条件得证。 至此我们已经证明了原根存在的充要条件是模为 之一，但如果想要找出原根，目前还没有很简单的方法。一般只能逐个尝试每个数，然而利用公式（5）的构造法是可以加快计算的，比如如果已经知道 和 ，因为 ，故素因子 2,3 必定也是模 41 的原根的素因子，经过尝试后得 是 41 的原根。 如果原根存在，选定一个原根 g 后，它的幂次遍历整个既约剩余系。如果 ，称 k 为a 的 指标 ，记作 ，或简记为 和 。指标将既约剩余系变成了一个完全剩余系，使其结构由分散的变为线性的，由此可以更好地研究它的性质。以下为原根的一些性质，其中性质（3）中蕴含了指数为 的数有 φ(d)个，它们是 。特别地共有 个原根，它们是 。 (1) (2) ,特别地有 (3) 我们一直想把指数当做即约剩余系的“ 坐标 ”，现在就来着手做这件事。一般的，将模m进行素数分解 ，其既约剩余系的每个数 a 在各个维度都有一个值 。对 g_k gamma_k=gamma_{p_k^{e_k},g_k}(a_k)$就可以看做a 在第 k 维的坐标。 但对于 ，除 外是没有原根的， 时怎么建立坐标？通过 归纳法 你可以证明 ，并且容易知道 是它的一个既约剩余系。这样任何既约数都有唯一表达式（8）， 就可以看做它的坐标。完整的就得到任何既约数的指标表达式（9）和（10）（（10）中 的是（9）中的 取1、其它取0得来），使用（10）来证明威尔逊定理就简单多了。 最后再来看同余方程（11）它一般称为 二项同余方程 。如果方程有解，称a为m的n 次剩余 ，否则称为n次 非剩余 。对m进行素数分解 后，方程可以化为一个方程组，我们只需分别讨论这些方程即可。 　　 　　模 （p为奇素数）有原根 g，用它来分析二项方程会很简单（下面的讨论针对有原根的模m都成立）。将原根带入原方程，得到式子（12）的左侧，它显然对应于右侧的一元一次同余方程。可以先回顾一下一次方程 的特点，令 ，则 ，且方程解的周期为 ，请先在脑子想象一下它们的布局。回到原方程，令 ，则方程有解的充要条件是 ，且共有 个n次剩余。方程的解有d个，它们的周期是 。 　　 　　现在来把条件 转化为与a直接相关的。因为 ，使用公式（1）直接有式子（13）。结合条件d|γ(a)，显然有 ，它又等价于公式（14）。这就是方程有解的充要条件，明显二次剩余的判定条件只是它的特例。 对模 的情景需要单独考虑，前面的讨论中说明了它的既约剩余系有两个独立的维度，故只需分别讨论两个维度就行了。令 ，可知方程有解的充要条件是 且 ，方程解的个数为 。展开说就是，当 时有且仅有1解，既约剩余系的每个值都是n次剩余。当 时有解的充要条件是 且 ，并且有2d个解，共有 个数是n次剩余。 下面把 有解的充要条件转化为与 a 相关的，首先易知必有形式 。因为 ，我们的条件 其实等价于 ，这就得到充要条件为公式（15）。当然你也可以得到与 类似的式子，但因为不如上式简洁，这里就不赘述了。 经过前面关于初等数论的基础知识的学习和理解，这里我们就可以开始不定方程的简单论述。不定方程是初等数论向前发展直接的驱动力之一。不定方程又叫丢潘图方程，它们以整数（或有理数）为变量和参数，而且有两个以上的未知数，多以多项式形式出现。不定方程既是数论的应用，也是数论理论形成的来源，对不定方程的思考可以将前面学习过的知识和内容串起来。 最简单的不定方程就是一次方程（1），它表现为一个 多元线性方程 。如果你还记得前面最大公约数的线性组合定义，就容易得到方程有整数解的充要条件是 。多元方程的第一步往往是降元，令 ，则方程等价于一次方程组（2）（想想为什么？以及为什么要先抽出最大公约数？）。如果对（2）式一直做类似处理，就会得到多个二元一次方程，这样就把问题集中到了简单的情景。 而对于二元一次方程 ，它有明显的几何意义，方程的解就是直线方程上的整数点，所有对其讨论都可以从图形中找出。容易看出，如果已知一个解 ，则方程的全部解为公式（3）。至于如何求得一个特解，一般还是用辗转相除法，对于一些简单的情况，也可以直接尝试各种值。 勾股定理 大家都熟悉，有一个自然的问题是：如何求它的所有解？这个问题一般叫商高方程或毕达哥拉斯方程。容易证明当 时方程的解两两互素，如果再限定解为正数，这样的解叫 本原解 。方程的解要么是平凡解 (0,0,0)，要么是本原解的倍数，因此我们只需专注于找到所有本原解。 另外，因为素数的平方只能是 的形式，可推得 x,y 必定是一奇一偶，下面就假设 y 为偶数，原方程整理为式子（4）。容易证明 （这个性质以后会经常用），故可设 和 ，其中 。用 表示 就得到了方程的解（5），但要注意要使得它们两两互素，还需要限定 （自行证明）。 做一个简单的推广，形如（6）式的方程这么解？这就是著名的 费马大定理 （Fermat Last Theorem），当然它在1994年被彻底证明前叫费马猜想。费马发现它们并无非平凡解，并声称找到了一个绝妙的证明方法，但由于书的空白太小写不下。后来人经过了三百多年的努力，才用现代数学的方法将它攻破，大家多数倾向于认为费马的证明并不存在或并不成立。 使用类似的方法和 无穷递降法 ，你可以证明 无非平凡解，进而 无非平凡解，它就是费马大定理在 时的情况。下面可以思考一下如下几个问题： u2022 求解 和 ； u2022 求解 ；（提示： 无互质解 ） u2022 证明 都有无穷多组解。（提示： 构造 ） 再来看费马大定理在 的情景，欧拉证明了它没有非平凡解，采用的是 无穷递降法 。假设 是使得 最小的一组非零解，我们的目的是构造一组值更小的解。首先当然有 ，并且其中仅有一个偶数，经过调整后可以使 为偶数。这时可以令 ，则有 （总结成式（7）），这个变换的重要意义在于 降次 。 现在来研究 ，其中 ，它里面有我们熟悉的二次表达式。考察 的每个素因子 p，因为 ，故总有 （可参考下面将要介绍的平方数分解的最后一段）。使用公式（8）（使用复数证明这类等式更容易，并且体现了范数的思想），可知总有 。下面证明总能找到合适的 ，使得关系式（9）成立。 使用归纳法证明，当 时，公式（9）显然成立。若结论对 成立，则考虑 ，我们的目的是找到表达式（9）。由前面的结论可有 ，且有 和 满足类似（9）的关系式。与刚才的式子相乘并除以 得到（10），然后证明（10）式右侧的两项可以都是整数。若记 ，则由假设知存在 和 满足类似（9）的关系式。综合以上结论，可得到的相关结论（11），它们满足公式（9），定理得证。 现在回过头来看式子（7）中的 。当 时，由 必为一奇一偶且互素（想想为什么）和 为偶数，容易有 ，可以假设式子（12）左侧。而由上面的结论可知（12）的右侧成立，其中最右边三项互质，故有式子（13）。而 。当 时可以得到同样的结论，由此我们得到了一组积单调递减的解，这是不可能的，所以原方程没有非平凡解。 将商高方程在系数上进行扩展，得到一般性的 （ 且无平方因子），当然我们只需研究其本原解 。首先容易有 ，则存在 ，变换 得到式子（14），从而 是 的二次剩余。这样我们就得到了方程有解的一个必要条件： 分别是 的二次剩余。 下面来看它们是否是方程有解的充分条件，使用的是 降次法 和 构造法 。另外，利用同余方程研究不定方程也是常见方法，这里我们可以先考虑同余方程（15）。先来看降次，首先容易判断 ，则可以有式（16）。对模 也可以有类似的表达式，它们将原式表示成了两个线性表达式之积，问题也就容易转化到一次方程了。使用剩余定理

基础知识定义（欧拉(Euler)函数）一组数称为是模的既约剩余系,如果对任意的,且对于任意的,若＝1,则有且仅有一个是对模的剩余,即.并定义中和互质的数的个数,称为欧拉（Euler）函数.这是数论中的非常重要的一个函数,显然,而对于,就是1,2,…,中与互素的数的个数,比如说是素数,则有.引理：；可用容斥定理来证（证明略）.定理1：（欧拉（Euler）定理）设＝1,则.定理2：（费尔马（Fermat）小定理）对于质数及任意整数有.定理推论：设为质数,是与互质的任一整数,则.定理3：（威尔逊（Wilson）定理）设为质数,则.定理4：（中国剩余定理）设是两两互素的正整数,那么对于任意整数,一次同余方程组,必有解,

1。素数的剩余类构成域，2。公式：a^p ≡ a （mod p），若 a 不能被 p 整除，则 a^(p-1) ≡ 1 （mod p），需要学习、研究集合中的群环域理论，

从本文开始，我们将正式开始介绍有关初等数论的相关知识与概念，我们争取用通俗的语言去把握和描述理论的精髓所在。而不拘泥于具体概念的束缚，以窥探初等数论巧妙的一些思想方法。从这里开始你的行囊里不需要太多的东西，只要会整数的加减乘除即可。东西多了不仅帮不了你，反而会成为前进的负担。你需要首先抛开一切固有思维，清空大脑，带着孩童般的好奇心重新认识这个世界。由于数论经常出现于奥数和智力题中，它往往被当成一种锻炼思维的智力游戏，但随着研究的深入，我们需要建立一套理论才能看清本质。我们可以从最简单的定义出发，利用理性思维建立这些理论。但通过做题与不断地思考是学习数论的必经途径，这样才能有更深刻的理解，这一部分笔者不能代劳，这里只能力图尽力而为，将其中的思想和方法展现在各位面前。 数论研究整数本身（或自然数，语境自明），初等数论主要研究整数之间的关系。整数的运算中，加减是最平凡的，得不出什么深入的结论，从而乘除法是唯一可以着手的地方。考虑一个简单的等式 ma=b（以后若不作特殊说明，所有符号表示整数），任何两个整数之间都可以有像 m,a 这样的乘法运算，但却并不是所有整数都有等式中类似a与b这样的关系。为此，当 a≠0 时，定义满足等式的 a 能整除 b，或b被a整除，a称为b的约数，b称为a的倍数，记作a∣b，否则记为au2224b。 仅从定义出发可以得到整除的许多基本性质，这里就不一一列举了，只给出一个最具代表性的：式子（1），即 a 的倍数的线性组合仍是 a 的倍数。整数集线性组合的这一性质体现了元素之间的共性，后面还会继续深究，这里先举一例来感受其意义。若a∣n,b∣n，则有 ab∣nb,ab∣na，进而有 ab∣n(ax+by)，所以如果有 ax+by=1，则有 ab∣n。 考虑n的所有 倍数 的集合 kn，它的元素有无穷多个，且性质是 平凡的 ，不多阐述。现在来考虑 n 的所有 约数 ，显然它们是有限的，但我们似乎还得不出更多的结论。不妨先考察一类特殊的数：如果 p>1 除了±1和±p外没有其它约数，p称为 质数 或 素数 ，反之叫合数，今后我们会约定俗成地用 p, q 表示素数。直观上素数是不能再分解的数，它们是整数的 基本因子 ，任何整数都可以通过有限步分解为素数的乘积。 一个自然的问题是，这样的分解唯一吗？你固有的知识可能使你对这个问题相当地自信，但如果冷静思考地一番，就会发现这种自信其实是没有根据的。它的证明并不十分显然，这里通过反证法来推导。假设有某些 整数的素数分解不唯一，则存在最小的这样的数，并设它有两个分解式a=p1p2u22efpn=q1q2u22efqm，其中m,n>1，并且素数按大小排列。由a的最小性知pi≠qj，假设p1>q1，考察式（2）。容易证明后一分解式中不含q1，从而b<a有两个不同的分解式。这与a的最小性矛盾，故所有整数都存在唯一的的素数分解式，即表达式（3）唯一,此方法被叫做无穷递降法。这个证明最早由高斯给出，被称为 算术基本定理 ，它使得整数可以被完全解析。 现在来看数a的所有约数，容易知道它们的分解式必定是式子（4）。若记a共有 个约数，且它们的和为 ，则有公式（5）（6）。 这里可以尝试来思考如下几个问题： 　 　　u2022 求满足 的最小整数； 　　u2022 求 的值。 有了 算术基本定理 ，整数之间的倍数关系就基本清楚了。而对于两个任意的整数（不一定有倍数关系），只能通过它们共同的 约数 或 倍数 来取得联系。两个数a,b共同的约数称为它们的 公约数 ，最大的那个叫 最大公约数 ，记作(a,b)，类似还有公倍数和 最小公倍数 [a,b]的概念，最大公约数为1的两个数称为 互素 或 既约 的。这些概念都有一些比较简单的性质，可以通过算术基本定理去证明，后面会罗列。公约（倍）数为研究 整数之间的关系 提供了便利，但它们的定义并不依赖于算术基本定理，你完全可以仅从定义出发得到那些常用结论，算术基本定理只是提供了一种方法而已。 公约数一定程度上体现了整数之间的相关程度， 互素 则表现了整数之间的 无关性 。这个观念为我们分析整数集的结构提供了一个好的思想，不大于m的所有数可以按照和m的相关程度分类，这个话题我们会在后面展开。现在来考虑一下 与 m 无关的（互素）数的个数 <font color=red> φ(m)（欧拉函数） ，对素数 p 显然有 和 ，利用 容斥原理 排除掉不互素的数之后可以得到公式（7）。 　　 关于这个计算式的证明可参见： 欧拉函数的计算式 算术基本定理虽然很强大，但用它来求公约数或进行整数关系分析的代价太大，并且也很难得到进一步的结论，这时必须引入别的工具。在不做素数分解的情况下，分析整数关系最直观的方法就是带余除法，对任意整数 a≠0, b，存在唯一数对 m, r 满足式子（8）。由 知 a,b 的公约数必定是 r 的约数，并且 r 更小。如果继续对 a, r 做这样的运算，我们一定可以得到a,b的最大公约数。这便是辗转相除法的基本思想，早在欧几里得的《几何原本》中就有记载（故又称Euclid算法），熟悉算法的你一定也不陌生，这里就不展开细节了。 带余除法 为整数的分析提供了一个简单有效的方法。比如我们再回头考虑一下式（1）中的所有线性组合，首先(b1,b2,u22ef,bn)显然也是每个线性组合的约数。考察线性组合中的最小正数 c，如果它不是 bk 的约数，使用带余除法 也是线性组合但却更小。所以c是b1,b2,u22ef,bn的公约数，结合刚才的结论可知c=(b1,b2,u22ef,bn)。 最大公约数 可以看做是整数间的一个 基本代数运算 ，我们已经看到有很多不同的途径来得到它，而这些途径并不依赖于最大公约数的定义。这就让我们想到，其实可以将它们看成是最大公约数的等价定义，在不同的场合灵活使用，可以得到更简洁的方法。以下便列举了这些等价定义，你可以尝试证明它们的等价性。 u2003u2003（1）原始定义：最大的公约数； 　　（2）约数的公倍数：是所有公约数的最小公倍数； 　　（3）素数基本定理：素数分解式的公共部分； 　　（4）线性组合：线性组合的最小正数； 　　（5）辗转相除法：辗转相除法得到的最小正数。 作为一个 基本运算 ，需要稍微研究一下 最大公约数的基本性质 ，你可以尝试通过不同途径证明下面的基本性质： u2003u2003（1） 　　（2） 　　（3）若 ，则有 　　（4）若 则 　　（5）若 则 　　（6） 公约数虽然定义简单，但却变化多端，当和其它知识结合起来时，问题会变得很困难。你需要熟练掌握初等数学中各种变形技巧，并需要足够的想象力和创造力。必要的练习是最好的锻炼场所，你不能绕过那一步，如下只列几例供参考。 u2003u2003 u2022 已知 求证 　　u2022 a为奇数，则必有 使得 设这样数最小为 ，则 成立的充要条件是 　　u2022 证明梅森（Mersenne）数 两两互素； 　　u2022 求证 不是整数；（提示：构造一个整数与之相乘后不为整数） 　　u2022 若(a,b)=1，则对任意 中有无数个与m互质的数。（提示：无穷递降） 话说素数的确非常重要，后面我们还会看到它更多的性质，这里再多说两句。首先，欧几里得在《几何原本》回答了素数的个数问题，假设仅有有限个素数 ，考察表达式 。它不以任何 为约数，从而它也是素数，与假设矛盾，这就证明了素数有无穷多个。该证明使用了 构造法和反证法 ，它的美妙是数学史上惊艳的一笔，你不妨可以用同样的方法解决以下问题。 　 u2003 u2022 相邻素数之间的间隔可以有任意大； 　　u2022 证明费马数 的素因子互不相同，从而素数有无穷多个； 　　u2022 使用数列 ，证明素数有无穷多个； 　　u2022 求证形如 的素数有无穷多个； 　　u2022 如果 则n必为素数。 根据算术基本原理，并使用 级数 理论，容易有以下著名的 欧拉公式 （式子（9））。这个神奇的公式将 调和级数 与 所有素数 扯上了关系，这也成为了研究素数的一个突破口，巍峨耸立的 黎曼猜想 就是对它的扩展研究。顺便提一句，因为 调和级数是发散的，故由此此也可以证明素数有无穷多个。 　　 关于素数，还有一些自然的问题是：如何判定一个数是否为素数？如何找出一定范围内的所有素数？它们的分布是怎样的？是否有素数的通项公式？这些问题是很难回答的，它们也是数论的难点，很多问题都还没有被解决。古希腊时期的 Eratosthenes筛法 是目前仍在使用的筛选素数的方法，它逐步划去每个素数的倍数，从而仅余下素数，这在一般的算法教材里都有介绍。另外一般用 π(x) 表示不大于x的素数的个数，公式（10）是就是著名的 素数定理 ，它表明了素数的平均密度。该定理最早由勒让德和高斯作为猜想提出，将近一百年后才被人用复变函数的理论所证明，再过了50年才有了初等证法。关于素数的问题我们就不深究了，它们也不是这里能回答得了的。 　　 公约数 是我们要讨论的主要 整数关系 ，对整数m而言，其它整数与它的关系以 m 为周期出现着重复，具体讲就是 任何整数 和 带余除法中的余数 是等价的。为此我们可以在整数中建立另一种 等价关系 ，如果 即 ，则称 a, b 在模 m 下<font color=red> 同余 </font> 或 a 同余于 b 模 m, b 是 a 对模 m 的剩余，记做 ，该关系式称为模 m 的同余式。比较容易证明同余关系是一个等价关系， 它将整数限定在一个有限的空间里 ，大大方便了讨论。<font color=purple> 同余理论由高斯提出，它是数论的基础语言 </font>。由于 同余继承自整除 的概念，它的性质一般还是用整除来证明，但作为一个强大的语言，它有着自己简洁清晰的特点。以下是一些同余的基础性质，各位可以自行证明或者查看网络资料，这些都是较常用的基本性质（重要）： u2003u2003（1）若 ，则有 和 ； 　　（2）若 ，则 ； 　　（3） 等价于 　　（4）若 ，则 ； 　　（5） 等价于 。 性质（1）比较平凡，（2）（3）是对操作数进行缩放时的性质，（3）中包含了两种极端情况 d∣m 和(d,m)=1 的性质。（4）（5）是对模数进行缩放时的性质，性质（5）可以将问题互相转化，把大模数分解为几个小模数，或者反过来将多个等式合并为一个。性质（2）中没有除法，那是因为“倒数”还没有被定义。当(a,m)=1时，使用线性组合的定义容易证明，一定存在d使得 ， 称为a的 逆 。有了逆就可以两边同时“除以”一个数了，但需要注意逆仅对与 模互素的数 存在。 既然同余是个等价关系，那它的等价类就可以看做是一个整体，所有满足 的整数组成的集合称为一个 剩余类 ，记作 ，模m的所有剩余类组成的集合记作 。当 (r,m)=1 时，即与 m 互素的数 r ， 又称为 既约剩余类 ，模m的所有既约剩余类的个数显然共有 φ(m) 个，φ(m) 又称为欧拉函数。在一个只有加减乘除的同余式里，任何数都可以等价地看成它的同余类，故以上性质对同余类也是成立的。同余类中同样可以定义 逆 ，容易证明逆存在则必是唯一的，且有 。 下面有一个思考题，你可以尝试利用同余的性质来解决： u2022 求 的末两位数。 主要区分上面在同余理论下的 剩余类 与我们这里要讨论的 剩余系 。 虽然剩余类和它的元素是等价的，但元素本身更容易被直接讨论。于是从每个剩余类中取一个元素组成的 集合 称为一个 完全剩余系 ，它的 定义 是：一组数 称为模 m 的完全剩余系，如果对任意的 a 有且仅有一个 是 a 对模 m 的剩余，即 a 同余于 模 m 。同时还应注意类似 称为模 m 的 最小非负（完全）剩余系 ； 为 绝对最小（完全）剩余系 ； 最大非正（完全）剩余系 。 相应地还有 既约剩余系 的概念。定义是：一组数 称为模 m 的既约（互素）剩余系，如果 ,以及对任意的 a, (a, m)=1, 有且仅有一个 是 a 对模 m 的剩余，即 a 同余于 模 m 。剩余系的元素可以根据需求来选取，而且它们有以下基本性质(关于具体证明可参考推荐书籍) : （1）若 是一个完全剩余系，则对任何整数c， 仍然是一个完全剩余系； （2）若 是一个完全（既约）剩余系，且 ，则 仍然是一个完全（既约）剩余系。 性质（2）告诉我们，如果 是n的既约剩余系，且 ，则 也是既约剩余系。那它们的乘积应该是模n同余的，即式子（1），这样就得到了著名的 欧拉定理 （公式（2））。取n为素数 p 时，则又有了 费马小定理 （公式（3））。欧拉定理给出了一个求元素逆的方法，即 。另外，欧拉定理还给出了既约剩余系的元素与“单位元”的关系，这里是我们首次讨论既约剩余系元素之间的关系，后面还会继续研究。 简单考虑一个的习题： u2022 求m的 最小正既约剩余系的所有元素之和。 剩余系的提出，最终还是为了研究同余意义下的整数空间，在这里就是要弄清完全（既约）剩余系的 结构 。既然整数 m 可以进行素数分解，想必把模m的剩余系按其素数分解分割会是个不错的想法。具体来说，对于 m 的互质分解 ，我们想看到的是 m 的剩余系和 的剩余系之间的关系。 先从简单的 看起，参考进制数的方法并考察 ，其中 是 的完全剩余系， 是 的完全剩余系。容易证明当 遍历 的完全剩余系，则 遍历m的完全剩余系。使用归纳法可以将这个结论推广到 的情形，但由于其形式不对称，推广的结论并无太大理论价值。由于 ，可知将上式中的 换成 结论任然成立。 另外，当 遍历 的既约剩余系时，首先由刚才的结论， 两两不同余，其次也容易证明它们与 m 互素。综合起来我们就有结论：当 遍历 的既约剩余系时， 正好遍历m的既约剩余系。使用对应的证明方法（两类剩余系方法不同），这个结论可以轻易地推广到 的情景，甚至为每一项再乘上任意与 互素的数，结论任然成立。即当 两两互素，且有 ，则当 遍历 的完全（既约）剩余系时，表达式（4）和（5）都正好遍历 m 的完全（既约）剩余系。 　 　　表达式中的 就像 x 的坐标一样，剩余系被分解到了个互相独立的维度，各个维度可以被单独地研究。值得提醒的是，以上表达式的每一项其实刚好是 的剩余系，它们可以相加得到m的剩余系 。有一个自然的问题是，有没有表示为乘法的表达式 ，同样满足这样的要求呢？结合前面结论，容易构造出公式（6）中的分解（ 的 意义同上 ），它的每一项是 的剩余系，各项相乘后是m的剩余系。有趣的是，表达式中各项之和任然遍历完全剩余系，而这对既约剩余系是不成立的（见下面练习）。 尝试解决以下问题： u2003u2003u2022 求13的一个完全剩余系 ，满足 和 ； 　　u2022 若 是m的既约剩余系，则对任何满足 的整数， 都不可能是既约剩余系。 　　u2022 不可能有 的既约剩余系 ，使得 和 都是m的既约剩余系； 以上分解方法从另一方面给出了欧拉函数的性质：如果 ，则 。利用这个性质可以得到公式（7），另外，这个公式还可以这样解释：将 按照与n的最大公约数d划分为不同的集合，容易知道每个集合有 个元素，所以共有 个元素，这样就得到公式（8）。换句话说，一个完全剩余系被划分成了若干个既约剩余系，不得不说是一个很新颖的划分方法。 剩余系分解 的一个典型应用就是 解一次同余方程组 ，下篇我们会专门研究同余方程，这里只介绍这类方程组（式子（9）的左侧）。当 两两互素时，根据前面的分解定理可知，在模 下方程有且仅有一解 。该结论历史上称为 孙子定理 （又称 中国剩余定理 ），因为《孙子算经》中“物不知数”的问题其实就是一次同余方程组。 以上定理限定 两两互素，且x系数为1，对于不满足条件的方程组，可以通过前面的结论进行等价变换。其中 意义同上 , 是 对模 的逆。即 。关于中国剩余定理其实还有很多中方法求解，更多解法，可参见， 中国剩余定理的五种解法 　 　你可以尝试如下练习： 　u2003u2022 求解“物不知数”问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？ 　　u2022 求的7一个完全剩余系，每个数模2,3,5的余数都是1； 　　u2022 解方程 ； 　　u2022 解方程组　 虽然我们还没有完全弄清既约剩余系的结构，但还是可以再做一些有趣的讨论的。既约剩余系中的任何数都有逆，尝试将它们两两配对，所有这样的数的乘积为 1，如果再将那些逆为自身的数单独研究，也许可以得到既约剩余系的整体性质。先从模 p 看起，对逆为自身的数有 ，从而，满足条件的只有两个数 ±1。这样便有了著名的 威尔逊（Wilson）定理 （公式（10）），它给出了既约剩余系 积的整体性质。 以上讨论过程对奇素数的幂 仍然成立，对 独立讨论也可知模为 1,2,4 时结果为 u22121，其它模 的结果为 1。对一般的模 ，考虑公式（6）表示的既约剩余系的积 ，因为除了 外都有 ，故除了模为 外都有 。总结以上可以有威尔逊定理的扩展定理：模为 （p为奇素数）的既约剩余系的乘积模m余为 u22121，其它形式模的既约剩余数之积模m余为1。这个既约剩余系的整体性质在一些问题中很有作用，你可以尝试者解决以下问题： u2022 若 和 是奇素数p的两个完全剩余系，证明 一定不是完全剩余系。再证明该结论对任意模m也成立； u2022 求证 。 　　 以上证明中的配对思想非常重要，请考虑以下问题： u2022 求证存在 的充要条件是 ，并由此证明格式为 ，的素数有无穷多个。

刚翻开人教版大学本科小学教育专业教材《初等数论》的目录，许多在校本科小学教育专业的学生，包括我都存在这样的感觉，那就是觉得这些是再简单不过的内容：整除、质数与合数、最大公约数与最小公倍数、同余等等，这些内容在我们读小学的时候都已经学习过，似乎觉得没有必要再去研究，直到接触学习了这门课程，才扭转了我们的看法。初等数论是小学教育专业，尤其是理科方向学生的必修专业课程，也是从事小学数学教学的老师的进修课程。其中包括整数的整除性、同余、同余方程、不定方程、不定方程、简单连分数几方面的知识。这些方面的内容在符合了小学数学教师应具有的教学思维外，也有利于学习者积累从事小学数学教育工作必备的能力与知识。有人说：“数学是思维的体操，科学的王冠，数论是王冠上的明珠。”这颗明珠在小学数学中早已是熠熠闪光——我们小学所学习到的数论内容主要包含以下几类：整除问题：（1）整除的性质；（2）数的整除特征 （小升初常考内容） 余数问题：（1）带余除式的运用 被除数=除数×商+余数.（余数总比除数小） （2）同余的性质和运用奇偶问题：（1）奇偶与加减运算；（2）奇偶与乘除运算 质数合数：重点是质因数的分解约数倍数：（1）最大公约最小公倍两大定理 （2）约数个数决定法则可见，初等数论的应用与小学数学教育事业是息息相关的。对于初等数论，我学到的也只是九牛一毛，谈不上有什么有建设性的问题，只能粗略地谈谈初等数论中的核心内容——同余，并通过其在初等数论在小学数学中的应用来说明两者的关系。同余是由德国数学家高斯首先提出并系统地进行研究的，它是初等数论的核心部分。其中蕴含大量的数论所特有的思想、概念和方法，它的出现使数论成为一个独立的数学分支的标志。在这一内容中包括其性质，剩余类与剩余系，欧拉定理和循环小数等几个知识点。在没接触初等数论学习之前，我们对同余这个概念很陌生，其实同余在我们小学数学学习，奥数中已经有了很深入的运用。在小学中主要体现在余数的运用上，余数是小学数学中的重要概念，也是数学竞赛的热门话题，其中有关概念多，方法性强。在小学，关于余数问题我们知道：如果整数a除以正整数m，商为q，余数为r，则a=qm+r，其中q与r都是自然数，并且0≤r＜m.而现在我们学的同余知识是：如果两个正整数a,b被非零自然数m除时所得的余数相同，a=qm+r,b=pm+r，那么就说a与b关于模m同余,记为a≡b（mod m）.此时a与b的差能被m整除，记为a-b ≡0（mod m）.因此同余问题常常转化为整除问题求解。下面，我以一个例题来反应同余在小学数学教学中的应用：例题、a除以5余1，b除以5余4，如果3a＞b，那么3a－b除以5余几？ 这道题目出现在小学奥数中，小学生一般的解答方法是：方法一：凑数法。取a为6，取b为9，这样a.b满足了条件a除以5余1，b除以5余4，3a-b=9,9/5余数为4。方法二、设a=5x+1 b=5y+4 3a-b=15x-5y-1=15x-5y-5+4=5(3x-y-1)+1 3a－b除以的余数是4 a=5x+1 （x为正的整数） b=5y+4（ y为正的整数 ） (3a-b)/5 =(15x+3-5y-4)/5 =3x-y-1/5 =(3x-y-1)+4/5 根据x,y均为正的整数,并且3a>b，所以余数为4。 而在初等数论中的解法： 解：∵a≡1（mod5）， ∴3a≡3（mod 5）， 或者3a≡8（mod 5）．（1） 又∵ b≡4（mod 5），（2） ∴（1）－（2）得： 3a－b≡8－4≡4（mod 5）．因此，3a－b除以5余4．在小学生解法中我们可以看出，两种方法，尤其是第二种，都是以同余知识出发去处理问题，只是在形式表达上相对于大学里初等数论练习中较为简单化。在小学的奥数思维训练中，同余思想的应用更是数不胜数，如“抽屉原理”是同余应用中最典型的例子，可以说，同余理论是近世代数中一个很重要的数学模型。除此之外，其他很多数学知识都涉及到了同余，比如像欧拉函数，它也是初等数论中的重要函数之一，在证明过程中就大量地体现了同余的思想。学过初等数论的人应该都知道，小学数学和初等数论之间最大的不同在于小学数学在于如何应用定理、法则，而初等数论则要明白为什么这么应用。显然，初等数论是更为深层次的学习，在难度上有了一个跨越。那么数论部分在小学数学考试题型中占据什么地位呢？可以说，翻开任何一本数学辅导书，数论的题型都占据了显著的位置。有专家在小学各类数学竞赛中研究发现，直接运用数论知识解题的题目分值大概占据整张试卷总分的30%左右，而在竞赛的决赛试题中，这一分值比例更高。出题老师喜欢将数论题作为区分尖子生和普通学生的依据，这一部分学习的好坏将直接决定学生在选拔性考试中成绩的好坏。综上所述，初等数论作为一门为小学教育专业的学生开设的课程，在培养学生扎实的数学基础之外，更多的是有利于师范生更好地将初等数论的理论灵活地应用于小学教育中，进一步培养科学的人生观、价值观。

——当p=4k+1时(3/p)=（p/3) ＝1（仅当p＝3m+1时）解得p=12R+1——当p=4k-1时（3/p)=-(p/3)=1（仅当p=3m-1时）解得p=12R-1结论：所有形如12R+1或者12R-1的素数都可以。

(2^n+1)/(2^m-1)（1）n<m时，分母大于分子，当然不能整除（2）n>=m时，(2^n+1)/(2^m-1)＝（2^(n-m)(2^m-1)+2^(n-m)+1)/(2^m-1)＝2^(n-m)+(2^(n-m)+1)/(2^m-1)可以看出原式化成一个速数加上（2^(n-m)+1)/(2^m-1)下面再比较n-m与m的大小　　　　1。如n-m>m,2^(n-m)+1)/(2^m-1)又可以同上面作一样的变换成一个整数和类似原式一样的一个分数，可以反复分离出整数来，最后的分数肯定是分子小于分母，也就是题中结论成立　　　　2、如n-m<m,则就已说明，(2^n+1)/(2^m-1)化成一个整数和一个真分数的和，非整数，故题中结论成立　　综合，原结论成立　我认为初等数论问题非常复杂,我都这么辛苦作答了，给个最佳答案把，谢谢啦！煤矸石粉碎机

1、证明：70!≡61!（mod71）引理：ac==bcmodm,(c,m)=1,则a==b.证略.依引理,只须证70!/61!==1mod71即70*69*...62==-1*-2*...*-9==-9!==-362880==1,显然.2、求3的100次方的模10的余数引理：(a,m)=1,则a^φ（m）==1modm.证略.由于3^φ（10）==1mod10,即3^4==1故3^100==13、求3的50次方的十进制数表示中最末的两位数同上理,3^25==1mod100故3^50==1即其十进表示最末二位数为01

模8的完全剩余系，就是组内各数除以8后，所得余数从0~7都正好出现一次（1）2,4,6,8,10,17,21,23除以8后，余数分别为：2,4,6,0,2,1,5,7缺少3，所以该组数不是模8的完全剩余系（2）-2,2,-3,3,5,6,7,8除以8后，余数分别为：6,2,5,3,5,6,7,0缺少1和4，所以该组数不是模8的完全剩余系

5、欧拉定理：若n,a为正整数，且n,a互质，即(a,n) = 1，则a^φ(n) ≡ 1 (mod n)二、证明：这个问题需要分类讨论（按除以3的余数） （1）当a≡0(mod3)时，a^2≡0(mod3)，则a^2+a+1≡0+0+1≡1(mod3) （2）当a≡1(mod3)时，a^2≡1(mod3)，则a^2+a+1≡1+1+1≡3≡0(mod3) （3）当a≡2(mod3)时，a^2≡4≡1(mod3)，则a^2+a+1≡1+2+1≡4≡1(mod3) 综上所述：a^2+a+1≡1(mod3)或者a^2+a+1≡0(mod3)三、证明：∵13^2=169≡49≡-11(mod60) ∴13^4≡(-11)^2≡121≡1(mod60)，即13^4≡1(mod60) 又∵1956=4*489 ∴13^(1956)=(13^4)^489≡1^489≡1(mod60) 即13^(1956)≡1(mod60)四、证明：设这4个连续的自然数为n, n+1, n+2, n+3 则这4个数的乘积加1为：n(n+1)(n+2)(n+3)+1 ∵n(n+1)(n+2)(n+3)+1 =[n(n+3)][(n+1)(n+2)]+1 =(n^2+3n)(n^2+3n+2)+1 =(n^2+3n)^2+2(n^2+3n)+1（这里把n^2+3n看成一个整体） =(n^2+3n+1)^2 ∴n(n+1)(n+2)(n+3)+1是平方数 证毕！ （望采纳！有不懂的可以追问！）

给你提供方法,但答案还是你自己做吧,不然你会没有成就感的,再说,太多依赖别人,那不是阻碍了自己进步的步伐?方法：这里讲到：N!的素因子分解式中素数p的指数h=[N/p]+[N/(p^2)]+[N/(p^3)]+...其中[x]是高斯取整函数,也记作int(x).我的补充：一个数m的素因子分解式中素数p的指数,记作函数Pot_p(m).另外,[x/(ab)]=[[x/a]/b]比较完整的解题过程：N!的标准(素因子)分解式中素数p的指数h=Pot_p(n!)=[N/p]+[N/(p^2)]+[N/(p^3)]+...,这里简记作h_p.取N=30,p=2,对[N/p^i],i=1,2,3,...,得到一列值：15,7,3,1,0（注：后面全是0,到0就可以终止了.这里注意：[30/2^2]=[[30/2]/2],于是可以直接利用[30/2]=15,迭代计算）累加得:h_2=26(注：15,7,3,1累加)同理,取N=30,p=3,得到h_3=10+3+1=14同理,h_5=6+1=7...h_29=1于是30!=2^26*3^14*.*17*19*23*29.补充：计算如有错误,请为我更正.请补充.祝快进步,培养自己的成就感.

如果有解，则必有本原解，可设（x,y,z)=1则(x,3)=1,(y,3)=1x^2==1 mod3y^2==1 mod3x^2+y^2==2 mod33z^2==0 mod 3显然无非全0解

这问题是同余那讲的，主要是用一个数次方后的模，与现对这个数取模再次方后再取模相等这个结论。那么原题就是要证2^32同余640（mod 641），2^32=(256^2)^2，256^2=65536，65536除以641余154，154^2=23716，23716除以641余640，故得证，希望能采纳

怎么求不大于M且与M互质的正整数的个数（例：M=60）解：不大于M且与M互质的正整数的个数，称为m的欧拉函数,或欧拉函数φ(m),注：φ是希腊字母，拉丁字记为phi,读作[fai](斐).下面给出计算方法。设m的标准质因子分解式为m=p1^a1*p2^a2……ps^as则φ(m)=φ(p1^a1)*…*φ(ps^as)=p1^(a1-1)*(p1-1)*…*ps^(as-1)*(ps-1)=p1^(a1-1)*…*ps^(as-1) * (p1-1)*…*(ps-1) =m/(p1*...*ps) * (p1-1)*…*(ps-1) （式VIP1）=m*(1-1/p1)*...*(1-1/ps) （式VIP2）其中式VIP1在m较大时，便于计算。式VIP2在理论推导中常用。以60为例来说明。60=2^2*3*5于是φ(60)=60/(2*3*5)*(1*2*4)=2*8=16并且我们还有一个这样的结论：如果m是n的倍数，m,n有共同的质因子，则φ(m)=m/n*φ(n).再如：φ(360)=360/60*φ(60)=6*16=96外一则：缩系与同余类的概念不大于M且与M互质的正整数构成的集合，称作m的既约剩余系(也称简化剩余系，缩剩余系,缩系)。注：既约：就是说与m互质。剩余：这样的数是所有与m互质的数除以m的余数（与M互质的正整数关于除数(模)M的最小正余数）系：相当于系列，集合。这里构成M的最小正缩系。对其中每一个数t,{t+mk}称作以t为代表的同余类(剩余类)。一般情况下，一个同余类中的任一个数均可以作为该同余类的代表。所有同余类中各取一个代表，即构成缩系。欧拉函数，就是缩系在集合意义上的基数(card)。 下面我们将与m互质并不大于m的数的集合记为{φ_m},其中的任一元素记成<φ_m>。举例和计算:以含有1个质因子的数来举例。如m=p^r.与它互质，就是与p互质，即排除被p整除的数。于是{φ_m}={1,2,…,p^r}-{p,2p,3p,…,p^r}={1,2,…,p-1；p+1,p+2,…,2p-1...p^r-2p+1,p^r-2p+2,…,p^r-2p+(p-1)p^r-p+1,p^r-p+2,…,p^r-p+(p-1)}于是φ(m)=p^r-p^(r-1)=p^(r-1)*(p-1)=p^r*(1-1/p)=p^r*((p-1)/p)以上连等号中的各种形式在计算中可能都会用到。很显然φ(p)=p-1.例：{φ_2^3}={1,2,...,8}-{2,4,6,8}={1,3,5,7}φ(8)=2^3-2^2=2^2*(2-1)=2^3*(1-1/2)同理：φ(4)=2^2-2=2*(2-1)=2^2*(1-1/2)以含有2个质因子的数来举例。如p^r*q^s.证明过程先略去。只是说明方法。φ(p^r*q^s）=φ(p^r)*φ(q^s）=p^(r-1)*(p-1)*q^(s-1)*(q-1)=p^(r-1)*q^(s-1)* (p-1)(q-1)=p^r*q^s (1-1/p)(1-1/q)事实上，如果两个数m,n互质，则φ(mn)=φ(m)φ(n)，由此很容易向多个数互质的情形推广。于是可以将一个数进行质因子分解，含有不同质因子的部分两两互质，从而得到多因子的情形，即前面的结论。

初等数论的话，勤思考、多锻炼思维，把一些非常基础有用的内容掌握（比如整除、带余数除法、同余、剩余类、原根和指标）、一些基础重要的定理、方法掌握（比如辗转相除法、算术基本定理、欧拉定理、费马定理、孙子定理（也叫中国剩余定理）、二次互反律）再进一步可以接触质数分布定理，不过这个继续深入会需要你进入非初等的数论的一个分支数论的话，主要是解析数论和代数数论两个初等数论只要中学的知识作预备知识而学习解析数论和代数数论之前，你需要学完数学系本科到研究生的大部分专业课代数数论的话，可能需要 本科的高等代数、抽象代数 研究生的交换代数 以及拓扑、代数拓扑、代数几何方向的内容，这些掌握之后就能开始看懂 费马大定理的证明（因为跟代数几何的椭圆模曲线有很大的关系） 了解析数论的话，需要 本科的 数学分析微积分、实变函数、复变函数、Fourier分析、和一些代数基础，还需要研究生的 (单)复分析(关系非常密切) 可能也需要一点点实分析的内容做铺垫掌握之后就能看懂 黎曼猜想 的意思，并且能看懂 素数分布定理 的高等证明（因为跟复变函数的解析延拓概念有很大的关系)

模23：二次剩余：1,4,9,16,2,13,3,18,12,8,6,二次非剩余：余下的模37：二次剩余：1,4,9,16,25,36,12,27,7,26,10,33,21,11,3,34,30,28,二次非剩余：余下的

如图，直接计算就可以了。

1)尾数是7。这个只要直接计算尾数就能找到规律，7的各次方尾数如下：1 |2 |3 |4 |5 |6 |7 7 |9 |3 |1 |7 |9 |3 因此7的7次方尾数是3，而同理列出3的各次方尾数规律：1 |2 |3 |4 |5 |6 |73 |9 |7 |1 |3 |9 |7因此7的7次方的7次方的末尾数字是3。2）本题只要考虑对7的余数就可以了。10除7余3，3的各次方除7的余数为（3的2次方除7的余数为3*3-7=2.3的3次方除7的余数为2*3=6,3的4次方除7的余数为6*3-7*2=4,依此类推）1 |2 |3 |4 |5 |6 |7 |8 |9 |103 |2 |6 |4 |5 |1 |3 |2 |6 |4即3的10次方除7余4，同理写出4的各次方除7的余数1 |2 |3 |4 |5 |6 |7 |8 |9 |104 |2 |1 |4 |2 |1 |4 |2 |1 |4即10的10次方的10次方除7余4。若今天周二，则到时过4天是周六

三者是并列关系，属于数学中的不同一级学科。数学史，是讲数学历史文化的，属于科学史性质，比较偏文科。初等数论，是研究数论中比较经典的初等问题（注意，初等数论不代表理解起来初级简单，许多理论反而相当深奥）离散数学，是与计算机等联系最紧密的学科，知识概念一般都属于具体离散型（相对于连续数学而言）。

可用归纳法证明n=1,[11^(6n)-2^(6n)]/91=(11^6-2^6)/91=(11^3-2^3)(11^3+2^3)/91;=[(11-2^2)(11^2+2)+2*11(2*11-1)](11^3+2^3)/91=(7*123+22*21)(11^3+2^3)/91;=7(123+66)[(11+2)(11^2+2^2)-11*2*(11+2)]/91=(7*189)(13*125-22*13)/91;=(7*189)(125-22)*13/(7*13)=189*103;91|11^6-2^6;n=2,[11^(6n)-2^(6n)]/91=(11^12-2^12)/91=(11^6-2^6)(11^6+2^6)/91=189*103(11^6+2^6);91|11^(6*2)-2^(6*2);n=3,[11^(6n)-2^(6n)]/91=(11^18-2^18)/91;=[(11^6-2^6)(11^12+2^12)-11^6*2^12+2^6*11^12]/91;=189*103(11^12+2^12)+(2*11)^6(11^6-2^6)/91;=189*103[(11^12+2^12)+(2*11)^6];91|11^(6*3)-2^(6*3);::假设当n=N时成立，即91|11^(6N)-2^(6N);则当n=N+1时，11^(6n)-2^(6n)=11^[6(N+1)]-2^[6(N+1)]=11^(6N+6)-2^(6N+6);=[11^(6N)+2^(6N)](11^6-2^6)+2^6*11^(6N)-11^6*2^(6N);=[11^(6N)+2^(6N)](11^6-2^6)+(2^6*11^6){[11^[6(N-1)]-2^[6(N-1)]};91|11^6-2^6,91|11^[6(N-1)]-2^[6(N-1)],所以91|11^[6(N+1)]-2^[6(N+1)];所以则当n=N+1时，91|11^[6(N+1)]-2^[6(N+1)]也成立;所以对于任意给定的正整数，都有91|11^(6n)-2^(6n)

这是裴蜀定理的直接推论定理：对任意两个不全为0的整数a、b，存在 最大公约数d=（a,b），且对d可以表示成 如下形式：d=ax+by，其中x、y为整数。证明：如果 a 和 b 有一个是0，那么它们两 个的最大公约数是0。这时定理显然成 立。以下证明a和b都不等于0的情况。不妨设a,b都大于零，a>=b.设(a,b)=d对ax+by=d，两边同时除以d，可得(a1)x+(b1)y=1，其中(a1,b1)=1。转证(a1)x+(b1)y=1。由带余除法：a1=(q1)b+(r1),其中0=<r1<b1b1=(q2)(r1)+(r2),其中0=<r2<r1(r1)=(q3)(r2)+(r3),其中0=<r3<r2.....(rn-3)=(qn-1)(rn-2)+(rn-1)(rn-2)=(qn)(rn-1)+(rn)(rn-1)=(qn+1)(rn)于是，有(a1,b1)=(b1,r1)=(r1,r2)=...=(rn-1,rn)=1故(rn-2)=(xn)(rn-1)+1即1=(rn-2)-(xn)(rn-1)由倒数第三个式子（rn-1）=(rn-3)-(xn-1)(rn-2)代入上式，得1=[1+(xn)(xn-1)](rn-2)-(xn)(rn-3)然后用同样的办法用它上面的等式逐个地消去(rn-2),...(r1),可证得1=(a1)x+(b1)y。

哥德尔不完全性定理 哥德尔是德国著名数学家,不完备性定理是他在1931年提出来的.这一理论使数学基础研究发生了划时代的变化,更是现代逻辑史上很重要的一座里程碑.该定理与塔斯基的形式语言的真理论,图灵机和判定问题,被赞誉为现代逻辑科学在哲学方面的三大成果. 哥德尔证明了任何一个形式体系,只要包括了简单的初等数论描述,而且是一致的,它必定包含某些体系内所允许的方法既不能证明也不能正伪的命题.哥德尔第一不完全定理　　设系统S包含有一阶谓词逻辑与初等数论，如果S是一致的，则下文的T与非T在S中均不可证。哥德尔第二不完全定理　　如果系统S含有初等数论，当S无矛盾时，它的无矛盾性不可能在S内证明。第一不完备性定理　　任意一个包含算术系统在内的形式系统中，都存在一个命题，它在这个系统中既不能被证明也不能被否定。第二不完备性定理　　任意一个包含算术系统的形式系统自身不能证明它本身的无矛盾性。

1．解同余式 :2x=3(mod45)解：2x==3==48 mod45x==24这里用到同余式的性质：等号两边同除与模互质的数，同余式仍成立。2.解同余式组： x=1(mod2) x=2(mod5) x=3(mod11)解：x==1==5*11 mod 2x==2==2**11 mod 5x==3==2*5*(-3) mod 11[注：此处中括号内的内容是为了说明中国剩余定理（孙子定理）的原理，正式求解时不必写。事实上，由下面的过程可以看出，中国剩余定理是可以活用的，可以简化的。易见：x==1==5*11+2**11+2*5*(-3) mod 2x==2==5*11+2**11+2*5*(-3) mod 5x==3==5*11+2**11+2*5*(-3) mod 11]故解为：x==5*11+2**11+2*5*(-3) mod 2*5*11x==47 mod 110

分类讨论：（1）如果x,y,z被3除的余数互不相同，即余数分别是0，1，2，则它们的和能被3整除，即等式(x-y)(y-z)(z-x)=x+y+z（*）的右边能被3整除，从而左边也能被3整除，于是x-y, y-z, z-x中至少有一个能被3整除，这与x,y,z余数不同矛盾！此情况不可能。（2）若x,y,z中恰有两个被3除余数相同，设x,y除以3余数都是r，z除以3余数为s，由于此时（*）式左边能被3整除，进而右边也能，即2r+s能被3整除，由于r,s都取值于0，1，2，验算易知此情况不可能。（3）剩下就是x,y,z被3除的余数都相同，此时（*）式左边显然能被三个3的乘积27整除，所以右边也能被27整除，所以，27|（x+yz+）。说明1. 由于不知你对数论有多少了解，所以不敢使用数论术语，叙述太详细了（是我多虑！）；说明2. 此问题离结束只有4天了，可能已经无人问津了，枉费我用心打字！

初等数论对大学生的意义是培养学生的能力。根据查询相关公开信息：开设初等数论课程的必要性，帮助学生更准确地理解中小学数学知识，而高校数学课程的教学是其核心影响因素之一。

初等数论有以下几部分内容：1.整除理论。引入整除、因数、倍数、质数与合数等基本概念。这一理论的主要成果有：唯一分解定理、裴蜀定理、欧几里德的辗转相除法、算术基本定理、素数个数无限证明。2.同余理论。主要出自于高斯的《算术研究》内容。定义了同余、原根、指数、平方剩余、同余方程等概念。主要成果：二次互反律、欧拉定理、费马小定理、威尔逊定理、孙子定理（即中国剩余定理）等等。3.连分数理论。引入了连分数概念和算法等等。特别是研究了整数平方根的连分数展开。主要成果：循环连分数展开、最佳逼近问题、佩尔方程求解。4.不定方程。主要研究了低次代数曲线对应的不定方程，比如勾股方程的商高定理、佩尔方程的连分数求解。也包括了四次费马方程的求解问题等等。5.数论函数。比如欧拉函数、莫比乌斯变换等等。6.高斯函数。 第一个层次叫做数学概念，是反映对象的本质属性的思维形式。人类在认识过程中，从感性认识上升到理性认识，把所感知的事物的共同本质特点抽象出来，加以概括，就成为概念。表达概念的语言形式是词或词组。科学概念，特别是数学概念要求更加严格，至少必须具备三个条件：专一性，精确性，可以检验。例如：”孪生素数“就是一个数学概念。第二个层次叫做数学命题，数学命题是对一系列数学概念之间的关系作出判断的句子。一个命题要么真，要么不真（这由逻辑中的排中律保证）。真命题包含定理，引理，推论，事实等。命题既可以是存在性命题（表述为”存在......."），也可以是全称命题（表述为“对于一切....."）。　　第三个层次叫做数学理论，把方法，公式，公理，定理，原理，组合成为一个体系叫做数学理论。例如“初等数论”，由公理（例如等量公理），定理（例如费马小定理），原理（例如抽屉原理，一一对应原理），公式等组成。　　在数学证明时，全称命题常常不能通过枚举法来判断真伪，这是因为数学有时面对的是无穷多个对象，永远不可能一一枚举出每一种情况。不完全归纳法在数学中是不可行的，数学只承认演绎逻辑（数学归纳法，超限归纳法等均属于演绎逻辑）。

初等数论是研究数的规律，特别是整数性质的数学分支。它是数论的一个最古老的分支。它以算术方法为主要研究方法，主要内容有整数的整除理论、同余理论、连分数理论和某些特殊不定方程。 换言之，初等数论就是用初等、朴素的方法去研究数论。另外还有解析数论（用解析的方法研究数论）、代数数论（用代数结构的方法研究数论）。

http://baike.baidu.com/view/17568.htm

初等数论适合初中生，如果对此感兴趣，在课余时间可以学一学。初等数论是研究数的规律，特别是整数性质的数学分支。它是数论的一个最古老的分支。它以算术方法为主要研究方法，主要内容有整数的整除理论、同余理论、连分数理论和某些特殊不定方程。换言之，初等数论就是用初等、朴素的方法去研究数论。另外还有解析数论（用解析的方法研究数论）、代数数论（用代数结构的方法研究数论）。初等数论有以下几部分内容：1、整除理论。引入整除、因数、倍数、质数与合数等基本概念。这一理论的主要成果有：唯一分解定理、裴蜀定理、欧几里德的辗转相除法、算术基本定理、素数个数无限证明。2、同余理论。主要出自于高斯的《算术研究》内容。定义了同余、原根、指数、平方剩余、同余方程等概念。主要成果：二次互反律、欧拉定理、费马小定理、威尔逊定理、孙子定理（即中国剩余定理）等等。3、连分数理论。引入了连分数概念和算法等等。特别是研究了整数平方根的连分数展开。主要成果：循环连分数展开、最佳逼近问题、佩尔方程求解。4、不定方程。主要研究了低次代数曲线对应的不定方程，比如勾股方程的商高定理、佩尔方程的连分数求解。也包括了四次费马方程的求解问题等等。5、数论函数。比如欧拉函数、莫比乌斯变换等等。6、高斯函数。以上内容参考：百度百科-初等数论

在20世纪90年代之前，我国的数学教科书是把自然数定义为正整数。此后，为了与计算机的应用一致，把0当作自然数。学习《初等数论》，可以了解整数的很多性质，学习解不定方程，对提高自己的逻辑思维能力很有帮助。仅供参考，祝您进步！

简单。初等数论为比较基本的数学，知识点比较分散，所以简单。初等数论是研究数的规律，特别是整数性质的数学分支。它是数论的一个最古老的分支。它以算术方法为主要研究方法，主要内容有整数的整除理论、同余理论、连分数理论和某些特殊不定方程。换言之，初等数论就是用初等、朴素的方法去研究数论。另外还有解析数论（用解析的方法研究数论）、代数数论。

1. 因为(k,n)=d，则存在整数s, t，使得ks+nt=d. 所以a^(ks)=1(mod m) a^(nt)=1(mod m) a^d=a^(ks+nt)=1(mod m)2. 因为当(b,a)=1当且仅当(a-b, a)=1. 用如同高斯求1+2+......+100相同的方法可知： 和=1/2 *(a-b+b) *φ(a)=1/2 *a*φ(a).3. 需要证ax+b(x取遍m的完全剩余系)是m的完全剩余系。 因为ax+b=ay+b(mod m) 当且仅当a(x-y)=0(mod m) 当且仅当m|a(x-y). 因为(a,m)=1. 所以m|x-y. 即x=y(mod m). 所以所求式子=1/m+2/m+......+(m-1)/m=1/2 *(m-1).4. 接上题： 所求式子=a/m+2a/m+......+(m-1)a/m-1/2 *(m-1). =1/2 *(m-1)(a-1).5. 先看第6题，证明(p-1)!=-1(mod p). 因为p-a=-a(mod p). 所以(p-1)!=(((p-1)/2)!)*(-(p-1)/2)*......*(-2)(-1) =(((p-1)/2)!)^2 * (-1)^((p-1)/2). =-1(mod p). 所以(((p-1)/2)!)^2+(-1)^((p-1)/2)=0(mod p).6. (p, p-1)=1. (p-1)!=0(mod p-1). 下面证(p-1)!=-1(mod p). p=2, 3时成立；p>=5时： 首先对于任意a(2<=a<=p-2)，存在唯一的b(2<=b<=p-2)，使得ab=1(mod p). 对于a、2a、......、(p-1)a这p-1个数中，它们两两mod p不同余。 否则存在i、j（i、j不相等）使得ia=ja(mod p). p|a(i-j). p|i-j. 则i=j，矛盾。 又因为ia mod p不为0， 所以a、2a、......、(p-1)a这p-1个数中，mod p是1~p-1的一个排列， 所以存在唯一的b(1<=b<=p-1)，使得ab=1(mod p). 又因为a与(p-1)a mod p都不为1，所以2<=b<=p-2. 这样，将每个a、b进行配对a1、b1、a2、b2...... 2*3*......*(p-2)=(a1*b1)(a2*b2)......=1(mod p). 所以(p-1)!=1*1*(p-1)=-1(mod p). 综上(p-1)!=p-1(mod p(p-1)). 7. x^y=y^(x-y). 显然x-y>=0. 若x=y，则x^x=x^0=1. 则x=1, y=1. 若x>y，则y<x-y, x>2y. 设x=ky，k>2. 则k^y * y^y=y^((k-1)y). ky=y^(k-1). k=y^(k-2). y=k^(1/(k-2)). 根据求导发现函数f(k)=k^(1/(k-2))在k>2递减， 而f(k)->正无穷(k->2), f(3)=3, f(4)=2, f(k)->1(k->正无穷). 所以k=3, 4时对应两组解：x=9, y=3; x=8, y=2. 且k>4时无解。 下面证2<k<3时无解即可。 因为k=x/y是有理数，设k=p/q, (p, q)=1. 所以y^(k-2)=k y^(p/q -2)=p/q. y^(p-2q)=(p/q)^q. 当q不为1时，左边是整数，右边不是整数，矛盾。 综上：x=1, y=1; x=8, y=2; x=9, y=3.8. 5^x-3^y=2. x=y=1是一组解. 当x>1, y>1时： 原式mod 4： 1-(-1)^y=2(mod 4). y=1(mod 2). 原式mod 9： 5^x=2(mod 9). x=5(mod 6). 原式mod 7： 因为当x=5(mod 6)时，5^x=3(mod 7). 所以3^y=1(mod 7). 所以y=0(mod 6). 与y是奇数矛盾。 综上只有一组解x=y=1.

α = [α] +{a} nα =n[a] +n{a} [nα] =n[a] +[n{a}] [na]/n =[a] +[n{a}]/n [ [nα]/n ] =[ [a] +[n{a}]/n ] =[a] +[ [n{a}]/n ] --------n{a},10,初等数论证明题 设n是任意正整数,α是实数,证明：[ [nα ]/ n ]= [α ]有谁能解一下呢,

数论四大定理是：威尔逊定理、欧拉定理、孙子定理（中国剩余定理）、费马小定理。数论是纯粹数学的分支之一，主要研究整数的性质。整数可以是方程式的解（丢番图方程）。有些解析函数（像黎曼ζ函数）中包括了一些整数、质数的性质，透过这些函数也可以了解一些数论的问题。透过数论也可以建立实数和有理数之间的关系，并且用有理数来逼近实数（丢番图逼近）。按研究方法来看，数论大致可分为初等数论和高等数论。初等数论是用初等方法研究的数论，它的研究方法本质上说，就是利用整数环的整除性质，主要包括整除理论、同余理论、连分数理论。高等数论则包括了更为深刻的数学研究工具。

解：初等数论：整除理论。引入整除、因数、倍数、质数与合数等基本概念。这一理论的主要成果有：唯一分解定理、裴蜀定理、欧几里德的辗转相除法、算术基本定理、素数个数无限证明。同余理论。主要出自于高斯的《算术研究》内容。定义了同余、原根、指数、平方剩余、同余方程等概念。主要成果：二次互反律、欧拉定理、费马小定理、威尔逊定理、孙子定理（即中国剩余定理）等等。

　　数论主要是解析数论和代数数论两个。　　1.初等数论只要中学的知识作预备知识。　　2.学习解析数论和代数数论之前，你需要学完数学系本科到研究生的大部分专业课。　　3.代数数论的话，可能需要 本科的高等代数、抽象代数，研究生的交换代数，以及拓扑、代数拓扑、代数几何方向的内容，这些掌握之后就能开始看懂。　　4.解析数论的话，需要 本科的 数学分析微积分、实变函数、复变函数、Fourier分析、和一些代数基础，还需要研究生的 (单)复分析(关系非常密切) 可能也需要一点点实分析的内容做铺垫。

（-1859，1573）=（1859，1573）=（1859-1573，1573）=（286，1573）=（286，1573-5×286）=（286，143）=143

解：当n=2时，11是素数，当n=3时，111=3*37，111是合数，1111=11*101，1111是合数，11111=41*271，11111是合数，111111=3x7x11x13x37，1111111=239x4649，、、、、11111111111=21649x513239

应添加a＞b≠0 不妨设a=Ad b=Bd (A,B)=1 a-b=Se b=Te (S,T)=1则(a,b)=d (a-b,b)=e 由a=Ad b=Bd 得a-b=Ad-Bd=(A-B)d 则必有d|e由a-b=Se b=Te 得a=Se+Te=(S+T)e 则必有e|d 即d=e (a,b)=(a-b,b),(62,48)=(62-48,48)=(14,48)=(14,48-14)=(14,34)=(14,20)=(14,6)=(8,6)=(2,6)=(4,2)=(2,2)=2(n,n-1)=(n-(n-1),n-1)=(1,n-1)=1(n,n-2)=(n-(n-2),n-2)=(2,n-2) 若n为奇数，则(n,n-2)=1 若n是偶数(n,n-2)=2

所求解有以下形式：x=2rs y=r^2-s^2 z=r^2+s^2r>s (r,s)=1 2|(r+s+1)1^2+2^2=5<=z<=29　　r=2,s=1 解为（4,3,5）　　r=3, s=2解为（12, 5,13） r=4,s=1解为（8,15,17）　　　r=4,s=3解为(24,7,25) r=5,s=2解为（20,21,29）