同余與不定方程的求解

劉志平

(宜賓學院數學學院，四川宜賓644007)

同余與不定方程的求解

劉志平

(宜賓學院數學學院，四川宜賓644007)

不定方程的求解是數論學習的重要內容，利用同余與同余式解不定方程是不定方程求解的常用方法.利用一次同余式、二次同余式與同余性質解不定方程的一般方法，對求不定方程整數解的學習難點有所幫助.

不定方程;整數解;同余;同余式;模

不定方程在各國歷史上有極其豐富的研究,文獻豐富,也留下過很多經典難題.另一方面,由于數學應用的空前普及,對方程與不定方程的整數解問題研究,也有了應用前景.而同余式與不定方程的關系,使得利用同余式與同余的性質去求不定方程的整數解有時可順利完成.

1 準備知識

定義1[1]給定正整數m，把它叫做模,如果用m去除任意兩個整數a與b所得余數相同,稱a,b對模m同余,記作a≡b(modm).如果余數不同,稱a,b對模m不同余,記作a≡b(modm).

定理1[1]二元一次不定方程ax+by=c(a,b,c為整數,a≠0,b≠0)有整數解的充分必要條件是(a,b)| c.

定理2[1]二元一次不定方程ax+by=c(a,b,c為整數,a≠0,b≠0)有整數解，若有解(x0,y0)，則它的一切解具有平方非剩余.

定理3[2](a,p)=1，若a是模p的平方剩余，則同余式x2≡a(modp)有兩個解.

定義3[1]勒讓得（Legendre）符號是一個對于給定的奇質數p定義在一切整數a上的函數,它的值規定如下:

2 不定方程與同余式

通常,研究不定方程的整數解,f(x1,…,xn)是n元整系數多項式.(1)對應的同余式為m＞1,是給定的整數.

顯然,如(1)有整數解xi=ai(i=1,2,…,n),則對于m＞1,(2)有解xi≡ai(modm),(i=1,2,…,n).則得以下定理.

定理4不定方程(1)有整數解,則同余式(2)對所有的正整數m＞1有解.

定義2[2]若同余式x2≡a(modm),(a,m)=1有解,則a叫模m的平方剩余,如同余式無解,則a叫模m的

但如果同余式(2)對所有正整數m＞1有解,對不定方程(1)卻不一定有整數解.

例1[3]：不定方程6xy-2x-3y+1=0沒有整數解.但是同余式

有解.可設m=2k-1(2a-1),k＞0,a＞0,因為3|22k+1+1,故可設22k+1+1=3b,由6ab-2a-3b+1=(2a-1)(3b-1) =(2a-1) 22k+1=2k+2?m.故a,b是(3)的一組解.

推論 如果選擇適當的m使(2)無解,從而(1)無整數解.

例2[3]：證明不定方程x13+x23+x33=9x4±4沒有整數解.

解：取模m=9.因為xi3≡0,±1(mod9),i=1,2,3，所以同余式x13+x23+x33≡±4(mod9)無解，故不定方程x13+x23+x33=9x4±4沒有整數解.

3 二元一次不定方程與一次同余式

二元一次不定方程ax+by=c(a,b,c為整數, a≠0,b≠0)的一切整數解,關鍵是求特解(x0,y0),而(x0,y0)的求法,古今中外的數學家研究了大量的方法,如輾轉相除法,降低系數法等.除了這些常用方法之外,還可利用一次同余式的求解求(x0,y0).

例3：解不定方程325x+161y=20.

解：因為(325,161)=1,1|20,所以方程有整數解,取模m=161得一次同余式325x≡20(mod161),即3x≡20(mod161),所以

4 平方剩余與不定方程

二次同余式與平方剩余,這是初等數論整一章的內容,而二次不定方程的整數解的判斷與求法,與平方剩余與平方非剩余有關.

例4：求不定方程x2+11y=5的整數解.

解：取模m=11,得二次同余式x2≡5() mod11.因為勒讓得符號

所以同余式有整數解,且x2≡5() mod11有解時,恰有兩個解.而

所以

為所求.

例5：證明不定方程x2+85y=24沒有整數解.

解：取模m=85,由方程得二次同余式x2≡24(mod85).而同余式x2≡24(mod85)有解?同余式組

無解,所以x2≡24(mod85)無解,故不定方程x2+85y= 24沒有整數解.

利用不定方程有正整數解的條件,還可判斷其中質數的形狀.

例6[4]：不定方程p=x2+2y2有正整數解,p為質數,則有即p=8m+1,或p=8m+3.

解：因為不定方程p=x2+2y2有正整數解,所以x2≡-2y2(modp)成立,又因為p-1

當p=8m+1時,且(-1)2=1,所以當p=8m+3時,所以

