初等数论与中学数学竞赛课件

初等数论与中学数学竞赛数学与统计学院陈国慧初等数论与中学数学竞赛数学与统计学院陈国慧一、数论概述

人类从学会计数开始就一直和自然数打交道了，后来由于实践的需要，数的概念进一步扩充，自然数被叫做正整数，而把它们的相反数叫做负整数，介于正整数和负整数中间的中性数叫做0。它们合起来叫做整数。（注：现在，自然数的概念有了改变，包括正整数和0）。

对于整数可以施行加、减、乘、除四种运算，叫做四则运算。其中加法、减法和乘法这三种运算，在整数范围内可以毫无阻碍地进行。一、数论概述人类从学会计数开始就一直和自然数打交道了2数论概述也就是说，任意两个或两个以上的整数相加、相减、相乘的时候，它们的和、差、积仍然是一个整数。但整数之间的除法在整数范围内并不一定能够无阻碍地进行。人们在对整数进行运算的应用和研究中，逐步熟悉了整数的特性。比如，整数肤浅地划分可分为两大类—奇数和偶数（通常被称为单数、双数）；深刻地划分可以分为素数，合数，“1”等。

数论概述也就是说，任意两个或两个以上的整数相加、相减、相乘的3数论概述

数论这门学科最初就是从研究整数开始的，所以叫做整数论。后来整数论又进一步发展，就叫做数论了。确切的说，数论就是一门研究整数性质的学科。

数论这一数学分支，历史悠久，而且有着强大的生命力。数论问题叙述简明，“很多数论问题可以从经验中归纳出来，并且仅用三言两语就能向一个行外人解释清楚，但要证明它却远非易事”.数论概述 数论这门学科最初就是从研究整数开始的，所以叫做4数论的发展简况自古以来，数学家对于整数性质的研究一直十分重视，但是直到十九世纪，这些研究成果还只是孤立地记载在各个时期的算术著作中，也就是说还没有形成完整统一的学科。我国古代，许多著名的数学著作中都有关于数论内容的论述，比如求最大公约数、勾股数组、某些不定方程整数解的问题等等。在国外，古希腊时代的数学家对于数论中一个最基本的问题——整除性问题就有系统的研究，关于质数、合数、因数、倍数等一系列概念也已经被提出来应用了。数论的发展简况自古以来，数学家对于整数性质的研究一直十分重视5后来的各个时代的数学家也都对整数性质的研究做出过重大的贡献，使数论的基本理论逐步得到完善。在整数性质的研究中，人们发现质数是构成正整数的基本“材料”，要深入研究整数的性质就必须研究质数的性质。因此关于质数性质的有关问题，一直受到数学家的关注。到了十八世纪末，历代数学家积累的关于整数性质零散的知识已经十分丰富了，把它们整理加工成为一门系统的学科的条件已经完全成熟了。后来的各个时代的数学家也都对整数性质的研究做出过重大的贡献，6 德国数学家高斯集中前人的大成，写了一本书叫做《算术探讨》，1800年寄给了法国科学院，但是法国科学院拒绝了高斯的这部杰作，高斯只好在1801年自己发表了这部著作。这部书开始了现代数论的新纪元。在《算术探讨》中，高斯把过去研究整数性质所用的符号标准化了，把当时现存的定理系统化并进行了推广，把要研究的问题和已知的方法进行了分类，还引进了新的方法。 德国数学家高斯集中前人的大成，写了一本书叫做《算术探讨》，7数论的基本内容数论形成了一门独立的学科后，随着数学其他分支的发展，研究数论的方法也在不断发展。如果按照研究方法来说，可以分成初等数论、解析数论、代数数论和几何数论四个部分。初等数论是数论中不求助于其他数学学科的帮助，只依靠初等的方法来研究整数性质的分支。比如中国古代有名的“中国剩余定理”，就是初等数论中很重要的内容。数论的基本内容数论形成了一门独立的学科后，随着数学其他分支的8关于“中国剩余定理”: 公元4-5世纪之交的《孙子算经》中有一个有趣的问题：“今有物不知其数，三三数之剩二；五五数之剩三；七七数之剩二。问：物几何？”秦九韶对同余方程组进行了系统的理论研究，在《数书九章》中创立了称之为大衍求一术的一整套算法，即把上述问题的解法推广至盛誉中外的“中国剩余定理”-----孙子定理。关于“中国剩余定理”:9

