橢圓曲線整數(shù)點(diǎn)的遞推序列及二次剩余法求解

董 鑫,牟全武

(西安工程大學(xué) 理學(xué)院,陜西 西安 710048)

0 引言與主要結(jié)果

橢圓曲線是虧格為1的代數(shù)曲線,至少有一個(gè)已知點(diǎn)。根據(jù)Riemann-Roch定理,在同構(gòu)意義下有理數(shù)域上任一橢圓曲線的方程總可以化為Weierstrass方程E:y2=x3+Ax+B,這里A與B為有理數(shù)。方程E的判別式定義為Δ=-16(4A3+27B2)。當(dāng)A與B為整數(shù)且判別式Δ非零時(shí),由Siegel定理知，在橢圓曲線E上只有有限個(gè)整數(shù)點(diǎn)。盡管人們已從Mordell-Weil定理[1]知橢圓曲線E上所有有理點(diǎn)構(gòu)成的集合是有限生成的Abel群,但在一般情形下要求出具體的有理點(diǎn)或整數(shù)點(diǎn)，仍是數(shù)論中十分困難的問(wèn)題,至今沒(méi)有得到完全解決。針對(duì)某些特殊的橢圓曲線,國(guó)內(nèi)外學(xué)者已得到不少結(jié)果[2-13]。

在文獻(xiàn)[14]中,Zagier給出了尋找有理數(shù)域上的橢圓曲線大整數(shù)點(diǎn)的3種方法；Zagier還構(gòu)造了一批有大整數(shù)點(diǎn)的橢圓曲線。例如，橢圓曲線

y2=x3+27x-62

(1)

有大整數(shù)點(diǎn)

(x,y)=(28 844 402,±154 914 585 540)

橢圓曲線

y2=x3-30x+133

(2)

有整數(shù)點(diǎn)(x,y)=(5 143 326,±11 664 498 677)。

文獻(xiàn)[15]用代數(shù)數(shù)論及p-adic分析方法給出了橢圓曲線(1)的全部整數(shù)點(diǎn);文獻(xiàn)[16-17]根據(jù)四次丟番圖方程的已知結(jié)果,對(duì)文獻(xiàn)[15]的結(jié)果分別給出了簡(jiǎn)化證明。文獻(xiàn)[18]證明了以下結(jié)果:

定理1橢圓曲線(2)的所有整數(shù)點(diǎn)是

(x,y)=(-7,0),(-3,±14),(2,±9),(6,±13),

(5 143 326,±11 664 498 677)

由于文獻(xiàn)[18]的證明需要在一類全虛四次域的子環(huán)上討論二次代數(shù)整數(shù)的分解并計(jì)算其單位,所以證明過(guò)程比較復(fù)雜。 在文獻(xiàn)[19-20]中, 羅明通過(guò)改進(jìn)Cohn的遞推序列方法[21], 先后解決了Fibonacci數(shù)列和Lucas數(shù)列中的三角數(shù)問(wèn)題, 后來(lái)他又用這一方法解決了Lucas數(shù)列中的五角數(shù)問(wèn)題[22]。 這些工作顯示了遞推序列方法在解決一些困難的數(shù)論問(wèn)題時(shí)十分有效。 受文獻(xiàn)[19-20]及[22]證明思想的啟發(fā), 本文利用遞推序列及二次剩余給出了定理1的初等證明。

1 若干引理

xn=5un+26vn,zn=-21un+78vn

(3)

容易驗(yàn)證下列關(guān)系式成立:

un+2=1 298un+1-un,u0=1,u1=649

(4)

vn+2=1 298vn+1-vn,v0=0,v1=180

(5)

(6)

un≡1(mod 24),un≡±1(mod 13),

u2n≡1(mod 5)

(7)

u2n+1≡0(mod 11),u8n+1≡3(mod 17),

u8n+5≡-3(mod 17)

(8)

u8n≡1(mod 17),v8n≡0(mod 17),

v4n+3≡-4(mod 11)

(9)

v8n+1≡-7(mod 17),v8n+5≡7(mod 17)

(10)

引理1?n,k,m∈N+,有

un+2km≡(-1)kun(modum)

vn+2km≡(-1)kvn(modum)

(11)

0(modum)

(12)

un+2km=Aun+13Bvn≡(-1)kun(modum)

