高次剩余规律初探(二) (2)

《高次剩余规律初探(二) (2)》由会员分享，可在线阅读，更多相关《高次剩余规律初探(二) (2)（33页珍藏版）》请在装配图网上搜索。

1、 高 次 剩 余 规 律 初 探（二）陈文渊（陕西咸阳）摘 要高次剩余问题，是个未能得到很好解决的问题。本文运用初等数论方法，在以素数为模的情况下，研究了、类型数集的剩余问题。在延伸前人理论的同时，定义了二项同余方程的真解，研究了二项同余方程解集的内在同余关系和性质；研究了二项同余方程、型数集、型数集三者之间的内在同余关系和性质。初步给出了高次剩余之和的剩余规律多条，与高次剩余之积的剩余规律多条，以及高次矩阵的剩余规律。关键词：高次剩余、同余、对模。一些理论的延伸定义1：设m是一个大于1的正整数，a是正整数，且（m，a）=1，若有anr （mod m） （1rm-1）成立，则r就叫做对模m的高

2、次剩余。定理（一）p是一个奇素数，a是一个正整数，且（p，）=1,若p-1= d1b1 = d2b2 =dsbs，则当 r （mod p）有 1 （mod p） （1rp-1）当 r （mod p） 有 1 （mod p） （i=1,2，s）证明：由费尔马定理可知 =ap-11 （mod p）又 （mod p） 1 （mod p）定理（二）p是一个奇素数，a是一个正整数，且（p，a）=1，则 当 ak1 （mod p）有 akn1 （mod p） （） 当 ak-1 （mod p） 有 ak（2n-1）1 （mod p）证明：（ak）n1n （mod p） akn1 （mod p） 同理可得

3、（ak）2n-1（-1）2n-1 （mod p） ak（2n-1）-1 （mod p）定理（三）若p是奇素数，a是正整数，（p，）=1，且有 anr （mod p） （1rp-1，） 当 ak1 （mod p） 则 ak+nr （mod p） 当 ak-1 （mod p）则 ak+np-r （mod p）证明 ： akan1r （mod p） ak+nr （mod p） akan（-1）rp-r （mod p） ak+np-r （mod p）定理（四）若p是素数，a，c分别是正整数，且p=a+c， 当 a2nr （mod p） （1rp-1，nN） 则 c 2nr （mod p） 当 a2n+

4、1r （mod p） 则 c 2n+1p-r （mod p）证明：由 p=a+c，得 a=p-c。 a2n=（p-c）2n =p（p-2c）+c2n =pq+c2n式中q为由二项展开式所有含p各项决定的一个正整数。 a2nc2n （mod p）已知 a2nr （mod p） c2nr （mod p）同理，由 p=a+c，得 a=p-c。 a2n+1=（p-c）2n+1 =（p-c）（p-c）2n =ap（p-2 c）+c2n =paq+ac2n式中q为由二项展开式所有含p各项决定的一个正整数。给上式两边同时加c2n+1，有 a2n+1+ c2n+1=paq+ac2n+c2n+1 =paq+（a

5、+c）c2n =p（aq+c2n）已知 a2n+1r （mod p） c2n+1p-r （mod p）定理（五）若p是素数，a是正整数，（p，a）=1，在数集am中有 ak1 （mod p）当am对模p分为k个不为零的剩余类，依次分别为 ank+1r1 （mod p） ank+2r2 （mod p） a(n+1)k-1rk-1 （mod p） （n=0，1，2，） a(n+1)krk=1 （mod p） （i=1，2，,k）则在(ank+i-ri)/p中，任截连续p个项，对模p是一个完全剩余系的充要条件是（p，(ak-1)/p）=1。证明： ak1 （mod p） 令 ak=pq+1 显然 q

6、=(ak-1)/p (ak)n-1/p=(pq+1)n-1/p由二项式原理可得当n=0时，(pq+1)0-1/p=0当n=1时，(pq+1)1-1/p=pq1+q当n=2时，(pq+1)2-1/p=pq2+2q 当n=j时，(pq+1)j-1/p=pqj+jq 由上式可知，只有当（p，q）=（p, (ak-1)/p）=1时，则在上式中任截连续p个项（式），对模p是一个完全剩余系。 ank1 （mod p） airi （mod p） ank+iri （mod p）故只有(p, (ak-1)/p)= (p, (ank-1)/p)=1时，则在(ank+i-ri)/p中, 任截连续p个项，对模p是一个

