關(guān)于覆蓋同余式的一個(gè)應(yīng)用

管訓(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ù).

1　預(yù)備知識(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得證.

2　定理的證明

分兩步進(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.001