覆蓋同余式組及其應(yīng)用

華 程

(泰州學(xué)院 數(shù)理學(xué)院，江蘇 泰州 225300)

0 引言及主要結(jié)論

若每個(gè)整數(shù)都至少滿足同余式組

x≡a1(modn1),x≡a2(modn2),…，x≡at(modnt)

(1)

中的1個(gè)，這里1

關(guān)于覆蓋同余式組的性質(zhì)與構(gòu)造已有許多結(jié)果，具體內(nèi)容可參考文獻(xiàn)[1～4]。

由于覆蓋同余式通過(guò)一切非負(fù)整數(shù)，故可用來(lái)解決一類與合數(shù)有關(guān)的數(shù)論問(wèn)題。1980年，著名數(shù)學(xué)家Erd?s曾提出“能否找到一個(gè)正整數(shù)k，使得k·2n+1對(duì)每一個(gè)非負(fù)整數(shù)n均為合數(shù)？”的求解問(wèn)題。文獻(xiàn)[5]利用覆蓋同余式組證明了k的存在性，并給出21類這樣的k值。文獻(xiàn)[6]證明了當(dāng)素?cái)?shù)p=7、13及p≡5(mod6)時(shí)，存在正整數(shù)k，使得2kpn+1對(duì)每一個(gè)非負(fù)整數(shù)n均為合數(shù)，并猜測(cè)當(dāng)素?cái)?shù)p≡1(mod6)時(shí)，結(jié)論仍成立。文獻(xiàn)[7]證明了當(dāng)素?cái)?shù)p=19、31、37、43、61、67、73、79、97時(shí)，結(jié)論成立。至此提出如下猜想：

猜想 若素?cái)?shù)p≡1(mod6)，則存在正整數(shù)k，使得2kpn+1對(duì)每一個(gè)非負(fù)整數(shù)n均為合數(shù)。

2017年，文獻(xiàn)[7]證明了當(dāng)素?cái)?shù)p≡19、31、37、43、61、67、73、79、97時(shí)，猜想成立。

至此，已經(jīng)證明當(dāng)素?cái)?shù)p≡1(mod6)且7≤p<100時(shí)， 猜想成立。 作為該問(wèn)題的延續(xù)， 本文對(duì)p≡1(mod6)(100

定理 設(shè)素?cái)?shù)p=103、109、127、139、151、157、163、181、193、199，則存在正整數(shù)k，使得2kpn+1對(duì)每一個(gè)非負(fù)整數(shù)n均為合數(shù)。

1 引理

引理1[6]n≡0(mod2),n≡0(mod3),n≡1(mod4),n≡5(mod6),n≡7(mod12)是一組覆蓋同余式。

引理2[8](中國(guó)剩余定理)設(shè)m1,m2,…,mk(k≥2)是兩兩互素的正整數(shù)，令m1m2…mk=M=m1M1=m2M2=…=mkMk,則同余方程組

x≡Ci(modmi),i=1,…,k

有唯一解

這里Miαi≡1(modmi)(i=1,…，k)。

2 定理的證明

情形1p=103

因?yàn)?032≡1(mod3),1033≡1(mod17),1034≡1(mod5),1036≡1(mod7),10312≡1(mod13),

所以

當(dāng)n≡0(mod2),即n=2m時(shí)，有2k·103n+1=2k·1032m+1≡2k+1(mod3);

當(dāng)n≡0(mod3),即n=3m時(shí)，有2k·103n+1=2k·1033m+1≡2k+1(mod17);

當(dāng)n≡1(mod4),即n=4m+1時(shí)，有2k·103n+1=2k·1034m+1+1≡k+1(mod5);

當(dāng)n≡5(mod6),即n=6m+5時(shí)，有2k·103n+1=2k·1036m+5+1≡ -k+1(mod7);

當(dāng)n≡7(mod12),即n=12m+7時(shí)，有2k·103n+1=2k·10312m+7+1≡ -2k+1(mod13)。

因此，只需k滿足下列同余方程組

(2)

由引理1知，對(duì)每一個(gè)非負(fù)整數(shù)n,2k·103n+1至少被3、17、5、7、13中一數(shù)整除，因而2k·103n+1必是1個(gè)合數(shù)。

由計(jì)算知，(2)式等價(jià)于下列同余方程組

(3)

由于模m1=3,m2=17,m3=5,m4=7,m5=13兩兩互素，故(3)式可用引理2求得k≡2269(mod23205)。于是，所求的正整數(shù)k=2269+23205t，這里t是任意非負(fù)整數(shù)。

情形2p=109