7、完全剩余系。定理（六）如果p是奇素数，a、b、d、k、m皆为正整数，（a，p）=1，db=p-1， ak为am中任意一项时，有 ak a0 （mod p） ab+k a1 （mod p）a2b+k a2 （mod p） aib+k ai （mod p） 则 r（mod p）式中1aip-1；1rp-1；i=0、1、2证明： （aib+k）d= ai（p-1） akd由定理（二）可知ai（p-1）1 （mod p）当 akd r （mod p） （1rp-1）由定理（三）可知 r （mod p） r （mod p）一些同余方程解集的性质定义2、设0是同余方程1 （mod p） d（p-1）的一个

8、解，若在、中，有 （mod p） （ij，i、j=1，2，d）即、对模p无两两同余，则0就叫做其同余方程的一个真解。定义3、设r是对模p的d次剩余，0是同余方程r （mod p） （1rp-1）的一个解，若在、中，有 （mod p） （ij，i、j =1、2p-1）即、对模p无两两同余，则0就叫做其同余方程的一个原根或真解。 定理（七）若p是奇素数，且db=p-1，当1 （mod p）的一个真解为0时，则其同余方程的d个解，可由如下关系式表示： （mod p） （mod p） （1p-1） （mod p） =1 （mod p）证明： 1 （mod p）又由定理（二）可知 1 （mod p） （

9、i=1.2d）1 （mod p）由真解的性质可知、对模p无两两同余。定理得证。定理（八）p是奇素数，且db=p-1，当-1 （mod p）的一个真解为0时，则其同余方程的d个解，可由如下关系式表示： （mod p） （mod p） (1p-1) （mod p） （mod p）证明： -1 （mod p）又由定理（二）可知 -1 （mod p） (i=1,2d) -1 （mod p）由真解的性质可知、对模p无两两同余.定理得证。定理（九）若p是奇素数，且db=p-1，当r （mod p） （1rp-1）的一个真解为0时，则其同余方程的d个解，可由如下关系式表示： （mod p） （mod p）

10、(1p-1) （mod p） （mod p）证明：由定理（六）立得： r （mod p）由真解的性质可知、对模p无两两同余.即定理成立。定理（十）若p是素数，又有db=p-1，如果r1 、 r2 、 rb 是对模p的b个d次剩余，有 r1 （mod p） r2 （mod p） （1p-1） r3 （mod p） rb （mod p） 成立，若式的一个原根（真解）为时，则其每式的d个解，可由如下关系式表示：对于式有 （mod p） （mod p） （mod p） (1p-1) （mod p）对于式有 （mod p） （mod p） （mod p） （mod p） 对于式有 （mod p） （mo

11、d p） （mod p） （mod p）证明：由定理（六）立得（1）r1 （mod p）（2）r2 （mod p） （b）rb （mod p）由真解的性质可知，这p-1解对模p是互不同余的，且1p-1，故其与1、2、3(p-1)是一一对应相等地。即本理成立。定理（十一）若p是奇素数，又有db=p-1，则方程 1 （mod p） 的d个解，与对模p的d个b次剩余，是一一对应相等地。而方程 1 （mod p） 的b个解，与对模p的b个d次剩余，是一一对应相等地。证明：令式的d个解为，。由定理（七）可知：其是对模 p互不同余的d个剩余数；有（1p-1）、（，p）=1; 显然有 1 （mod p） d

12、b=p-1 所以由数论导引定理3.7.3可知，当方程 （mod p） 中的通过1、2、3(p-1)时，则r可取d个值，分别为，,同时可知：这d个剩余值对模p互不同余；有（1p-1）、（，p）=1 , 由定理（一）可知 （mod p） 显然，这d个解和这d个剩余，分别与p之间的关系和性质是相同地。故由定理（七）可知：在这d个剩余值中有一个同真解一样使得： （mod p） （mod p） （mod p） （mod p）成立。由此可知：当与取同一真解时，则，与，是依顺序一一对应相等地；当所取真解不同时，那么只是对应的顺序有所不同。 同理可证式成立。即本理成立。定理（十二）若p是奇素数，且db=p-1

