同余數(shù)的部分驗證

張家俊，史展銘，王振華，張明達(dá)

（中國礦業(yè)大學(xué)（北京），北京）

一 引言

“勾三股四弦五”，這樣的直角三角形的三邊都是有理數(shù)，我們稱它為“有理直角三角形”。同時，比較湊巧的是，這個“勾三股四弦五”的直角三角形的面積又恰好是一個整數(shù)，這樣的有理直角三角形所對應(yīng)的為整數(shù)的面積被稱為同余數(shù)。

同余數(shù)問題在數(shù)學(xué)界被稱為三大千年數(shù)論難題之一（另外兩個是完全數(shù)問題與三次和三次以上丟番圖方程有解問題）。古阿拉伯人是通過研究直角三角形的面積提出同余數(shù)問題的。對于直角三角形，人們已經(jīng)知道，它的三邊滿足方程a2+b2=c2，這就是我們所說的的勾股定理（在國外又被稱為畢達(dá)哥拉斯定理）。當(dāng)直角三角形的三邊 a, b, c均為有理數(shù)，若直角三角形的面積為正整數(shù)，這樣的就是古阿拉伯人所欲求得的同余數(shù)。

二 預(yù)備知識與相關(guān)結(jié)論

（一） 勾股數(shù)

勾股數(shù)，又名畢氏三元數(shù) 。勾股數(shù)就是可以構(gòu)成一個直角三角形三邊的一組正整數(shù)。勾股定理：直角三角形兩條直角邊a、b的平方和等于斜邊c的平方（a2+b2=c2）

（二） 同余數(shù)

n 被稱為同余數(shù)，如果它是三邊邊長都是有理數(shù)的直角三角形的面積[2]。即：如果存在三個正有理數(shù) a, b, c, 滿足a2+b2=c2,和面積此數(shù)n就稱為同余數(shù)。

整同余數(shù): 如果正整數(shù)n是同余數(shù), 那么,n 稱為整同余數(shù)。

設(shè) n 是正有理數(shù),且對n=s2r,這里s是正有理數(shù),而r是無平方因子的正整數(shù),那么n是同余數(shù)當(dāng)且僅當(dāng)r是同余數(shù)。

由此可見同余數(shù)的問題可轉(zhuǎn)化為整同余數(shù)來處理。

整同余數(shù)重要結(jié)論：

定理： n 是整同余數(shù)的充要條件為存在正整數(shù) a,b, v，使得：

nv2=|6a2b2?a4?b4| or 4ab(a2b2) 其中 ,a,b 是正整數(shù) ,a ＞ b,(a,b)=1, a, b 一奇一偶。

本原同余數(shù)：

如果一個A 是不含平方因子的整同余數(shù)，則 A稱為本原同余數(shù)。

（三） BSD猜想

BSD 猜想，全稱貝赫和斯維納通-戴爾猜想BirchandSwinnerton?Dyer，屬于世界七大數(shù)學(xué)難題之一。它描述了阿貝爾簇的算術(shù)性質(zhì)與解析性質(zhì)之間的聯(lián)系[2-3]。

由 BSD 猜想可以推出奇偶性猜想、西爾維斯特猜想等很多猜想。其中最著名的是與同余數(shù)問題的關(guān)系，從BSD猜想可以推出模 8余5,6,7的無平方因子的正整數(shù)一定可以成為某個有理邊長直角三角形的面積。

把這個定理與橢圓曲線理論相聯(lián)系，使人們對同余數(shù)問題的研究有了重大的進(jìn)展，不過人們同時也發(fā)現(xiàn)，用這個定理去求解一個具體的同余數(shù)仍然非常地困難。例如，人們已知157是同余數(shù)，但在方程的最小解中，x的分母和分子都近100位。

注 1：阿貝爾簇是一個代數(shù)群,它同時又是完全代數(shù)簇。完全性的條件蘊涵著對阿貝爾簇的嚴(yán)格限制。因 而阿貝爾簇可以作為閉子簇嵌入射影空間；非奇異簇道阿貝爾簇道每個有理映射都是正則的， 阿貝爾簇上的 群律是可交換的。

注 2：環(huán)面（torus）是一個面包圈形狀的旋轉(zhuǎn)曲面，由一個圓繞一個和該圓共面的一個軸回轉(zhuǎn)所生成。在拓?fù)鋵W(xué)上，環(huán)面是一個定義為兩個圓的積的閉合曲面。

定義一：與S1×S2同胚的曲面稱為環(huán)面，它是虧格為 1 的可定向閉曲面。通常，環(huán)面可以看作由一個長方體按照逆時針方向分別疊合左右兩邊和上下兩邊而得到的。