因?yàn)?092≡1(mod3),1093≡1(mod7),1094≡1(mod5),1096≡1(mod11),10912≡1(mod13),

所以

當(dāng)n≡0(mod2),即n=2m時(shí)，有2k·109n+1=2k·1092m+1≡2k+1(mod3);

當(dāng)n≡0(mod3),即n=3m時(shí)，有2k·109n+1=2k·1093m+1≡2k+1(mod7);

當(dāng)n≡1(mod4),即n=4m+1時(shí)，有2k·109n+1=2k·1094m+1+1≡ -2k+1(mod5);

當(dāng)n≡5(mod6),即n=6m+5時(shí)，有2k·109n+1=2k·1096m+5+1≡2k+1(mod11);

當(dāng)n≡7(mod12),即n=12m+7時(shí)，有2k·109n+1=2k·10912m+7+1≡3k+1(mod13)。

因此，只需k滿足下列同余方程組

(4)

由引理1知，對(duì)每一個(gè)非負(fù)整數(shù)n,2k·109n+1至少被3、7、5、11、13中一數(shù)整除，因而2k·109n+1必是1個(gè)合數(shù)。

由計(jì)算知，(4)式等價(jià)于下列同余方程組

(5)

由于模m1=3,m2=7,m3=5,m4=11,m5=13兩兩互素，故(5)式可用引理2求得k≡7843(mod15015)。于是，所求的正整數(shù)k=7843+15015t,這里t是任意非負(fù)整數(shù)。

情形3p=127

因?yàn)?272≡1(mod3),1273≡1(mod7),1274≡1(mod5),1276≡1(mod13),12712≡1(mod457),

所以

當(dāng)n≡0(mod2),即n=2m時(shí)，有2k·127n+1=2k·1272m+1≡2k+1(mod3);

當(dāng)n≡0(mod3),即n=3m時(shí)，有2k·127n+1=2k·1273m+1≡2k+1(mod7);

當(dāng)n≡1(mod4),即n=4m+1時(shí)，有2k·127n+1=2k·1274m+1+1≡ -k+1(mod5);

當(dāng)n≡5(mod6),即n=6m+5時(shí)，有2k·127n+1=2k·1276m+5+1≡ -6k+1(mod13);

當(dāng)n≡7(mod12),即n=12m+7時(shí)，有2k·127n+1=2k·12712m+7+1≡203k+1(mod457)。

因此，只需k滿足下列同余方程組

(6)

由引理1知，對(duì)每一個(gè)非負(fù)整數(shù)n,2k·127n+1至少被3、7、5、13、457中一數(shù)整除，因而2k·127n+1必是1個(gè)合數(shù)。

由計(jì)算知，(6)式等價(jià)于下列同余方程組

(7)

由于模m1=3,m2=7,m3=5,m4=13,m5=457兩兩互素，故(7)式可用引理2求得k≡356926(mod623805)。于是，所求的正整數(shù)k=356926+623805t,這里t是任意非負(fù)整數(shù)。

情形4p=139

因?yàn)?392≡1(mod5),1393≡1(mod3),1394≡1(mod7),1396≡1(mod13).13912≡1(mod23),

所以

當(dāng)n≡0(mod2),即n=2m時(shí)，有2k·139n+1=2k·1392m+1≡2k+1(mod5);

當(dāng)n≡0(mod3),即n=3m時(shí)，有2k·139n+1=2k·1393m+1≡2k+1(mod3);

當(dāng)n≡1(mod4),即n=4m+1時(shí)，有2k·139n+1=2k·1394m+1+1≡-2k+1(mod7);

當(dāng)n≡5(mod6),即n=6m+5時(shí)，有2k·139n+1=2k·1396m+5+1≡6k+1(mod13);

當(dāng)n≡7(mod12),即n=12m+7時(shí)，有2k·139n+1=2k·13912m+7+1≡2k+1(mod23)。

因此，只需k滿足下列同余方程組

(8)

由引理1知，對(duì)每一個(gè)非負(fù)整數(shù)n,2k·139n+1至少被5、3、7、13、23中一數(shù)整除，因而2k·139n+1必是1個(gè)合數(shù)。

由計(jì)算知，(8)式等價(jià)于下列同余方程組

(9)

由于模m1=5,m2=3,m3=7,m4=13,m5=23兩兩互素，故(9)式可用引理2求得k≡21907(mod31395)。于是，所求的正整數(shù)k=21907+31395t,這里t是任意非負(fù)整數(shù)。

情形5p=151

因?yàn)?512≡1(mod3),1513≡1(mod7),1514≡1(mod13),1516≡1(mod5),15112≡1(mod19),

所以

