インテジャーズ

INTEGERS

数、特に整数に関する記事。

30:Lucas数列と原始的約数

(\alpha, \beta)*1Lucasペアであるとは、\alpha, \betaが代数的整数で、a:=\alpha +\betaおよびb:=\alpha \betaがともに零でない互いに素な整数であり、更に\alpha /\beta1の冪根でないときにいいます。

Lucasペア(\alpha, \beta)に対して、二種類のLucas数列\{u_n\}_{n=0}^{\infty}, \{v_n\}_{n=0}^{\infty}

\begin{align}&u_n = u_n(\alpha, \beta ) = \frac{\alpha^n-\beta^n}{\alpha -\beta} \\ &v_n = v_n(\alpha, \beta) = \alpha^n+\beta^n\end{align}

によって定義します。漸化式で書くと、

\begin{align}u_n &= au_{n-1}-bu_{n-2}, (u_0=0, u_1=1) \\ v_n &= av_{n-1}-bv_{n-2}, (v_0=2, v_1=a)\end{align}

となります。

a=1, b=-1のとき(\alpha =\phi, \beta = -\phi^{-1}, \phiは黄金比)u_n, v_nはそれぞれFibonacci数、Lucas数を表します。

89:フィボナッチ数 - INTEGERS
199:リュカ数 - INTEGERS

つまり、Lucas数列はFibonacci数やLucas数を含む数列をもっと一般に取り扱おうというものです。 例えば、

144:フィボナッチ平方数 - INTEGERS

で扱った補題1は一般のLucas数列でも成立します(証明は定義から計算するだけ):

相互法則 D:=a^2-4bとする。任意の非負整数m, nに対して次が成立。
\begin{align}2u_{m+n} &= u_mv_n+u_mv_n \\ 2v_{m+n} &= v_mv_n+Du_mu_m.\end{align}

次の性質もFibonacci数に限らずに成立します:

命題 nmの倍数であれば、u_nu_mの倍数である。

証明. 上記相互法則を使おうとすると、係数にある2が邪魔である。代わりにu_{m+n}=u_mv_n-b^nu_{m-n}を使えば、u_{km}=u_{(k-1)m}v_m-q^mu_{(k-2)m}となってkに関する帰納法が使える形になる。u_{2m}=u_mv_mより、k=2のときもOK。 Q.E.D.

さて、この記事ではu_nに関する原始的約数の話を紹介しようと思います。

定義 n \geq 1に対して、u_nの素因子p原始的約数であるとは*2D=a^2-4bおよびm < nに対するu_mのいずれも割り切らないときにいう。

例えば、Fibonacci数の場合(D=5)は

F_1=1, 原始的約数なし
F_2=1, 原始的約数なし
F_3=2, 2が原始的約数
F_4=3, 3が原始的約数
F_5=5, 原始的約数なし
F_6=8=2^3, 原始的約数なし
F_7=13, 13が原始的約数
F_8=21=3\times 7, 7が原始的約数
F_9=34=2\times 17, 17が原始的約数
F_{10}=55=5\times 11, 11が原始的約数
F_{11}=89, 89が原始的約数
F_{12}=144=2^4\times 3^2, 原始的約数なし
F_{13}=233, 233が原始的約数
F_{14}=377=13\times 29, 29が原始的約数

のようになっています。実は、F_1, F_2, F_5, F_6, F_{12}以外のFibonacci数は全て原始的約数を持ちます! 或る意味でF_{12}以降のFibonacci数は常に新しい情報を有していると表現できるでしょう。F_{12}はただでさえ冪乗数となる最大のFibonacci数という素敵な性質を持っていたのですが、かような性質(原始的約数をもたない最大のFibonacci数という特徴)も持っていたのです!

Lucas数列に関する非常にチャレンジングな問題として、原始的約数を持たないようなLucas数列の項の全把握という問題がありました。この問題はBilu-Hanrot-Voutierによって2001年に完全解決されています(彼らはLehmer数列も同時に扱っていますがこの記事では省略します):

Y. Bilu, G. Hanrot, P. M. Voutier, Existence of primitive divisors of Lucas and Lehmer numbers, J. Reine Angew. Math. 539 (2001), 75--122.

まず、彼らの論文の主結果である次の定理は極めて強い結果です:

定理 (Bilu-Hanrot-Voutier) 任意のLucasペア(\alpha, \beta)に対して、u_nn > 30ならば原始的約数を持つ!

非常に強力かつ美しいです。Fibonacci数列の場合だけを考えても、少数の例外を除いてずっと原始的約数を持ち続けるというのは非自明なことでしたが、どんなLucas数列を考えても例外が30個そこら(実際には最大で10個)を超えることはないと言っているのです。これはLucas数列が単なる一般化ではなく非常に深い数列のクラスであることを表していると言えるでしょう。あんなに単純なる数列と一般性からかような定理が成り立つとは想像もできません!しかも、これはベストポッシブルな結果のため、30に今まで以上に特別な感情を抱いてしまいます。個人的には30定理という名称を与えたいです。

残念ながら証明は(難解なため)現段階では当ブログで紹介することはできません。実はZsigmondyの定理という1800年代後半に得られた有名な定理があるのですが、Zsigmondyの定理を(今から述べるものも含めた)Bilu-Hanrot-Voutierの結果はそのプロトタイプとして含んでいます。Zsigmondyの定理の方は近いうちに証明を紹介するつもりです*3。今回は証明抜きに結果を味わうことにしましょう。

