リュカ数列のソースを表示

{{Otheruses|一般のリュカ数列|フィボナッチ数の同伴数列|リュカ数}}

'''リュカ数列'''（リュカすうれつ）または'''ルーカス数列'''（ルーカスすうれつ）(''Lucas sequence'')とは、二次の整係数[[二次方程式|方程式]] ''G''(''x'') = ''x''<sup>2</sup> &minus; ''Px'' + ''Q'' = 0 の二つの解

:<math>\alpha=(P+\sqrt{D})/2, \beta=(P-\sqrt{D})/2, D=P^2-4Q</math>

に対し、

{{Indent|<math>U_n(P, Q)=(\alpha^n-\beta^n)/(\alpha-\beta), V_n(P, Q)=\alpha^n+\beta^n</math>}}

と定義される[[数列]]である。また同じことであるが、
{{Indent|
<math>U_0(P,Q)=0, U_1(P,Q)=1, U_n(P,Q)=PU_{n-1}(P,Q)-QU_{n-2}(P,Q) \mbox{  for }n>1,</math><br />
<math>V_0(P,Q)=2, V_1(P,Q)=P, V_n(P,Q)=PV_{n-1}(P,Q)-QV_{n-2}(P,Q) \mbox{  for }n>1</math>
}}
という関係式を満たす数列として定義される数列である。

リュカ数列は二階[[線形回帰数列]]の一種で、[[フィボナッチ数]]、[[リュカ数]]、[[ペル数]], [[メルセンヌ数]]など数論に現れる重要な数列がこれに属する。

== 用語 ==

''U''<sub>''n''</sub> , ''V''<sub>''n''</sub> を( ''P'' , ''Q'' )に伴うリュカ数列という。''V''<sub>''n''</sub> を同伴リュカ数列と呼ぶこともある。 &alpha;/&beta; が1の[[冪根]]であるとき ''U''<sub>''n''</sub> , ''V''<sub>''n''</sub> を'''退化'''(''degenerate'')、そうでないとき'''非退化'''(''non-degenerate'')という。

''D'' を割り切らない[[素数]] ''p'' が ''U''<sub>''n''</sub> を割り切るが、 ''U''<sub>''m''</sub> ( ''m'' < ''n'' )を割り切らないとき、 ''p'' を ''U''<sub>''n''</sub> の'''原始約数'''( 'primitive divisor' )という。

== 例 ==
''U''<sub>''n''</sub> (1, -1)はフィボナッチ数, ''V''<sub>''n''</sub> (1, -1)は（通常の）リュカ数である。

''U''<sub>''n''</sub> (3, 2)=2<sup> ''n''</sup>-1, ''V''<sub>''n''</sub> (3, 2)=2<sup> ''n''</sup>+1で、それぞれメルセンヌ数, [[フェルマー数]]を含んでいる。

''U''<sub>''n''</sub> (2, -1), ''V''<sub>''n''</sub> (2, -1)はペル数となる。

== 性質 ==
次のような等式が成り立つ<ref>以下の性質については{{citation
 | last = Carmichael | first = R. D. | author-link = Robert Daniel Carmichael
 | doi = 10.2307/1967797
 | issue = 1/4
 | journal = Annals of Mathematics
 | pages = 30–49
 | title = On the numerical factors of the arithmetic forms α<sup>''n''</sup>±β<sup>''n''</sup>
 | volume = 15
 | year = 1913
 | jstor = 1967797}}, {{citation
 | last = Carmichael | first = R. D. | author-link = Robert Daniel Carmichael
 | doi = 10.2307/1967798
 | issue = 1/4
 | journal = Annals of Mathematics
 | pages = 50–70
 | title = On the numerical factors of the arithmetic forms α<sup>''n''</sup>±β<sup>''n''</sup> (continued)
 | volume = 15
 | year = 1913
 | jstor = 1967798}}, {{Cite journal
  | last = D. H.
  | first = Lehmer
  | title = An Extended Theory of Lucas' Functions
  | journal = Ann. of Math.
  | volume = 31
  | issue = 3
  | pages = 419--448
  | publisher = 
  | location = 
  | date = 1930
  | jstor = 1968235
  | issn = 
  | doi = 10.2307/1968235
  | id = 
  | naid = 
  | accessdate = }} および Ribenboim を参照
