奇數(shù)的拆分循環(huán)及應(yīng)用

吳金釵

(華僑大學(xué) 數(shù)學(xué)科學(xué)學(xué)院， 福建 泉州 362021)

Mersenne數(shù)Mp=2p-1是以2為底的冪再減1的數(shù)[1-4]，F(xiàn)ermat數(shù)Fn=22n+1是以2為底的冪再加1的數(shù)[4-9].在Mersenne數(shù)的分解方面，Cambraia[10]給出了方程Mm+Mn=2pa的整數(shù)解(m，n，a)，其中，m，n≥2，p是一個質(zhì)數(shù)，a是一個正整數(shù).目前，國內(nèi)外學(xué)者對于Fermat數(shù)分解算法研究的不多，國外有專門的網(wǎng)站介紹分解Fermat數(shù)的進展[10-12].Wang[13]提出分解Fermat數(shù)的新方法，理論上可分解Fn(n>100 001)的任何Fermat數(shù).王鈺[14]對Wang[13]的方法進行優(yōu)化，運用Maple數(shù)學(xué)軟件解析Fermat數(shù)小因數(shù)，優(yōu)化后的算法提高了計算效率.然而，Wang[13]利用GMP大數(shù)庫運算在32位系統(tǒng)中只能計算到F22，王鈺[14]利用Maple在64 位系統(tǒng)中也只能計算到F29.因此，研究更通用、更高效的大數(shù)算法是很有必要的.基于此，本文提出奇數(shù)的拆分循環(huán)及其應(yīng)用.

1 奇數(shù)的和式拆分循環(huán)

1.1 奇數(shù)的和式拆分

由于A是有限集合，所以?α0∈A，?αi∈A，不妨設(shè)i=1，2，…，k及數(shù)l1，l2，…，lk，使得p-αi-1=2liαi，α0=αk，拆分序列為

p-α0=2l1α1，p-α1=2l2α2， …，p-αk-1=2lkαk=2lkα0.

(1)

如果奇數(shù)p有兩個拆分循環(huán)，且兩個循環(huán)有一個相同的節(jié)點，則這兩個循環(huán)的節(jié)點必完全相同，即這兩個循環(huán)實質(zhì)是同一個拆分循環(huán)，只是它們的起點不同.如果p有兩個拆分循環(huán)(Ⅰ)，(Ⅱ)，則僅當(dāng)拆分循環(huán)(Ⅰ)的節(jié)點與拆分循環(huán)(Ⅱ)的節(jié)點全不相同時，才稱拆分循環(huán)(Ⅰ)，拆分循環(huán)(Ⅱ)是p的兩個不同的拆分循環(huán).當(dāng)p為素數(shù)時，則p與拆分循環(huán)的各節(jié)點的最大公因數(shù)(p，α0，α1，…，αk-1)=1；當(dāng)p是合數(shù)時，如p=p1·p2(p1，p2為素數(shù))，則p與拆分循環(huán)的各節(jié)點的最大公因數(shù)(p，α0，α1…，αk-1)=1或p1或p2.

1.2 拆分循環(huán)結(jié)果

因為p-α0=2l1α1=2l1(p-2l2α2)=2l1p-2l1+l2α2=2l1p-2l1+l2(p-2l3α3)=(2l1-2l1+l2)p+2l1+l2+l3α3，所以當(dāng)2j

p·(2l1+l2+…+l2j-1-2l1+l2+…+l2j-2+…+2l1-1)=2l1+l2+…l2jα2j-α0；

(2)

當(dāng)2j-1

p·(2l1+l2+…+l2j-2-2l1+l2+…+l2j-3+…-2l1+1)=2l1+l2+…l2j-1α2j-1+α0.

(3)

當(dāng)k=2s時，α2s=α0，由拆分序列(1)，有

p·(2l1+l2+…+l2s-1-2l1+l2+…+l2s-2+…+2l1-1)=α0(2l1+l2+…+l2s-1)=α0(2m-1).

(4)

當(dāng)k=2s-1時，α2s-1=α0，由拆分序列(1)，有

