一類高階線性齊次遞歸數(shù)列的幾個模性質(zhì)

林志雄

(福建工程學(xué)院數(shù)理系,福建福州 350108)

一類高階線性齊次遞歸數(shù)列的幾個模性質(zhì)

林志雄

(福建工程學(xué)院數(shù)理系,福建福州 350108)

給出一類特殊的高階線性遞歸序列的幾個模性質(zhì).

高階遞歸;F-L序列;模

1 引 言

由常系數(shù)齊次線性遞歸關(guān)系和初始條件

確定的序列w=w(c0,c1,…,ck-1),其中a1,a2,…,ak,c0,c1,…,ck-1為數(shù)域F中取值(注:除特別說明外,本文所涉及的變量均為整數(shù)。),這類序列通常被稱為k階斐波那契—盧卡斯序列[1],記為Ω=Ωz(a1,a2,…,ak),簡稱為F-L序列.

由于這一類序列對于素性的判別有著特別重要的作用,因此頗受人們廣泛的研究著.尤其是二階的Fibonacci序列和二階的Lucas序列,有著相當(dāng)豐富且成熟的性質(zhì)[1].還有三階的Perrin序列w0=3,w1=0,w2=2,wn=wn-2+wn-3也是人們研究的熱門課題[4,5,6].這種齊次遞歸序列Ω=Ωz(a1,a2,…,ak)中的主相關(guān)序列(或廣L序列)有很多關(guān)于模性質(zhì)的結(jié)論.但是,有些結(jié)論要進(jìn)一步從低階往高階推廣卻相當(dāng)困難.

本文通過一個四階的序列(Ω=Ωz(1,1,-1,1)中主相關(guān)序列),首先討論其一條性質(zhì)(見性質(zhì)),然后仿文獻(xiàn)[1]中關(guān)于引理3的證明方法將模pr的結(jié)論從三階推廣到四階,同時給出其它幾個模結(jié)論.

2 引理與推廣

引理1[1]設(shè)w為Ω=Ωz(a1,a2,…,ak)中的主相關(guān)序列,p為素數(shù),則對于一切m∈Z+,有

wmp≡wm(modp).

引理2[1]設(shè)w為Ω=Ωz(a,b)中的主相關(guān)序列,p為素數(shù),pgcd(a,b),r∈Z+,則對于一切m∈Z+,有

引理3[1]設(shè)w為Ω=Ωz(a,b,1)中的主相關(guān)序列,p為素數(shù),r∈Z+,則對于一切m∈Z+,有

引理4[1]設(shè)p為素數(shù),w為Ω=Ωz(a1,a2,…,ak)中的主相關(guān)序列,則對一切m∈Z+,有

以上四個引理均引自文獻(xiàn)[1],具體的證明方法見文獻(xiàn)[1].性質(zhì) 設(shè)w為Ωz(1,1,-1,1)中的主相關(guān)序列,n∈Z+,則

證(a)考察序列

關(guān)于模2的周期序列為1,1,1,1,0,…,便可發(fā)現(xiàn)模2的周期為5,當(dāng)且僅當(dāng)5|n時,2|wn.

(b)由(a)的結(jié)論立得(b)成立.

定理1 設(shè)w為Ωz(1,1,-1,1)中的主相關(guān)序列,p為奇素數(shù),r∈Z+,則對于一切m∈Z,有

證設(shè)wn∈Ωz(1,1,-1,1),其特征方程x4-x3-x2+x-1=0的特征根為α,β,γ,δ.令

設(shè)U為Ωz(A,B,C,1)中的主相關(guān)序列,則有

其中H(A,B,C)為整系數(shù)多項式,即

所以wmp≡≡wm(modp),即r=1時定理成立.現(xiàn)設(shè)對r-1定理已成立,即對任何m∈Z,

推論1 設(shè)p為奇素數(shù),w為Ωz(a,b,c,1)為中主相關(guān)序列,若對任意m∈Z有2|w2m-w2m,則

