關于線性丟番圖方程的Frobenius問題

(中山開放大學，中山，528403)

1 引言與主要結果

考慮k(≥2)個變元的線性丟番圖方程：

a1x1+…+akxk=b,

(1.1)

這里a1,…,ak,b皆為正整數，滿足條件

(a1,…,ak)=1.

(1.2)

可以證明[1]：當整數

b≥(ak-1)(a1+…+ak-1)

(1.3)

時，方程(1.1)總存在非負整數解(x1,…,xk).因而，存在一個最小的整數G(a1,…,ak),使得當整數b≥G(a1,…,ak)時，方程(1.1)總存在非負整數解；而當b=G(a1,…,ak)-1時，方程(1.1)不存在非負整數解.

Frobenius問題是找到G(a1,…,ak)的具體表示形式.熟知當k=2時，有[1,2]

G(a1,a2)=(a1-1)(a2-1).

(1.4)

而對于k>2,尚未見到類似的表示形式.M. B. Nathanson稱這是一個困難的開問題[1](a difficult open problem).

本文的目的，是要借助于(1.4)式，對于k>2,給出G(a1,…,ak)的一種表示形式.

不失一般性，本文始終假設a1

(a1,…,ak)={b;b>a1為正整數且使得方程(1.1)沒有非負整數解},

(1.5)

稱之為相對于a1,…,ak的非負不可解集.顯然，它是一個有限集合，而且成立

G(a1,…,ak)=max(a1,…,ak)+1.

(1.6)

例1.1(3,7)={4,5,8,11},(3,7,11)={4,5,8}.G(3,7)=12,G(3,7,11)=9.

我們的主要結果是：

定理1.2設k(≥3)個正整數a1

(1.7)

……

2 一個基本引理

本節，我們給出一個后面常常要用到的結論.

引理2.1給定整數a>b>0,(a,b)=1.如果整數i滿足：0

0

(2.1)

使得

nb+i=ka.

(2.2)

證明考慮模a的剩余類形成的加法群,有

={[0],[1],…,[a-1]},

這里[i]表示i所在的剩余類.

另一方面，由(a,b)=1,還有

={[0],[b],…,[(a-1)b]}.

于是，[i]在中的加法逆元可記為[nb].由i≠0可知n≠0,故得0

nb+i≡0(moda)，

從而存在k,使得(2.2)式成立.由(2.2)式左端大于0，可知k>0,再由

ka=nb+i

可得kb.故得(2.1)的后半部分.

這就完成了引理的證明.

借助這個基本引理，我們可以給出(1.4)式一個構造性的證明.

不妨假設a1

a1a2-a1-a2=a1(a1q+r)-a1-a1q-r=a1((a1-1)q+r-2)+a1-r.

將方程(1.1)改記為

a1x1+a2x2=b.

(2.3)

如果整數b>a1a2-a1-a2,則可記

b=a1a2-a1-a2+a1t+i,

(2.4)

當i=0時，必有t>0,因而得到：b=a1(t-1)+a2(a1-1).這表明x1=t-1,x2=a1-1便是方程(2.3)的非負整數解.

當0

nr+a1-i=ka1,

(2.5)

其中

0

(2.6)

由(2.5)，可得

a1-r+i=(2-k)a1+(n-1)r.

于是有

b=a1a2-a1-a2+a1t+i=a1((a1-1)q+r-2+t)+a1-r+i

=a1((a1-1)q+r-2+t)+(2-k)a1+(n-1)r

=a1((a1-n)q+r-k+t)+(n-1)a2.

由(2.6)，可知：(a1-n)q+r-k+t>0,n-1≥0.這表明x1=(a1-n)q+r-k+t,x2=n-1便是方程(2.3)的非負整數解.

如果整數b=a1a2-a1-a2,則方程(2.3)沒有非負整數解.如若不然，就有x1≥0,x2≥0,使得：a1x1+a2x2=a1a2-a1-a2.即

