橢圓曲線整數點的遞推序列及二次剩余法求解

董 鑫,牟全武

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

0 引言與主要結果

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

在文獻[14]中,Zagier給出了尋找有理數域上的橢圓曲線大整數點的3種方法；Zagier還構造了一批有大整數點的橢圓曲線。例如，橢圓曲線

y2=x3+27x-62

(1)

有大整數點

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

橢圓曲線

y2=x3-30x+133

(2)

有整數點(x,y)=(5 143 326,±11 664 498 677)。

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

定理1橢圓曲線(2)的所有整數點是

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

(5 143 326,±11 664 498 677)

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

1 若干引理

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

(3)

容易驗證下列關系式成立:

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,那么

證明當m>0且8|m時,由式(6)與(7)得

(16)

另外,由式(7)推出

所以

(17)

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

(18)

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

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

引理3?m∈N+,有

(19)

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

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

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

H0=676,H1=206 596

假設對于非負整數n,Hn是完全平方數。下面的模素數p的運算是直接對數列{Hn}進行的,取最小非負剩余。證明分為4步進行。

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

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

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

為簡便起見,以下省略了關于剩余類序列周期的說明。

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

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

5) mod 239,排除n≡40(mod 80),因為Hn≡177(mod 239)是非平方剩余。故余下n≡0,2,10,42,50(mod 80),等價于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),因為Hn≡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),因為Hn≡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),因為Hn≡668(mod 673)是非平方剩余。故排除n≡90,122(mod 240),余下n≡0,2,210(mod 240)。

9) mod 3 121,排除n≡10(mod 40),因為Hn≡2 162(mod 3 121)是非平方剩余,故排除n≡210(mod 240),余下n≡0,2(mod 240),等價于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),因為Hn≡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),因為Hn≡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),因為Hn≡820,390(mod 1 429)是非平方剩余。mod 29,排除n≡4,11(mod 14),因為Hn≡27,21(mod 29)是非平方剩余。故排除n≡4(mod 7),余下n≡0,2,3,5(mod 7)。注意前面已經證明了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),因為Hn≡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),因為Hn≡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),因為Hn≡2,12,35,23,18(mod 53)是非平方剩余;mod 443,排除n≡8,9,11(mod 13),因為Hn≡228,60,353(mod 443)是非平方剩余。余下n≡0,2,5,6,10(mod 13),等價于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),因為Hn≡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),因為Hn≡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),因為Hn≡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),因為Hn≡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),因為Hn≡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),因為Hn≡163(mod 547)是非平方剩余。故排除n≡100 802(mod 1 200·7·13),余下n≡0,2(mod 1 200·7·13)。

綜上,引理4得證。

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

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

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

G0=0,G1=11 232

下面的模素數p的運算是對數列{Gn}進行的,取最小非負剩余。假設對某些n∈N,Gn是完全平方數。

1) mod 5,排除n≡1(mod 2),因為Gn≡2(mod 5)是非平方剩余。余下n≡0(mod 2),等價于n≡0,2(mod 4)。

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

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

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

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

6) mod 181,排除n≡10(mod 30),因為Gn≡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),因為Gn≡51,668(mod 919)是非平方剩余。故排除n≡60,120(mod 180),余下n≡0(mod 180)。

引理5得證。

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

證明根據式(3)～(5),當n=0時26(xn+21)=262。 若n>0,不妨設

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

1) 當k≡1(mod 4)時,令

可得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) 當k≡3(mod 4)時,令

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

(22)

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

(23)

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

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

證明若n=2,則26(xn+21)=16 3542。 當n>2時,設

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是奇數。由式(13)可得xn≡-x2≡-10 286 645(modum),故根據式(7)推出

容易驗證

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

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

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

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

1) 當k≡1(mod 4)時,設

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

(25)

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

(26)

2) 當k≡3(mod 4)時,令

則m≡1,3,4,5,10,16,18,19,21,22(mod 25),相應地有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)

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

2 定理的證明

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

(29)

消去x可得

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

(30)

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

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

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

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

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

(31)

(32)

(33)

(34)

如果式(31)成立,那么

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

(35)

2b=2un+5vn

(36)

由式(35)知，26(xn+21)是完全平方數。根據引理4、引理6及引理7,有n=0,2,相應地得到(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)是完全平方數。由引理5及引理8知n=0, 所以a=0。與a>0矛盾。

當d=117時,式(30)可化為

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

(37)

(38)

或

(39)

式中：n為非負整數。

綜上所述,定理1得證。

3 結 語

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