</ref>。

* <math>V_n^2-DU_n^2=4Q^n</math>,
* <math>U_n^2-U_{n-1}U_{n+1}=Q^{n-1}</math>,
* <math>DU_n=V_{n+1}-QV_{n-1}</math>,
* <math>V_n=U_{n+1}-QU_{n-1}</math>,
* <math>2U_{m+n}=U_mV_n+U_nV_m</math>,
* <math>2V_{m+n}=V_mV_n+DU_mU_n</math>,
* <math>U_{2n}=U_nV_n</math>,
* <math>V_{2n}=V_n^2-2Q^n</math>,
* <math>U_{m+n}=U_mV_n-Q^nU_{m-n}</math>,
* <math>V_{m+n}=V_mV_n-Q^nV_{m-n}=DU_mU_n+Q^nV_{m-n}</math>,
* <math>2^{n-1}U_n={n \choose 1}P^{n-1}+{n \choose 3}P^{n-3}D+\cdots</math>,
* <math>2^{n-1}V_n=P^n+{n \choose 2}P^{n-2}D+{n \choose 4}P^{n-4}D^2+\cdots</math>.

また ''n'' が正のとき
:<math>F_n=\prod_{d\mid n}U_{n/d}^{\mu(d)}=\frac{U_n \prod_{p\neq q, p, q\mid n} U_{n/pq} \cdots}{\prod_{p\mid n} U_{n/p}\cdots}=\prod_{\gcd(k, n)=1}(\alpha-\zeta_n^k \beta)=\beta^{\varphi(n)}\Phi_n (\alpha/\beta)</math>
とおく（&mu; は[[メビウス関数]]、&zeta;<sub>''n''</sub> は[[1の冪根|1の原始 ''n'' 乗根]]、{{math|''φ''}}は[[オイラーのφ関数|オイラーの {{mvar|φ}} 関数]]、&Phi;<sub>''n''</sub> は1の原始 ''n'' 乗根に関する[[円分多項式]]）と、 ''F''<sub>''n''</sub> も整数で
:<math>U_n=\prod_{d\mid n}F_d, V_n=\prod_{d\mid 2n, 2\not\mid 2n/d} F_d</math>
が成り立つ。特に ''F''<sub>''n''</sub> は ''U''<sub>''n''</sub> の約数で、 ''p'' が素数のとき ''F''<sub>''p''</sub> = ''U''<sub>''p''</sub> となる。

また、 リュカ数列の整除性について、次のような性質が成り立つ。

* <math>m|n</math>ならば、<math>U_m|U_n</math>,
* ''n'' が ''m'' の[[奇数]]倍ならば、<math>V_m|V_n</math>,
* ''N'' が 2 ''Q'' と[[互いに素 (整数論)|互いに素]]な整数とする。<math>N|U_r</math>となる最小の ''r'' が存在するとき、<math>N|U_n</math>となる ''n '' 全体は ''r'' の[[倍数]]全体と一致する。

* ''P'', ''Q'' が[[偶数]]ならば、 ''U''<sub>''n''</sub>, ''V''<sub>''n''</sub> は ''U'' <sub>1</sub>を除いていつも偶数である。
* ''P'' が偶数で、 ''Q''が[[奇数]]ならば、 ''U''<sub>''n''</sub> の偶奇 は ''n'' の偶奇と一致し、 ''V''<sub>''n''</sub> はいつも偶数である。
* ''P'' が奇数で、 ''Q''が偶数ならば、 ''U''<sub>''n''</sub> , ''V''<sub>''n''</sub> はいつも奇数である。
* ''P'', ''Q'' が奇数ならば、 ''U''<sub>''n''</sub> , ''V''<sub>''n''</sub> は ''n'' が3の倍数であるとき偶数で、そうでないとき奇数である。