a1(x1+1)+a2(x2+1)=a1a2.

由(a1,a2)=1,從上式可得：a1|(x2+1),a2|(x1+1).并據此導出：

a1a2=a1(x1+1)+a2(x2+1)≥a1a2+a2a1=2a1a2,

矛盾！因而得出：

G(a1,a2)=a1a2-a1-a2+1=(a1-1)(a2-1).

這就是(1.4)式.

3 非負不可解集(a1,a2)的若干性質

依據(1.6)式，解答Frobenius問題，須要了解非負不可解集(a1,…,ak)的主要性質.而且，例1.1暗示著重要的關系式：(a1,…,ak)?(a1,…,ak-1)！因此，本節先討論(a1,a2)的若干性質.

性質3.1(1,a2)=?.

證明由(1.4)式，G(1,a2)=0.從而得證結論.

0(a1,a2)={x;x∈(a1,a2),x

(3.1)

和

1(a1,a2)={x;x∈(a1,a2),x>a2}.

(3.2)

由G(2,a2)=a2-1,易得

性質3.21(2,a2)=?.

根據上述兩個性質，以下我們總設：2

a2=a1q+r,q≥1,0

(3.3)

由(a1,a2)=1,可知

(r,a1)=1.

(3.4)

性質3.3x∈0(a1,a2),當且僅當x=a1t+i,1≤t≤q,其中，當1≤t

證明是顯而易見的.

記M=a1a2-a1-a2,由(1.4)式知M∈1(a1,a2).進一步，還有

性質3.4x∈1(a1,a2),當且僅當

x=M-l2a2-l1a1,

(3.5)

這里

0≤l2≤a1-3,

(3.6)

以及

0≤l1≤(a1-2-l2)q+r-2-tr,

(3.7)

如果0≤tr≤1+l2使得

tra1≤(2+l2)r<(tr+1)a1.

(3.8)

進一步，表示式(3.5)是唯一的.

證明首先，如果(3.5)式成立，且l1≥0,l2≥0,則方程

a1x1+a2x2=x

沒有非負整數解.如若不然，則有

a1(x1+l1)+a2(x2+l2)=M.

這與(1.4)式相矛盾！

進一步，為使x∈1(a1,a2),須x>a2,即

M-l2a2-l1a1>a2.

(3.9)

此即a2(a1-2-l2)>a1(l1+1)>0，因而須a1-2-l2>0,故而得到(3.6)式.

現在來估計l1.當(3.8)式滿足時，有

r<(tr+1)a1-(1+l2)r

(3.10)

和

x=a1((a1-1-l2)q+r-2-tr-l1)+(tr+1)a1-(1+l2)r.

(3.11)

如果

(a1-1-l2)q+r-2-tr-l1≥q,

(3.12)

此即(3.7)式，將它和(3.10)一起代入(3.11)中，就得到(3.9)式.即有x∈1(a1,a2).

其次，如果x∈1(a1,a2),則有a2

x=a2+a1m+i,0

注意到i=a1-r時，x=a1(q+m+1)?(a1,a2),故還有i≠a1-r.

現在應用引理2.1，有

nr+a1-i=ka1,

(3.13)

其中0

記l2=a1-n-2,則(3.6)式成立.從(3.13)式，可得

r+i=a1(1-k)+(n+1)r.

因而有

a2+i=a1(q+1-k)+(a1-1-l2)r.

另一方面，有

M-l2a2=a1((a1-1-l2)q-1)+(a1-1-l2)r.

記m1=(a1-2-l2)q+k-2,則從上述兩式可得

a2+a1m1+i=M-l2a2.

記l1=m1-m,則有x=a2+a1m+i=M-l2a2-l1a1.此即(3.5)式.

注意到l1<0時，M-l2a2-l1a1?(a1,a2)(證明可見隨后的性質3.6).故有l1≥0.

在(3.13)中，記k=r-t,并將a1-n=l2+2代入之，得

ta1<(t+1)a1-i=(2+l2)r<(t+1)a1.

將它與(3.8)式比較，可知t=tr,從而得到

0≤l1≤m1=(a1-2-l2)q+r-2-tr.

此即(3.7)式.

為證明表示式的唯一性，假設還有x=M-m2a2-m1a1,代入(3.5)中得到

(m2-l2)a2=(l1-m1)a1.

由(a1,a2)=1,可知a1|(m2-l2).再由|m2-l2|≤a1-3,可得m2-l2=0,代入上式，又可得m1-l1=0.因而唯一性得證.

至此便完成了性質3.4的證明.

由此性質，當a1=3時，l2=0,于是若x∈1(3,a2),則有

x=M-3l1=2a2-3(l1+1),0≤l1≤q-1.

注記3.5由(3.8)式可知，tr還是l2的函數.例如，取a1=5,a2=5q+4,即r=4.則有：l2=0時，tr=1；l2=1時，tr=2；l2=2時，tr=3.

因此，我們可以記tr=tr(l2).而且，由(3.8)式，有

這里[x]表示x的整數部分.由此，顯然可見，當l2′≤l2″時，成立tr(l2′)≤tr(l2″).

性質3.6若l>0,0≤l2≤a1-3,0≤l1≤(a1-2-l2)q+r-2-tr,則有

M-l2a2+la1?(a1,a2),

(3.14)

M+la2-l1a1?(a1,a2).

(3.15)

證明由

M-l2a2+la1=(a1-1-l2)a2+(l-1)a1

及a1-1-l2≥a1-1-a1+3=2,l-1≥0，可知(3.14)式成立.

又由

M+la2-l1a1=(a2-1-l1)a1+(l-1)a2

及a2-1-l1≥a1q+r-1-(a1-2)q-r+2+tr=2q+1+tr>0,l-1≥0，可知(3.15)式成立.

故性質3.6得證.

令

(3.16)

這里[x]表示x的整數部分.

(3.17)

使得

M-l2a2-Nka1∈1(a1,a2)

(3.18)

以及

k(M-l2a2-Nka1)=M-(k(l2+1)-1)a2-jka1∈1(a1,a2).

(3.19)

證明對于整數k≥2,由a2>3,顯然有k<(k-1)(a2-1),于是存在整數qk和rk,使得

(k-1)(a2-1)=kqk+rk,0

(3.20)

取jk=k-rk和Nk=qk+1,便得到(3.17)式.

k((2+l2)q+1+tr)+jk

故有

(k-1)(a2-1)+jk≤ka2-k(2+l2)q-k(2+tr)，

進而導出Nk≤(a1-2-l2)q+r-2-tr.由性質3.4，便得知(3.18)式成立.

由(3.17)式，可得

k(M-l2a2-Nka1)=M-kl2a2+(k-1)M-Nka1

=M-kl2a2+(k-1)(a2-1)a1-(k-1)a2

-(k-1)(a2-1)a1-jka1=M-(k(l2+1)-1)a2-jka1.

這是(3.19)式的前半部分.

jk≤a2-1-k(2+l2)q-k(1+tr)=(a1-2-(k(l2+1)-1))q+r-2

-tr-(k-1)(q+1+tr)<(a1-2-(k(l2+1)-1))q+r-2-tr.

再由性質3.4，便得知(3.19)式成立.

故性質3.7得證.

事實上，(3.16)式定義的K(l2)還是a1,q和r的函數，故我們可記為：

K(l2)=K(a1,q,r,l2).

易見，a1=4時，K(l2)≤1.一般地，我們有如下：

性質3.8設x=M-l2a2-l1a1∈1(a1,a2),則下列結論成立：

證明由(3.16)式知，K(l2)≤1等價于

(a1-2-l2)q+r-3-tr(l2)<(2+l2)q+2+tr(l2),

即

(a1-2(2+l2))q<5+2tr(l2)-r.

(3.21)

(3.22)

如果r=2s,則代入上式可得

由此導出tr(l2)=s-1,從而得知5+2tr(l2)-r=3.此時(3.21)式當q≥3時不成立.

如果r=2s+1,代入(3.22)式得到

由此導出s-1≤tr(l2)≤s,從而得知2≤5+2tr(l2)-r≤4.此時(3.21)式當q≥4時不成立.

這就得到結論(2).

(3.23)

如果r=2s,則代入上式可得

由此導出s-2≤tr(l2)≤s-1,從而得知1≤5+2tr(l2)-r≤3.此時(3.21)式當q≥2時不成立.

如果r=2s+1,代入(3.23)式得到

由此導出s-1≤tr(l2)≤s,從而得知2≤5+2tr(l2)-r≤4.此時(3.21)式當q≥2時不成立.

這就得到結論(3).

(3.24)

如果r=2s,則代入上式可得

據此導出tr(l2)≤s-1,從而得知5+2tr(l2)-r≤3.此時(3.21)式當q≥1時不成立.

如果r=2s+1,則由(3.24)式可得

據此導出tr(l2)≤s,從而得知5+2tr(l2)-r≤4.此時(3.21)式當q≥2時不成立.

這就得到結論(4).

至此性質3.8得證.

性質3.9若

0≤l1≤(a1-2-l2)q+r-2-tr(l2),

則有

k(M-l2a2-l1a1)=M-(kl2-(k-1)(a1-1))a2-(kl1+k-1)a1∈1(a1,a2).

(3.25)

證明由

k(M-l2a2-l1a1)=M+(k-1)M-kl2a2-kl1a1

=M+(k-1)(a1a2-a2-a1)-kl2a2-kl1a1

=M-(kl2-(k-1)(a1-1))a2-(kl1+k-1)a1,

就得到(3.25)式的前半部分.

=l2-(k-1)(a1-1-l2)≤l2-2(k-1)

其次，由0≤l1≤(a1-2-l2)q+r-2-tr(l2),顯然有kl1+k-1>0.記

l2′=kl2-(k-1)(a1-1).

由注記3.5可得

于是有

kl1+k-1≤k(a1-2-l2)q+k(r-2-tr(l2))+k-1

=(a1-2-l2′)q+r-2-tr(l2′)-(tr(l2)-tr(l2′)+(k-1)(q+1+tr(l2)-r)).

從(3.10)式得到的

同時注意到(k-1)q-1>0,就得到

tr(l2)-tr(l2′)+(k-1)(q+1+tr(l2))

因而導出

kl1+k-1<(a1-2-l2′)q+r-2-tr(l2′).

根據性質3.4，就得到(3.25)式的后半部分.

性質3.9得證.

4 不可解集1(a1,a2)上的一個自映射

對于每個x∈1(a1,a2),引進集合

1(x;a1,a2)={b;b∈1(a1,a2)且存在m>0,m1≥0,m2≥0使得b=mx+m1a1+m2a2}

(4.1)

和

0(x;a1,a2)=1(a1,a2)1(x;a1,a2).

(4.2)

如果a1=3,由性質3.4，當x∈1(3,a2)時，有

x=2a2-3(1+l1),0≤l1≤q-1.

(4.3)

據此，當x=2a2-3q時，成立0(x;3,a2)=?,這是唯一的例外.

一般地，我們有

命題4.1如果a1>3,則對于每個x∈1(a1,a2),總有

0(x;a1,a2)≠?.

(4.4)

證明依據性質3.4，當x∈1(a1,a2)時，有

x=M-l2a2-l1a1,

其中0≤l2≤a1-3.再由a1>3,知l2至少可取兩個值.

若l2

若l2=a1-3,則有x+a2-a1=M-(l2-1)a2-(l1+1)a1∈0(x;a1,a2).

這就完成命題4.1的證明.

據此，對于a1>3,我們定義映射η:1(a1,a2)→1(a1,a2)為：如果x∈1(a1,a2),則令

η(x)=max0(x;a1,a2).

(4.5)

對于a1=3,我們拓廣上述映射為η:1(a1,a2)→(a1,a2)∪{2}：

(4.6)

這里q=1時，3q-1=2?(a1,a2).而x>3q+2r時，皆有η(x)∈1(a1,a2),及(4.5)式成立.

命題4.2如果a3∈1(a1,a2),則當b>η(a3)時，方程

a1x1+a2x2+a3x3=b

(4.7)

總存在非負整數解；而當b=η(a3)時，方程(4.7)不存在非負整數解.

證明先考慮a1>3的情形.

當b>η(a3)時，如果b?1(a1,a2),則b?(a1,a2),因而存在x1≥0,x2≥0,使得x1a1+x2a2=b.由此知(x1,x2,0)是方程(4.7)的一個非負整數解.

如果b∈1(a1,a2),則由映射η的定義知b∈1(a3;a1,a2),從而有

b=ma3+m2a2+m1a1,m>0,m2≥0,m1≥0.

由此知(m1,m2,m)是方程(4.7)的一個非負整數解.

當b=η(a3)時，有b∈0(a3;a1,a2).如果方程(4.7)存在非負整數解(x1,x2,x3),x3=1將與b∈0(a3;a1,a2)矛盾；x3=0,則得x1a1+x2a2=b,這與b∈1(a1,a2)矛盾.故得，此時方程(4.7)不存在非負整數解.

對于a1=3的情形，只有a3=3q+2r時，產生例外.這時，0(a3;3,a2)=?.但在拓廣的映射下，當b=η(a3)時，仍有方程(4.7)不存在非負整數解.

命題4.2證畢.

命題4.3對于a1>3,x=M-l2a2-l1a1∈1(a1,a2),映射η的表示形式為：

η(x)=max{M-k(l2+1)a2,M-(k-1)(l2+1)a2-(jk+k(l1-Nk)+1)a1}；

(4.8)

這里N1=0,j1=0,k≥2時的jk和Nk由(3.17)式定義.

η(x)=max{M-(l2+1)a2,M-(l1+1)a1}；

(4.9)

η(x)=max{M-(l2+1)a2,M-(l1+1)a1}；

(4.10)

η(x)=max{M-((s+1)l2-s(a1-1)+1)a2-s(l1+1)a1,s=1,…,k-1;M-k(l1+1)a1}.

(4.11)

證明由K=K(l2)≥2和(3.16)式可知

K(2+l2)q+2K+Ktr(l2)≤a1q+r-1.

(4.12)

據此導出：K(2+l2)

即

r-K(tr(l2)+1)<0.

結合(4.12)式，有

a1q≤K(2+l2)q≤a1q+r-1-(2K+Ktr(l2))

矛盾！故有：K(2+l2)

kx=M-(kl2+k-1)a2-(jk+k(l1-Nk))a1∈1(a1,a2).

而由性質3.6和性質3.4知

(k+1)x=M-((k+1)l2+k)a2-(jk+1+(k+1)(l1-Nk+1))a1?(a1,a2).

事實上，當k≤K-1時，有(k+1)l2+k≤a1-3；由(3.17)式知jk+1+(k+1)(l1-Nk+1)<0,故由性質3.6得到上式.而當k=K時，如果(K+1)l2+K≤a1-3,則由性質3.6得到上式；如果(K+1)l2+K>a1-3,由性質3.4得到上式.

現在，由kl2+k-1≤Kl2+K-1

kx+(jk+k(l1-Nk))a1-a2=M-k(l2+1)a2∈0(x;a1,a2)

和

kx+l2a2-a1=M-(k-1)(l2+1)a2-(jk+k(l1-Nk)+1)a1∈0(x;a1,a2).

為證明(4.8)式，取y=M-m2a2-m1a1∈1(a1,a2).如果y>M-k(l2+1)a2,則有

(k(l2+1)-m2)a2>m1a1.

由此導出：k(l2+1)-m2>0.記m2=k(l2+1)-i2-1,則有i2≥0.另一方面，由

y>M-(k-1)(l2+1)a2-(jk+k(l1-Nk)+1)a1

可得

((jk+k(l1-Nk)+1)-m1)a1>(l2-i2)a2.

因此，當0≤i2≤l2時，有(jk+k(l1-Nk)+1)-m1>0.記m1=(jk+k(l1-Nk)+1)-i1-1.由i1≥0,得

y=kx+i2a2+i1a1∈1(x;a1,a2).

而當l2(k-1)x+(l2+1)a2-a1,可得

y>M-((k-2)(l2+1)-1)a2-(jk-1+(k-1)(l1-Nk-1)+1)a1,

從而有

jk-1+(k-1)(l1-Nk-1)+1-m1>(2l2+2-i2)a2>0.

此時記m1=jk-1+(k-1)(l1-Nk-1)-i1.由i1≥0,得

y=(k-1)x+(i2-l2-1)a2+i1a1∈1(x;a1,a2).

一般地，當sl2+s≤i2≤(s+1)l2+s時，s=0,1,…,k-1,由

kx+l2a2-a1>(k-s)x+(l2+s)a2-a1

可得

y>M-((k-s-1)(l2+1)-s)a2-(jk-s+(k-s)(l1-Nk-s)+1)a1,

從而有

jk-s+(k-s)(l1-Nk-s)+1-m1>((s+1)l2+2s-i2)a2≥0.

此時記i1,s=jk-s+(k-s)(l1-Nk-s)-m1.由i1,s≥0,得

y=(k-s)x+(i2-sl2-s)a2+i1,sa1∈1(x;a1,a2).

據此得證(4.8)式.

由K=K(l2)≤1和(3.16)式可知

a2-1<2((2+l2)q+2+tr(l2)),

據此導出l1≤a2-((2+l2)q+2+tr(l2))≤N2.

2x=M-(2l2+1)a2-(j2+2(l1-N2))a1?(a1,a2),

從而得知

x+l1a1-a2=M-(l2+1)a2∈0(x;a1,a2)

和

x+l2a2-a1=M-(l1+1)a1∈0(x;a1,a2).

為證明(4.9)式，取y=M-m2a2-m1a1∈1(a1,a2).如果y>M-(l2+1)a2,則有

(l2+1-m2)a2>m1a1.

由此導出：l2+1-m2>0.記i2=l2-m2,則有i2≥0.另一方面，由y>M-(l1+1)a1,有

(l1+1-m1)a1>m2a2.

由此導出：l1+1-m1>0.記i1=l1-m1,則有i1≥0.于是得到：

y=x+i2a2+i1a1∈1(x;a1,a2).

這就證明了(4.9)式.

sx+(a1-l2-2)a2-a1∈0(x;a1,a2),

這里

sx+(a1-l2-2)a2-a1=M-((s+1)l2-s(a1-1)+1)a2-s(l1+1)a1,

以及

kx+(kl2-(k-1)(a1-1))a2-a1=M-k(l1+1)a1∈0(x;a1,a2).

注意到x>a2,導出(a1-l2-2)a2>(l1+1)a1,進而得知：

M-l2a2=x+l1a1

為證明(4.11)式，取y=M-m2a2-m1a1∈1(a1,a2).由

y>x+(a1-l2-2)a2-a1>M-l2a2

有

(l2-m2)a2>m1a1.

由此導出：l2-m2>0,從而0≤m2≤l2.

現在，如果0≤m2≤kl2-(k-1)(a1-1),記i2=kl2-(k-1)(a1-1)-m2，則有i2≥0.另一方面，由y>M-k(l1+1)a1,有

(k(l1+1)-m1)a1>m2a2.

由此導出：k(l1+1)-m1>0.記i1=k(l1+1)-1-m1,則有i1≥0.于是得到：

y=kx+i2a2+i1a1∈1(x;a1,a2).

如果對于s=1,…,k-1,有(s+1)l2-s(a1-1)+1≤m2≤sl2-(s-1)(a1-1),則由

y>sx+(a1-l2-2)a2-a1=M-((s+1)l2-s(a1-1)+1)a2-s(l1+1)a1

可得

(s(l1+1)-m1)a1>(m2-((s+1)l2-s(a1-1)+1))a2≥0.

由此導出：s(l1+1)-m1>0.記i1,s=s(l1+1)-1-m1,則有i1,s≥0；同時記

i2,s=sl2-(s-1)(a1-1)-m2,

則有i2,s≥0.從而導出：

y=sx+i2,sa2+i1,sa1∈1(x;a1,a2).

這就證明了(4.11)式.

至此命題4.3得證.

5 G(a1,a2,a3)的表示形式

本節，我們給出G(a1,a2,a3)的表示形式.注意到方程(1.1)變成

a1x1+a2x2+a3x3=b,

(5.1)

其中

a1

(5.2)

顯然地，有

G(1,a2,a3)=G(1,a2)=0.

(5.3)

故以下總設a1>1,并分兩種情況來討論.

定理5.1如果(a1,a2)=1,則當a3?1(a1,a2)時，有

G(a1,a2,a3)=G(a1,a2)；

(5.4)

而當a3∈1(a1,a2)時，有

G(a1,a2,a3)=η(a3)+1.

(5.5)

證明當a3?1(a1,a2)時，僅須證明當b=G(a1,a2)-1時，方程(5.1)沒有非負整數解.如果成立a3>b,則這是顯然的.如果a3

a1(x1+x3t1)+a2(x2+x3t2)=b=a1a2-a1-a2.

這與a1a2-a1-a2∈1(a1,a2)相矛盾！故得證(5.4)式.

當a3∈1(a1,a2)時，由命題4.2得到(5.5)式.定理證畢.

定理5.2如果(a1,a2)=d>1,則有

G(a1,a2,a3)=d×(G(c1,c2,a3)-1)+(d-1)a3+1,

(5.6)

其中ai=cid,i=1,2,而G(c1,c2,a3)由定理5.1所定義.

證明令b=d×(G(c1,c2,a3)-1)+(d-1)a3.先證明此時方程(5.1)沒有非負整數解.如若不然，便有xi≥0,i=1,2,3,使得

a1x1+a2x2+a3x3=d×(G(c1,c2,a3)-1)+(d-1)a3,

此即

d(c1x1+c2x2)+a3(x3-d+1)=d×(G(c1,c2,a3)-1).

由(5.2)式，有d

c1x1+c2x2+a3t=G(c1,c2,a3)-1.

矛盾！故此時方程(5.1)沒有非負整數解.

現在，對于b>d×(G(c1,c2,a3)-1)+(d-1)a3,我們來構造方程(5.1)的非負整數解.記

b=d×(G(c1,c2,a3)-1)+(d-1)a3+td+i,

(5.7)

其中t≥0,0

b=d×(G(c1,c2,a3)-1+t+k+nq)+a3(d-1-n).

由G(c1,c2,a3)-1+t+k+nq>G(c1,c2,a3),可知存在ti≥0,i=1,2,3,使得

c1t1+c2t2+a3t3=G(c1,c2,a3)-1+t+k+nq.

因此，(t1,t2,t3d+d-1-n)是方程(5.1)的一個非負整數解.

至此定理5.2得證.

注意到依據公式(1.4)，有G(d,a3)=(d-1)(a3-1),我們可以將上述兩個定理的結論整合成一個公式：

(5.8)

這里(a1,a2)=d,ai=cid,i=1,2.

6 定理1.2的證明

現在，我們來證明本文的主要結果.

首先，我們將映射η:1(a1,a2)→1(a1,a2)的結果符號改記為η(x;a1,a2)=η(x).并仿此推廣到一般的情形.設(a1,…,ak)=1.令

0(a1,…,ak)={x;x∈(a1,…,ak),x

(6.1)

1(a1,…,ak)={x;x∈(a1,…,ak),x>ak}.

(6.2)

再對于x∈1(a1,…,ak),令

(6.3)

0(x;a1,…,ak)=(a1,…,ak)1(x;a1,…,ak)，

并定義映射η:1(a1,…,ak)→1(a1,…,ak)為：

η(x)=η(x;a1,…,ak)=max0(x;a1,…,ak).

(6.4)

據此，我們將定理5.1推廣到一般情形.

定理6.1如果(a1,…,ak-1)=1,則當ak?1(a1,…,ak-1)時，有

G(a1,…,ak-1,ak)=G(a1,…,ak-1)；

(6.5)

而當ak∈1(a1,…,ak-1)時，有

G(a1,…,ak-1,ak)=η(ak;a1,…,ak-1)+1.

(6.6)

證明當ak?1(a1,…,ak-1)時，僅須證明對于b=G(a1,…,ak-1)-1,方程(1.1)沒有非負整數解.如果ak>b,(x1,…,xk)是方程(1.1)的非負整數解，則有xk=0.因此有

a1x1+…+ak-1xk-1=G(a1,…,ak-1)-1,xi≥0,i=1,…,k-1.

這與G(a1,…,ak-1)的定義相矛盾！

如果ak

ak=a1t1+…+ak-1tk-1.

假如此時方程(1.1)有非負整數解(x1,…,xk),則有

a1(x1+t1xk)+…+ak-1(xk-1+tk-1xk)=G(a1,…,ak-1)-1.

這同樣與G(a1,…,ak-1)的定義相矛盾！

當ak∈1(a1,…,ak-1)時，如果b=η(ak;a1,…,ak-1),則方程(1.1)沒有非負整數解.如若不然，設(x1,…,xk)是方程(1.1)的非負整數解.則xk>0使得b=a1x1+…+akxk∈1(ak;a1,…,ak-1)與b=η(ak;a1,…,ak-1)=max0(ak;a1,…,ak-1)相矛盾！故xk=0,因而有

a1x1+…+ak-1xk-1=b.

這與b∈1(a1,…,ak-1)相矛盾！

如果b>η(ak;a1,…,ak-1),則方程(1.1)總有非負整數解.事實上，若b?1(a1,…,ak-1),則有b?(a1,…,ak-1).因而存在整數ti≥0,i=1,…,k-1,使得b=a1t1+…+ak-1tk-1.于是，(t1,…,tk-1,0)是方程(1.1)的一個非負整數解.

若b∈1(a1,…,ak-1),則有b∈1(ak;a1,…,ak-1),即于是，(m1,…,mk-1,m)是方程(1.1)的一個非負整數解.

定理6.1得證.

定理6.2如果(a1,…,ak-1)=d>1,則有

G(a1,…,ak)=d×G(c1,…,ck-1,ak)+G(d,ak),

(6.7)

其中ai=cid,i=1,…,k-1.

本定理的證明與定理5.2的證明完全類似，從略.

將上述兩個定理整合，可以得到一個表示公式：

(6.8)

其中(a1,…,ak-1)=d,ai=cid,i=1,…,k-1.

據此，我們便可以遞推地給出定理1.2的證明.過程是平凡的，從略.

注記6.3我們對于k>3的情形，略去了映射η(ak;c1,…,ck-1)的表示形式，因為它太繁瑣冗長，從命題4.3就可見一斑.或許它存在簡潔的形式，只是我們未能發現，就留給有興趣的讀者吧！