vn+2km=Avn+13Bun≡(-1)kvn(modum)

引理1得證。

由式(3)及引理1可得如下的推論：

推論1?n,k,m∈N+有

xn+2km≡(-1)kxn(modum),

zn+2km≡(-1)kzn(modum)

(13)

x2m(4k+1)≡x2m(modu2m),

x2m(4k+3)≡-x2m(modu2m)

(14)

z2m(4k+1)≡z2m(modu2m),

z2m(4k+3)≡-z2m(modu2m)

(15)

引理2如果m>0且8|m,那么

證明當(dāng)m>0且8|m時(shí),由式(6)與(7)得

(16)

另外,由式(7)推出

所以

(17)

當(dāng)8|m時(shí),由式(9)得21um±26vm≡4(mod 17),因此

(18)

由式(16)～(18),引理2得證。

利用與引理2類似的證明過(guò)程,可以得到引理3，證明過(guò)程略去。

引理3?m∈N+,有

(19)

引理4當(dāng)n≥0時(shí),若26(xn+21)是完全平方數(shù),則n≡0,2(mod 1 200·7·13)。

證明為方便起見,令Hn=26(xn+21)。根據(jù)式(3)～(5)容易證明以下遞推關(guān)系:

Hn+2=1 298Hn+1-Hn-707 616

H0=676,H1=206 596

假設(shè)對(duì)于非負(fù)整數(shù)n,Hn是完全平方數(shù)。下面的模素?cái)?shù)p的運(yùn)算是直接對(duì)數(shù)列{Hn}進(jìn)行的,取最小非負(fù)剩余。證明分為4步進(jìn)行。

第1步：證明n≡0,2(mod 1 200)。

1) mod 59,{Hn}的剩余類序列周期是4。因?yàn)閚≡1,3(mod 4)分別對(duì)應(yīng)著Hn≡37,52(mod 59),是非平方剩余,故排除。故余下n≡0,2(mod 4)等價(jià)于n≡0,2,4,6(mod 8)。

2) mod 7,{Hn}的剩余類序列周期是8。因?yàn)閚≡4,6(mod 8)，對(duì)應(yīng)著Hn≡3(mod 7)是非平方剩余,故排除。余下n≡0,2(mod 8)。

為簡(jiǎn)便起見,以下省略了關(guān)于剩余類序列周期的說(shuō)明。

3) mod 61,排除n≡1(mod 5),因?yàn)镠n≡50(mod 61)是非平方剩余;mod 131,排除n≡3,4(mod 5),因?yàn)镠n≡116,47(mod 131)是非平方剩余。故，余下n≡0,2(mod 5 )。由于n≡0,2(mod 8),有n≡0,2,10,32(mod 40),等價(jià)于n≡0,2,10,32,40,42,50,72(mod 80)。

4) mod 19,排除n≡12(mod 20),因?yàn)镠n≡3(mod 19)是非平方剩余。故排除n≡32,72(mod 80),余下n≡0,2,10,40,42,50(mod 80)。

5) mod 239,排除n≡40(mod 80),因?yàn)镠n≡177(mod 239)是非平方剩余。故余下n≡0,2,10,42,50(mod 80),等價(jià)于n≡0,2,10,42,50,80,82,90,122,130,160,162,170,202,210(mod 240)。

6) mod 433,排除n≡1(mod 3),因?yàn)镠n≡55(mod 433)是非二次剩余。故排除n≡10,82,130,160,202(mod 240),余下n≡0,2,42,50,80,90,122,162,170,210(mod 240)。

7) mod 181,排除n≡12,20(mod 30),因?yàn)镠n≡104,54(mod 181)是非平方剩余。故排除n≡42,50,80,162,170(mod 240),余下n≡0,2,90,122,210(mod 240)。

8) mod 673,排除n≡10(mod 16),因?yàn)镠n≡668(mod 673)是非平方剩余。故排除n≡90,122(mod 240),余下n≡0,2,210(mod 240)。

9) mod 3 121,排除n≡10(mod 40),因?yàn)镠n≡2 162(mod 3 121)是非平方剩余,故排除n≡210(mod 240),余下n≡0,2(mod 240),等價(jià)于n≡0,2,240,242,480,482,720,722,960,962(mod 1 200)。