定義二：若一個線性代數(shù)群 G 同構(gòu)于某個 D(n,k)，則稱 G 是一個環(huán)面。連通的可對角化代數(shù)群一定是一個環(huán)面。

（四） 橢圓曲線

橢圓曲線是域上虧格為 1 的光滑射影曲線，它的(仿射) 方程，通常稱為維爾斯特拉斯方程，可以 寫 作：y2+ay=x3+ax2+bx+c或y2=x（x-1）（x-λ），λ=0,1復(fù)數(shù)域上的橢圓曲線為虧格為 1 的黎曼面[5,7]。

如果這個域的特征不等于2和3,則可以改寫成y2=x3+ax+b

作為實曲面看，橢圓曲線是帶有一個“洞”的環(huán)面。此環(huán)面可以通過同向粘合正方形的兩對對邊得到，其拓?fù)涮澑駷?1。

注 1：虧格是代數(shù)幾何和代數(shù)拓?fù)渲凶罨镜母拍钪?。虧格的定義為若曲面中最多可畫出n條閉合曲線同時不將曲面分開，則稱該曲面虧格為n。以實的閉曲面為例，虧格g 就是曲面上洞眼的個數(shù)。

注 2：環(huán)面（torus）是一個面包圈形狀的旋轉(zhuǎn)曲面，由一個圓繞一個和該圓共面的一個軸回轉(zhuǎn)所生成。在拓?fù)鋵W(xué)上，環(huán)面是一個定義為兩個圓的積的閉合曲面。

定義一：與S1×S2同胚的曲面稱為環(huán)面，它是虧格為1的可定向閉曲面。通常環(huán)面可以看作由一個長方體按照逆時針方向分別疊合左右兩邊和上下兩邊而得到的。

定義二：若一個線性代數(shù)群G同構(gòu)于某個D（n,k），則稱G是一個環(huán)面。連通的可對角化代數(shù)群一定是一個環(huán)面。

即Q上的橢圓曲線E的有理點是有限生成Abel群：E(Q)=ZR⊕T，T是撓點全體，為有限Abel群，r稱為E的秩。

Nagell-Lutz theorem：P=(x,y)E(Q),如 果是torsion point(即存在正整數(shù)n,使得nP=O,其全體記為E(Q)),則x和y都是整數(shù),并且或者y=0或y2|△[7]。

Mordell-Weil theorem：對于具有二階點的EC，有形如y2=x3+ax3+bx其中a,b為整數(shù)，則其上的有理點群為有限生成[8]。

siegel定理：Q上的橢圓曲線E的整點（坐標(biāo)均為整數(shù)的點），或者更一般的坐標(biāo)有一者為整數(shù)的點，只有有限個[9]。

（五） 無窮遞減法

無窮遞降法是證明方程無解的一種方法。其步驟為：假設(shè)方程有解，并設(shè)X為最小的解。從X推出一個更小的解Y，從而與X的最小性相矛盾。所以，方程無解[2]。

（六） 橢圓曲線的加密算法

橢圓加密算法（ECC）是一種公鑰加密體制，最初由Koblitz和Miller兩人于1985年提出，其數(shù)學(xué)基礎(chǔ)是利用橢圓曲線上的有理點構(gòu)成Abel加法群上橢圓離散對數(shù)的計算困難性。公鑰密碼體制根據(jù)其所依據(jù)的難題一般分為三類：大素數(shù)分解問題類、離散對數(shù)問題類、橢圓曲線類。有時也把橢圓曲線類歸為離散對數(shù)類[5-6]。

在橢圓曲線加密（ECC）中，利用了某種特殊形式的橢圓曲線，即定義在有限域上的橢圓曲線。其方程如下：

y2=x3+ax+b(mod p)

這里p是素數(shù)，a和b為兩個小于p的非負(fù)整數(shù)，它們滿足：(1)4a3+27b2(mod p)≠0 其中，x,y,a,b∈Fp，則滿足式（2）的點（x,y）和一個無窮點O就組成了橢圓曲線E。

橢圓曲線離散對數(shù)問題ECDLP定義如下：給定素數(shù)p和橢圓曲線E，對 Q=kP,在已知P,Q的情況下求出小于p的正整數(shù)k。

三 具體計算

（一） 求解依據(jù)

找一個面積為n的有理直角三角形。我們可以把三邊互素的直角三角形的三邊用很簡單的公式表示出來a=2pq;b=p2-q2;c=p2+q2