彼らは問題を完全解明したと言いましたが、そのためにはn \leq 30の場合に原始的約数を持たないようなLucasペアとnの組を全て列挙すればよいです。まず、次は明らかです:

任意のLucasペアに対して、u_1=1は原始的約数をもたない。

2 \leq n \leq 30の場合の分類表において、簡単のため、Lucasペアに同値関係を定義します:

定義 二つのLucasペア(\alpha_1, \beta_1), (\alpha_2, \beta_2)が同値であるとは、\alpha_1/\alpha_2 =\beta_1/\beta_2=\pm 1のときにいう。

次の定理によって、原始的約数をもたない例が全て列挙されています:

定理 2 \leq n \leq 30に対して、原始的約数をもたないようなLucasペアは必ず\displaystyle \left( \frac{a-\sqrt{b}}{2}, \frac{a+\sqrt{b}}{2} \right)なる形をしたペアと同値である*4。更に、実際に原始的約数をもたないものは各n毎に次のような(a, b)の場合である。

  • \color{red}{n=2} (1, 1-4q), (q\neq 1); (2^k, 4^k-4q), (q \equiv 1 \pmod{2}, (k, q) \neq (1, 1))
  • \color{red}{n=3} (m, 4-3m^2), (m > 1); (m, 4\cdot 3^k-3m^2), (m\not \equiv 0\pmod{3}, (k, m) \neq (1, 2))
  • \color{red}{n=4} (m, 2-m^2), (m > 1, m \equiv 1\pmod{2}); (m, 4-m^2), (m > 2, m \equiv 0\pmod{2})
  • \color{red}{n=5} (1, -7); (2, -40); (1, -11); (1, -15); (12, -76); (12, -1364)
  • \color{red}{n=6} (m, (4-m^2)/3), (m \geq 4, m \not \equiv 0 \pmod{3}); (m, (4^{k+1}-m^2)/3), (m \equiv \pm 1\pmod{6}); (m, 4-m^2/3), (m \equiv 0 \pmod{3}); (m, 2^{k+2}-m^2/3), (m \equiv 3 \pmod{6})
  • \color{red}{n=7} (1, -7); (1, -19)
  • \color{red}{n=8} (2, -24); (1, -7)
  • \color{red}{n=10} (2, -8); (5, -3); (5, -47)
  • \color{red}{n=12} (1, 5); (1, -7); (1, -11); (2, -56); (1, -15); (1, -19)
  • \color{red}{n=13} (1, -7)
  • \color{red}{n=18} (1, -7)
  • \color{red}{n=30} (1, -7)

ここで、qは非負整数であり、k, mは自然数。

(a, b)=(1, -7)というペアがかなり原始的約数なしのケースが多いようなので実際に確認してみましょう。これは((1-\sqrt{-7})/2, (1+\sqrt{-7})/2/)なるLucasぺアに対するLucas数列で、漸化式は

u_n=u_{n-1}-2u_{n-2}

で与えられます(D=-7)。

u_0=0,
u_{1}=1, 原始的約数なし
u_{2}=1, 原始的約数なし
u_{3}=-1, 原始的約数なし
u_{4}=-3, 3が原始的約数
u_{5}=-1, 原始的約数なし
u_{6}=5, 5が原始的約数
u_{7}=7, 原始的約数なし
u_{8}=-3, 原始的約数なし
u_{9}=-17, 17が原始的約数
u_{10}=-11, 11が原始的約数
u_{11}=23, 23が原始的約数
u_{12}=45=3^2\times 5, 原始的約数なし
u_{13}=-1, 原始的約数なし
u_{14}=-91=-7\times 13, 13が原始的約数
u_{15}=-89, 89が原始的約数
u_{16}=93=3\times 31, 31が原始的約数
u_{17}=271, 271が原始的約数
u_{18}=85=5\times 17, 原始的約数なし
u_{19}=-457, 457が原始的約数
u_{20}=-627=-3\times 11 \times 19, 19が原始的約数
u_{21}=287=7\times 41, 41が原始的約数
u_{22}=1541=23 \times 67, 67が原始的約数
u_{23}=967, 967が原始的約数
u_{24}=-2115=-3^2\times 5\times 47, 47が原始的約数
u_{25}=-4049, 4049が原始的約数
u_{26}=181, 181が原始的約数
u_{27}=8279=17\times 487, 487が原始的約数
u_{28}=7917=3\times 7\times 13 \times 29, 29が原始的約数
u_{29}=-8641, 8641が原始的約数
u_{30}=-24475 = -5^2\times 11\times 89 原始的約数なし
u_{31}=-7193, 7193が原始的約数
u_{32}=41757=3\times  31 \times 449, 449が原始的約数
u_{33}=56143=23 \times 2441, 2441が原始的約数

このあとは、定理よりずっと原始的約数が現れ続けるのです。

個人的疑問 どのようなLucasペアに対して、そのペアに対する原始的約数の全体集合が全ての素数のなす集合に一致するか?

*1:u_n(\alpha, \beta) = u_n(\beta, \alpha)なので、Lucasペアは順序対ではなく、順序を無視したペアと考えることにします。

*2:個人的には原始的素因子の方がよい気がします。

*3:しました: integers.hatenablog.com

*4:a, bはこの記事の初めに現れたものとは別ものであることに注意。