ルーカスシーケンス

数学において、ルーカス数列 とルーカス列は、再帰関係を満たす特定の定数再帰整数数列である。${\displaystyle U_{n}(P,Q)}$${\displaystyle V_{n}(P,Q)}$

${\displaystyle x_{n}=P\cdot x_{n-1}-Q\cdot x_{n-2}}$

ここで、およびは固定された整数である。この再帰関係を満たす任意のシーケンスは、ルーカスシーケンスと${\displaystyle P}$${\displaystyle Q}$${\displaystyle U_{n}(P,Q)}$${\displaystyle V_{n}(P,Q).}$

より一般的には、ルーカス数列と は整数係数を持つ およびの多項式の数列を表します。 ${\displaystyle U_{n}(P,Q)}$${\displaystyle V_{n}(P,Q)}$${\displaystyle P}$${\displaystyle Q}$

ルーカス数列の有名な例としては、フィボナッチ数、メルセンヌ数、ペル数、ルーカス数、ヤコブスター数、フェルマー数のスーパーセット（下記参照）などがあります。ルーカス数列はフランスの数学者エドゥアール・ルーカスにちなんで名付けられました。

2つの整数パラメータとが与えられた場合、第1種ルーカス列と第2種ルーカス列は再帰関係によって定義されます。 ${\displaystyle P}$${\displaystyle Q}$${\displaystyle U_{n}(P,Q)}$${\displaystyle V_{n}(P,Q)}$

${\displaystyle {\begin{aligned}U_{0}(P,Q)&=0,\\U_{1}(P,Q)&=1,\\U_{n}(P,Q)&=P\cdot U_{n-1}(P,Q)-Q\cdot U_{n-2}(P,Q){\mbox{ }}n>1 の場合、\end{aligned}}}$

そして

${\displaystyle {\begin{aligned}V_{0}(P,Q)&=2,\\V_{1}(P,Q)&=P,\\V_{n}(P,Q)&=P\cdot V_{n-1}(P,Q)-Q\cdot V_{n-2}(P,Q){\mbox{ }}n>1 の場合.\end{aligned}}}$

について、 ${\displaystyle n>0}$

${\displaystyle {\begin{aligned}U_{n}(P,Q)&={\frac {P\cdot U_{n-1}(P,Q)+V_{n-1}(P,Q)}{2}},\\V_{n}(P,Q)&={\frac {(P^{2}-4Q)\cdot U_{n-1}(P,Q)+P\cdot V_{n-1}(P,Q)}{2}}.\end{aligned}}}$

上記の関係は、行列形式で次のように表すことができます。

${\displaystyle {\begin{bmatrix}U_{n}(P,Q)\\U_{n+1}(P,Q)\end{bmatrix}}={\begin{bmatrix}0&1\\-Q&P\end{bmatrix}}\cdot {\begin{bmatrix}U_{n-1}(P,Q)\\U_{n}(P,Q)\end{bmatrix}},}$

${\displaystyle {\begin{bmatrix}V_{n}(P,Q)\\V_{n+1}(P,Q)\end{bmatrix}}={\begin{bmatrix}0&1\\-Q&P\end{bmatrix}}\cdot {\begin{bmatrix}V_{n-1}(P,Q)\\V_{n}(P,Q)\end{bmatrix}},}$

${\displaystyle {\begin{bmatrix}U_{n}(P,Q)\\V_{n}(P,Q)\end{bmatrix}}={\begin{bmatrix}P/2&1/2\\(P^{2}-4Q)/2&P/2\end{bmatrix}}\cdot {\begin{bmatrix}U_{n-1}(P,Q)\\V_{n-1}(P,Q)\end{bmatrix}}.}$

ルーカス数列の初期項とは次の表に示すとおりです。 ${\displaystyle U_{n}(P,Q)}$${\displaystyle V_{n}(P,Q)}$

${\displaystyle {\begin{array}{r|l|l}n&U_{n}(P,Q)&V_{n}(P,Q)\\\hline 0&0&2\\1&1&P\\2&P&{P}^{2}-2Q\\3&{P}^{2}-Q&{P}^{3}-3PQ\\4&{P}^{3}-2PQ&{P}^{4}-4{P}^{2}Q+2{Q}^{2}\\5&{P}^{4}-3{P}^{2}Q+{Q}^{2}&{P}^{5}-5{P}^{3}Q+5P{Q}^{2}\\6&{P}^{5}-4{P}^{3}Q+3P{Q}^{2}&{P}^{6}-6{P}^{4}Q+9{P}^{2}{Q}^{2}-2{Q}^{3}\end{配列}}}$

