初等数论中地几个重要定理(竞赛必备)

1、初等数论中的几个重要定理基础知识定义（欧拉（Euler）函数）一组数工称为是模吨的既约剩余系，如果对任意的：' , '"1且对于任意的-心二，若=1,则有且仅有一个 I是宾对模吨的剩余，即：m»。并定义' 1 .中和“互质的数的个数， -称为欧拉（Euler）函数。这是数论中的非常重要的一个函数，显然-,而对于讥匸-, f 就是1,2，,代一中与w互素的数的个数，比如说 芒是素数，则有 f '-。卩O）二阳-口 G-引理：;可用容斥定理来证（证明略）。定理1 :（欧拉（Euler）定理）设 n： = 1，则一"：；.。分析与解答：要

2、证一 ' 一I ：.，我们得设法找出个齐相乘，由-个数我们想到中与勺互质的；? '的个数：'八，由于 一 =1，从而 "W S"也是与円互质的个数，且两两余数不一样， 故，' 三 皿1卫口茄旳%町三/和”叭.口附）严站税），而（叭勺.口的）鳴）=1， 故八-：.。证明：取模喇的一个既约剩余系- ''' -丁"： 考虑心 vC：，由于文与空互质，故：":. '' '仍与汽:互质，且有 J I. "'：，于是对每 个_二_二_都能找到唯一的一个二二_，使得&qu

3、ot;.-:r ，这种对应关系（必j） 口右创（妣如）匸肉3嘶川（nh；）（口妇驱咖）网 口划）=1?是一一的，从而，护=l（rnod 故川紀三l（tnod潮）。证毕。这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。定理2 :（费尔马（Fermat ）小定理）对于质数及任意整数主有''-'"二。设”为质数，若戈是&的倍数，则Y 一。若；不是兰的倍数，则！ 口 由引理及欧拉定理得I ：；l- ' /，一宀一 _J ,由此即得。定理J推论：设&为质数，煮是与口互质的任一整数，则/ 。定理3 :（威

4、尔逊（Wils on ）定理）设亍为质数，则。分析与解答：受欧拉定理的影响，我们也找L -个数，然后来对应乘法。证明：对于.' / ，在:中，必然有一个数除以尹余1，这是因为宀-则好是-"的一个剩余系去0。从而对b卞巴戸-卩，（1,2-,戸一1，使得；若 2i忙旳血0日誉），（尽勿=】，则用31-此）。血皿戸），p丨Vi -旳），故 对于F，有迂八。即对于不同的疋对应于不同的"，即- '亠中数可两两配对，其积除以 F余1，然后有芒，使:一"1 ，即与它自己配对，这时疋_1二°血朋勿，（斗+巩忑-1）°血加勿，兀三1或忙1血抑并）

5、， X = P 1 或天=1。除2 一外，别的数可两两配对，积除以余1。故-'-；，' -O定义：设 匚山 为整系数多项式（），我们把含有二的一组同余式/兀）O（rW竹）（1"“）称为同余方组程。特别地，当办均为尤的一次整系 数多项式时，该同余方程组称为一次同余方程组若整数疋同时满足：'' ' _1 ''''<'"殳，则剩余类 胚二刘工总乙天匚（mod朋）（其中聊二蚀叫叫）称为同余方程组的一个解，写作一 ，；定理4 :（中国剩余定理）设'<:，：?；- '"

6、，：'；-是两两互素的正整数，那么对于任意整数，一次同余方程组：-L ,"必有解，且解可以写为：工s晒坷码+ M2舷?2 + "" +施0以（mo d曲）M. = （1<j这里隠二叫遇叫，i阻，以及眄满足叫川汗1（血同叫）,:-宀（即C为叮对模t的逆）。中国定理的作用在于它能断言所说的同余式组当模两两互素时一定有解，而对于解的 形式并不重要。定理5 :（拉格郎日定理） 设决是质数，：'是非负整数，多项式八"'+，/|-是一个模八为'；'次的整系数多项式（即° ' 程-'：'二

7、至多有专个解（在模有意义的情况下）。定理6 :若为：对模吃的阶，为某一正整数，满足-'，则三必为的倍数。以上介绍的只是一些系统的知识、 方法，经常在解决数论问题中起着突破难点的作用。 另外 还有一些小的技巧则是在解决、 思考问题中起着排除情况、辅助分析等作用，有时也会起到2 fl（mod8）川为奇数时2 f0（mod9） 3整除川时M）1 黑 <意想不到的作用，如：，。这里我们只介绍几个较为直接的应用这些定理的例子。典例分析例1.设1,求证：T J -。证明：因为-_ 一 工，故由：知”丨小一 ，从而-1.、-亠|-,但是贰7） = 6,奴13） = 12 ,故由欧拉定理得：0