p·(2l1+l2+…+l2s-2-2l1+l2+…+l2s-3+…-2l1+1)=α0(2l1+l2+…+l2s-1+1)=α0(2m+1)，

(5)

綜上所述，當(dāng)p的拆分循環(huán)為偶循環(huán)時，p|2m-1；當(dāng)p的拆分循環(huán)為奇循環(huán)時，p|2m+1.

1.3 拆分指數(shù)和

L=nNn+(n-1)Nn-1+…+2N2+1·N1.

定理1設(shè)p=2a+1=2n+δn-12n-1+δn-22n-2+…+δn22+δ12+1，δi取1或0，i=1，2，…，n-1，則p的全體和式拆分的指數(shù)和為a，即L=nNn+(n-1)Nn-1+…+2N2+N1=a.因此，p是素數(shù)或合數(shù)，a是奇數(shù)或偶數(shù)，此結(jié)論均成立.

證明：將p改寫為

p=2a+1=2l(2n-l+δn-12n-1-l+…+δl+12+δl2-1)+

[(1-δl)2l+δl-12l-1+…+δ12+1]，

則右端第一項圓括號中的數(shù)和第二項的數(shù)都是奇數(shù)，所以和式拆分指數(shù)≥l的拆分節(jié)點為奇數(shù)，即1，3，5，…，2n-l+δn-12n-1-l+…+δl+12+δl2-1.

和式拆分指數(shù)≥l的拆分個數(shù)為

Nn+Nn-1+…+Nl=[(2n-l+δn-12n-1-l+…+δl+12-δl2-1)+1]÷2=

2n-1-l+δn-12n-2-l+…+δl+22+δl+1+δl，

因此，

Nn+Nn-1+…+N1=2n-2+δn-12n-3+…+δ32+δ2+δ1，

Nn+Nn-1+…+N2=2n-3+δn-12n-4+…+δ42+δ3+δ2，

?

Nn+Nn-1+Nn-2=2+δn-1+δn-2，

Nn+Nn-1=1+δn-1，

Nn=1，

L=nNn+(n-1)Nn-1+…+2N2+1N=2n-1+δn-12n-2+…+δ12+1=a.

1.4 超半和式拆分及所有超半拆分的指數(shù)和

設(shè)p=α+2lβ是一個和式拆分，則α，β≤a，且2lβ>a.若1

因為Nn+Nn-1+…+Nk=2n-k-1+δn-12n-k-2+…+δk+22+δk+1+δk，Nn+Nn-1+…+Nk+1=2n-k-2+δn-12n-k-3+…+δk+32+δk+2+δk+1，所以Nk=2n-k-2+δn-12n-k-3+…+δk+32+δk+2+δk(k=1，2，…，n-2)，而Nn=1，Nn-1=δn-1，Nn-2=1+δn-2，有

(6)

引理1對任意的n≥1，有

(7)

將式(7)代入式(6)，全體超半拆分的指數(shù)和為

L1=2n-1-1+(2n-2+1)δn-1+(2n-3-1)δn-2+…+(22-1)δ3+(2-1)δ2=

2n-1+δn-12n-2+δn-22n-3+…+δ322+δ22+δ1-(1+δn-1+δn-2+…+δ2+δ1)=

a-(1+δn-1+δn-2+…+δ1).

證明：對任意自然數(shù)n，有恒等式

成立.

再設(shè)bk=ak-ak-1，則bn=an-an-1=(n-1)+(n-3)+(n-4)·2+(n-5)·22+…+(k-1)2n-2-k+…+3·2n-6+2·2n-5+1·2n-4，bn-1=an-1-an-2=(n-2)+(n-4)+(n-5)·2+(n-6)·22+…+(k-1)2n-3-k+…+3·2n-7+2·2n-6+2n-5.所以有

bn-bn-1=1+1+2+22+…+2n-6+2n-5+2n-4=2n-3.

由數(shù)列an=2n-1-1，得a1=0.

1.5 范例

例1求下列各數(shù)的所有和式拆分循環(huán)：a) 素數(shù)p=23；b) 素數(shù)p=43；c) 合數(shù)p=35.