ルーカス列との再帰関係の特性方程式は次のようになります。 ${\displaystyle U_{n}(P,Q)}$${\displaystyle V_{n}(P,Q)}$

${\displaystyle x^{2}-Px+Q=0\,}$

判別式 と語根は次のようになります。 ${\displaystyle D=P^{2}-4Q}$

${\displaystyle a={\frac {P+{\sqrt {D}}}{2}}\quad {\text{and}}\quad b={\frac {P-{\sqrt {D}}}{2}}.\,}$

したがって：

${\displaystyle a+b=P\,,}$

${\displaystyle ab={\frac {1}{4}}(P^{2}-D)=Q\,,}$

${\displaystyle ab={\sqrt {D}}\,.}$

シーケンスとシーケンスも再帰関係を満たすことに注意してください。ただし、これらは整数シーケンスではない可能性があります。 ${\displaystyle a^{n}}$${\displaystyle b^{n}}$

のとき、aとbは異なるので、次のことがすぐに証明される。 ${\displaystyle D\neq 0}$

${\displaystyle a^{n}={\frac {V_{n}+U_{n}{\sqrt {D}}}{2}}}$

${\displaystyle b^{n}={\frac {V_{n}-U_{n}{\sqrt {D}}}{2}}.}$

したがって、ルーカス数列の項はaとbを使って次のよう に表すことができる。

${\displaystyle U_{n}={\frac {a^{n}-b^{n}}{ab}}={\frac {a^{n}-b^{n}}{\sqrt {D}}}}$

${\displaystyle V_{n}=a^{n}+b^{n}\,}$

このケースは、ある整数Sに対して となるとき、まさにその場合に発生します。この場合、 ${\displaystyle D=0}$${\displaystyle P=2S{\text{ かつ }}Q=S^{2}}$${\displaystyle a=b=S}$

${\displaystyle U_{n}(P,Q)=U_{n}(2S,S^{2})=nS^{n-1}\,}$

${\displaystyle V_{n}(P,Q)=V_{n}(2S,S^{2})=2S^{n}.\,}$

通常の生成関数は

${\displaystyle \sum _{n\geq 0}U_{n}(P,Q)z^{n}={\frac {z}{1-Pz+Qz^{2}}};}$

${\displaystyle \sum _{n\geq 0}V_{n}(P,Q)z^{n}={\frac {2-Pz}{1-Pz+Qz^{2}}}.}$

のとき、ルーカス数列とは次のペル方程式を満たします。 ${\displaystyle Q=\pm 1}$${\displaystyle U_{n}(P,Q)}$${\displaystyle V_{n}(P,Q)}$

${\displaystyle V_{n}(P,1)^{2}-D\cdot U_{n}(P,1)^{2}=4,}$

${\displaystyle V_{2n}(P,-1)^{2}-D\cdot U_{2n}(P,-1)^{2}=4,}$

${\displaystyle V_{2n+1}(P,-1)^{2}-D\cdot U_{2n+1}(P,-1)^{2}=-4.}$

• 任意の数cに対して、シーケンスと${\displaystyle U_{n}(P',Q')}$${\displaystyle V_{n}(P',Q')}$