13、，设-1,1同时是对模p的d次剩余，则方程 -1 （mod p） 与方程 1 （mod p） 的解，是方程1 （mod p） （2dp-1）的2d个解。 证明：设是式的一个真解， -1p-1 （mod p） 由定理（三）可知p-（p-1）1 （mod p） 显然也就是式的一个真解，同时可知式与式等价。由定理（七）可知：、（mod p）的2d个剩余，即为式的2d个解。又由定理（八）可知，其中的奇次项、（mod p）的d个剩余，即为式的d个解。又 -1 （mod p） （mod p） 1 （mod p）即偶次项、（mod p）的d个剩余，即为式的d个解。即本理成立。定理（十三）若p是素数，a是正整

14、数，（p，a）=1，当k为最小使得 ak1 （mod p）能成立的正整数时，则数集am对模p的剩余数可分为k个剩余类。证明：当 m=1,2,，k 时，在 am 中，a1r1 （mod p） a2r2 （mod p） akrk=1 （mod p）由题设条件可令：a=,则由定理（六）可知：r1、r2rk 对模p无两两同余。当 m=k+1,k+2,，2k 时，由定理(三) 可知 ak+1r1 （mod p） ak+2r2 （mod p） a2k-1rk-1 （mod p） a2krk=1 （mod p）余类推因为由（p，a）=1和定理(三) 可知r1、r2rk是对模p的k个不为零的两两互不同余的剩余

15、数。由上述可得am对模可分为k个剩余类。依次表示为 ank+1r1 （mod p） ank+2r2 （mod p） a(n+1)k-1rk-1 （mod p） a(n+1)krk=1 （mod p） 式中 1rip-1，n=0、1、2、3 一些高次剩余之和的剩余规律定理（十四）若p是奇素数，则 （mod p）证：由费尔马定理可知： 1 （mod p） （mod p）定理（十五）若p是奇素数，则 （mod p）证： 将其（p-1）个项经组合整理，得，等个项，又由定理（四）可知，有 （mod p）故立即可得本理成立。定理（十六）若p是奇素数，则 （mod p） （mod p）证： 当 n=p-1；

16、时显然 ，得证；当 n=；时，显然 ，得证。即本理成立。定理（十七）若p是奇素数，当-1 （mod p）， 则 （mod p） 证明：将其2n个项经组合整理，得、等n个项，由定理（三）可知： （mod p） (j=1,2n) 故本理成立。定理（十八）若p是奇素数，当 1 （mod p） （1ap-1，nN）则 （mod p） 证明： 由题设可令： 则 即本理成立。由本理可直接推得：推理（一）若p是奇素数， 当 （mod p） （1ap-1）则 （mod p）推理（二）若p是奇素数，当 （mod p） （1ap-1） 则 （mod p）定理（十九）若p是奇素数，则 （mod p） （1n） 证明

17、： （mod p） 的（p-1）个解为1、2、3p-1，当其中一个解为一个真解时，则由定理（七）可得 （mod p） （mod p） (1p-1) （mod p） （mod p）又因 （mod p） 又由定理（二）得 （mod p）故由定理（十八）可得 （mod p）因（、）中的各项与（1、2、3p-1）中各项是一一对应相等的，所以所以本理得证。定理（二十）若p是奇素数，且db=p-1，为中任意一项，则 （mod p）证明： 又因 （mod p） 故根据推理（二）， 令 则 即本理成立。定理（廿一）若p是奇素数，则 （mod p） (1ap-1)证： 又因 （mod p）所以由定理（十八）可知

18、，本理成立。定理（廿二）若p是奇素数，且有db=p-1，如果r是对模p的一个d次剩余，即 （mod p）其d个解分别为、，则 （mod p）式中1rp-1，1nd-1，i=1、2、3d证明：设其中一个解为真解， 由定理（九）可知 （mod p） （mod p） (1p-1) （mod p） （mod p）给上式两边同时乘方、求和，即可用归纳法证明本理。当n=1时，左边和= =又因 （mod p）所以由定理（二十）可知： （mod p）即当n=1时本理成立，假定当n=k时，定理成立，即 （mod p）那么，当n=k+1时左边和= =又因 由定理（二）可知， （mod p）又由定理（二十）可知 （