43-1=2·21，43-21=2·11，43-11=25·1，由此奇循環(huán)導(dǎo)出43·(22-2+1)=27+1；

43-3=23·5，43-5=2·19，43-19=23·3，由此奇循環(huán)導(dǎo)出43·(24-23+1)=3·(27+1)；

43-7=22·9，43-9=2·17，43-17=2·13，43-13=2·15，43-15=22·7，由此奇循環(huán)導(dǎo)出了43·(25-24+23-22+1)=7·(27+1).

其基循環(huán)為35-1=2·17，35-17=2·9，35-9=2·13，35-13=2·11，35-11=23·3，其偶循環(huán)為35-3=25·1，由此循環(huán)導(dǎo)出35·(27-24+23-22+2-1)=212-1；35-5=2·15，35-15=22·5，由此循環(huán)導(dǎo)出35·(2-1)=5·(23-1)，35-7=22·7，35=7·(22+1).

因此，素數(shù)43有3個奇循環(huán)，且各循環(huán)的指數(shù)和都是7；而合數(shù)35有偶循環(huán)，也有奇循環(huán)，各循環(huán)的指數(shù)和也不一樣.

例2用a)p=23；b)p=35的超半拆分，驗證超半拆分指數(shù)和定理.

a)p=2a+1=2·11+1=23=24+22+2+1，故a=11，δ1=1，δ2=1，δ3=0，a-(δ3+δ2+δ1+1)=8.23的超半拆分為23-13=2·5，23-15=23，23-17=2·3，23-19=22，23-21=2，這些超半拆分指數(shù)和是8.

b)p=2a+1=2·17+1=35=25+2+1，所以a=17，δ4=0，δ3=0，δ2=0，δ1=1，a-(δ4+δ3+δ2+δ1+1)=17-2=15.35的超半拆分為35-19=24，35-21=2·7，35-23=22·3，35-25=2·5，35-27=23，35-29=2·3，35-31=22，35-33=21，超半拆分的指數(shù)和是15.

2 奇數(shù)的差式拆分循環(huán)

2.1 奇數(shù)的差式拆分

設(shè)p=2a+1=2n+δn-12n-1+δn-12n-2+…+δ12+1，令奇數(shù)集{1，3，5，…，p-2}為B，|B|=a，則?α∈B，?β∈B及數(shù)l(1≤l≤n+1)，使得p=2lβ-α，其中，p為一個差式拆分，α為拆分的起點，β為拆分的接點，l為拆分的指數(shù).

由于B是有限集，所以?α0∈B，?αi∈B及數(shù)li，1≤li≤2n(i=1，2，…，k)，αk=α0，使得

p+α0=2l1α1，p+α1=2l2α2， …，p+αk-1=2lk·αk=2lkα0.

(8)

式(8)中：拆分序列是一個以α0為起點的差式拆分循環(huán).

由拆分序列(8)導(dǎo)出

p+α0=2l1(2l2α2-k)=2l1+l2(2l3α3-p)-2l1p=2l1+l2+l3(2l4α4-p)-2l1p-2l1+l2p=…=

2l1+l2+…+lkα0-2l1p-2l1+l2p-…-2l1+l2+…+lk-1p，

2.2 奇數(shù)p的差式拆分循環(huán)與和式拆分循環(huán)的關(guān)系

當(dāng)l1>1時，由于

p+α0=2(2l1-1α1+α0)，

p+(2l1-1α1+α0)=2l1-1α1+2(2l1-1α1+α0)=2[(2l1-1+2l1-2)α1+α0]，

p+[(2l1-1+2l1-2)α1+α0]=2[(2l1-1+2l1-2+2l1-3)α1+α0]=…，

p+[(2l1-1+2l1-2+…+2)α1+α0]=2[(2l1-1+2l1-2+…+2+1)α1+α0]=

2[(2l1-1)α1+α0]=2(p-α1)=21+l2α2，

由p-α0=2l1α1，p-α1=2l2α2導(dǎo)出l1個差式拆分序列，這個拆分序列前l(fā)1-1個的拆分指數(shù)為1，最后一個拆分的指數(shù)為l2+1.所以這個拆分的指數(shù)和為l1+l2.與這l1個拆分序列對應(yīng)的節(jié)點序列起點是α0，最后的節(jié)點是α2.