解析数论是使用数学分析作为工具来解决数论问题的分支。数学分析是以函数作为研究对象的、在极限概念的基础上建立起来的数学学科。用数学分析来解决数论问题是由欧拉奠基的，俄国数学家车比雪夫等也对它的发展做出过贡献。解析数论是解决数论中艰深问题的强有力的工具。比如，对于“质数有无限多个”这个命题，欧拉给出了解析方法的证明，其中利用了数学分析中有关无穷级数的若干知识。解析数论是使用数学分析作为工具来解决数论问题的分支。10

二十世纪三十年代，苏联数学家维诺格拉多夫创造性的提出了“三角和方法”，这个方法对于解决某些数论难题有着重要的作用。我国数学家陈景润在解决“哥德巴赫猜想”问题中使用的是解析数论中的筛法。 二十世纪三十年代，苏联数学家维诺格拉多夫创造性的提出了“三11代数数论是把整数的概念推广到代数整数的一个分支。数学家把整数概念推广到一般代数数域上去，相应地也建立了素整数、可除性等概念。几何数论是由德国数学家、物理学家闵可夫斯基等人开创和奠基的。几何数论研究的基本对象是“空间格网”。什么是空间格网呢？在给定的直角坐标系上，坐标全是整数的点，叫做整点；全部整点构成的组就叫做空间格网。空间格网对几何学和结晶学有着重大的意义。由于几何数论涉及的问题比较复杂，必须具有相当的数学基础才能深入研究。代数数论是把整数的概念推广到代数整数的一个分支。数学家把整数12数论是一门高度抽象的数学学科，长期以来，它的发展处于纯理论的研究状态，它对数学理论的发展起到了积极的作用。但对于大多数人来讲并不清楚它的实际意义。由于近代计算机科学和应用数学的发展，数论得到了广泛的应用。比如在计算方法、代数编码、组合论等方面都广泛使用了初等数论范围内的许多研究成果；有文献报道，现在有些国家应用“孙子定理”来进行测距，用原根和指数来计算离散傅立叶变换等。数论是一门高度抽象的数学学科，长期以来，它的发展处于纯理论的13此外，数论的许多比较深刻的研究成果也在近似分析、差集合、快速变换等方面得到了应用。特别是现在由于计算机的发展，用离散量的计算去逼近连续量而达到所要求的精度已成为可能。数论在数学中的地位是独特的，高斯曾经说过“数学是科学的皇后，数论是数学中的皇冠”。因此，数学家都喜欢把数论中一些悬而未决的疑难问题，叫做“皇冠上的明珠”，以鼓励人们去“摘取”。下面简要列出几颗“明珠”：费尔马大定理、孪生素数问题、歌德巴赫猜想、圆内整点问题、完全数问题……此外，数论的许多比较深刻的研究成果也在近似分析、差集合、快速14费尔马大定理：起源于三百多年前，挑战人类3个世纪，多次震惊全世界，耗尽人类众多最杰出大脑的精力，也让千千万万业余者痴迷。终于在1994年被安德鲁·怀尔斯攻克。古希腊的丢番图写过一本著名的“算术”，经历中世纪的愚昧黑暗到文艺复兴的时候，“算术”的残本重新被发现研究。1637年，法国业余大数学家费尔马（PierredeFremat）在“算术”的关于勾股数问题的页边上，写下猜想：a^n+b^n=c^n是不可能的（这里n大于2；a，b，c，n都是非零整数)。此猜想后来就称为费尔马大定理。费尔马大定理：起源于三百多年前，挑战人类3个世纪，多次震惊全15

费尔马还写道“我对此有绝妙的证明，但此页边太窄写不下”。一般公认，他当时不可能有正确的证明。猜想提出后，经欧拉等数代天才努力，200年间只解决了n＝3,4,5,7四种情形。1847年，库木尔创立“代数数论”这一现代重要学科，对许多n（例如100以内）证明了费尔马大定理，是一次大飞跃。