* ''p'' が奇[[素数]]ならば、<math>U_p\equiv\left(\frac{D}{p}\right), V_p\equiv P\pmod{p}, \left(\frac{D}{p}\right)</math>は[[平方剰余]]の記号である。
* ''p'' が奇素数で、 ''P'' , ''Q'' を割り切るならば、''p'' は ''U'' <sub>1</sub>を除く全ての ''U''<sub>''n''</sub> を割り切る。
* ''p'' が奇素数で、 ''P'' を割り切り ''Q'' を割り切らないならば、''p'' が ''U''<sub>''n''</sub> を割り切るのは ''n'' が偶数であることと同値である。
* ''p'' が奇素数で、 ''P'' を割り切らず ''Q'' を割り切るならば、''p'' は決して ''U''<sub>''n''</sub> を割り切らない。
* ''p'' が奇素数で、 ''PQ'' を割り切らず、 ''D''を割り切るならば、''p'' が ''U''<sub>''n''</sub> を割り切るのは ''n'' が ''p'' の倍数であることと同値である。
* ''p'' を ''PQD'' を割り切らない奇素数とし <math>l=p-\left(\frac{D}{p}\right)</math> とおくと、 ''p'' は ''U''<sub>''l''</sub> を割り切る。

最後の定理は[[フェルマーの小定理]]の一般化である。これと原始約数の定義から、次のことがわかる。

* ''p'' を ''PQD'' を割り切らない奇素数とする、 <math>l=p-\left(\frac{D}{p}\right)</math> とおく。 ''p'' が ''U''<sub>''n''</sub> の原始約数ならば ''n'' は ''l'' を割り切る。特に、<math>p\equiv\left(\frac{D}{p}\right)\pmod{n}</math> が成り立つ。

フェルマーの小定理の逆が成り立たないように、上の定理の逆も成り立たない。つまり ''D'' と互いに素な合成数 ''n'' が ''U<sub>l</sub>'' （<math>l=n-\left(\frac{D}{n}\right)</math>）を割り切る場合が存在する。そのような ''n'' は '''リュカ擬素数''' (''Lucas pseudoprime'') という。
非退化の数列に対応するリュカ擬素数は無数に存在する。さらに正確に、任意の与えられた非退化の数列と正整数 ''k'', ''s'' に対し、 ''s'' 個の素因数をもち、それらがすべて等差数列 ''kx'' +1 に属するリュカ擬素数が無数に存在する<ref>Peter Kiss, On Lucas pseudoprimes which are products of ''s'' primes, ''Fibonacci Numbers and Their Applications'', 1986, 131--139.</ref>。

''P'' と ''Q'' が[[互いに素 (整数論)|互いに素]]ならば、次の性質も成り立つ。

* ''U''<sub>''n''</sub> と ''Q'' は互いに素、また ''V''<sub>''n''</sub> と ''Q'' も互いに素である。
* ''U''<sub>''n''</sub> と ''V''<sub>''n''</sub> は互いに素であるか、最大公約数は2である。
* <math>\gcd(U_m, U_n)=U_{\gcd (m, n)}.</math>
* <math>d=\gcd(m, n)</math> とする。 <math>m/d, n/d</math> が共に奇数ならば <math>\gcd(V_m, V_n)=V_d.</math>

リュカ数列の値は少数の例外を除いて原始約数を持つことが知られている。''D'' を割り切らない素数 ''p'' が ''F''<sub>''n''</sub> の原始約数であるための必要十分条件は ''p'' が ''n'' を割り切らないことである<ref>Carmichael, 上記論文, 定理20</ref>。