同理可證，若p有一個和式拆分奇循環(huán)，即

2.3 范例

例3求p=23的導(dǎo)出結(jié)果.

p=23只有一個和式拆分偶循環(huán)，指數(shù)和為m=11.p=23的一個差式拆分循環(huán)為23+1=23·3，23+3=2·13，23+9=25·1，此循環(huán)導(dǎo)出的結(jié)果為23·(26+24+23+1)=1·(211-1).23的另一個差式拆分循環(huán)為23+5=22·7，23+7=2·15，23+15=2·19，23+19=2·21，23+21=22·11，23+11=2·17，23+17=23·5.此循環(huán)導(dǎo)出的結(jié)果為23·(28+27+25+24+23+22+1)=5·(211-1).

例4求p=43的導(dǎo)出結(jié)果.

p=43的基循環(huán)43-1=2·21，43-21=2·11，43-11=25是一個指數(shù)和m=7的奇循環(huán)，此循環(huán)導(dǎo)出的結(jié)果為43·(22-2+1)=1·(27+1).

對應(yīng)于此奇循環(huán)，43有一個差式拆分循環(huán)：43+1=22·11，43+11=2·27，43+27=2·35，43+35=2·39，43+39=2·41，43+41=22·21，43+21=26·1，此循環(huán)導(dǎo)出的結(jié)果為

43·(28+26+25+24+23+22+1)=22·7-1=214-1.

3 素數(shù)和式拆分循環(huán)

3.1 素數(shù)的和式拆分

定理2素數(shù)p的任一偶循環(huán)的指數(shù)和都是奇數(shù).

由反證法，設(shè)m為偶數(shù)，且m=2m1.因為p|2m-1=(2m1-1)(2m1+1)，所以2m1≡1(modp)或2m1≡-1(modp).因m1

當(dāng)k為奇數(shù)時，p|2l1+l2+…+lkαk+α0，即2m1+tαk+α0≡0(modp)，因為2m1≡±1(modp)，0

推論1設(shè)素數(shù)p有一個偶循環(huán)，指數(shù)和為m，則所有滿足2r≡1(modp)，minr=m.

證明：設(shè)(m，r)=m1，若m1=1，則m，r互素，因此?P>0，Q>0，使得Pm-Qr=1，或Pr-Qm=1.因為2Pm=2Qr+1，或2Pr=2Qm+1，所以1≡2Pm≡2Qr+1≡2(modp)或1≡2Pr≡2Qm+1≡2(modp)不成立.若1

定理3素數(shù)p的基循環(huán)若是指數(shù)和為m的偶循環(huán)，則p的任一循環(huán)都是指數(shù)和為m的偶循環(huán).素數(shù)p的基循環(huán)若是指數(shù)和為m的奇循環(huán)，則p的任一循環(huán)都是指數(shù)和為m的奇循環(huán).

證明：若p只有一個拆分循環(huán)，定理結(jié)論自然成立.設(shè)p有一個異于基循環(huán)，指數(shù)和為m1的循環(huán)(Ⅰ)，若循環(huán)(Ⅰ)是偶循環(huán)，則由定理2可斷定m1|m，則基循環(huán)是偶循環(huán)，且p|2m1-1.由定理2可斷定m|m1，因此，m1=m.

若循環(huán)(Ⅰ)是奇循環(huán)，則p|2m1+1，由定理2及推論1易證，m1是所有滿足2r+1≡0(modp)r的最小值.若2r+1≡0(modp)，則m1|r.如果p|2m1+1成立，則因為p|2m-1，p|2m+1不能同時成立，故m1≠m.若m0時，則由于r1m1，設(shè)m=m2m1+r，0≤r0時，由于r

推論2如果素數(shù)p=2a+1有b個拆分循環(huán)，每個循環(huán)的指數(shù)和為m，那么，p的和式拆分的指數(shù)和a=bm(定理1)，即p=2a+1=2bm+1.

3.2 范例