${\displaystyle P'=P+2c}$

${\displaystyle Q'=cP+Q+c^{2}}$

は およびと同じ判別式を持ちます。 ${\displaystyle U_{n}(P,Q)}$${\displaystyle V_{n}(P,Q)}$

${\displaystyle P'^{2}-4Q'=(P+2c)^{2}-4(cP+Q+c^{2})=P^{2}-4Q=D.}$

• 任意の数cに対しても、

${\displaystyle U_{n}(cP,c^{2}Q)=c^{n-1}\cdot U_{n}(P,Q),}$

${\displaystyle V_{n}(cP,c^{2}Q)=c^{n}\cdot V_{n}(P,Q).}$

ルーカス数列の項は、フィボナッチ数 とルーカス数の関係を一般化した関係を満たします。例: ${\displaystyle F_{n}=U_{n}(1,-1)}$ ${\displaystyle L_{n}=V_{n}(1,-1)}$

${\displaystyle {\begin{array}{r|l}{\text{General case}}&(P,Q)=(1,-1)\\\hline (P^{2}-4Q)U_{n}={V_{n+1}-QV_{n-1}}=2V_{n+1}-PV_{n}&5F_{n}={L_{n+1}+L_{n-1}}=2L_{n+1}-L_{n}\\V_{n}=U_{n+1}-QU_{n-1}=2U_{n+1}-PU_{n}&L_{n}=F_{n+1}+F_{n-1}=2F_{n+1}-F_{n}\\U_{2n}=U_{n}V_{n}&F_{2n}=F_{n}L_{n}\\V_{2n}=V_{n}^{2}-2Q^{n}&L_{2n}=L_{n}^{2}-2(-1)^{n}\\U_{m+n}=U_{n}U_{m+1}-QU_{m}U_{n-1}={\frac {U_{m}V_{n}+U_{n}V_{m}}{2}}&F_{m+n}=F_{n}F_{m+1}+F_{m}F_{n-1}={\frac {F_{m}L_{n}+F_{n}L_{m}}{2}}\\V_{m+n}=V_{m}V_{n}-Q^{n}V_{m-n}=DU_{m}U_{n}+Q^{n}V_{m-n}&L_{m+n}=L_{m}L_{n}-(-1)^{n}L_{m-n}=5F_{m}F_{n}+(-1)^{n}L_{m-n}\\V_{n}^{2}-DU_{n}^{2}=4Q^{n}&L_{n}^{2}-5F_{n}^{2}=4(-1)^{n}\\U_{n}^{2}-U_{n-1}U_{n+1}=Q^{n-1}&F_{n}^{2}-F_{n-1}F_{n+1}=(-1)^{n-1}\\V_{n}^{2}-V_{n-1}V_{n+1}=DQ^{n-1}&L_{n}^{2}-L_{n-1}L_{n+1}=5(-1)^{n-1}\\DU_{n}=V_{n+1}-QV_{n-1}&F_{n}={\frac {L_{n+1}+L_{n-1}}{5}}\\V_{m+n}={\frac {V_{m}V_{n}+DU_{m}U_{n}}{2}}&L_{m+n}={\frac {L_{m}L_{n}+5F_{m}F_{n}}{2}}\\U_{m+n}=U_{m}V_{n}-Q^{n}U_{m-n}&F_{n+m}=F_{m}L_{n}-(-1)^{n}F_{m-n}\\2^{n-1}U_{n}={n \choose 1}P^{n-1}+{n \choose 3}P^{n-3}D+\cdots &2^{n-1}F_{n}={n \choose 1}+5{n \choose 3}+\cdots \\2^{n-1}V_{n}=P^{n}+{n \choose 2}P^{n-2}D+{n \choose 4}P^{n-4}D^{2}+\cdots &2^{n-1}L_{n}=1+5{n \choose 2}+5^{2}{n \choose 4}+\cdots \end{array}}}$

結果として、 はの倍数である、つまり、数列 は割り切れる数列 となります。これは特に、 が素数になるのはnが素数のときだけであることを意味します。もう 1 つの結果として、 2 乗によるべき乗の類似物により、 nの大きな値に対してを高速に計算できます。さらに、の場合、 は強い割り切れる数列となります。 ${\displaystyle U_{km}(P,Q)}$${\displaystyle U_{m}(P,Q)}$${\displaystyle (U_{m}(P,Q))_{m\geq 1}}$${\displaystyle U_{n}(P,Q)}$${\displaystyle U_{n}(P,Q)}$${\displaystyle \gcd(P,Q)=1}$${\displaystyle (U_{m}(P,Q))_{m\geq 1}}$

その他の割り切れる性質は以下の通りである: ^[1]

• が奇数の場合、 を割り切ります。${\displaystyle n\mid m}$${\displaystyle V_{m}}$${\displaystyle V_{n}}$
• N を2 Q と互いに素な整数とする。Nを割り切る最小の正の整数r が存在する場合、 Nを割り切るnの集合はrの倍数の集合とまったく同じである。${\displaystyle U_{r}}$${\displaystyle U_{n}}$
• PとQが偶数の場合、 を除いて は常に偶数になります。${\displaystyle U_{n},V_{n}}$${\displaystyle U_{1}}$
• Pが偶数でQが奇数の場合、の奇偶はnと同じになり、常に偶数になります。${\displaystyle U_{n}}$${\displaystyle V_{n}}$
• Pが奇数でQが偶数の場合、 は常に奇数になります。${\displaystyle U_{n},V_{n}}$${\displaystyle n=1,2,\ldots }$
• PとQが奇数の場合、 nが 3 の倍数である場合にのみ、P と Q は偶数になります。${\displaystyle U_{n},V_{n}}$
• p が奇数の素数である場合、 (ルジャンドル記号を参照)。${\displaystyle U_{p}\equiv \left({\tfrac {D}{p}}\right),V_{p}\equiv P{\pmod {p}}}$
• p が奇数の素数であり、PとQ を割り切る場合、p は任意の を割り切ります。${\displaystyle U_{n}}$${\displaystyle n>1}$
• pが奇数の素数で、 P を割り切れるがQを割り切れない場合、nが偶数のときのみp が割り切れます。${\displaystyle U_{n}}$
• p が奇数の素数であり、PではなくQ を割り切る場合、p はを割り切ることはありません。${\displaystyle U_{n}}$${\displaystyle n=1,2,\ldots }$
• p が奇数の素数であり、 PQ ではなく D を割り切る場合、 pがnを割り切れる場合のみ、 pがn を割り切れます。${\displaystyle U_{n}}$
• p が奇数の素数であり、 PQD を割り切れない場合、p はを割り切れます。ただし、 です。${\displaystyle U_{l}}$${\displaystyle l=p-\left({\tfrac {D}{p}}\right)}$

最後の事実は、フェルマーの小定理を一般化します。これらの事実は、ルーカス・レーマー素数判定で使用されます。最後の事実の逆は成り立ちません。フェルマーの小定理の逆は成り立たないのと同じです。 Dと互いに素で、を割り切る合成数 n が存在します。このような合成数はルーカス擬素数と呼ばれます 。 ${\displaystyle U_{l}}$${\displaystyle l=n-\left({\tfrac {D}{n}}\right)}$

ルーカス数列の項の素因数が数列の前の項を割り切れない場合、その項は原始素因数と呼ばれます。カーマイケルの定理によれば、ルーカス数列の項のうち有限個を除くすべての項は原始素因数を持ちます。[ 2 ^] 実際、カーマイケル (1913) は、Dが正でnが 1、2、6 のいずれでもない場合、には原始素因数があることを示しました。D が負の場合、 Bilu、Hanrot、Voutier、および Mignotte の詳細な結果^{[3]によると、} n > 30の場合、には原始素因数があり、すべての場合に原始素因数がないことが示されます。 ${\displaystyle U_{n}}$${\displaystyle U_{n}}$${\displaystyle U_{n}}$

PとQのいくつかの値に対する Lucas シーケンスには特定の名前があります。

U _n (1, −1)  :フィボナッチ数列

V _n (1, −1)  :ルーカス数

U _n (2, −1)  :ペル数

V _n (2, −1)  :ペル・ルーカス数（コンパニオン・ペル数）

U _n (1, −2)  :ヤコブスター数

V _n (1, −2)  :ヤコブスタール・ルーカス数

U _n (3, 2)  :メルセンヌ数2 ⁿ  − 1

V _n (3, 2) : 2 ⁿ + 1 の形の数。フェルマー数 を含む^[2]

U _n (6, 1) :平方三角数 の平方根。

U _n ( x , −1)  :フィボナッチ多項式

V _n ( x , −1)  :ルーカス多項式

U _n (2 x , 1)  :第二種チェビシェフ多項式

V _n (2 x , 1)  :第一種チェビシェフ多項式の2倍

U _n ( x +1, x )  : xを底とする反復単位

Vn ( x + 1, x )  : xn  + 1 で^ある_。

いくつかのルーカス数列は、オンライン整数数列百科事典に掲載されています。

• ルーカス数列は、一般的に使用されるベイリー-PSW素数判定テストの一部である確率的ルーカス擬素数テストで使用されます。
• ルーカス数列は、ルーカス・レーマー・リーゼルテストや、ブリルハート・レーマー・セルフリッジ1975のようなN+1法やハイブリッドN−1/N+1法など、いくつかの素数証明法で使用されている。^[4]
• LUC は、ルーカス シーケンス^[5]に基づく公開鍵暗号システムであり、エルガマル(LUCELG)、ディフィー ヘルマン(LUCDIF)、およびRSA (LUCRSA)の類似物を実装しています。LUC でのメッセージの暗号化は、RSA やディフィー ヘルマンのようにモジュラー指数を使用するのではなく、特定のルーカス シーケンスの項として計算されます。ただし、Bleichenbacher らによる論文^[6]では、モジュラー指数に基づく暗号システムに対する LUC のセキュリティ上の利点の多くは存在しないか、主張されているほど重要ではないことが示されています。

Sagemathは、およびをそれぞれおよびとして 実装します。^[7]${\displaystyle U_{n}}$${\displaystyle V_{n}}$lucas_number1()lucas_number2()

• ルーカス擬素数
• フロベニウス擬素数
• サマー・ルーカス擬素数

• カーマイケル、RD (1913)、「算術形式 α ⁿ ±β ⁿの数値因数について」、Annals of Mathematics、15 (1/4): 30–70、doi :10.2307/1967797、JSTOR  1967797
• Lehmer, DH (1930). 「ルーカス関数の拡張理論」Annals of Mathematics . 31 (3): 419–448. Bibcode :1930AnMat..31..419L. doi :10.2307/1968235. JSTOR  1968235.
• Ward, Morgan (1954). 「2 次再帰シーケンスの素因数分解」Duke Math. J. 21 ( 4): 607–614. doi :10.1215/S0012-7094-54-02163-8. hdl : 10338.dmlcz/137477 . MR  0064073.
• Somer, Lawrence (1980). 「素数に関する一次ルーカス再帰の割り切れる性質」(PDF) . Fibonacci Quarterly . 18 (4): 316–334. doi :10.1080/00150517.1980.12430140.
• Lagarias, JC ( 1985)。「ルーカス数を割り切る素数の集合の密度は 2/3 である」。Pac . J. Math . 118 ( 2): 449–461。CiteSeerX 10.1.1.174.660。doi :  10.2140 /pjm.1985.118.449。MR  0789184。
• ハンス・リーゼル(1994)。素数と因数分解のためのコンピュータ手法。数学の進歩。第 126 巻 (第 2 版)。ビルクハウザー。pp. 107–121。ISBN 0-8176-3743-5。
• Ribenboim, Paulo; McDaniel, Wayne L. (1996). 「ルーカス数列の平方項」. J. Number Theory . 58 (1): 104–123. doi : 10.1006/jnth.1996.0068 .
• Joye, M.; Quisquater, J.-J. (1996). 「完全な Lucas シーケンスの効率的な計算」(PDF) . Electronics Letters . 32 (6): 537–538. Bibcode :1996ElL....32..537J. doi :10.1049/el:19960359. 2015-02-02 にオリジナル(PDF)からアーカイブされました。
• リベンボイム、パウロ (1996)。『素数記録の新書』（電子書籍版）。Springer -Verlag、ニューヨーク。doi : 10.1007 /978-1-4612-0759-7。ISBN 978-1-4612-0759-7。
• リベンボイム、パウロ（2000年）。『私の数、私の友人：数論に関する人気講義』ニューヨーク：シュプリンガー・フェアラーク。pp. 1-50。ISBN 0-387-98911-0。
• ルカ、フロリアン (2000)。「完全なフィボナッチ数とルーカス数」。Rend . Circ Matem. パレルモ. 49 (2): 313–318. doi :10.1007/BF02904236. S2CID  121789033。
• 薮田 正之 (2001). 「カーマイケルの原始因子定理の簡単な証明」(PDF) .フィボナッチ・クォータリー. 39 (5​​): 439–443. doi :10.1080/00150517.2001.12428701.
• ベンジャミン、アーサー T. ;クイン、ジェニファー J. (2003)。本当に重要な証明: 組み合わせ証明の技術。ドルチアーニ数学解説。第 27 巻。アメリカ数学協会。p. 35。ISBN 978-0-88385-333-7。
• 数学百科事典のルーカス数列。
• ワイスタイン、エリック・W.「ルーカス・シーケンス」。マスワールド。
• Wei Dai . 「暗号におけるルーカスシーケンス」