一類高階線性齊次遞歸數列的幾個模性質

林志雄

(福建工程學院數理系,福建福州 350108)

一類高階線性齊次遞歸數列的幾個模性質

林志雄

(福建工程學院數理系,福建福州 350108)

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

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

1 引 言

由常系數齊次線性遞歸關系和初始條件

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

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

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

2 引理與推廣

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

wmp≡wm(modp).

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

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

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

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

證(a)考察序列

關于模2的周期序列為1,1,1,1,0,…,便可發現模2的周期為5,當且僅當5|n時,2|wn.

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

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

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

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

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

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

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

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

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

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

II)當gcd(i,pr)=p時,設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)(偶數)個元素,

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

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

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

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

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

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

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

當5|m+p時,由于p≠5,且為素數,所以

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

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

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

進行分析,得到以下幾個主要結果:

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

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

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

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

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

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

[3] 張禾瑞.高等代數[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