10) mod449,排除n≡30,32,60,90,92,120,122(mod 150),因?yàn)镠n≡109,402,151,15,284,432,17(mod 449)是非平方剩余。故排除n≡240, 242, 480, 482, 720, 722, 960(mod 1 200),余下n≡0,2,962(mod 1 200)。

11) mod 4 801,排除n≡162(mod 200),因?yàn)镠n≡2 508(mod 4 801)是非平方剩余。故排除n≡962(mod 1 200),余下n≡0,2(mod 1 200)。

第2步:證明n≡0,2(mod 7)。

1)mod 1 429,排除n≡1,6(mod 7),因?yàn)镠n≡820,390(mod 1 429)是非平方剩余。mod 29,排除n≡4,11(mod 14),因?yàn)镠n≡27,21(mod 29)是非平方剩余。故排除n≡4(mod 7),余下n≡0,2,3,5(mod 7)。注意前面已經(jīng)證明了n≡0, 2(mod 1 200),故余下n≡0,2,1 200,1 202, 3 600,4 800,4 802,6 002(mod 8 400)。

2) mod 83,排除n≡12,26(mod 28),因?yàn)镠n≡50,46(mod 83)是非平方剩余。故排除n≡4 800,1 202(mod 8 400),余下n≡0,2,1 200,3 600,4 802,6 002(mod 8 400)。

3) mod 113,排除n≡10,16,24(mod 56),因?yàn)镠n≡76,24,23(mod 113)是非平方剩余。故排除n≡6 002,3 600,1 200(mod 8 400),余下n≡0,2,4 802(mod 8 400),即n≡0,2(mod 7)。

第3步:證明n≡0,2(mod 13)。

1) mod 53,排除n≡1,3,4,7,12(mod 13),因?yàn)镠n≡2,12,35,23,18(mod 53)是非平方剩余;mod 443,排除n≡8,9,11(mod 13),因?yàn)镠n≡228,60,353(mod 443)是非平方剩余。余下n≡0,2,5,6,10(mod 13),等價(jià)于n≡0,2,5,6,10,13,15,18,19,23(mod 26)。

2) mod 157,排除n≡5,10,13,15,18,19,23(mod 26),因?yàn)镠n≡85,65,102,65,150,85(mod 157)是非平方剩余,余下n≡0,2,6(mod 26)。又由于n≡0,2(mod 3),所以余下n≡0,2,6,26,32,54(mod 78)。

3) mod 1 873,排除n≡6,26,32(mod 39),因?yàn)镠n≡1 140,1 233,1 429(mod 1 873)是非平方剩余,故排除n≡6,26,32(mod 78),余下n≡0,2,54(mod 78),即n≡0,2(mod 13)。

第4步:證明n≡0,2(mod 1 200·7·13)。

從前面3步推出n≡0,2,8 400,38 402,46 802,62 400,70 800,100 802(mod 1 200·7·13)。

1) mod 127,排除n≡9(mod 21),因?yàn)镠n≡105(mod 127)是非平方剩余。故排除n≡62 400,70 800(mod 1 200·7·13),余下

n≡0,2,8 400,38 402,46 802,100 802(mod 1 200·7·13)

2) mod 337,排除n≡42(mod 56),因?yàn)镠n≡134(mod 337)是非平方剩余。故排除n≡38 402,46 802(mod 1 200·7·13)。余下n≡0,2,8 400,100 802(mod 1 200·7·13)。

3) mod 521,排除n≡80(mod 260),因?yàn)镠n≡272(mod 521)是非平方剩余。故排除n≡8 400(mod 1 200·7·13),余下n≡0,2,100 802(mod 1 200·7·13)。

4) mod 547,排除n≡65(mod 91),因?yàn)镠n≡163(mod 547)是非平方剩余。故排除n≡100 802(mod 1 200·7·13),余下n≡0,2(mod 1 200·7·13)。

綜上,引理4得證。

引理5當(dāng)n≥0時(shí),若26(zn+21)是完全平方數(shù),則n≡0(mod 180)。

證明證明過(guò)程與引理4類似。令Gn=26(zn+21),根據(jù)式(3)～(5)可得遞推關(guān)系式

Gn+2=1 298Gn+1-Gn-707 616,

G0=0,G1=11 232