這里的 p q 只需要考慮整數(shù)，而*是個平方數(shù)。

橢圓曲線相交理論：Bezout定理告訴我們， 兩條光滑橢圓曲線相交于9個點（切點重復(fù)計算）。 進(jìn)一步，如果有第三條光滑橢圓曲線經(jīng)過其中的8個交點，那它必定經(jīng)過第九個點。這是古典代數(shù)幾何中的一個重要的結(jié)論。歐拉對此問題也有過考慮[5-6]。

作為推廣，X.諾特（Noether）曾經(jīng)得到了更一般的代數(shù)曲線交點的類似結(jié)論。 這個問題和代數(shù)曲面上秩2向量叢的半穩(wěn)定性有著深刻的內(nèi)在聯(lián)系。談勝利利用秩2向量叢的Bogomolov不等式， 將此問題推廣到最一般的情形。

橢圓曲線的退化情形：由于橢圓曲線在射影平面中是三次曲線，所以它可以退化為許多特殊的情形：

（1）三條直線；（2）一條直線和一條二次曲線（即圓錐曲線，比如橢圓，雙曲線，拋物線）。

通過同余數(shù)的定義方式與橢圓曲線上相關(guān)計算的性質(zhì)與結(jié)論，將同余數(shù)的相關(guān)直角三角形的邊長以橢圓曲線上的有理點坐標(biāo)表示出來并給出相關(guān)正有理點的坐標(biāo)。固定所得點坐標(biāo)分母，通過運用數(shù)學(xué)工具編程等方法，在相關(guān)條件的約束下求解符合直角三角形特征的點坐標(biāo)即直角三角形三邊長度。

根 據(jù)Mordell-Weil theorem與Nagell-Lutz theorem，則存在有理數(shù)x，使得x-aiQ2等價于存在公差為n的有理數(shù)平方組成的等差數(shù)列,根據(jù)簡單的勾股定理,這等價于存在一個有理邊長的直角三角形,面積為n。

則我們有如下三個結(jié)論：

存在公差為n的等差數(shù)列u2,v2,w2,其中u,v,w為有理數(shù)；

存在邊長為有理數(shù)a,b,c 的直角三角形，面積為n；

在橢圓曲線E(n):y2=x3-n2x能找到一個有理點，其y坐標(biāo)不為0。

則滿足上述等價的三個條件之一的n稱為同余數(shù)。

（二） 同余數(shù)驗證

驗證方法：

首先，我們設(shè)置四個變量： n, a, b, v

根據(jù)整同余數(shù)的相關(guān)結(jié)論，若n為一個同余數(shù)，則此四個變量應(yīng)符合以下關(guān)系[1]：

(1).(a,b) = 1

(2).a,b一奇數(shù)一偶數(shù)

(3).a,b為正整數(shù)并且 a ＞ b

(4).a,b,n,v 需要滿足nv2=|6a2b2-a4-b4|or4ab(a2b2)

則根據(jù)上述條件進(jìn)行編程計算，驗證部分正整數(shù)n是否為同余數(shù)。

結(jié)果：

5是同余數(shù)，所對應(yīng)數(shù)值為a=5,b=4,v=12

7為同余數(shù),所數(shù)值為a=2,b=1,v=1

13為同余數(shù),所數(shù)值為a=772,b=195,v=8652

14為同余數(shù),所數(shù)值為a=8,b=1,v=12

21為同余數(shù),所對應(yīng)數(shù)值為a=4,b=3,v=4

22為同余數(shù),所對應(yīng)數(shù)值為a=50,b=49,v=210

23為同余數(shù),所對應(yīng)數(shù)值為a=13,b=6,v=17

通過驗證得出5,7,13,14,15,21,2,23為同余數(shù)，進(jìn)而根據(jù)橢圓曲線與同余數(shù)的相關(guān)關(guān)系與橢圓曲線的部分知識，構(gòu)建以上同余數(shù)所對應(yīng)的直角三角形并計算其各邊邊長。

（三） 直角三角形的構(gòu)建

1.橢圓曲線上的基本算法

2.直角三角形的構(gòu)造

固定分母q，則分子只有有限個值，根據(jù)編程篩選得出符合條件的有理數(shù)，構(gòu)建直角三角形。

根據(jù)原理編程得出同余數(shù)相關(guān)三角形邊長結(jié)果：

四 結(jié)語

本文通過同余數(shù)與橢圓曲線相關(guān)知識，驗證了5,7,13,14,21,22,23為同余數(shù)并給出了相關(guān)直角三角形的三邊長。