费尔马还写道“我对此有绝妙的证明，但此页边太窄写不下”。一16

历史上费尔马大定理高潮迭起，传奇不断。其惊人的魅力，曾在最后时刻挽救自杀青年于不死。他就是德国的沃尔夫斯克勒，他后来为费尔马大定理设悬赏10万马克（相当于现在160万美元多），期限1908－2007年。无数人耗尽心力，空留浩叹。最现代的电脑加数学技巧，验证了400万以内的N，但这对最终证明无济于事。1983年德国的法尔廷斯证明了：对任一固定的n，最多只有有限多个a，b，c振动了世界，获得费尔兹奖（数学界最高奖）。 历史上费尔马大定理高潮迭起，传奇不断。其惊人的魅力，曾在最17历史的新转机发生在1986年夏，贝克莱·瑞波特证明了:费尔马大定理包含在“谷山丰—志村五朗猜想”之中。童年就痴迷于此的怀尔斯，闻此立刻潜心于顶楼书房7年，曲折卓绝，汇集了20世纪数论所有的突破性成果。终于在1993年6月23日剑桥大学牛顿研究所的“世纪演讲”最后，宣布证明了费尔马大定理。立刻震动世界，普天同庆。不幸的是，数月后逐渐发现此证明有漏洞，一时更成世界焦点。历史的新转机发生在1986年夏，贝克莱·瑞波特证明了:费尔马18这个证明体系是千万个深奥数学推理连接成千个最现代的定理、事实和计算所组成的千百回转的逻辑网络，任何一环节的问题都会导致前功尽弃。怀尔斯绝境搏斗，毫无出路。1994年9月19日，星期一的早晨，怀尔斯在思维的闪电中突然找到了迷失的钥匙：解答原来就在废墟中！他热泪夺眶而出。怀尔斯的历史性长文“模椭圆曲线和费尔马大定理”1995年5月发表在美国《数学年刊》第142卷，实际占满了全卷，共五章，130页。1997年6月27日，怀尔斯获得沃尔夫斯克勒10万马克悬赏大奖。离截止期10年，圆了历史的梦。他还获得沃尔夫奖(1996.3），美国国家科学家院奖（1996.6），费尔兹特别奖（1998.8）。这个证明体系是千万个深奥数学推理连接成千个最现代的定理、事实19孪生素数问题：

孪生素数是指一对素数，它们之间相差2。例如3和5，5和7，11和13，10016957和10016959等等都是孪生素数。孪生素数猜想，即是否存在无穷多对孪生素数，是数论中未解决的一个重要问题。 哈代-李特尔伍德猜想（Hardy-Littlewoodconjecture）是孪生素数猜想的一个增强形式，猜测孪生素数的分布与素数定理中描述的素数分布规律相类似。1900年希尔伯特在国际数学家大会上说有了素数公式，哥德巴赫猜想和孪生素数猜想都可以得到解决。孪生素数问题： 孪生素数是指一对素数，它们之间相差2。例如320素数定理素数定理描述素数的大致分布情况。素数的出现规律一直困惑著数学家。一个个地看，素数在正整数中的出现没有什么规律。可是总体地看，素数的个数竟然有规可循。对正实数x，定义π(x) 为不大于x的素数个数。数学家找到了一些函数来估计π(x)的增长。以下是第一个这样的估计。π(x)≈x/lnx其中lnx为x的自然对数。上式的意思是当x趋近∞，π(x)和x/lnx的比趋近1.（注：该结果为高斯所发现）。素数定理素数定理描述素数的大致分布情况。素数的出现规律一直21歌德巴赫猜想：哥德巴赫猜想的由来1729年~1764年，哥德巴赫与欧拉保持了长达三十五年的书信往来。在1742年6月7日给欧拉的信中，哥德巴赫提出了一个命题。他写道："我的问题是这样的：随便取某一个奇数，比如77，可以把它写成三个素数之和：77=53+17+7；再任取一个奇数，比如461，461=449+7+5，也是三个素数之和，461还可以写成257+199+5，仍然是三个素数之和。这样，我发现：任何大于5的奇数都是三个素数之和。歌德巴赫猜想：哥德巴赫猜想的由来22歌德巴赫猜想：但这怎样证明呢？虽然做过的每一次试验都得到了上述结果，但是不可能把所有的奇数都拿来检验，需要的是一般的证明，而不是个别的检验。"欧拉回信说：“这个命题看来是正确的”。但是他也给不出严格的证明。同时欧拉又提出了另一个命题：任何一个大于2的偶数都是两个素数之和，但是这个命题他也没能给予证明。不难看出，哥德巴赫的命题是欧拉命题的推论。歌德巴赫猜想：但这怎样证明呢？虽然做过的每一次试验都得到了上23歌德巴赫猜想事实上，任何一个大于5的奇数都可以写成如下形式：2N+1=3+2(N-1)，其中2(N-1)≥4。若欧拉的命题成立， 则偶数2N可以写成两个素数之和，于是奇数2N+1可以写成三个素数之和，从而，对于大于5的奇数，哥德巴赫的猜想成立。但是哥德巴赫的命题成立并不能保证欧拉命题的成立。因而欧拉的命题比哥德巴赫的命题要求更高。 现在通常把这两个命题统称为哥德巴赫猜想。即1.每个不小于6的偶数都可以表示为两个奇素数之和；2.每个不小于9的奇数都可以表示为三个奇素数之和。歌德巴赫猜想事实上，任何一个大于5的奇数都可以写成如下形式：24中国数学家的贡献

华罗庚是中国最早从事哥德巴赫猜想的数学家。1936～1938年，他赴英国剑桥大学留学，在哈代的指导下从事数论研究，并开始研究哥德巴赫猜想，取得了很好的成果，证明了对于“几乎所有”的偶数，猜想（1）都是正确的。1950年，华罗庚从美国回国，在中科院数学研究所组织数论研究讨论班，选择哥德巴赫猜想作为讨论的主题，倡议并指导他的一些学生研究这一问题。中国数学家的贡献 华罗庚是中国最早从事哥德巴赫猜想的数学家。25

他曾对学生们说：“我并不是要你们在这个问题上作出成果来。我的着眼点是哥德巴赫猜想跟解析数论中所有的重要方法都有联系，以哥德巴赫猜想为主题来学习，将可以学会解析数论中所有的重要方法……哥德巴赫猜想真是美极了，现在还没有一个方法可以解决它。”参加这个数论讨论班的学生有王元、潘承洞和陈景润等。 他曾对学生们说：“我并不是要你们在这个问题上作出成果来。我26出乎华罗庚的意料，学生们在哥德巴赫猜想的证明上取得了相当好的成绩。1956年，王元证明了“3＋4”；同年，原苏联数学家阿·维诺格拉朵夫证明了“3＋3”；1957年，王元又证明了“2＋3”；潘承洞于1962年证明了“1＋5”；1963年，潘承洞、巴尔巴恩与王元又都证明了“1＋4”；1966年，陈景润在对筛法作了新的重要改进后，证明了“1＋2”。出乎华罗庚的意料，学生们在哥德巴赫猜想的证明上取得了相当好的27

1974年，由英国数学家哈勃斯坦和西德数学家李希特合著的《筛法》一书出版，书中以“陈氏定理”作为最后一章的标题。书中写道：“我们本章的目的是为了证明陈景润下面的惊人定理，我们在前10章已经付印时才注意到这一结果。从筛法的任何方面来说，它都是光辉的顶点。”华罗庚曾对王元说：“在我的学生的工作中，最使我感动的是‘1＋2’。 1974年，由英国数学家哈勃斯坦和西德数学家李希特合著的《28初等数论与中学教学

在中学数学学习过程中，初等数论的知识和思想方法是常见的。在《普通高中·数学课程标准》中，初等数论初步是作为选修课程系列4的一个专题，教师在日常教学中要给予足够的重视。随着新课程改革的逐步深入，初等数论知识和思想方法，一方面出现在日常教学中，另一方面是以竞赛的形式出现的，后者更为突出。对于前者《课标》是这样要求的，该专题是为对数学有兴趣和希望进一步提高数学素养的学生而设置的，所涉及的内容反映了某些重要的数学思想方法，有助于学生进一步打好数学基础，提高应用意识，有助于学生终身的发展，有助于扩展学生的数学视野，有助于提高学生对数学的科学价值、应用价值、文化价值的认识。初等数论与中学教学在中学数学学习过程中，初等数论的知29初等数论与中学教学对于后者，初等数论在奥林匹克竞赛中占有愈来愈重要的地位，对提高中学生的数学素养很有帮助。有人说：“用以发现天才，在初等数学中再也没有比数论更好的课程了。任何学生，如能把当今任何一本数论教材中的习题做出，就应当受到鼓励，并劝他将来从事数学方面的工作。”所以在国内外各级各类的数学竞赛中，数论问题总是占有相当大的比重。初等数论与中学教学对于后者，初等数论在奥林匹克竞赛中占有愈来30初等数论与中学教学

致力于数学竞赛的教师而言，必须明确数论的基本结构，它包括整除理论，同余理论和不定方程。

整除理论是初等数论的基础，它是在带余除法的基础上建立起来的，整除理论的中心内容是算术基本定理和最大公因数理论。同余理论是初等数论的核心，它是数论所特有的思想、概念与方法。从历史来看，求解不定方程是推进数论发展的最重要的课题，它是建立在整除理论和同余理论上来进行求解的。初等数论与中学教学致力于数学竞赛的教师而言，必须明确31

整除理论——因数和倍数定义设a,b为整数，a≠0.若有一整数q,使得b=aq,则称a是b的因数为是a的倍数;并称a整除b,记为a|b,可形式地表示为:a|b:=(

q)(b=aq)若a不能整除b，记为a\b.若b=aq,而a既非b又非1,则称a是b的真因数.整除理论——因数和倍数定义设a,b为整数，a≠0.若32因数和倍数关于整除，显然有下列定理：定理①对所有a,1|a.②对所有a,a|0.③对所有a,a|a.④若a|b且b|c,则a|c.⑤若a|b,则对任意的c,有ac|bc.⑥若ac|bc且c≠0,则a|b.因数和倍数关于整除，显然有下列定理：33因数和倍数⑦若a|b且a|c,则对任意的m,n,有a|(bm+cn).⑧若a|b,则b=0或|a|≤|b|,其中|a|是a的绝对值,当a≥0时|a|=a;当a＜0时|a|=-a.⑨若a|b,则(-a)|b,a|(-b),(-a)|(-b),|a|||b|.证明只证明⑦,余下不难证明.⑦因为a|b且a|c,故b=aq1和c=aq2.于是,bm+cn=a(q1m+q2n),所以,a|(bm+cn).因数和倍数⑦若a|b且a|c,则对任意的m,n,有34因数和倍数定理

若a是b的真因数,则1＜|a|＜|b|.定理

若a为是整数,且|a|＜|b|,|b|||a|,则

a=0.证明因为|b|||a|,故有整数q,使得|a|=|b|q.若|a|=0,则a=0.若|a|>0,则由于0<|a|<|b|和|a|=|b|q,有q≥0.若q>0,则由q是整数而有q≥1.由|a|=|b|和q≥1有|a|>|b|,这与|a|<|b|矛盾,故q=0;若q=0和|a|=|b|q有a=0.因数和倍数定理若a是b的真因数,则1＜|a|35因数和倍数定理(带余除法)若a为是二个整数,b≠0,则唯一存在两个整数q和r,使得下式成立:a=bq+r,0≤r<|b|.因数和倍数定理(带余除法)若a为是二个整数,b≠0,则唯一36素数和合数在正整数中,1只能被它本身整除.任何大于1的整数都至少能被1和它本身整除．定义一个大于1且只能被1和它本身整除的整数,称为素数;否则,称为合数.由该定义可知，正整数集合可分三类:素数、合数和1.素数常用p或p1,p2…,来表示.素数和合数在正整数中,1只能被它本身整除.任何大于1的整37最大公因数和最小公倍数定义设al,a2,…,an和d都是正整数,n≥2.若d|ai,1≤i≤n,则称d是al,a2,…,an.的公因数.在公因数中最大的那一个数,称为al,a2,…,an的最大公因数,记为gcd{al,a2,…,an}.(greatestcommondivisor)或者(al,a2,…,an).若gcd(al,a2,…,an)=1,称al,a2,…,an是互素的.最大公因数和最小公倍数定义设al,a2,…,an和d都是正38最大公因数和最小公倍数定理设a和b都是正整数,且a>b,a=bq+r0<r<b其中q和r都是正整数.则:①a和b的任一公因数也是b和r的公因数；②b和r的任一公因数也是a和b的公因数；③(a,b)=(b,r);④若(a,b)=d,则(a|d,b|d)=1.最大公因数和最小公倍数定理设a和b都是正整数,且a>b,39整数分解唯一性定理定理(整数分解唯一性定理)每个大于1的正整数a均可分解成有限个素数之积,并且若不计素因数的次序,其分解是唯一的.证明先证分解式的存在性.若a=2,则2为素数,从而2即所求分解式.现在假设小于a的每个正整数均可分解成有限个素数之积.考虑a,若a是素数,则证毕.否则a便有真因数d,而a=cd,其中c和d均是大于1的正整数,并且c和d均小于a.由归纳假设,c和d均有分解式c=p1p2…pk和d=q1q2…ql,其中p1,p2,…,pk,ql,q2,…,ql均是素数.因此a=cd=p1p2…,pkql…ql;即为所求的分解式．整数分解唯一性定理定理(整数分解唯一性定理)每个大于1的正40整数分解唯一性定理再证唯一性.当a=2时,分解式显然是唯一的.现设比a小的正整数其分解式均是唯一的.考虑正整数a,假设a有两个分解式a=plp2…pk和a=q1q2…ql,其中pl,p2,…,pk和q1,q2,…,ql都是素数.于是p1|q1q2…ql,根据定理7.4.7知必有一qi,,使得p1|qi.不妨令i=1,即p1|q1,显然p1=q1.令a’=a/p1,则a’=p2p3…pk,a’＝q2q2…ql.若a’=1,则a=p1=q1,即a’的分解式唯一.若a’＞1,注意到a’<a,从而由归纳假设知,a’的分解式是唯一的.因此k=l,并且p1=q1,…,pk=qk,再由p1=ql,知a分解式也是唯一的.整数分解唯一性定理再证唯一性.当a=2时,分解式显然是唯41整数分解唯一性定理若将n的分解式中相同素因数合并为它的幂数,则任意大于1的整数a只能分解成一种形式:

,n≥1,其中p1,p2,…,pn是互不相同的素数,al,a2,…,an是正整数.并称(1)

是a的标准分解式.整数分解唯一性定理若将n的分解式中相同素因数合并为它的幂数42函数[x]与{x}定义设x是实数，以[x]表示不超过x的最大整数，称它为x的整数部分，又称{x}=x-[x]为x的小数部分。函数[x]与{x}定义设x是实数，以[x]表示不超过x的43函数[x]与{x}函数[x]与{x}44函数[x]与{x}函数[x]与{x}45不定方程不定方程 ：未知数个数多于方程个数，且对解有一定限制（比如要求解为正整数等）的方程。是数论中最古老的分支之一。古希腊的丢番图早在公元3世纪就开始研究不定方程，因此常称不定方程为丢番图方程。不定方程不定方程 ：46

研究不定方程要解决三个问题：①判断何时有解。②有解时决定解的个数。③求出所有的解。中国是研究不定方程最早的国家，公元初的五家共井问题就是一个不定方程组问题，公元5世纪的《张丘建算经》中的百鸡问题标志中国对不定方程理论有了系统研究。秦九韶的大衍求一术将不定方程与同余理论联系起来。百鸡问题说：“鸡翁一，直钱五，鸡母一，直钱三，鸡雏三，直钱一。百钱买百鸡，问鸡翁、母、雏各几何？”。设x，y，z分别表鸡翁、母、雏的个数，则此问题即为不定方程组的非负整数解x，y，z，这是一个三元不定方程组问题。研究不定方程要解决三个问题：①判断何时有解。47

不定方程问题的常见类型（1）求不定方程的解；（2）判定不定方程是否有解； （3）判定不定方程的解的个数（有限个还是无限个）。 不定方程问题的常见类型48

解不定方程问题常用的解法（1）代数恒等变形：如因式分解、配方、换元等；（2）不等式估算法：利用不等式等方法，确定出方程中某些变量的范围，进而求解；（3）同余法：对等式两边取特殊的模（如奇偶分析），缩小变量的范围或性质，得出不定方程的整数解或判定其无解；（4）构造法：构造出符合要求的特解，或构造一个求解的递推式，证明方程有无穷多解；（5）无穷递推法。 一些特殊方程的求解方法 解不定方程问题常用的解法49同余理论定义给定一正整数m,若用m去除两个整数a和b所得余数相同,则称a为对模m同余,记作a

b(modm);若余数不同,则称a为对模m不同余,记作a

b(modm).显然，a0(modm)iffm|a.由同余的定义,可得下列简单性质:①自反性:a

a(modm).②对称性:若a

b(modm),则b

a(modm).③传递性:若a

b(modm),b

c(modm),则:a

c(modm).可见,同余关系是等价关系.同余理论定义给定一正整数m,若用m去除两个整数a和b所50同余理论定理整数a,b对模m同余，若m|(a-b),

即:a

b(modm),若m|(a-b).证明设a

b(modm),则a=mq1+r,b=mq2+r,0≤r<m.故(a-b)=m(q1-q2),m|(a-b).反之,设a=mq1+r1,b=mq2+r2,0<r1≤m,0<r2≤m,m|(a-b).于是,m|(a-b)=m(ql-q2)+(rl-r2),故:m|(r1-r2).又因|r1-r2|<m,得r1=r2.同余理论定理整数a,b对模m同余，若m|(a-b),51同余理论由定理可知,同余又可定义如下:若m|(a-b),则称a为对模m同余.定理若a

b(modm),c

d(modm),则:①ax+cy

bx+dy(modm),其中x和y为任给整数.②ac

bd(modm).③an

bn(modm),其中n＞0.④f(a)f(b)(modm),其中f(x)为任给的一个整系数多项式.同余理论由定理可知,同余又可定义如下:52同余理论证明①因为m|(a-b),m|(c-d),故有m|x(a-b)+y(c-d)=(ax+cy)-(bx+dy).②由m|(a-b)+b(c-d)=ac-bd立即可得.③由于a-b=mq,其中q是一整数,因此:an=(b+mq)n=bn+Cn1bn-1(mq)1+…+Cnn-1b1(mq)n-1+(mq)n=bn+mq,其中:q1是一整数.所以,an

bn(modm).④由①和③可证.同余理论证明53同余式定义和基本性质定理正整数a能被9整除，若9整除a的十进制表示各数字的和．则由10i1(mod9)(i=1,2,…,n)和定理可得:

同余式定义和基本性质定理正整数a能被9整除，若9整除a54同余理论定理若ac=bc(modm),(c,m)=d,则a

b(mod(m/d))证明因为m|c(a-b),于是(m/d)|((a-b)(c/d)),又因为(c,m)=d,则有((c/d,m/d)=1,因此由定理7.4.2知,(m/d)|(a-b),即:a

b(mod(m/d)).显然,由本定理可得如下推论.推论若ac=bc(modm),(c,m)=1,则:a

b(modm).同余理论定理若ac=bc(modm),(c,m)=d,55同余理论定理①若a

b(modm),且d|m,则:a

b(modm).③若a

b(modm),则(a,m)=(b,m).③a

b(modmi),(1≤i≤n),iffa

b(mod[m1,m2,…,mn]).证明只给出③的证明,①和②读者完成.③必要性:由①知,是成立的.充分性:若a

b(modmi),1≤i≤n,则:mi|(a-b),1≤i≤n,即(a-b)是m1,m2,…,mn的公倍数,从而也是[m1,m2,…,mn]的倍数,因此:a

b(mod[m1,m2,…,mn]).同余理论定理56不定方程不定方程57以下题目选自1998年～2008年全国初中数学联赛试题、初一、初二数学希望杯竞赛试题（部分）以下题目选自1998年～2008年全国初中数学联赛试题、初一58有关整除的问题有关整除的问题59有