下面的模素?cái)?shù)p的運(yùn)算是對(duì)數(shù)列{Gn}進(jìn)行的,取最小非負(fù)剩余。假設(shè)對(duì)某些n∈N,Gn是完全平方數(shù)。

1) mod 5,排除n≡1(mod 2),因?yàn)镚n≡2(mod 5)是非平方剩余。余下n≡0(mod 2),等價(jià)于n≡0,2(mod 4)。

2) mod 59,排除n≡2(mod 4),因?yàn)镚n≡30(mod 59)是非平方剩余。余下n≡0(mod 4),等價(jià)于n≡0,4,8,12,16(mod 20)。

3) mod 61,排除n≡1,2,4(mod 5),因?yàn)镚n≡8,59,37(mod 61)是非平方剩余。故排除n≡4,12,16(mod 20),余下n≡0,8(mod 20)。

4) mod 211,排除n≡3(mod 5),因?yàn)镚n≡162(mod 211)是非平方剩余。故排除n≡8(mod 20),余下n≡0(mod 20),即余下n≡0,20,40(mod 60)。

5) mod 89,排除n≡20(mod 30),因?yàn)镚n≡58(mod 89)是非平方剩余。故排除n≡20(mod 60),余下n≡0,40(mod 60)。

6) mod 181,排除n≡10(mod 30),因?yàn)镚n≡109(mod 181)是非平方剩余。故排除n≡40(mod 60),余下n≡0(mod 60),即n≡0,60,120(mod 180)。

7) mod 919,排除n≡3,6(mod 9),因?yàn)镚n≡51,668(mod 919)是非平方剩余。故排除n≡60,120(mod 180),余下n≡0(mod 180)。

引理5得證。

引理6若n≥0且n≡0(mod 1 200·7·13),則僅當(dāng)n=0時(shí),26(xn+21)是完全平方數(shù)。

證明根據(jù)式(3)～(5),當(dāng)n=0時(shí)26(xn+21)=262。 若n>0,不妨設(shè)

n=2·2t·3·52·7·13·k,t≥3, 2?k

1) 當(dāng)k≡1(mod 4)時(shí),令

可得m≡2,4,12(mod 14),由此知21um+26vm≡25,23,5(mod 29),因此

(20)

另外,由式(14)推出xn≡x2m(modu2m),而由式(3)可知，x2m≡26v2m(modu2m),因此，xn≡26v2m(modu2m)。利用式(7),(20)及引理2可得

(21)

2) 當(dāng)k≡3(mod 4)時(shí),令

則m≡2,10(mod 14),由此知21um-26vm≡5,23(mod 29),所以

(22)

由式(14)、(3)得xn≡-26v2m(modu2m)。 與式(21)類似,由式(7)、引理2及式(22)推出

(23)

顯然由式(21)和式(23)可知，當(dāng)n>0時(shí),26(xn+21)不是完全平方數(shù)。引理6得證。

引理7若n>0且n≡2(mod 1 200·7·13),則僅當(dāng)n=2時(shí)26(xn+21)是完全平方數(shù)。

證明若n=2,則26(xn+21)=16 3542。 當(dāng)n>2時(shí),設(shè)

n=2+2·2t·3·52·7·13·k,t≥3, 2?k

(24)

m的取值為

1)m=2t·3,若t≡1,2,3,5,6,8,9,12,15,17,20,23,24,25,27,29,30,32,34,35,36,40,43,44,45,46,49(mod 51);

2)m=2t,若t≡0,7,16,21,22,28,33,39,42,47,48,50,55,61,64,69,70,82,88,98,101(mod 102);

3)m=2t·52,若t≡4,10,11,13,14,26,38,58,62,65,67,77,79,89(mod 102);

4)m=2t·3·5,若t≡37,41,84,90,92,93(mod 102);

5)m=2t·3·52,若t≡72,73(mod 102);

6)m=2t·7,若t≡51,99(mod 102);

7)m=2t·13,若t≡18,19,31(mod 102)。

則式(24)可寫成n=2+2mr,r是奇數(shù)。由式(13)可得xn≡-x2≡-10 286 645(modum),故根據(jù)式(7)推出

容易驗(yàn)證

因此當(dāng)n>2時(shí),26(xn+21)不是完全平方數(shù)。引理7得證。