Mp=2p-1形的數(shù)為Mersenne數(shù)，其中，p為素數(shù).當(dāng)p=2，3，5，7，13，17，19，31，61，89，107，127，521，807，1 279，2 203，2 281時，Mp為素數(shù)[1].近代大型計算機偶然算出幾個大數(shù)p的Mp是素數(shù).

例5如果p=4m+3是素數(shù)，q=2p+1也是素數(shù)，則q|2p-1，Mp=2p-1是合數(shù).

要證明M23=223-1有素因數(shù)p=2·23+1=47，設(shè)223-1=(2·23+1)(2·23·4b+1)，則222-1=(211-1)(211+1)=2·232·4b+23·(1+4b).因為211=2 048，211-1=2 047=23·89，所以89· 2 049-1=4·47b，22·2 049+512=47b，令b=2b1，得47b1=11·2 049+256=22 795，求得b1=485，b=970，2·23·4b+1=8·23·970+1=178 481，即223-1=47·178 481.

例6設(shè)素數(shù)p=4n+1，q=2p+1 也是素數(shù)，則q|2p+1.

例7p為素數(shù)，且q=4p+1也是素數(shù)，則q|22p+1.

證明：設(shè)q的拆分循環(huán)指數(shù)和為m，m|2p，若m=p，q有兩個拆分循環(huán)，兩循環(huán)的節(jié)點個數(shù)之和必是偶數(shù)，而q的節(jié)點總個數(shù)為奇數(shù)2p/2=p，所以m≠p，m=2p.因為q只有一個指數(shù)和為2p的奇循環(huán)，所以q|22p+1.如p=3，q=4p+1=13，13|22p+1=26+1；p=13·q=4p+1=53，53|226+1.

例5說明p=4m+3是素數(shù)，q=2p+1是素數(shù)，則Mp必為合數(shù).反之，若p=4m+3是素數(shù)，q=2p+1是合數(shù)，則Mp必為素數(shù).如p=31，q=2p+1=63是合數(shù)，M31=231-1是素數(shù)；p=61，q=2p+1=123是合數(shù)，M61是素數(shù)；p=107，q=2p+1=215是合數(shù)，M107是素數(shù)；p=127，q=2p+1=215是合數(shù)，M127是素數(shù)；p=807，q=2p+1=2·807+1是合數(shù)，M807是素數(shù)；p=1 279，q=2p+1=2·1 279+2 559是合數(shù)，M1 279是素數(shù)；p=2 203，q=2p+1=2·2 203+1=4 407是合數(shù)，M2 203是素數(shù).

例8p=19是素數(shù)，2p+1=39是合數(shù)，而M19=219-1是素數(shù).

例9用拆分理論證明F5=225+1=232+1是合數(shù).

證明：設(shè)F5=232+1=p·q，p=2a+1為F5的素因數(shù)，p的拆分循環(huán)為奇循環(huán)，指數(shù)和為25=32，25|a，p應(yīng)當(dāng)是形如2·25n+1的數(shù).當(dāng)n為奇數(shù)時，p有奇數(shù)個拆分奇循環(huán)，其總節(jié)點數(shù)應(yīng)當(dāng)是奇數(shù)，這與p=2·25n+1的節(jié)點總數(shù)24n個矛盾，故n應(yīng)當(dāng)是偶數(shù).

設(shè)p=2·25·2a+1=27a+1，q=27b+1，即F5=232+1=(27a+1)(27b+1)，則225=27ab+a+b，令a+b=27c，則218=ab+c=27ca-a2+c，即218+a2=(27a+1)c，將其變形為218a+a3=(27a+1)ca，218a+211-211+a3=(27a+1)ca，-211+a3=(27a+1)(ca-211)，再變形為24+a4=(27a+1)(ca2-211a+24).

若ca2-211a+24=1，則24-1+a4=5·3+a4=27a.取a=5，則3+53=128=27，所以F5=225+1有一素因數(shù)p=27·5+1=641.再由ca2-211a+24=25c-2 048·5+16=1，求得c=409，b=27c-a=128·409-5=52 347，q=27b+1=128·52 347+1=6 700 417.