李 濱

（成都師范學(xué)院 數(shù)學(xué)系，四川 成都 611130）

不定方程是指變元為整數(shù)的方程.對不定方程的研究是數(shù)論中的一個非常重要的課題，一個多世紀以來人們對它進行了不斷地研究，特別是近幾十年來取得了豐碩的成果.如Lander［1］解決了相異冪和不定方程問題；Silvernan［2］得到了三次等冪和不定方程的參數(shù)解；Taylor等［3］證明了Fermat大定理，即對奇數(shù)p，不定方程xp＋yp＝zp不可能有正整數(shù)解；李志剛等［4］證明了聯(lián)立不定方程組的正整數(shù)解的個數(shù)不超過1；劉燕妮等［5］利用初等方法研究了丟潘方程xy＋yz＋zx＝0的可解性，并求出了該方程的所有整數(shù)解等等.對于多元一次不定方程，現(xiàn)在已經(jīng)能夠直接利用整除理論來判斷其是否有解，并能夠求出二元一次不定方程的一般解.但對于三元以上的情形，目前還沒有關(guān)于其解的表示形式.論文研究的目的就是試圖求出三元以上的一次不定方程解的結(jié)構(gòu)形式.

1 預(yù)備知識

設(shè)整數(shù)n≥2，M，a1，a2，…，an是整數(shù)且a1，a2，…，an都不等于零，x1，x2，…，xn是整數(shù)變元，方程

稱為n元一次不定方程，其中a1，a2，…，an稱為它的系數(shù).當(dāng)n≥3時，稱（1）為多元一次不定方程.找出多元一次不定方程的全部整數(shù)解的問題稱為解多元一次不定方程.

為了求解多元一次不定方程，首先給出下面引理：

引理1［6］若任給非零的整數(shù)a，b，則存在兩個整數(shù)u，v，使得

對不定方程（1）引入下面一些記號

即（a1，a2，…，ai）＝di（2≤i≤n），

由引理1知，存在整數(shù)u1，u2，…，un和v2，v3，…，vn－1滿足

關(guān)于不定方程（1）的解的存在性問題有下面引理：

引理2［8］不定方程（1）有解的充要條件是dn｜M，進而，不定方程（1）有解時，它的解與不定方程

的解相同.

對于二元一次不定方程解的結(jié)構(gòu)如下：

引理3［9］設(shè)二元一次不定方程

若x1，y1是它的一組解，那么它的一般解為為任意整數(shù).

2 主要定理

定理1 設(shè)a1，a2，a3為非零整數(shù)，M是整數(shù)且滿足d3｜M，則不定方程

的一般解為

其中：t1，t2為任意整數(shù)

證明 將（3）代入不定方程a1x1＋a2x2＋a3x3＝M，易知（3）是該方程的解.下面該方程的一切解具有形式（2）.

由于a1u1＋a2u2＝d2，由引理3可知方程a1x1＋a2x2＝d2的一般解為

其中：t1為任意整數(shù)，從而方程a1x1＋a2x2＝sd2的一般解為

由此可見，方程a1x1＋a2x2＋a3x3＝d3的整數(shù)解必使a1x1＋a2x2為整數(shù)，從而必有a1x1＋a2x2＝sd2，且s為整數(shù)，即此時方程a1x1＋a2x2＋a3x3＝d3轉(zhuǎn)化為求方程

的整數(shù)解，由于

因此，由引理3可知方程d2s＋a3x3＝d3的一般解為

其中：t2為任意整數(shù)，從而方程d2s＋a3x3＝M的一般解為

其中：δ＝Md－13，將（5）代入（4）得原不定方程（2）的一般解，即為（3）式，證畢.

下面將不定方程推廣到n（n≥4）元的情形.

定理2 設(shè)整數(shù)n≥4，ai（1≤i≤n）為非零整數(shù)，M為整數(shù)且dn｜M，則不定方程

的一般解為

其中：ti（1≤i≤n－1）為任意整數(shù)，且

證明 先計算n＝4時不定方程（6）的一般解.由定理1的證明可知方程

的一般解為

其中：t1，t2為任意整數(shù).

方程a1x1＋a2x2＋a3x3＋a4x4＝d4的整數(shù)解必使a1x1＋a2x2＋a3x3為整數(shù)，從而必有a1x1＋a2x2＋a3x3＝sd3，s為整數(shù)，即此時方程a1x1＋a2x2＋a3x3＋a4x4＝d4轉(zhuǎn)化為求方程

的整數(shù)解，由于

因此，由引理1知方程d3s＋a4x4＝d4的一般解為

其中：t3為任意整數(shù)，從而方程d3s＋a4x4＝M的一般解為

將（9）代入（7），得n＝4時不定方程（6）的一般解為

其中：ti（1≤i≤3）為任意整數(shù)，且

即當(dāng)n＝4時，定理2成立.

假設(shè)n＝m時，不定方程（6）的一般解具有（7）的結(jié)構(gòu)形式，那么不定方程

解的結(jié)構(gòu)式為

其中：ti（1≤i≤m－1）為任意整數(shù).

方程a1x1＋a2x2＋…＋am＋1xm＋1＝dm＋1的整數(shù)解必使a1x1＋a2x2＋…＋amxm為整數(shù)，從而必有a1x1＋a2x2＋…＋amxm＝sdm，s為整數(shù)，即此時方程a1x1＋a2x2＋…＋am＋1xm＋1＝dm＋1轉(zhuǎn)化為求方程

的整數(shù)解.由于有

所以，方程dms＋am＋1xm＋1＝dm＋1的一般解為

其中：tm為任意整數(shù)，從而方程dms＋am＋1xm＋1＝M的一般解為

將（11）代入（10）得不定方程

