初等数论中的几个重要定理 引理 和推论

1、初等数论中的几个重要定理基础知识定义（欧拉（Euler）函数）一组数可卫2,，称为是模険的既约剩余系，如果对任意 的1牛（亏的）=1且对于任意的応？，若（恥）=1，则有且仅有一个心是对模 聊的剩余，即勺并定义阴= =（12屈中和聊互质的数的个数,勿朋）称为欧拉（Euler ）函数。这是数论中的非常重要的一个函数，显然帆D = l,而对于険1,疑欣）就是1,2,欣一1中与険互素的数的个数，比如说戸是素数，则有帆勿=戸一1。引理：；可用容斥定理来证（证明略）。引理：；可用容斥定理来证（证明略）。定理1：（欧拉（Euler）定理）设仏陀）=1，贝严的三l（nwd燃）。分析与解答：要证/欄三1血加网，

2、我们得设法找出疑枕）个相乘，由疑琬个数我们想到12我们想到12，然中与那互质的强漉）的个数:眄宀，卫畑，由于仏的）=1，从而叫叫，叫也也是与然互质的念）个数，且两两余数不一样，故眄叫冏三，而（吐g）=i.住的，处2,，加冏也三茂贰柚ai 13，而（吐g）=i.故屮网三l（nwd琬）。证明：取模欣的一个既约剩余系忌皿疝），考虑叭3鮎曲，由于总与険互质，故珂仍与燃互质，且有込叫于是对每 个1 “出都能找到唯一的一个15曲，使得必厂认価品初，这种对应关系b匸0乌）三匸如亦伽）三匸乌.（modm）a5匸也J三口即（mo伽）是一一的，从而沁*沁，- 曲N，故9 .亍三l（nwd燃）故屮的三l（nwd燃）

3、 证比，故这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩 余系来解决问题。定理2：（费尔马（Fermat）小定理）对于质数芒及任意整数说有尬*三圧血。心壬）。设戸为质数，若说是戸的倍数，则圧三三班血法勿。若说不是戸的倍数，则伐刃T 由引理及欧拉定理得您）=F7沖三畑轴），沁三恥。執胪三问屈，由此即得。定理茁推论：设歹为质数，总是与0互质的任一整数，贝三1価。曲）。定理3：（威尔逊（Wilson）定理）设戸为质数，则9一1）1三一1血加切。分析与解答：受欧拉定理的影响，我们也找戸一1个数，然后来对应乘法。，在证明：对于2） = 1，在心，心-中，必然有一个数除以戸余

4、1,这是因为，在兀2兀心则好是F的一个剩余系去0。从而对写忑已门2尹_1,已1,2,，尹_1，使得砂三l（mod）；若础三心2（品戸），（兀芒）=1，贝旳）三0逐品勿，尹心_旳），故 对于戸，旳已12：戸-1，有明4品切。即对于不同的卞对应于不同的尹，即12,左-1中数可两两配对，其积除以戸余1,然后有疋，使忑三血閔盯，即与它自己配对，这时“ 一1三mClldP）, （” + 1）任一1）三（mc心,疋三一1或三1垃心戸），除=1卩一1夕卜，别的数可两两配对，积除以戸余1。故9一惦9-1）1三-1亦曲）。定义：设为整系数多项式（1至丿至丘），我们把含有X的一组同余式心= O（nwW（1乞称为同

5、余方组程。特别地，当（初均为疋的一次整系 数多项式时，该同余方程组称为一次同余方程组若整数亡同时满足：门三航吋，则剩余类Mc = xxeZ,xc（m）（其中稠=硯，叫，,他）称为同余方程组的一个解，写作忑三沁皿）定理4：（中国剩余定理）设叫叫叫是两两互素的正整数，那么对于任意整数 鬥叫，叫，一次同余方程组兀三叭伽品鹫），1勺金必有解，且解可以写为:x =+ M2 N2a2 H1- MH% (mod m)甌二一（10乞这里心刚叫叫，徨，以及旳满足叫三1（皿），曲赧（即为叫对模附的逆）。中国定理的作用在于它能断言所说的同余式组当模两两互素时一定有解，而对于解的 形式并不重要。定理5：（拉格郎日定理

6、）设戸是质数,，是非负整数，多项式了=X+% +呦 是一个模戸为次的整系数多项式（即戸*比），则同余方程三叽心至多有 个解（在模戸有意义的情况下）。定理6：若/为尬对模欣的阶，占为某一正整数，满足亍三畑艸，贝呼必为！的倍 数。以上介绍的只是一些系统的知识、方法，经常在解决数论问题中起着突破难点的作用。另外 还有一些小的技巧则是在解决、思考问题中起着排除情况、辅助分析等作用，有时也会起到O（mod?） 3整除”时_0（mod3）环整除川时。这里我们O（mod?） 3整除”时_0（mod3）环整除川时。这里我们典例分析例 1.设（93例 1.设（93）i求证：证明：因为9I = 7xI3,故由，从