''P'', ''Q'' が互いに素かつ ''U''<sub>''n''</sub> が非退化とする。 ''D'' &gt; 0のとき、 ''n'' &ne; 1, 2, 6ならば ''U''<sub>''n''</sub> は <math>U_3(1, -2)=U_3(-1, -2)=3, U_5(1, -1)=U_5(-1, -1)=5, U_{12}(1, -1)=144, U_{12}(-1, -1)=-144</math>を除いて原始約数を持つことは既にカーマイケルにより示されている<ref>Carmichael, 上記論文, 定理21</ref>。 ''D'' &lt; 0のときは難しい問題であったが  ''n'' &gt; 30ならば、 ''U''<sub>''n''</sub> は原始約数を持つ<ref>{{cite journal | first1=Yuri | last1=Bilu | first2=Guillaume | last2=Hanrot | first3=Paul M. | last3=Voutier | first4=Maurice | last4=Mignotte | title=Existence of primitive divisors of Lucas and Lehmer numbers | journal = J. Reine Angew. Math. | year=2001 | volume=539 |pages= 75--122 | mr=1863855 | doi=10.1515/crll.2001.080}}[http://www.loria.fr/~hanrot/index.html.en Guillaume Hanrot Publication list, 2001(preliminary version).]</ref>。また、 ''n'' &le; 30で、 ''U''<sub>''n''</sub> が原始約数を持たないものは先に全て知られている<ref>{{cite journal | first=Paul M. | last=Voutier | title=Primitive divisors of Lucas and Lehmer sequences | journal = J. Reine Angew. Math. | year=1995 | volume=64 |pages= 869--888 | mr=1284673 | doi=10.1515/crll.2001.080}}[http://www.loria.fr/~hanrot/index.html.en Guillaume Hanrot Publication list, 2001(preliminary version).]</ref>。<math>U_n (n=5, 7\leq n\leq 30)</math> が原始約数を持たないもの（ ''P'' が正の場合のみ挙げる。 ''P'' が負の場合は (-1)<sup>''n''</sup> 倍する）は次の通り。
{|class="wikitable"
!''n''
!<math>U_n(P, Q)</math>
|-
|style="text-align:right"|5
|style="text-align:right"|''U''<sub>5</sub>(1, -1)=5, ''U''<sub>5</sub>(1, 2)=-1, ''U''<sub>5</sub>(2, 11)=5, ''U''<sub>5</sub>(1, 3)=1, ''U''<sub>5</sub>(1, 4)=7, ''U''<sub>5</sub>(12, 55)=1, ''U''<sub>5</sub>(12, -1364)=1
|-
|style="text-align:right"|7
|style="text-align:right"|''U''<sub>7</sub>(1, 2)=1, ''U''<sub>7</sub>(1, 5)=1
|-
|style="text-align:right"|8
|style="text-align:right"|''U''<sub>8</sub>(2, 7)=-40, ''U''<sub>8</sub>(1, 2)=-3
|-
|style="text-align:right"|10
|style="text-align:right"|''U''<sub>10</sub>(2, 3)=-22, ''U''<sub>10</sub>(5, 7)=-3725, ''U''<sub>10</sub>(5, 18)=10025
|-
|style="text-align:right"|12
|style="text-align:right"|''U''<sub>12</sub>(1, -1)=144, ''U''<sub>12</sub>(1, 2)=-45, ''U''<sub>12</sub>(1, 3)=160, ''U''<sub>12</sub>(1, 4)=-231, ''U''<sub>12</sub>(1, 5)=-3024, ''U''<sub>12</sub>(2, 15)=-23452
|-
|style="text-align:right"|13
|style="text-align:right"|''U''<sub>13</sub>(1, 2)=-1
|-
|style="text-align:right"|18
|style="text-align:right"|''U''<sub>18</sub>(1, 2)=85
|-
|style="text-align:right"|30
|style="text-align:right"|''U''<sub>30</sub>(1, 2)=-24475
|}

== 参考文献 ==
{{reflist}}

*{{Citation |first= Paulo |last= Ribenboim |title=The New Book of Prime Number Records | publisher=[[Springer-Verlag]], New York | edition=eBook | isbn=978-1-4612-0759-7 | DOI=10.1007/978-1-4612-0759-7 | year=1996}}

*{{Citation |editor1-first= Andreas |editor1-last= Philippou |editor2-first= G. E. |editor2-last= Bergum |editor3-first= Alwyn. F. |editor3-last= Horadam |title=Fibonacci Numbers and Their Applications | origyear=1986 | publisher=[[Kluwer Academic Publishers]], Dordrecht, The Netherlands | edition=Softcover reprint | isbn=978-1402003271 | year=2001}}


{{DEFAULTSORT:りゆかすうれつ}}
[[Category:数論]]
[[Category:整数の類]]
[[Category:エドゥアール・リュカ]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]