引理8若n≥0且n≡0(mod 180),則僅當(dāng)n=0時(shí)26(zn+21)是完全平方數(shù)。

證明若n=0, 則26(zn+21)=0。 如果n>0,設(shè)

n=2·2t·32·5·k,t≥1, 2?k

1) 當(dāng)k≡1(mod 4)時(shí),設(shè)

則m≡3,4,6,7,9,15,20,21,22,24(mod 25),相應(yīng)地有7um+26vm≡1,68,97,71,88,9,52,76,20,65(mod 101)。因此,

(25)

由式(3)及推論1得，zn≡z2m≡78v2m(modu2m)。再根據(jù)引理3、式(7)及式(25),可得

(26)

2) 當(dāng)k≡3(mod 4)時(shí),令

則m≡1,3,4,5,10,16,18,19,21,22(mod 25),相應(yīng)地有7um-26vm≡65,20,76,52,9,88,71,97,68,1(mod 101)。因此

(27)

由式(3)及推論1，可得zn≡-z2m≡-78v2m(modu2m)。由此及引理3及式(7)、(27)推出

(28)

結(jié)合式(26)和式(28)可以得到，當(dāng)n>0時(shí)26(zn+21)不是完全平方數(shù)。引理8得證。

2 定理的證明

因?yàn)閥2=x3-30x+133=(x+7)(x2-7x+19),顯然(x,y)=(-7,0)是方程(2)的一個(gè)解。因此,只需要考慮x>-7的情況。令d為x+7和x2-7x+19的最大公因數(shù),那么d=1,3,9,13,39,117,且存在互素的正整數(shù)a,b使得

(29)

消去x可得

(2da2-21)2-d(2b)2=-27

(30)

當(dāng)d=1時(shí),由式(30)知(a,b)=(2,7),再由式(29)可得(x,y)=(-3,±14)；

當(dāng)d=3時(shí),由式(30)推出2a2-7≡0(mod 3),與a2≡0,1(mod 3)矛盾。

當(dāng)d=9時(shí),由式(30)得(2b)2-(6a2-7)2=3,解得a=b=1,因此(x,y)=(2,±9)；

當(dāng)d=39時(shí),由式(30)推出26a2-7≡0(mod 3),與a2≡0,1(mod 3)矛盾；

注意到,26a2-21≥-21。根據(jù)文獻(xiàn)[23]的定理109,式(30)的全部解可寫成下面的形式：

(31)

(32)

(33)

(34)

如果式(31)成立,那么

26a2-21=5un+26vn=xn

(35)

2b=2un+5vn

(36)

由式(35)知，26(xn+21)是完全平方數(shù)。根據(jù)引理4、引理6及引理7,有n=0,2,相應(yīng)地得到(a,b)=(1, 1), (629,1 426 501)。再由式(27)可得(x,y)=(6,±13),(5 143 326,±11 664 498 677)

如果式(32)成立,則26a2-21=-5un+26vn。由式(5)和式(7)得到a2≡2(mod 3)。矛盾。

如果式(34)成立,那么26a2-21=-21un+78vn=zn,可得26(zn+21)是完全平方數(shù)。由引理5及引理8知n=0, 所以a=0。與a>0矛盾。

當(dāng)d=117時(shí),式(30)可化為

(78a2-7)2-13(2b)2=-3

(37)

(38)

或

(39)

式中：n為非負(fù)整數(shù)。

綜上所述,定理1得證。

3 結(jié) 語(yǔ)

橢圓曲線的整數(shù)點(diǎn)問(wèn)題一直是數(shù)論學(xué)者研究的熱點(diǎn)問(wèn)題。 由于曲線類型的多樣性,沒(méi)有一個(gè)統(tǒng)一的方法或算法能在有限步之內(nèi)求解出任意給定的橢圓曲線的整數(shù)點(diǎn)。本文將橢圓曲線的整數(shù)點(diǎn)問(wèn)題轉(zhuǎn)化為研究遞推序列的數(shù)論性質(zhì)(主要是同余性質(zhì)),并最終利用排除法求出了所有整數(shù)點(diǎn)。遞推序列方法雖然是一種初等的方法,但通過(guò)與二次剩余相結(jié)合并運(yùn)用一定的技巧,往往變得十分有力,能解決一些困難的丟番圖方程求解問(wèn)題。