7、而7卫）= 1,（13卫）= 1,但是飙7） = 炉（13） = 12，故由欧拉定理得：卅三（卅尸三F三，和2三（垃。心3）,从而严三1血心1）；同理，沪三1血品汕。日 a12-i12 1-1 0(mod91)于疋，注明：现考虑整数总的幕/所成的数列：说卫-,/，若有正整数此使三购如）,则有/三 d/(nwd 険)则有/三 d/(nwd 険)其中因而关于m。璇燃），数列戈卫$，卫J的项依次同余于4込心代於心这个数列相继的疋项成一段，各段是完全相同的，因而是周期数列。如下例： 例2.试求不大于100，且使IM+严+4）成立的自然数的和。解：通过逐次计算，可求出于关于modH的最小非负剩余（即为被

8、11除所得的余数）为:33（modll）?32 XmodlDSCmodll）, 34 5x34（modl 1）;354x3= 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,这就表明，当1血创时，当且仅当农=3,40 时,+严

9、 +4三 O(modll),即 H| (3M +T +4)；又由于数列的周期性打故当1+1兰心灭+1）时，满足要求的只有三个，即占二10七 + 310七 + 4,10七 + 6从而当応总勺叩时,满足要求的的和为：2(10+3) + (l(k-99+ 4)+(l(k + Q = 230+13 = 30+10 x13 = 30 x45+130 = 1480 JUOM).下面我们着重对Fetmat 小定理及其应用来举例：l/+l?+lx例 3求证：对于任意整数315是一个整数。lx证明：令畑=乙5十1严+ 7疋耳15，则只需证呵= 3+5+仏是15的倍数即可。由 3 ， 5 是素数及 Fetmat小

10、定理得宀咖品讥三咖品3），则3严+砥了+7三 3x+ 7x = 0(mod 5)3x5 +5x3 +lx = 2x + x = 0(mod 3)9而（3, 5） =1,故引P+乐3+7x三即15/W是15的倍数。所以/W 是整数。例4.求证：2730 1讣f （为任意整数）。证明：令$竝二沪-丸，贝I了3)二呛-1)0 + 1)(起2+总+1)02-巴+ 1)(/+1)；所以/何含有因式分-丸冷-很总f卅7由 Fet mat 小定理，知 13| 一 蹟 7| 朮一心5 - ,33 ,22 - K又13，7，5，3，2两两互素，所以2730=门灯注心餐能整除川 7。例5.设恥 是直角三角形的三边

11、长。如果心疋是整数，求证:煤 可以被30整除。证明：不妨设匸是直角三角形的斜边长，贝I=*出。C则川二屮+护三1 + 1三0(皿均，又因为 =2)矛盾!所以2|必匕c,因为 al)_l&-g,则护 +护=1+I=2(mod3)，又亦心，矛盾！从而3|心护 +护=1+I=2(mod3)，又亦心，矛盾！从而3|心a，5，5c 因为號1尸三lmocl为 (5k -I(m0d5)所以护+护三2或o(mod5)与三10加矛盾!从而5| abc又(2,3,5)=1,所以 30| abc面讲述中国剩余定理的应用例6.证明：对于任意给定的正整数，均有连续起个正整数，其中每一个都有大于1的平 方因子。证明：由于

12、素数有无穷多个，故我们可以取挖个互不相同的素数P叫.孤,而考虑同余组 x 三一p2i = ln2n-n因为叭 4、从 显然是两两互素的，故由中国剩余定理知，上述同余组有正整数解。于是，连续找个数x + +旳分别被平方数巩4，化 整除。注：（1）本题的解法体现了中国剩余定理的一个基本功效，它常常能将“找连续个正整 数具有某种性质”的问题转化为“找个两两互素的数具有某种性质”，而后者往往是比较 容易解决的。（2）本题若不直接使用素数，也中以采用下面的变异方法：由费尔马数理二沪+g）两两互素，故将中的塚转化为用Ci2M）后，相应的同余式也 有解，同样可以导出证明。例7.证明：对于任意给定的正整数，均

13、有连续起个正整数，其中每一个都不是幕数。分析：我们来证明，存在连续个正整数，其中每一个数都至少有一个素因子，在这个数的 标准分解中仅出现一次，从而这个数不是幕数。证明：取挖个互不相同的素数孙卫节,恳，考虑同余组心一曲品小花2用 因为叭 4、从 显然是两两互素的，故由中国剩余定理知，上述同余组有正整数解。尺），即円对于1兰因为卄戸伽皿），故曲+讥但由式可知塚* 在 W 的标准分解中恰好出现一次，故*+都不是幕数。尺），即円例8.设朮是给定的偶数且*T）是偶数。，且证明：存在整数亿尹使得（兀挖）=3卫）=1，且疋+尹三疋血品。，且证明：我们先证明，当”为素数幕戸时结论成立。实际上，能够证明，存在兀歹使若J则条件表明疋为偶数，此时可取A疋-1； 若p2，则托=1丿二七_1与x=2,y=k-2中有一对满足要求。一般情形下，设*试瑣戸仁S,F是川的一个标准分解，上面已经证明，对每个刃存在整数可”使得同余式疋三再(moc!)(i =