的一般解的結(jié)構(gòu)形式為

由此可見，當(dāng)n＝m＋1時，定理結(jié)論也成立，因而定理得證，證畢.

由不定方程一般解的結(jié)構(gòu)形式，可以得到如下推論：

推論1 設(shè)整數(shù)n≥3，ai（1≤i≤n）為非零整數(shù).M為整數(shù)且dn｜M，則不定方程

的一個特解為

證明 在定理1、2的一般解的結(jié)構(gòu)式中取ti＝0（1≤i≤n－1），即得不定方程的一個特解結(jié)構(gòu)式（13），很容易驗證（13）滿足不定方程（12），證畢.

由推論1，可以得到下面關(guān)于同余方程解的存在性.

推論2 設(shè)a1，a2，…，an為非零整數(shù)，w為不等于1的正整數(shù)，若（dn，w）＝1，則同余方程

存在整數(shù)解xi（1≤i≤n），滿足0≤xi＜w.

證明 設(shè)aj＝a′jdn，則（a′1，a′2，…，a′n）＝1，由于（dn，w）＝1，則dn－1modw存在，方程（14）同解于方程

構(gòu)造不定方程

由推論1可知不定方程（15）的一個特解為

它也滿足同余方程（14），只要選取適當(dāng)?shù)恼麛?shù)k1，k2，…，kn，令

使得0≤xi＜w（1≤i≤n），顯然x1，x2，…，xn是同余方程（14）的一個整數(shù)解，證畢.

由此結(jié)合引理2可知：當(dāng)dn≠1時，不定方程a1x1＋a2x2＋…＋anx＝1無整數(shù)解，而同余方程a1x1＋a2x2＋…＋anxn≡1modw在（dn，w）＝1時有整數(shù)解.

3 對RSA公鑰密碼體制的改進

RSA公鑰密碼體制是1978年由Rivest，Shamir和Adleman提出的［10］，它的基礎(chǔ)是數(shù)論的歐拉定理，其安全性依賴于大數(shù)分解的困難性.下面將RSA密碼體制進行改進，描述如下：

（1）選取兩個保密的大素數(shù)p和q.

（2）計算N＝pq，φ（N）＝（p－1）（q－1），其中φ（N）是N的歐拉函數(shù)值，將N公開，φ（N）保密.

（3）選取正整數(shù)a1，a2，…，an滿足dn≠1且（dn，φ（N））＝1.

（4）求解同余方程a1b1＋a2b2＋…＋anbn≡1modφ（N）得到b1，b2，…，bn滿足

（5）以｛a1，a2，…，an｝為公開密鑰，｛b1，b2，…，bn｝為秘密密鑰.

若要對明文m進行加解密，其算法如下：

下面證明一下這個解密過程的正確性，由于p、q為大素數(shù)，不妨設(shè)明文m＜min｛p，q｝，則有（m，N）＝1.

改進后的RSA密碼體制呈現(xiàn)出密鑰多元化的狀態(tài)，能將單個明文加密成由多個密文組成的密文組，增加了攻擊者破譯的難度，因而更為安全.下面舉個例子來展示一下這個密碼體制的實現(xiàn)過程.

例 信息接收方選取p＝11，q＝13，計算N＝pq＝143，φ（N）＝（p－1）（q－1）＝120.

再選取a1＝28，a2＝42，a3＝35，a4＝21，并計算，顯然

由4u1＋6u2＝d2＝2，2v2＋5u3＝d3＝1，v2＋3u3＝d4＝1，得u1＝－1，u2＝1，u3＝1，u4＝1，v2＝－2，v3＝－2.

由（13）結(jié)構(gòu)式計算不定方程（17）的一個特解為

則同余方程

的滿足0≤bi＜120（1≤i≤4）的解為

消息接收方保密數(shù)據(jù)為p、q、φ（N）、｛b1，b2，b3，b4｝.公開數(shù)據(jù)為N和｛a1，a2，a3，a4｝.若發(fā)送方對明文m＝6加密，則由加密算法計算密文

發(fā)送方將密文c＝｛48，25，76，83｝發(fā)給接收方，接收方利用解密算法計算出明文

由此可見，改進后的RSA公鑰密碼體制易于實現(xiàn).

［1］Lander L J.Equal sums of unlike powers［J］.Fibonacci Quart，1990，28（2）：141－150.

［2］Silvernan J H.Taxicabs and sums of two cubes［J］.Amer Math Monthly，1993，100（3）：331－340.

［3］Taylor R，Wiles A.Ring－theoretic properties of certain Hecke algebras［J］.Ann of Math，1995，141（4）：553－572.

［4］李志剛，袁平之.一類不定方程組的解的個數(shù)［J］.數(shù)學(xué)學(xué)報，2007，50（6）：129－135.

［5］劉燕妮，郭曉艷.一個丟番圖方程及其它的整數(shù)解［J］.數(shù)學(xué)學(xué)報，2010，53（5）：853－856.

［6］Tom M A.Introduction to analytic number theory［M］.New York：Springer－Verlag，1976.

［7］石玉，陳寶鳳，李威，等.非線性拋物方程的一個新混合元格式的超收斂分析［J］.信陽師范學(xué)院學(xué)報：自然科學(xué)版，2014，27（3）：328－331.

［8］王小云，王明強，孟憲萌.公鑰密碼學(xué)的數(shù)學(xué)基礎(chǔ)［M］.北京：科學(xué)出版社，2013.

［9］陸洪文，田廷彥.數(shù)論開篇［M］.黑龍江：哈爾濱工業(yè)大學(xué)出版社，2012.

［10］Rivest R L，Shamir A，Adleman L.A method for obtaining digital signatrues and public－key cryptosystems［J］.Communication of the ACM，1978，21（2）：120－126.