當(dāng)n≡0(mod2),即n=2m時(shí)，有2k·151n+1=2k·1512m+1≡2k+1(mod3);

當(dāng)n≡0(mod3),即n=3m時(shí)，有2k·151n+1=2k·1513m+1≡2k+1(mod7);

當(dāng)n≡1(mod4),即n=4m+1時(shí)，有2k·151n+1=2k·1514m+1+1≡3k+1(mod13);

當(dāng)n≡5(mod6),即n=6m+5時(shí)，有2k·151n+1=2k·1516m+5+1≡2k+1(mod5);

當(dāng)n≡7(mod12),即n=12m+7時(shí)，有2k·151n+1=2k·15112m+7+1≡ -2k+1(mod19)。

因此，只需k滿足下列同余方程組

(10)

由引理1知，對(duì)每一個(gè)非負(fù)整數(shù)n,2k·151n+1至少被3、7、13、5、19中一數(shù)整除，因而2k·151n+1必是1個(gè)合數(shù)。

由計(jì)算知，(10)式等價(jià)于下列同余方程組

(11)

由于模m1=3,m2=7,m3=13,m4=5,m5=19兩兩互素，故(11)式可用引理2求得k≡3202(mod25935)。于是，所求的正整數(shù)k=3202+25935t，這里t是任意非負(fù)整數(shù)。

情形6p=157

因?yàn)?572≡1(mod3),1573≡1(mod13),1574≡1(mod5),1576≡1(mod7),15712≡1(mod17),

所以

當(dāng)n≡0(mod2),即n=2m時(shí)，有2k·157n+1=2k·1572m+1≡2k+1(mod3);

當(dāng)n≡0(mod3),即n=3m時(shí)，有2k·157n+1=2k·1573m+1≡2k+1(mod13);

當(dāng)n≡1(mod4),即n=4m+1時(shí)，有2k·157n+1=2k·1574m+1+1≡-k+1(mod5);

當(dāng)n≡5(mod6),即n=6m+5時(shí)，有2k·157n+1=2k·1576m+5+1≡3k+1(mod7);

當(dāng)n≡7(mod12),即n=12m+7時(shí)，有2k·157n+1=2k·15712m+7+1≡9k+1(mod17)。

因此，只需k滿足下列同余方程組

(12)

由引理1知，對(duì)每一個(gè)非負(fù)整數(shù)n,2k·157n+1至少被3、13、5、7、17中一數(shù)整除，因而2k·157n+1必是1個(gè)合數(shù)。

由計(jì)算知，(12)式等價(jià)于下列同余方程組

(13)

由于模m1=3,m2=13,m3=5,m4=7,m5=17兩兩互素，故(13)式可用引理2求得k≡20806(mod23205)。于是，所求的正整數(shù)k=20806+23205t,這里t是任意非負(fù)整數(shù)。

情形7p=163

因?yàn)?632≡1(mod3),1633≡1(mod7),1634≡1(mod5),1636≡1(mod19),16312≡1(mod13),

所以

當(dāng)n≡0(mod2),即n=2m時(shí)，有2k·163n+1=2k·1632m+1≡2k+1(mod3);

當(dāng)n≡0(mod3),即n=3m時(shí)，有2k·163n+1=2k·1633m+1≡2k+1(mod7);

當(dāng)n≡1(mod4),即n=4m+1時(shí)，有2k·163n+1=2k·1634m+1+1≡k+1(mod5);

當(dāng)n≡5(mod6),即n=6m+5時(shí)，有2k·163n+1=2k·1636m+5+1≡ -5k+1(mod19);

當(dāng)n≡7(mod12),即n=12m+7時(shí)，有2k·163n+1=2k·16312m+7+1≡ -k+1(mod13)。

因此，只需k滿足下列同余方程組

(14)

由引理1知，對(duì)每一個(gè)非負(fù)整數(shù)n,2k·163n+1至少被3、7、5、19、13中一數(shù)整除，因而2k·163n+1必是1個(gè)合數(shù)。

由計(jì)算知，(14)式等價(jià)于下列同余方程組

(15)

由于模m1=3,m2=7,m3=5,m4=19,m5=13兩兩互素，故(15)式可用引理2求得k≡23089(mod25935)。于是，所求的正整數(shù)k=23089+25935t,這里t是任意非負(fù)整數(shù)。

情形8p=181

因?yàn)?812≡1(mod3),1813≡1(mod5),1814≡1(mod7),1816≡1(mod13),18112≡1(mod31),

所以

當(dāng)n≡0(mod2),即n=2m時(shí)，有2k·181n+1=2k·1812m+1≡2k+1(mod3)