8、m （戊于mL l（tna时石，/二l（m町时1?）， 从而宀唤車；同理，屮二1血閃91）。于是十一沪二1一1二0（忆期91） 即91|（盯一0）。注明：现考虑整数 二的幕X所成的数列：匚''若有正整数使八一“I，则有二口'（mod空），其中冷=七©+几0乞厂k ；因而关于丄 ,数列的项依次同余于r " ' -; " 一二 这个数列相继的匕项成一段，各段是完全相同的，因而是周期数列。如下例：例2 .试求不大于100，且使 "I ' 成立的自然数的和。解：通过逐次计算，可求出 -：1关于U-的最小非负剩余（即为被 1

9、1除所得的余数）为：归 刖11）罗-9（modlT）33?5（moiMX 3*4（modll）35 三 4x3工 l（modl 1）因而通项为丁的数列的项的最小非负剩余构成周期为5的周期数列：3 , 9 , 5 , 4 , 1 , 3, 9 , 5 , 4 , 1 ,类似地，经过计算可得'的数列的项的最小非负剩余构成周期为10的周期数列：7, 5，2，3，10，4，6，9，8，1，于是由上两式可知通项为匸 “ -的数列的项的最小非负剩余，构成周期为10 （即上两式周期的最小公倍数）的周期数列：3 , 7 , 0 , 0 , 4, 0, 8 , 7 , 5 , 6 ,这就表明，当：n：时

10、，当且仅当十_加,时,|'r ' 111 ,即 1''；又由于数列的周期性，故当l 1二匚二-儿1时，满足要求的只有三个，即垃二10上+310上+ 4丄0上+ 6从而当时，满足要求的的和为：9»*2（10-t-b3）+（10t+（；lCfc+&） = 230 + 13 = 30Z+10xl3 = 30x45+130=MSOJt-0JU）JU）.下面我们着重对Fetmat小定理及其应用来举例：+乙例3 .求证：对于任意整数工一，-是一个整数。1 工证明：令',则只需证 -；厂 "是15的倍数即可。由3，5是素数及Fetmat小定

11、理得则录 + 5x3 -l x= -I- 7x = Ofmod 力；3rs + 5x? +7工=2xr+ x = 0(mod 习而（3，5）=1，故"1'，即X是15的倍数。所以-是整数。例4 .求证：'严为任意整数）。证明：令侃）=0-用，则呛11）（鳧+1）窗1+1）閒-冲+ 1）（*）；所以；1含有因式由Fetmat小定理，知又13 , 7, 5, 3 , 2两两互素，所以2730=：-'*能整除卞 ；。例5设'是直角三角形的三边长。如果 -'是整数，求证：可以被30整除。若 2-< ,2证明：不妨设芒是直角三角形的斜边长，则 c

12、则'_ r '-1_又因为"! _ r .矛盾！所以2|丸:.若 3，3 1 产，3 C，因为宀 ' 1-，则，；：-1 - 1 - ：又厂 -丄：，矛盾！从而 3|.；.，5因为(5jt±l)a-l(rnod5J (毀 ±2)彳-l(mGd5)所以"二或 o(m°d5)与，!-矛盾！从而 5|-；丁：.又(2,3,5)=1 ，所以 30| * :'.下面讲述中国剩余定理的应用例6 .证明：对于任意给定的正整数'，均有连续T个正整数，其中每一个都有大于1的平方因子。证明：由于素数有无穷多个， 故我们可以取

13、盒'个互不相同的素数-E,而考虑同余 组：-；2 2 2因为-显然是两两互素的，故由中国剩余定理知，上述同余组有正整数解。2 2 2于是，连续打个数分别被平方数 1"； 整除。注：（1 ）本题的解法体现了中国剩余定理的一个基本功效，它常常能将“找连续7个正整数具有某种性质”的问题转化为“找个两两互素的数具有某种性质”，而后者往往是比较容易解决的。（2）本题若不直接使用素数，也中以采用下面的变异方法：由费尔马数-J： '- - '：122厂两两互素，故将中的'厂转化为,J/:后，相应的同余式也有解，同样可以导出证明。例7.证明：对于任意给定的正整数町，均

14、有连续T个正整数，其中每一个都不是幕数。分析：我们来证明，存在连续 葺个正整数，其中每一个数都至少有一个素因子，在这个数的 标准分解中仅出现一次，从而这个数不是幕数。证明：取V个互不相同的素数，考虑同余组-"- 心八12 2 2因为7 显然是两两互素的，故由中国剩余定理知，上述同余组有正整数解。对于因为,故二，但由式可知J ' I,即厂在L的标准分解中恰好出现一次，故 I-都不是幕数。例8 .设宀是给定的偶数，是偶数。证明：存在整数 工“使得 -,且， 。证明：我们先证明，当 专为素数幕时结论成立。实际上，能够证明，存在"使若匸 一，则条件表明为偶数，此时可取-;若匸-,则一 一与'