李 滨

（成都师范学院 数学系，四川 成都 611130）

不定方程是指变元为整数的方程.对不定方程的研究是数论中的一个非常重要的课题，一个多世纪以来人们对它进行了不断地研究，特别是近几十年来取得了丰硕的成果.如Lander［1］解决了相异幂和不定方程问题；Silvernan［2］得到了三次等幂和不定方程的参数解；Taylor等［3］证明了Fermat大定理，即对奇数p，不定方程xp＋yp＝zp不可能有正整数解；李志刚等［4］证明了联立不定方程组的正整数解的个数不超过1；刘燕妮等［5］利用初等方法研究了丢潘方程xy＋yz＋zx＝0的可解性，并求出了该方程的所有整数解等等.对于多元一次不定方程，现在已经能够直接利用整除理论来判断其是否有解，并能够求出二元一次不定方程的一般解.但对于三元以上的情形，目前还没有关于其解的表示形式.论文研究的目的就是试图求出三元以上的一次不定方程解的结构形式.

1 预备知识

设整数n≥2，M，a1，a2，…，an是整数且a1，a2，…，an都不等于零，x1，x2，…，xn是整数变元，方程

称为n元一次不定方程，其中a1，a2，…，an称为它的系数.当n≥3时，称（1）为多元一次不定方程.找出多元一次不定方程的全部整数解的问题称为解多元一次不定方程.

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

引理1［6］若任给非零的整数a，b，则存在两个整数u，v，使得

对不定方程（1）引入下面一些记号

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

由引理1知，存在整数u1，u2，…，un和v2，v3，…，vn－1满足

关于不定方程（1）的解的存在性问题有下面引理：

引理2［8］不定方程（1）有解的充要条件是dn｜M，进而，不定方程（1）有解时，它的解与不定方程

的解相同.

对于二元一次不定方程解的结构如下：

引理3［9］设二元一次不定方程

若x1，y1是它的一组解，那么它的一般解为为任意整数.

2 主要定理

定理1 设a1，a2，a3为非零整数，M是整数且满足d3｜M，则不定方程

的一般解为

其中：t1，t2为任意整数

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

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

其中：t1为任意整数，从而方程a1x1＋a2x2＝sd2的一般解为

由此可见，方程a1x1＋a2x2＋a3x3＝d3的整数解必使a1x1＋a2x2为整数，从而必有a1x1＋a2x2＝sd2，且s为整数，即此时方程a1x1＋a2x2＋a3x3＝d3转化为求方程

的整数解，由于

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

其中：t2为任意整数，从而方程d2s＋a3x3＝M的一般解为

其中：δ＝Md－13，将（5）代入（4）得原不定方程（2）的一般解，即为（3）式，证毕.

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

定理2 设整数n≥4，ai（1≤i≤n）为非零整数，M为整数且dn｜M，则不定方程

的一般解为

其中：ti（1≤i≤n－1）为任意整数，且

证明 先计算n＝4时不定方程（6）的一般解.由定理1的证明可知方程

的一般解为

其中：t1，t2为任意整数.

方程a1x1＋a2x2＋a3x3＋a4x4＝d4的整数解必使a1x1＋a2x2＋a3x3为整数，从而必有a1x1＋a2x2＋a3x3＝sd3，s为整数，即此时方程a1x1＋a2x2＋a3x3＋a4x4＝d4转化为求方程

的整数解，由于

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

其中：t3为任意整数，从而方程d3s＋a4x4＝M的一般解为

将（9）代入（7），得n＝4时不定方程（6）的一般解为

其中：ti（1≤i≤3）为任意整数，且

即当n＝4时，定理2成立.

假设n＝m时，不定方程（6）的一般解具有（7）的结构形式，那么不定方程

解的结构式为

其中：ti（1≤i≤m－1）为任意整数.

方程a1x1＋a2x2＋…＋am＋1xm＋1＝dm＋1的整数解必使a1x1＋a2x2＋…＋amxm为整数，从而必有a1x1＋a2x2＋…＋amxm＝sdm，s为整数，即此时方程a1x1＋a2x2＋…＋am＋1xm＋1＝dm＋1转化为求方程

的整数解.由于有

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

其中：tm为任意整数，从而方程dms＋am＋1xm＋1＝M的一般解为

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

的一般解的结构形式为

由此可见，当n＝m＋1时，定理结论也成立，因而定理得证，证毕.

由不定方程一般解的结构形式，可以得到如下推论：

推论1 设整数n≥3，ai（1≤i≤n）为非零整数.M为整数且dn｜M，则不定方程

的一个特解为

证明 在定理1、2的一般解的结构式中取ti＝0（1≤i≤n－1），即得不定方程的一个特解结构式（13），很容易验证（13）满足不定方程（12），证毕.

由推论1，可以得到下面关于同余方程解的存在性.

推论2 设a1，a2，…，an为非零整数，w为不等于1的正整数，若（dn，w）＝1，则同余方程

存在整数解xi（1≤i≤n），满足0≤xi＜w.

证明 设aj＝a′jdn，则（a′1，a′2，…，a′n）＝1，由于（dn，w）＝1，则dn－1modw存在，方程（14）同解于方程

构造不定方程

由推论1可知不定方程（15）的一个特解为

它也满足同余方程（14），只要选取适当的整数k1，k2，…，kn，令

使得0≤xi＜w（1≤i≤n），显然x1，x2，…，xn是同余方程（14）的一个整数解，证毕.

由此结合引理2可知：当dn≠1时，不定方程a1x1＋a2x2＋…＋anx＝1无整数解，而同余方程a1x1＋a2x2＋…＋anxn≡1modw在（dn，w）＝1时有整数解.

3 对RSA公钥密码体制的改进

RSA公钥密码体制是1978年由Rivest，Shamir和Adleman提出的［10］，它的基础是数论的欧拉定理，其安全性依赖于大数分解的困难性.下面将RSA密码体制进行改进，描述如下：

（1）选取两个保密的大素数p和q.

（2）计算N＝pq，φ（N）＝（p－1）（q－1），其中φ（N）是N的欧拉函数值，将N公开，φ（N）保密.

（3）选取正整数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为大素数，不妨设明文m＜min｛p，q｝，则有（m，N）＝1.

改进后的RSA密码体制呈现出密钥多元化的状态，能将单个明文加密成由多个密文组成的密文组，增加了攻击者破译的难度，因而更为安全.下面举个例子来展示一下这个密码体制的实现过程.

例 信息接收方选取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）结构式计算不定方程（17）的一个特解为

则同余方程

的满足0≤bi＜120（1≤i≤4）的解为

消息接收方保密数据为p、q、φ（N）、｛b1，b2，b3，b4｝.公开数据为N和｛a1，a2，a3，a4｝.若发送方对明文m＝6加密，则由加密算法计算密文

发送方将密文c＝｛48，25，76，83｝发给接收方，接收方利用解密算法计算出明文

由此可见，改进后的RSA公钥密码体制易于实现.

［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］李志刚，袁平之.一类不定方程组的解的个数［J］.数学学报，2007，50（6）：129－135.

［5］刘燕妮，郭晓艳.一个丢番图方程及其它的整数解［J］.数学学报，2010，53（5）：853－856.

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

［7］石玉，陈宝凤，李威，等.非线性抛物方程的一个新混合元格式的超收敛分析［J］.信阳师范学院学报：自然科学版，2014，27（3）：328－331.

［8］王小云，王明强，孟宪萌.公钥密码学的数学基础［M］.北京：科学出版社，2013.

［9］陆洪文，田廷彦.数论开篇［M］.黑龙江：哈尔滨工业大学出版社，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.