當(dāng)n≡0(mod3),即n=3m時(shí)，有2k·181n+1=2k·1813m+1≡2k+1(mod5)

當(dāng)n≡1(mod4),即n=4m+1時(shí)，有2k·181n+1=2k·1814m+1+1≡ -2k+1(mod7)

當(dāng)n≡5(mod6),即n=6m+5時(shí)，有2k·181n+1=2k·1816m+5+1≡ -2k+1(mod13)

當(dāng)n≡7(mod12),即n=12m+7時(shí)，有2k·181n+1=2k·18112m+7+1≡ -10k+1(mod31)。

因此，只需k滿足下列同余方程組

(16)

由引理1知，對(duì)每一個(gè)非負(fù)整數(shù)n,2k·181n+1至少被3、5、7、13、31中一數(shù)整除，因而2k·181n+1必是1個(gè)合數(shù)。

由計(jì)算知，(16)式等價(jià)于下列同余方程組

(17)

由于模m1=3,m2=5,m3=7,m4=13,m5=31兩兩互素，故(17)式可用引理2求得k≡34717(mod42315)。于是，所求的正整數(shù)k=34717+42315t,這里t是任意非負(fù)整數(shù)。

情形9p=193

因?yàn)?932≡1(mod3),1933≡1(mod7),1934≡1(mod5),1936≡1(mod97),19312≡1(mod13),

所以

當(dāng)n≡0(mod2),即n=2m時(shí)，有2k·193n+1=2k·1932m+1≡2k+1(mod3);

當(dāng)n≡0(mod3),即n=3m時(shí)，有2k·193n+1=2k·1933m+1≡2k+1(mod7);

當(dāng)n≡1(mod4),即n=4m+1時(shí)，有2k·193n+1=2k·1934m+1+1≡k+1(mod5);

當(dāng)n≡5(mod6),即n=6m+5時(shí)，有2k·193n+1=2k·1936m+5+1≡ -2k+1(mod97);

當(dāng)n≡7(mod12),即n=12m+7時(shí)，有2k·193n+1=2k·19312m+7+1≡4k+1(mod13)。

因此，只需k滿足下列同余方程組

(18)

由引理1知，對(duì)每一個(gè)非負(fù)整數(shù)n,2k·193n+1至少被3、7、5、97、13中一數(shù)整除，因而2k·193n+1必是1個(gè)合數(shù)。

由計(jì)算知，(18)式等價(jià)于下列同余方程組

(19)

由于模m1=3,m2=7,m3=5,m4=97,m5=13兩兩互素，故(19)式可用引理2求得k≡66979(mod132405)。于是，所求的正整數(shù)k=66979+132405t,這里t是任意非負(fù)整數(shù)。

情形10p=199

因?yàn)?992≡1(mod3),1993≡1(mod11),1994≡1(mod5),1996≡1(mod7),19912≡1(mod13),

所以

當(dāng)n≡0(mod2),即n=2m時(shí)，有2k·199n+1=2k·1992m+1≡2k+1(mod3);

當(dāng)n≡0(mod3),即n=3m時(shí)，有2k·199n+1=2k·1993m+1≡2k+1(mod11);

當(dāng)n≡1(mod4),即n=4m+1時(shí)，有2k·199n+1=2k·1994m+1+1≡ -2k+1(mod5);

當(dāng)n≡5(mod6),即n=6m+5時(shí)，有2k·199n+1=2k·1996m+5+1≡3k+1(mod7);

當(dāng)n≡7(mod12),即n=12m+7時(shí)，有2k·199n+1=2k·19912m+7+1≡ -5k+1(mod13)。

因此，只需k滿足下列同余方程組

(20)

由引理1知，對(duì)每一個(gè)非負(fù)整數(shù)n,2k·199n+1至少被3,11,5,7,13中一數(shù)整除，因而2k·199n+1必是1個(gè)合數(shù)。

由計(jì)算知，(20)式等價(jià)于下列同余方程組

(21)

由于模m1=3,m2=11,m3=5,m4=7,m5=13兩兩互素，故(21)式可用引理2求得k≡1633(mod15015)。于是，所求的正整數(shù)k=1633+15015t,這里t是任意非負(fù)整數(shù)。

定理得證。

3 結(jié) 論

本文定理進(jìn)一步支持了文獻(xiàn)[6]中提出的猜想，具體給出了使2kpn+1(10013,使q|(p3-1),即可證猜想成立。

表1 p與q的取值

通過(guò)表1發(fā)現(xiàn)，當(dāng)p≡1(mod6)(7≤p<1000)時(shí)，猜想都成立。