5 利用同余的性質解不定方程

除了一次與二次不定方程可利用同余式求解外,許多不定方程的求解也與同余有關,利用同余的性質解不定方程,往往可起到事半功倍的作用.

例7：證明若n=9k+t，t=3,4,5,6,k∈?，則方程x3+y3=n沒有整數解.

解：對任意的整數x,y記x=3q1+r1,y=3q2+r2, 0≤r1,r2≤2,q1,q2∈?.則其中R1=0,1,8,R2=0,1,8. R=0,1,2,7,8,由此得到所要證明的結論.

例8：證明方程3x+1=5y+7z除x=y=z=0外沒有其他整數解.

解：設(x,y,z)是方程的解.容易證明x≥0, y≥0,z≥0.

若x＞0,則由方程有5y+7z≡1(mod3),所以2y+1≡1(mod3),即2y≡0(mod3).因此，3|2y,這是不可能的.所以必是x=0,于是原方程成為5y+7z=2.

由于y≥0,z≥0,所以由上式推出y=z=0.

例9：證明若實數x與y滿足方程x2-3y2=2,則x與y不能都是有理數.

考察兩種可能的情形.

(i)3/|n.此時n≡±1,n2≡1(mod3),因此，由(4)式2m2≡1(mod3).這是不可能的，因為對于m≡0,1,2(mod3),2m2≡0,或2(mod3).

(ii)3|n.此時，由式(4)得到2m2≡0(mod3),又(2,3)=1,因此3|m,再由式(4)得到3|l,所以(m,n,l)＞1,這與(m,n,l)=1的假設矛盾.

所以x與y不能都是有理數.

例10[5]：證明不定方程xn+1=yn+1沒有正整數解,這里n≥2,(x,n+1)=1.

證：設y＞2,因為(y-1)|(yn+1-1),所以y-1的質因數p能整除x,而(x,n+1)=1,所以(p,n+1)=1.

又因為

由y≡1(mody-1),所 以1+y+y2+…+yn≡n+ 1(mody-1).所以y-1與1+y+y2+…+yn互質.

又因為xn=(y-1)(1+y+y2+…+yn),得1+y+ y2+…+yn是某數的n次方,這是矛盾的.

因為yn＜1+y+y2+…+yn＜(y+1)n.當y=1,方程沒有正整數解;y=2時xn=2n+1-1=2n+2n-1+…+2+ 1,而2n＜2n+…+2+1＜3n,原方程不能成立.

例11[6]：證明不定方程

僅有正整數解(n,k)=(2,1),(3,1),(5,2).

證：n=2時,由(5)得解(2,1).當n＞2時,由(5)式推出n為奇數.當n=3,5時,由(5)可得出解(3,1),(5,2).

現設n＞5且n為奇數,所以n-1是整數且小2于n-3.

所以n-1|(n-2)!,再由(5)可得

因為

由(6)、(7)式得出k(n-1)≡0(mod(n-1)2),故得n-1|k,所以k≥n-1,故nk-1≥nn-1-1＞(n-1)!,這就證明了在n＞5時,(5)式沒有正整數解(n,k).

關于不定方程的求解,還有許多方法,而利用同余或同余式解不定方程,這是求不定方程整數解的常用方法.往往可以起到事半功倍的作用.

[1]閔嗣鶴,嚴士健.初等數論[M]北京:高等教育出版社,2004.

[2]潘承洞,潘承彪.初等數論[M].北京:北京大學出版社,1992.

[3]柯召,孫琦.數論講義[M].北京:高等教育出版社,1987.

[4]劉志平.質數及其判定[J].宜賓學院學報,2013(12):114-117.

[5]熊全淹.初等整數論[M].武漢:湖北教育出版社,1985.

[6]柯召,孫琦.初等數論100例[EB/OL].(2010-01-02)[2014-02-12]. http://wenku.baidu.com/view4e6a7984b9d528ea81c77927.html.

【編校：許潔】

Solutions to the Congruence and Indeterminate Equations

LIU Zhiping
(Mathematics College,Yibin University,Yibin,Sichuan 644007,China)

How to solve indeterminate equations is very important in the study of number theory.Congruence is usually used to solve the indeterminate equations.The method of using 1st or 2ed order congruence to solve the indeterminate equations is very helpful with the study of finding integer solution to indeterminate equations.

indeterminate equations;integer solution;congruence;congruence equations;mold

O156.1

A

1671-5365(2014)06-0020-03

2014-03-12修回：2014-03-25

劉志平(1963-)，女，副教授，理學學士，研究方向為數論、概率

時間：2014-03-27 16:53

http://www.cnki.net/kcms/detail/51.1630.Z.20140327.1653.003.html