19、mod p） 即 当n=k+1时，本理成立。 但是，当n=d时 有 （mod p） （mod p） （mod p） （mod p）时，显然 （mod p）故综上所述可得：结论（一）当1nd-1时，本理成立。结论（二）当；且dn时，本理成立。 定理（廿三）若p是奇素数， 则 （mod p）式中（p-1）nN.证明：当(p-1)n时，由定理（十四）可知本理不能成立当(p-1)n时，且 n为奇数，由定理（十五）可知本理成立；n为偶数，由定理（十九）可知本理成立。故综上所述可得：结论（一）当1np-2时，本理成立。结论（二）当，且（p-1）n时，本理成立。即本理成立。一些高次剩余之积的剩余规律定理（廿

20、四）若p是奇素数，（a,p）=1;且有2k.当 1 （mod p） 时，则 1 （mod p）证明： （mod p） 所以只有当 1 （mod p) 或 -1 （mod p） 时，上式才能成立。定理（廿五）若p是奇素数，且有1ap-1;1rp-1.如果 （mod p）即当r为模p的二次非剩余时， 则 -1 （mod p）证明：因费尔马定理为： 1 （mod p） 又因 所以只有当 1 （mod p） 或 -1 （mod p） 时，则费尔马定理才能成立； 又由定理（一）可知：只有当 r （mod p） 时，则 1 （mod p） 若当 （mod p） 时，则 -1 （mod p）即定理成立。定理

21、（廿六）p是奇素数，若同余方程 1 （mod p） 有解为、，且d为奇数时，则 （mod p）证明：设同余方程的一个真解为，由定理（七）可得： （mod p） （mod p） (1p-1) （mod p） （mod p） 左边积= = 1 （mod p） 又因d为奇数，所以为正整数，故由定理（二）可知： 左边积=1 （mod p） 那么 右边积=1 （mod p） 即本理成立。定理（廿七）若p为奇素数，如果同余方程 1 （mod p） 有解 为、，且d为偶数，又有时，则 +=+=+=p （mod p） 证明： 1 （mod p） 又因d为偶数，已知。 由定理（四）的逆定理可知： 当 = 时，

22、则 =p-； 当 = 时， 则 =p-； 当 = 时， 则 =p-故可得： +=+=+=p 得证。 设同余方程的一个真解为，由定理（七）可得： （mod p） （mod p） (1p-1) （mod p） （mod p） 左边积= = = 因d是偶数，所以为正整数，故由定理（二）可知： （mod p） 如果 （mod p） 便有 （mod p） 显然与真解的性质矛盾，故由定理（廿四）可知： （mod p） 所以 左边积=-1 （mod p） 那么 右边积= （mod p）即本理成立。定理（廿八）若p是奇素数，当同余方程-1 （mod p）有解为、，且d为奇数时，则 （mod p）证明：设同余方

23、程的一个真解为，由定理（八）可得： （mod p） （mod p） (1p-1) （mod p） （mod p）左边积= = -1 （mod p） 又因d为奇数，故由定理（二）可知： 左边积=-1 （mod p） 那么 右边积= （mod p） 即本理成立。定理（廿九）若p为奇素数，如果同余方程 -1 （mod p） 有解 为、，且d为偶数，又有时，则 +=+=+=p （mod p）证明：同定理（廿七）； 设同余方程的一个真解为，由定理（八）可得： （mod p） （mod p） (1p-1) （mod p） （mod p） 左边积= = -1 （mod p） 又因d是偶数，故由定理(二) 可

24、推得： 左边积=1 （mod p）那么 右边积= （mod p）即本理成立。定理（三十）若p为奇素数，如果同余方程 r （mod p） 有解 为、，且d为奇数时，则 （mod p） 证明：设同余方程的一个真解为，令 db=p-1,则由定理（九）可得： （mod p） （mod p） (1p-1) （mod p） （mod p） 左边积= = = 因d是奇数，所以是整数，由定理(二) 可知： 1 （mod p） 又因 r （mod p） 所以 左边积=r （mod p） 那么 右边积= （mod p） 即本理成立。定理（丗一）若p为奇素数，如果同余方程 r （mod p） 有解 为、，且d为偶数

