管訓(xùn)貴
(泰州學(xué)院 數(shù)理學(xué)院,江蘇 泰州 225300)
?
關(guān)于覆蓋同余式的一個(gè)應(yīng)用
管訓(xùn)貴
(泰州學(xué)院 數(shù)理學(xué)院,江蘇 泰州 225300)
建立了一組覆蓋同余式并通過(guò)對(duì)非負(fù)整數(shù)n進(jìn)行分類(lèi)等方法,給出了使2kpn+1對(duì)每一個(gè)非負(fù)整數(shù)n均為合數(shù)的k值,這里素?cái)?shù)p=7,13及p≡5(mod6).
覆蓋同余式;合數(shù);剩余;模
覆蓋同余式的構(gòu)造問(wèn)題是數(shù)論中較為復(fù)雜的問(wèn)題之一,目前這方面已有許多非常重要的成果[1-6].
由于覆蓋同余式通過(guò)一切非負(fù)整數(shù),故可用來(lái)解決一類(lèi)與合數(shù)有關(guān)的數(shù)論問(wèn)題.1980年國(guó)際數(shù)論會(huì)議上,著名數(shù)學(xué)家P.Erd?s 曾提出“能否找到一個(gè)正整數(shù)k,使得k·2n+1對(duì)每一個(gè)非負(fù)整數(shù)n均為合數(shù)?”的求解問(wèn)題.文獻(xiàn)[7]利用覆蓋同余式證明了k的存在性,并給出了21類(lèi)這樣的k值.作為該問(wèn)題的延續(xù),本文利用一組覆蓋同余式證明了以下一般性的結(jié)果.
定理設(shè)素?cái)?shù)p=7,13及p≡5(mod6),則存在正整數(shù)k,使得2kpn+1對(duì)每一個(gè)非負(fù)整數(shù)n均為合數(shù).
定義若每一個(gè)非負(fù)整數(shù)n都至少滿足下列同余式中的一個(gè):
n≡a1(modn1),n≡a2(modn2),…,n≡as(modns),
(1)
這里1 引理1 n≡0(mod2),n≡0(mod3),n≡1(mod4),n≡5(mod6),n≡7(mod12)是一組覆蓋同余式. 證全體非負(fù)偶數(shù)滿足n≡0(mod2);全體正奇數(shù)可按模12分成六類(lèi): 12r+1,12r+3,12r+5,12r+7,12r+9,12r+11,r=0,1,…. 這里12r+3,12r+9滿足n≡0(mod3),12r+1,12r+5滿足n≡1(mod4),12r+11,12r+7分別滿足n≡5(mod6)和n≡7(mod12). 引理2[8]設(shè)奇數(shù)n>1,則方程x2+x+1=yn僅有正整數(shù)解(x,y,n)=(18,7,3). 引理6設(shè)素?cái)?shù)p>13且p≡5(mod6),則存在素?cái)?shù)q>13,使q∣(p3-1). 證只需證在題設(shè)條件下,存在素?cái)?shù)q>13,使q∣(p2+p+1),或 p2+p+1≡0(modq). (2) 即可. p2+p+1=7a·13b, (3) 這里a,b是不全為0的非負(fù)整數(shù). 當(dāng)a=0或b=0或a,b同為偶數(shù)時(shí),結(jié)合引理2知,式(3)不成立.下設(shè)a,b為正整數(shù)且a,b中至少有一個(gè)為奇數(shù). 若a=b=1,則由式(3)得p2+p+1=91,解得p=9,不合題意.因此a,b中至少有一個(gè)是大于1的奇數(shù).由式(3)得 (4) s2-91r2=-3. (5) 根據(jù)引理3~5,方程(5)的全部正整數(shù)解(s,r)=(sn,rn)由以下兩個(gè)非結(jié)合類(lèi)給出: (6) 或 (7) 由式(6)得 sn+2=3 148sn+1-sn,s0=19,s1=59 936. (8) 因sn為奇數(shù),故n必為偶數(shù).對(duì)式(8)模3得剩余序列周期為2,且當(dāng)n為偶數(shù)時(shí),有sn≡1(mod3),即2p+1≡1(mod3),推知p=3與p>13矛盾.故式(6)不成立. 由式(7)得 sn+2=3 148sn+1-sn,s0=-19,s1=124. (9) 對(duì)式(8)模5得剩余序列周期為2,且當(dāng)n為偶數(shù)時(shí),有sn≡1(mod5),即2p+1≡1(mod5),推知p=5與p>13矛盾.故式(7)不成立.于是式(4)不成立. 由式(3)得 (10) s2-13r2=-3. (11) 根據(jù)引理3~5,方程(11)的全部正整數(shù)解(s,r)=(sn,rn)由以下兩個(gè)非結(jié)合類(lèi)給出: (12) 或 (13) 由式(12)得 sn+2=1 298sn+1-sn,s0=7,s1=9 223. (14) 由式(14)知,對(duì)任意非負(fù)整數(shù)n,有sn≡1(mod3),即2p+1≡1(mod3),推知p=3與p>13矛盾.故式(12)不成立. 由式(13)得 sn+2=1 298sn+1-sn,s0=-7,s1=137. (15) 由式(15)知,對(duì)任意非負(fù)整數(shù)n,有sn≡1(mod8),即2p+1≡1(mod8),推知p≡0(mod4),不可能.故式(13)不成立.于是式(10)不成立. 若a=1,則由式(3)得 (16) s2-28r2=-3. (17) 根據(jù)引理3~5,方程(17)的全部正整數(shù)解(s,r)=(sn,rn)由以下兩個(gè)非結(jié)合類(lèi)給出: (18) 或 (19) 由式(18)得 rn+2=254rn+1-rn,r0=1,r1=247. (20) 考慮到13∣rn,對(duì)式(20)模13得剩余序列周期為7,且有n≡1(mod7). 由式(19)得 sn+2=254sn+1-sn,s0=-5,s1=37. 易知,對(duì)任意非負(fù)整數(shù)n,有sn≡1(mod6),即2p+1≡1(mod6),推知p=3與p>13矛盾.于是式(16)不成立. 若a≥3,則由式(3)得 (21) s2-7r2=-3. (22) 根據(jù)引理3~5,方程(22)的全部正整數(shù)解(s,r)=(sn,rn)由以下兩個(gè)非結(jié)合類(lèi)給出: (23) 或 (24) 由式(23)得 sn+2=16sn+1-sn,s0=2,s1=37. (25) 因sn為奇數(shù),故n必為奇數(shù).對(duì)式(25)模3得剩余序列周期為2,且當(dāng)n為奇數(shù)時(shí),有sn≡1(mod3),即2p+1≡1(mod3),推知p=3與p>13矛盾.故式(23)不成立. 由式(24)得 rn+2=16rn+1-rn,r0=1,r1=2. (26) 對(duì)式(26)模7得剩余序列周期為7,且當(dāng)n≡6(mod7)時(shí),7∣rn;對(duì)式(26)模13得剩余序列周期為14,且當(dāng)n≡3,10(mod14)即n≡3(mod7)時(shí),13∣rn.此時(shí)有6≡3(mod7),顯然不可能.故式(24)不成立.于是式(21)不成立.引理6得證. 分兩步進(jìn)行: Ⅰ.若p=5,由于52≡1(mod3),53≡1(mod31),54≡1(mod13),56≡1(mod7),512≡1(mod601),所以 當(dāng)n≡0(mod2),即n=2m時(shí),有2k·5n+1=2k·52m+1≡2k+1(mod3); 當(dāng)n≡0(mod3),即n=3m時(shí),有2k·5n+1=2k·53m+1≡2k+1(mod31); 當(dāng)n≡1(mod4),即n=4m+1時(shí),有2k·5n+1=2k·54m+1+1≡-3k+1(mod13); 當(dāng)n≡5(mod6),即n=6m+5時(shí),有2k·5n+1=2k·56m+5+1≡-k+1(mod7); 當(dāng)n≡7(mod12),即n=12m+7時(shí),有2k·5n+1=2k·512m+7+1≡-10k+1(mod601). 因此,只需k滿足下列同余方程組 (27) 則由引理1知,對(duì)每一個(gè)非負(fù)整數(shù)n,2k·5n+1至少被3,31,13,7,601中一數(shù)整除,因而2k·5n+1必是一個(gè)合數(shù).由計(jì)算知,式(27)等價(jià)于下列同余方程組 進(jìn)而等價(jià)于 (28) 由于模m1=21,m2=13,m3=31,m4=601兩兩互素,故式(28)可用孫子剩余定理求得k≡1 107 583(mod5 086 263).于是所求的正整數(shù)k=1 107 583+5 086 263t,這里t是任意非負(fù)整數(shù). 若p=7,由于72≡1(mod3),73≡1(mod19),74≡1(mod5),76≡1(mod43),712≡1(mod13),所以 當(dāng)n≡0(mod2),即n=2m時(shí),有2k·7n+1=2k·72m+1≡2k+1(mod3); 當(dāng)n≡0(mod3),即n=3m時(shí),有2k·7n+1=2k·73m+1≡2k+1(mod19); 當(dāng)n≡1(mod4),即n=4m+1時(shí),有2k·7n+1=2k·74m+1+1≡-k+1(mod5); 當(dāng)n≡5(mod6),即n=6m+5時(shí),有2k·7n+1=2k·76m+5+1≡-12k+1(mod43); 當(dāng)n≡7(mod12),即n=12m+7時(shí),有2k·7n+1=2k·712m+7+1≡-k+1(mod13). 因此,只需k滿足下列同余方程組 (29) 則由引理1知,對(duì)每一個(gè)非負(fù)整數(shù)n,2k·7n+1至少被3,19,5,43,13中一數(shù)整除,因而2k·7n+1必是一個(gè)合數(shù).由計(jì)算知,式(29)等價(jià)于下列同余方程組 進(jìn)而等價(jià)于 (30) 由于模m1=195,m2=19,m3=43兩兩互素,故式(30)可用孫子剩余定理求得k≡58 111(mod159 315).于是所求的正整數(shù)k=58 111+159 315t,這里t是任意非負(fù)整數(shù). 若p=11,由于112≡1(mod5),113≡1(mod19),114≡1(mod3),116≡1(mod37),1112≡1(mod7),所以 當(dāng)n≡0(mod2),即n=2m時(shí),有2k·11n+1=2k·112m+1≡2k+1(mod5); 當(dāng)n≡0(mod3),即n=3m時(shí),有2k·11n+1=2k·113m+1≡2k+1(mod19); 當(dāng)n≡1(mod4),即n=4m+1時(shí),有2k·11n+1=2k·114m+1+1≡k+1(mod3); 當(dāng)n≡5(mod6),即n=6m+5時(shí),有2k·11n+1=2k·116m+5+1≡17k+1(mod37); 當(dāng)n≡7(mod12),即n=12m+7時(shí),有2k·11n+1=2k·1112m+7+1≡k+1(mod7). 因此,只需k滿足下列同余方程組 (31) 則由引理1知,對(duì)每一個(gè)非負(fù)整數(shù)n,2k·11n+1至少被5,19,3,37,7中一數(shù)整除,因而2k·11n+1必是一個(gè)合數(shù).由計(jì)算知,式(31)等價(jià)于下列同余方程組 進(jìn)而等價(jià)于 (32) 由于模m1=15,m2=19,m3=37,m4=7兩兩互素,故式(32)可用孫子剩余定理求得k≡50 777(mod73 815).于是所求的正整數(shù)k=50 777+73 815t,這里t是任意非負(fù)整數(shù). 若p=13,由于132≡1(mod7),133≡1(mod61),134≡1(mod17),136≡1(mod3),1312≡1(mod5),所以 當(dāng)n≡0(mod2),即n=2m時(shí),有2k·13n+1=2k·132m+1≡2k+1(mod7); 當(dāng)n≡0(mod3),即n=3m時(shí),有2k·13n+1=2k·133m+1≡2k+1(mod61); 當(dāng)n≡1(mod4),即n=4m+1時(shí),有2k·13n+1=2k·134m+1+1≡9k+1(mod17); 當(dāng)n≡5(mod6),即n=6m+5時(shí),有2k·13n+1=2k·136m+5+1≡2k+1(mod3); 當(dāng)n≡7(mod12),即n=12m+7時(shí),有2k·13n+1=2k·1312m+7+1≡-k+1(mod5). 因此,只需k滿足下列同余方程組 (33) 則由引理1知,對(duì)每一個(gè)非負(fù)整數(shù)n,2k·13n+1至少被7,61,17,3,5中一數(shù)整除,因而2k·13n+1必是一個(gè)合數(shù).由計(jì)算知,式(33)等價(jià)于下列同余方程組 進(jìn)而等價(jià)于 (34) 由于模m1=7,m2=61,m3=17,m4=15兩兩互素,故式(34)可用孫子剩余定理求得k≡59 566(mod108 885).于是所求的正整數(shù)k=59 566+108 885t,這里t是任意非負(fù)整數(shù). Ⅱ.設(shè)素?cái)?shù)p>13.易驗(yàn)證:p2+p+1≡0(mod32),p2+p+1≡0(mod5),p2+p+1≡0(mod11).根據(jù)引理6,p>13時(shí),必存在素?cái)?shù)q>13,使得q∣(p3-1),即p3≡1(modq). 又若p≠3,5,7,13,則gcd(p,3·5·7·13)=1,進(jìn)而p2≡1(mod3),p4≡1(mod5), p6≡1(mod7),p12≡1(mod13),所以 當(dāng)n≡0(mod2),即n=2m時(shí),有2kpn+1=2kp2m+1≡2k+1(mod3); 當(dāng)n≡0(mod3),即n=3m時(shí),有2kpn+1=2kp3m+1≡2k+1(modq); 當(dāng)n≡1(mod4),即n=4m+1時(shí),有2kpn+1=2kp4m+1+1≡2pk+1(mod5); 當(dāng)n≡5(mod6),即n=6m+5時(shí),有2kpn+1=2kp6m+5+1≡2p5k+1(mod7); 當(dāng)n≡7(mod12),即n=12m+7時(shí),有2kpn+1=2kp12m+7+1≡2p7k+1(mod13) 因此,只需k滿足下列同余方程組 (35) 則由引理1知,對(duì)每一個(gè)非負(fù)整數(shù)n,2kpn+1至少被3,q(q為大于13的素?cái)?shù)),5,7,13中一數(shù)整除,因而2kpn+1必是一個(gè)合數(shù).不難知道,式(35)中第三、四、五個(gè)同余方程分別有唯一解k≡a(mod5),k≡b(mod7),k≡c(mod13),故式(35)等價(jià)于下列同余方程組 由孫子剩余定理可得k. 綜上所述,對(duì)任意素?cái)?shù)p≡5(mod6)及p=7,13,存在正整數(shù)k,使得2kpn+1對(duì)每一個(gè)非負(fù)整數(shù)n均為合數(shù).定理得證. p2+p+1=3·7a·13b, (36) 這里a,b是不全為0的非負(fù)整數(shù). 只需證(36)式不成立,則當(dāng)p≡1(mod6)時(shí),便存在素?cái)?shù)q>13,使q∣(p3-1).因此,有下列 猜想:若素?cái)?shù)p≡1(mod6),則存在正整數(shù)k,使得2kpn+1對(duì)每一個(gè)非負(fù)整數(shù)n均為合數(shù). [1]Schinzel A.Reducibility of polynomials and covering systems of congruences[J]. Acta Arith.,1967/1968(13):91-101. [2] 孫琦,萬(wàn)大慶,曠京華.關(guān)于覆蓋同余式組的一個(gè)注記[J].數(shù)學(xué)研究與評(píng)論,1984,4(2):1-3. [3] 孫智偉,孫智宏. 關(guān)于覆蓋同余式組的若干結(jié)果[J].西南師范大學(xué)學(xué)報(bào),1987(1):10-15. [4]孫智偉.關(guān)于不同模覆蓋系[J].揚(yáng)州師院學(xué)報(bào)(自然科學(xué)版),1991,11(3):21-27. [5] SunZ.W.On exactly m times covers[J]. Israel J.Math.,1992,77:345-348. [6]及萬(wàn)會(huì). 關(guān)于覆蓋同余式組[J].貴州師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2000,18(4):72-75. [7]侯炮明,王炳安. 一類(lèi)覆蓋同余式組的一個(gè)應(yīng)用[J].遼寧工程技術(shù)大學(xué)學(xué)報(bào)(自然科學(xué)版),1999,18(1):93-97. [8] Nagell T. Note sur I’é quation indé terminé (xe-1)/(x-1)=yq[J]. Norsk. Mat.Tidsskr,1920,2:75-78. [9]柯召,孫琦.談?wù)劜欢ǚ匠蘙M].上海:上海教育出版社,1980. An application on covering systems of congruences GUAN Xungui (School of Mathematics and Physics ,Taizhou University,Taizhou Jiangsu 225300, China) In this paper, a kind of covering congruence group is constructed and with a method of classification for nonnegative integern,we give a method ofkvalue computation to make 2kpn+1 the composite for every nonnegative integern,wherepbe prime withp=7,13 and p≡5(mod6). covering systems of congruences;composite number;residue;moduli 2016-01-12; 2016-03-16 江蘇省教育科學(xué)“十二五”規(guī)劃課題(No.D201301083);泰州學(xué)院教授基金項(xiàng)目(No.TZXY2015JBJJ002);云南省教育廳科研課題(No.2014Y462) 管訓(xùn)貴(1963- ),男,江蘇興化人,教授,研究方向:數(shù)論. E-mail:tzszgxg@126.com O156.1 A 1671-9476(2016)05-0001-06 10.13450/j.cnki.jzknu.2016.05.0012 定理的證明