定理2 設(shè)p為素數(shù),w為Ωz(a1,a2,…,ak)中主相關(guān)序列,對任意r≥1,i＞0,m,n∈Z,且wmpr≡wmpr-1(modpr),則

證分I),II),III)三種情況證之.

I)當(dāng)gcd(i,pr)=1時,pr|Cipr.又由引理1,有p|wmpr+1-nip-wmpr-ni,故有

II)當(dāng)gcd(i,pr)=p時,設(shè)i=x p,x=1,2,…,p-1.記X={j|1≤j≤x p,gcd(j,p)=1},顯然X中共有x p-x=x(p-1)(偶數(shù))個元素,

因為gcd(x,p)=1,有pr-1|Cxpr-1.由上式得

定理3 設(shè)p≠5為奇素數(shù),w為Ωz(1,1,-1,1)主相關(guān)序列,則對一切m＞0,有

證由引理4,只要證明wm+4p≡wm+3p+wm+2p-wm+p+wm(mod 2)即可.

根據(jù)性質(zhì)(a),只要證明m+4p,m+3p,m+2p,m+p,m這五個數(shù)中必有一個且只有一個數(shù)被5整除即可.

(i)先證這五個數(shù)中必有一個數(shù)被5整除.因為p≠5,且為素數(shù),所以

(ii)再證這五個數(shù)中只有一個數(shù)被5整除.當(dāng)5|m時,由于p≠5,且為素數(shù),所以

均不能被5整除.故命題正確.

當(dāng)5|m+p時,由于p≠5,且為素數(shù),所以

均不能被5整除.故命題正確.

同理可證,當(dāng)5|m+2p,5|m+3p,5|m+4p時,命題正確.

筆者對本文所給的四階序列:

進(jìn)行分析,得到以下幾個主要結(jié)果:

(i)該序列與二階Lucas序列有很多相似的性質(zhì),如本文所證明的3個定理,其余可參考文獻(xiàn)[1]進(jìn)行給予推廣;

(ii)該序列除了有wp≡1(modp)外,還有w3p≡1(modp),p為素數(shù).所以存在大量3p型的偽素數(shù),而3p型的偽素數(shù)可通過2n-1≡1(modn)完全淘汰;

但對以2為底小于1015的1801533個偽素數(shù)(即2n-1≡1(modn)的偽素數(shù))用這序列進(jìn)行檢測(即wp≡1(modp)的檢測),結(jié)果只發(fā)現(xiàn)15個能通過該檢測的偽素數(shù).這15個數(shù)是

Adarms and Shanks對Perrin序列提出六元組的檢測方法[5,6],其目的是為了減少偽素數(shù)的產(chǎn)生,但仍然存在無限個Carmichael數(shù)的Perrin偽素數(shù).這一四階序列也存在無限個Carmichael偽素數(shù).

[1] 周持中.斐波那契—盧卡斯序列[M].長沙：湖南科學(xué)技術(shù)出版社,1993.

[2] 麥結(jié)華.3-周期軌道蘊(yùn)含6831 726876986508個85-周期軌道[J].中國科學(xué)A輯,1991(9)：929-937.

[3] 張禾瑞.高等代數(shù)[M].4版.北京：高等教育出版社,1999：93-102.

[4] Perrin R.“Item 1484”,L’Intermediare des Math[M].1899(6)：76-77.

[5] William Adarms and Daniel Shanks.Strong primality tests are not sufficient[J].Math.Comp.,1982,39(159)：225-300.

[6] Adarms W.It Characterizing pseudoprimes for third-order linear recurrences[J].Math.Comp.,1987,48(177)：1-15.

Some Modulus Properties of Higher-order Recurrence Sequences

L IN Zhi-xiong
(Department of Mathematics and Physics,Fujian University of Technology,Fuzhou 350108,China)

Some modulus properties of a special higher-order linear recurrence sequences was obtained in this paper.

higher-order linear recurrences;F-L sequences;modulus

O156

C

1672-1454(2011)05-0125-05

2011-02-24