25、，又有时，则 +=+=+=p （mod p） 证明：同定理（廿七）。 设同余方程的一个真解为，令 db=p-1,则由定理（九）可得： （mod p） （mod p） (1p-1) （mod p） （mod p）左边积= = = 因d为偶数，所以是整数，由定理（二）可知： 1 （mod p） 如果 1 （mod p） 便有 （mod p） 显然与真解的性质矛盾，故由定理（廿五）可知为模p的二次非剩余， 则有 p-1 （mod p） 又因 r （mod p）所以 左边积=p-r （mod p） 那么 右边积= （mod p） 即本理成立。定理（丗二）若p是奇素数，则 （mod p） （mod p）

26、证明： = = 故由威尔逊定理可知： （mod p） (mod p)即本理成立。一些高次矩阵的剩余规律定理（丗三）若p是奇素数，如果数集中a依次取1、2、3p-1;n=1,2,3 时，可得一无限之数阵；当依次每取其p-1个行为一矩阵，可得无限多个矩阵如下： （一） an 12345p-1112345p-121222324252（p-1）231323334353（p-1）341424344454（p-1）451525354555（p-1）5p-11 p-12p-13 p-14 p-15 p-1（p-1）p-1（二） an 12345p-1P1 p2p3p4p5p（p-1）pP+11 p+12 p

27、+13 p+14 p+15 p+1（p-1）p+1P+21 p+22 p+23 p+24 p+25 p+2（p-1）p+2P+31 p+32 p+33 p+34 p+35 p+3（p-1）p+3P+41 p+42 p+43 p+44 p+45 p+4（p-1）p+4 2（p-1）12（p-1）22（p-1）3 2（p-1）4 2（p-1）52（p-1）（p-1）2（p-1）余类推。则 矩阵中的元素之和的性质为 （mod p） 矩阵中的元素之积的性质为： 当为奇数时 （mod p） 当为偶数时, （mod p）证明：可分三步来证。第一步，由定理（廿一）可知：在矩阵（一）中自第2列至p-1列，每列

28、之和皆能被p整除；因又有第1列之和为 （mod p）故可知矩阵（一）中的所有元素之和为： （mod p）第二步，由定理（丗二）可知，在矩阵（一）中适合（丗二）、的各有个行，如果适合的个行相乘时，即 （mod p） （mod p） （mod p） （mod p）以上诸式相乘得： （mod p）当n=为奇数时，则 （mod p）当n=为偶数时，则 （mod p）故可知矩阵（一）中的所有元素之积为: 当为奇数时， （mod p）当为偶数时, （mod p）第三步 （mod p）即矩阵（一）中的第p-1行中之每个元素模p皆余1。所以由定理（三）可知：矩阵（一）中任意列中之任意元素，与矩阵（二）中对应列

29、中之对应元素，模p同余。故可推得矩阵（一）中任意元素，与矩阵（二）中对应元素，模p同余。由此可得矩阵（一）中所有元素之和，与矩阵（二）中所有元素之和，模p同余。 即 （mod p）又可得矩阵（一）中所有元素之积，与矩阵（二）中所有元素之积，模p同余。即 （mod p）又因为矩阵（二）最后一行中之任意元素模p皆余1。故同理由矩阵（一）、（二） 可推得：矩阵（三）、（四）有与矩阵（一）、（二）相同的性质。同理又由矩阵（一）、（二）、（三）、（四）可推得矩阵（五）、（六）、（七）、（八） .依理类推可得：矩阵（一）中之任意元素，与其以下任意矩阵中之对应元素，模p同余.立刻可得矩阵中的元素之和的性质为 （mod p）矩阵中的元素之积的性质为：当为奇数时 （mod p） 当为偶数时, (mod p)即定理成立。参考书目：（1）陈景润 初等数论 科学出版社 1978(2) 华罗庚 数论导引 科学出版社 1979 二零一二， 九， 十九。33