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

1、第五节初等数论中的几个重要定理根底知识定义(欧拉(Euler)函数)一组数 x1,x2, ,xs称为是模 m的既约剩余系,如果对任意的1 j s, (Xj,m) 1且对于任意的a Z ,假设(a, m)= 1,那么有且仅有一个Xj是a对*H m 的剩余,即a Xj(modm).并定义(m) s 1,2, ,m中和m互质的数的个数, (m) 称为欧拉(Euler)函数.这是数论中的非常重要的一个函数,显然(1) 1 ,而对于m 1, (m)就是1,2,m 1中与m互素的数的个数,比方说p是素数,那么有 (p) p 1.,一 1、引理：(m) m(1);可用容斥定理来证(证实略).P|mPP为质数

2、定理 1：(欧拉(Euler)定理)设(a,m)=1,那么 a (m) 1(mod m).证实：取模m的一个既约剩余系 “也,bs,(s(m),考虑ab1 ,ab2, ,abs,由于a与m互质,故abj (1 j s)仍与m互质,且有 abiabj( 1 i j s),于是对每个1 js都能找到唯一的一个1(j) s ,使彳a abjb(mod m),这种对应关系 是sssss的,从而(abj)b (j)(modm)bj (modm),as( bj) ( bj)(mocm)oj 1j 1j 1j 1j 1s(m,bj) 1,as 1(mod m),故 a (m) 1(modm).证毕.j 1分

3、析与解答：要证 a (m) 1(mod m),我们得设法找出(m)个n相乘,由(m)个数我们想到1,2, m中与m互质的(m)的个数：a1,a2,a (m),由于(a, m) = 1 ,从而aa1,aa2, ,aa也是与 m互质的 (m)个数,且两两余数不一样,故 a a2 a aa1,aa2, , aa (m)a (m) a a? a (modm ),而(a a2a m)= 1,故 a (m) 1(mod m).这是数论证实题中常用的一种方法,使用一组剩余系,然后乘一个数组组成另外一组剩余系来解决问题.a(mod p).定理2：(费尔马(Fermat)小定理)对于质数p及任意整数a有ap设p

4、为质数,假设a是p的倍数,那么ap 0 a(mod p).假设a不是p的倍数,那么(a,p) 1 由引理及欧拉定理得(p) p 1,a (p) 1(modp),ap1 1(modp),ap a(modp),由此即得.一一*p 1定理2推论：设p为质数,a是与p互质的任一整数,那么ap1(modp).定理3：(威尔逊(Wilson )定理)设p为质数,那么(p 1)! 1(mod p).分析与解答：受欧拉定理的影响,我们也找 p 1个数,然后来对应乘法.证实：对于(x,p) 1 ,在x,2x, ,(p 1)x中,必然有一个数除以p余1,这是由于x,2x, , (p 1)x那么好是p的一个剩余系去

5、 0.从而对x 1,2,p1, y1,2, p 1,使得 xy 1(mod p);假设 xyxy2(m0dp) ,(x, p)1 ,那么 x(y y?) 0(mod p), p|(yy?),故对于0,丫2 1,2, , p 1,有xy xy2 (mod p).即对于不同的x对应于不同的 y ,即 1,2, , p 1中数可两两配对,其积除以 p余1,然后有x ,使x2 1(mod p),即与它自 己配对,这时 x2 1 0(mod p) , (x 1)(x 1) 0(mod p) , x 1或 x 1(mod p), x p 1 或 x 1.除x 1, p 1外,别的数可两两配对,积除以p余1

6、.故(p 1)! (p 1) 1 1(modp). 定义：设 匕(x)为整系数多项式(1 j k ),我们把含有x的一组同余式 fj (x) 0(modmj)(1 j k)称为同余方组程.特别地,当fi(x)均为x的一次整系数 多项式时,该同余方程组称为一次同余方程组.假设整数c同时满足：fj (c) 0(mod mj)1 j k,那么剩余类 M c x|x Z,x c(mod m)(其中 m m,m2, ,mJ)称为同 余方程组的一个解,写作x c(mod m)定理4：(中国剩余定理)设m1,m2, , mk是两两互素的正整数,那么对于任意整数a1,a2,ak, 一次同余方程组 x aj (

7、mod mj) , 1 j k必有解,且解可以写为:xM1N1alM2N2a2M kNkak(mod m)mi这里 m m1m2 mk, M , 一(1 i k),以及 N j 满足 M j N j 1(modmj), 1 j k(即Nj为Mj对卞Hmj的逆).中国定理的作用在于它能断言所说的同余式组当模两两互素时一定有解,而对于解的形式并不重要.定理5：(拉格郎日定理) 设p是质数,n是非负整数,多项式 f (x) anxna1x a0是一个模p为n次的整系数多项式(即 咻an),那么同余方程f (x) 0(modp)至多有n个 解(在模p有意义的情况下).定理6：假设l为a对卞m的阶,s为

8、某一正整数,满足 as 1(mod m),那么s必为l的倍数.以上介绍的只是一些系统的知识、 方法,经常在解决数论问题中起着突破难点的作用. 另外 还有一些小的技巧那么是在解决、 思考问题中起着排除情况、辅助分析等作用,有时也会起到意想不到的作用,如:1(mod 8) n为奇数时0(mod 4) n为偶数时0(mod9)3整除n时.这里我们0(mod 3) 3不整除n时只介绍几个较为直接的应用这些定理的例子.典例分析例 1.设(91,ab) 1,求证：91|(a12 b12).证实：由于 91 7 13,故由(91,ab) 1 知(91,a) 1 ,从而(7,a) 1,(13,a) 1 ,但是

9、(7) 6, (13) 12 ,故由欧拉定理得：a12 (a6)2 12 1(mod 7), a12 1(mod13),从而 a12 1(mod91)；同理,b12 1(mod91).于是,a12 b12 1 1 0(mod 91),即 91|(a12 b12).注明：现考虑整数a的哥an所成的数列：a,a2, ,an,假设有正整数k使ak 1(mod m),那么有 an ar (mod m),其中 n kq r,0 r k；因而关于mod(m),数列a,a2, ,an,的项依次同余于a,a2, ,ak, a,a2, ,ak, a,这 个数列相继的k项成一段,各段是完全相同的,因而是周期数列.

10、如下例： 例2.试求不大于100,且使11|(3n 7n 4)成立的自然数n的和.解：通过逐次计算,可求出 3n关于mod11的最小非负剩余(即为被11除所得的余数)为：3 3(mod11),32 9(mod11),33 5(mod11), 34 5 3 4(mod11),35 4 3 1(mod11)因而通项为3n的数列的项的最小非负剩余构成周期为5的周期数列:3, 9, 5, 4, 1, 3, 9, 5, 4, 1,类似地,经过计算可得 7n的数列的项的最小非负剩余构成周期为10的周期数列:7, 5, 2, 3, 10, 4, 6, 9, 8, 1 ,于是由上两式可知通项为 3n 7n 4

11、的数列的项的最小非负剩余,构成周期为10 (即上两式周期的最小公倍数)的周期数列：3, 7, 0, 0, 4, 0, 8, 7, 5, 6,这就说明,当 1 n 10时,当且仅当 n 3,4,6时,3n 7n 4 0(mod11),即 11|(3n 7n 4)；又由于数列的周期性,故当 10k 1n 10(k 1)时,满足要求的n只有三个,即10k 3,10k4,10k 6从而当1 n 100寸,满足要求的n的和为:99(10k 3) (10k 4) (10k 6)30k 13k 0k 0930 k 10k 013 30 45 130 1480.下面我们着重对Fetmat小定理及其应用来举例：

12、例3.求证：对于任意整数 x, 1x5 1x3 x5315是一个整数.15 13 75证实：令f (x) -x -xx,那么只需证15f (x) 3x53155x37x是15的倍数即可.由 3, 5 是素数及 Fetmat 小定理得 x5 x(mod 5) , x3 x(mod 3),53533x 5x 7x 3x 7x 0(mod 5) ； 3x 5x 7x 2x x 0(mod 3)而(3, 5) =1,故 3x5 5x3 7x 0(mod15),即 15 f (x)是 15 的倍数.所以 f(x)是整数.13例4 .求证：2730 |n n ( n为任意整数).证实：令 f(n) n13

13、 n,那么 f(n) n(n 1)(n 1)(n2 n 1)(n2 n 1)(n6 1)；所以 f (n)含有因式 n7 n, n5 n,n3 n, n2 n由 Fetmat 小定理,知 13| n13 n, 7| n7 n,5 |n5 n,31 n3 n,2| n2 n又13, 7, 5, 3, 2两两互素,所以 2730=13 75 3 2能整除n13例5.设a, b,c是直角三角形的三边长.如果a,b,c是整数,求证：abc可以被30整除.证实：不妨设c是直角三角形的斜边长,那么C2 a2 b2.假设 2卡 a,咻b, 2 卡 c,贝 U c2 a2 b2 1 1 0(mod 2),又由

14、于 c2 1(mod2)矛盾！ 所以2| abc.假设 3 *a , 3 +b ,斗 c,由于(3k 1)2 1(mod 3),那么 a2 b2 1 1 2(mod3),又2c 1(mod 3),矛盾！从而 3| abc.假设 5 *a, 5 *b, 5 *c,由于(5k 1)2 1(mod 5) , (5k 2)2 1(mod 5),所以 a2 b22或 0(mod5)与 c21(mod 5)矛盾！从而5| abc.又(2,3,5)=1 ,所以 30| abc.下面讲述中国剩余定理的应用例6.证实：对于任意给定的正整数n ,均有连续n个正整数,其中每一个都有大于1的平方因子.证实：由于素数有

15、无穷多个,故我们可以取n个互不相同的素数 p1,p2, ,pn,而考虑同余组 x i(mod p2),i 1,2, ,n 222由于p1 , p2 , pn显然是两两互素的,故由中国剩余定理知,上述同余组有正整数解.于是,连续n个数x 1,x 2, ,x n分别被平方数p；, p22, , pn2整除.注：(1)此题的解法表达了中国剩余定理的一个根本成效,它常常能将“找连续n个正整数具有某种性质的问题转化为“找n个两两互素的数具有某种性质,而后者往往是比拟容易解决的.(2)此题假设不直接使用素数,也中以采用下面的变异方法：由费尔马数Fk 22k 1(k 0)两两互素,故将中的p：转化为F,(i

16、 1,2, ,n)后,相应的同余式也有解,同样可以导出证实.例7.证实：对于任意给定的正整数n ,均有连续n个正整数,其中每一个都不是哥数.分析：我们来证实,存在连续 n个正整数,其中每一个数都至少有一个素因子,在这个数的 标准分解中仅出现一次,从而这个数不是哥数.证实：取n个互不相同的素数 p1,p2, , pn,考虑同余组x i(mod p2),i 1,2, , n222 -由于p1 , p2 , pn显然是两两互素的,故由中国剩余定理知,上述同余组有正整数解.对于1 i n由于x i p/mod p2),故p：|(x i),但由式可知pN(x i),即pi在(x i)的标准分解中恰好出现

17、一次,故 x 1, x 2, ,x n都不是哥数.例8.设n,k是给定的偶数,n 0且k(n 1)是偶数.证实：存在整数 x,y使得(x,n) (y, n) 1,且x y k(modn).证实：我们先证实,当 n为素数哥p时结论成立.实际上,能够证实,存在 x,y使假设p 2,那么条件说明k为偶数,此时可取假设 p 2,贝Ux 1, y k 1与 x 2, y k 一般情形下,设 npjp；2p：r,i 1,2,个pi存在整数xi, yi使得pi yi且xi yi 同余式 x xi(mod pi i )(i 1,2, r)同余式 y yi(mod pi i)(i 1,2, ,r) 现不难验证解x,y符合问题中的要求：因于是(xy, n) 1 ,又由知 x y xix 1, y k 1 ；2中有一对满足要求.,r是n的一个标准分解,上面已经证实,对每k (i 1,2, r),而由中国剩余定理,有解x ,有解y.pWy,故 p*xy(i 1,2, r),yi(modpj)(i 1,2, ,r),故 x y k(mod n).将一个关于任意正整数 n的问题,化