インテジャーズ

インテジャーズ

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

フィボナッチ数とp進数

F_nn番目のFibonacci数とします:

integers.hatenablog.com

\mathcal{F}:=\{F_n \mid n \in \mathbb{Z}_{>0}\}に対して、二つのFibonacci数の商からなる集合Q({\mathcal F})

\displaystyle Q(\mathcal{F}) := \left\{ \left. \frac{F_n}{F_m} \right| n, m \in \mathbb{Z}_{>0} \right\}

と定義します。黄金比を\displaystyle \phi := \frac{1+\sqrt{5}}{2}とするとき、Binetの公式

\displaystyle F_n = \frac{\phi^n-(-\phi)^{-n}}{\sqrt{5}}

よりQ(\mathcal{F})の元は\mathbb{R}において\phiの整数乗の近くにしか分布しません。一方、次が成り立ちます:

定理*1 任意の素数pに対して、Q(\mathcal{F})p進数体\mathbb{Q}_pで稠密である。

この記事ではこの定理の証明を解説します。

準備

補題1 m \mid n \Longrightarrow F_m \mid F_n.

証明. これは
integers.hatenablog.com
に書いてある一般的な命題をFibonacci数に適用したもの。 Q.E.D.

補題2 mを正の整数とし、n_1, n_2を整数とする(ここでは0以下の整数も許す)。このとき、F_{n_1}F_{n_2}がともにmで割り切れるならば、F_{n_1+n_2}mで割り切れる。

証明. 整数n_1, n_2に対してF_{n_1+n_2}=F_{n_2-1}F_{n_1}+F_{n_2}F_{n_1+1}が成り立つ(例えば、Binetの公式で右辺を計算すると(L_{n_1+n_2-1}+L_{n_1+n_2})/5に等しいことがわかる。L_{n-1}+L_n=5F_nが成り立つことは数学的帰納法で示せる*2 )。よって、F_{n_1}F_{n_2}mで割り切れるならばF_{n_1+n_2}も割り切れる。 Q.E.D.

補題2とF_n=(-1)^{n-1}F_{-n}より

A_n:=\{n \in \mathbb{Z} \colon \ m \mid F_n\}

\mathbb{Z}のイデアルをなすことがわかる。A_nを生成する正の整数をz(m)で表す。冒頭のフィボナッチ数の記事で述べたようにF_nが偶数であるための必要十分条件はn3の倍数であることだったので、z(2)=3がわかる。

補題3 (Lucas) n, m, kを正整数とする。このとき、
\displaystyle (m+n)^k=m^k+n^k-\sum_{j=1}^{[k/2]}(-1)^j\frac{k}{j}\binom{k-j-1}{j-1}(mn)^j(m+n)^{k-2j}
が成り立つ*3

証明. kに関する数学的帰納法で証明する。k=1, 2の場合は成り立っている。k以下で成り立つと仮定してk+1の場合にも成り立つことを証明しよう。まず、kのときに成立するという仮定より

\begin{align} (m+n)^{k+1} &= (m+n)(m+n)^k \\ &=(m+n)(m^k+n^k)-\sum_{j=1}^{[k/2]}(-1)^j\frac{k}{j}\binom{k-j-1}{j-1}(mn)^j(m+n)^{k-2j+1}\end{align}

が成り立つ。次に、k-1の場合に成立するという仮定より

\displaystyle mn(m^{k-1}+n^{k-1})=mn(m+n)^{k-1}+\sum_{j=1}^{\left[\frac{k-1}{2}\right]}(-1)^j\frac{k-1}{j}\binom{k-j-2}{j-1}(mn)^{j+1}(m+n)^{k-2j-1}.

これを最初の式に代入することにより

\begin{align}(m+n)^{k+1}&=m^{k+1}+n^{k+1}+mn(m+n)^{k-1}\\ &\quad +\sum_{j=1}^{\left[ \frac{k-1}{2}\right]}(-1)^j\frac{k-1}{j}\binom{k-j-2}{j-1}(mn)^{j+1}(m+n)^{k-2j-1}\\ &\quad -\sum_{j=1}^{[k/2]}(-1)^j\frac{k}{j}\binom{k-j-1}{j-1}(mn)^j(m+n)^{k-2j+1}\end{align}

を得る。最後の和は

\begin{align}&\quad -\sum_{j=1}^{[k/2]}(-1)^j\frac{k}{j}\binom{k-j-1}{j-1}(mn)^j(m+n)^{k-2j+1} \\ &= kmn(n+n)^{k-1} -\sum_{j=2}^{[k/2]}(-1)^j\frac{k}{j}\binom{k-j-1}{j-1}(mn)^j(m+n)^{k-2j+1} \\ &= kmn(m+n)^{k-1}+\sum_{j=1}^{\left[ \frac{k-1}{2}\right]}(-1)^j\frac{k}{j+1}\binom{k-j-2}{j}(mn)^{j+1}(m+n)^{k-2j-1}\end{align}

と変形できるので*4

\begin{align}(m+n)^{k+1} &= m^{k+1}+n^{k+1}+(k+1)mn(m+n)^{k-1}\\
 & \quad +\sum_{j=1}^{\left[ \frac{k-1}{2}\right]}(-1)^j\left\{ \frac{k-1}{j}\binom{k-j-2}{j-1}+\frac{k}{j+1}\binom{k-j-2}{j}\right\}(mn)^{j+1}(m+n)^{k-2j-1} \\ &=m^{k+1}+n^{k+1}+(k+1)mn(m+n)^{k-1} \\ &\quad +\sum_{j=1}^{\left[\frac{k-1}{2}\right]}(-1)^j\frac{k+1}{j+1}\binom{k-j-1}{j}(mn)^{j+1}(m+n)^{k-2j-1} \\ &= m^{k+1}+n^{k+1}-\sum_{j=1}^{\left[\frac{k+1}{2}\right]}(-1)^j\frac{k+1}{j}\binom{k-j}{j-1}(mn)^j(m+n)^{k-2j+1}\end{align}

となって、k+1のときも成立することが示された。 Q.E.D.

補題4 pを奇素数とする。このとき、任意の正の整数k, iに対して
\mathrm{ord}_p(F_{kz(p)p^i}) = \mathrm{ord}_p(F_{kz(p)})+i
が成り立つ。

証明. 補題3においてm\mapsto \phi^{kz(p)}, n\mapsto-(-\phi)^{-kz(p)}, k\mapsto p^iとすると、

\displaystyle F_{kz(p)p^i}=\sqrt{5}^{p^i-1}F_{kz(p)}^{p^i}+\sum_{j=1}^{\frac{p^i-1}{2}}(-1)^{jkz(p)}\sqrt{5}^{p^i-2j-1}\frac{p^i}{j}\binom{p^i-j-1}{j-1}F_{kz(p)}^{p^i-2j}

が得られる。右辺について、和のj=\frac{p^i-1}{2}のときの項がp-orderが最も小さく、その項は符号を無視すればp^iF_{kz(p)}であり、p-orderは\mathrm{ord}_p(F_{kz(p)})+iである。j < \frac{p^i-1}{2}のときに1/jの寄与が気になるのでチェックしておく。

\begin{align} &\quad \mathrm{ord}_p\left( (-1)^{jkz(p)}\sqrt{5}^{p^i-2j-1}\frac{p^i}{j}\binom{p^i-j-1}{j-1}F_{kz(p)}^{p^i-2j} \right) \\
&\geq \mathrm{ord}_p\left( \frac{p^i}{j} \right) + \mathrm{ord}_p(F_{kz(p)}^{p^i-2j}) = i-\mathrm{ord}_p(j)+(p^i-2j)\mathrm{ord}_p(F_{kz(p)})\end{align}

なので、

 i-\mathrm{ord}_p(j)+(p^i-2j)\mathrm{ord}_p(F_{kz(p)}) > \mathrm{ord}_p(F_{kz(p)})+i

すなわち

(p^i-2j-1)\mathrm{ord}_p(F_{kz(p)}) > \mathrm{ord}_p(j)

を示せばよい。今、\mathrm{ord}_p(F_{kz(p)}) \geq 1であることに注意する。1 \leq \mathrm{ord}_p(j)=t \leq i-1であったと仮定する(t=0のときは自明)。このとき、j < \frac{p^i-1}{2}であることからj \leq \frac{p^i-p^t}{2}であることがわかる。よって、

p^i-2j-1 \geq p^t-1 > t

であり、示すべきことは全て示された。 Q.E.D.

補題5 任意の正の整数iに対して
\mathrm{ord}_2(F_{3\cdot 2^i}) = i+2
が成り立つ。

証明. iに関する数学的帰納法で証明する。\mathrm{ord}_2(F_6)=\mathrm{ord}_2(8)=3なのでi=1のときは成立する。\mathrm{ord}_2(F_{3\cdot 2^i})=i+2を仮定する。

integers.hatenablog.com

の補題1とリュカ数の記事で紹介したL_{2n}=L_n^2+(-1)^{n-1}\cdot 2より、

L_{2n}=(-1)^n\cdot 2+5F_n^2

が成り立つ。また、F_3=2なので、補題1よりF_{3\cdot 2^{i-1}}は偶数である。よって、

\mathrm{ord}_2(L_{3\cdot 2^i})=\mathrm{ord}_2(L_{2(3\cdot 2^{i-1})}) = \mathrm{ord}_2((-1)^{3\cdot 2^{i-1}}\cdot 2+5F_{3\cdot 2^{i-1}}^2) = 1.

144の記事の補題1よりF_{2n}=F_nL_nなので、

\mathrm{ord}_2(F_{3\cdot 2^{i+1}}) = \mathrm{ord}_2(F_{2(3\cdot 2^i)}) = \mathrm{ord}_2(F_{3\cdot 2^i}) + \mathrm{ord}_2(L_{3\cdot 2^i}) = i+3

となって、i+1のときも成立することが示された。 Q.E.D.

補題6 任意の素数pに対して、\{p^{-r}n \mid n, r \in \mathbb{Z}_{\geq 0}\}\mathbb{Q}_pで稠密である。

証明. p進数xを任意にとる。xp進展開が整数kを用いて

\displaystyle x=p^k\sum_{j=0}^{\infty}a_jp^j

と書けているとする(a_j0からp-1の整数)。NN\geq k+1を満たすような整数とし、\displaystyle n:=\sum_{j=0}^{N-k-1}a_jp^j \in \mathbb{Z}とする。このとき、

\displaystyle \mathrm{ord}_p(x-p^kn) = \mathrm{ord}_p\left( p^k\sum_{j=N-k}^{\infty}a_jp^j \right) = k +\mathrm{ord}_p\left( \sum_{j=N-k}^{\infty}a_jp^j \right) \geq k+(N-k) = N

となるので、xの非常に近いところにp^knはいる。 Q.E.D.

補題7 任意の素数pおよび正整数iに対して
\phi^{4z(p)p^{2i}} \equiv 1, \quad (-\phi)^{-4z(p)p^{2i}} \equiv 1 \pmod{p^{2i}\mathcal{O}_{K}}
が成立する。ここで、\mathcal{O}_{K}K:=\mathbb{Q}(\sqrt{5})の整数環\mathbb{Z}[\phi]

証明. \phi^{4z(p)p^{2i}} \equiv 1を示せば十分。pが奇素数のときは補題4より、p=2の場合は補題5よりp^{2i} \mid F_{z(p)p^{2i}}なので、

\phi^{z(p)p^{2i}}-(-\phi)^{-z(p)p^{2i}} = \sqrt{5}F_{z(p)p^{2i}} \equiv 0 \pmod{p^{2i}\mathcal{O}_K}.

よって、\phi^{z(p)p^{2i}}\equiv (-\phi)^{-z(p)p^{2i}} \pmod{p^{2i}\mathcal{O}_K}であり、これを変形すれば所望の合同式となる。 Q.E.D.

補題8 任意の素数pと正整数k、非負整数rに対して
\mathrm{ord}_p(F_{4z(p)p^{2(k+2r)}})=\mathrm{ord}_p(F_{4z(p)p^{2(k+r)}})+2r
が成り立つ。

証明. pが奇素数の場合は補題4、p=2の場合は補題5より従う。 Q.E.D.

定理の証明

n, kを任意の正整数、rを任意の非負整数とする。正整数mに対して成り立つ恒等式

x^m-y^m=(x-y)(x^{m-1}+x^{m-2}y+\cdots + xy^{m-2}+y^{m-1})

x=\phi^{4z(p)p^{2i}}, y=(-\phi)^{-4z(p)p^{2i}}を代入することによって(iは正整数)、

\begin{align} \frac{F_{4z(p)p^{2i}m}}{F_{4z(p)p^{2i}}} &= \frac{\phi^{4z(p)p^{2i}m}-(-\phi)^{-4z(p)p^{2i}m}}{\phi^{4z(p)p^{2i}}-(-\phi)^{-4z(p)p^{2i}}} \\ &=(\phi^{4z(p)p^{2i}})^{m-1}+\cdots + ((-\phi)^{-4z(p)p^{2i}})^{m-1} \\ &\equiv m \pmod{p^{2i}}\end{align}

ここで、左辺の分数が補題1によって有理整数であることと補題7を用いたことに注意。また、補題8よりpと素な正整数lが存在して、

\displaystyle \frac{F_{4z(p)p^{2(k+2r)}}}{F_{4z(p)p^{2(k+r)}}} = p^{2r}l

が成り立つ。先ほどの式でm=p^rnl, i=k+rとすると、

\displaystyle p^{2r}l\frac{F_{4z(p)p^{2(k+r)}p^rnl}}{F_{4z(p)p^{2(k+2r)}}} = \frac{F_{4z(p)p^{2(k+r)}p^rnl}}{F_{4z(p)p^{2(k+r)}}} \equiv p^rnl \pmod{p^{k+r}}

となり、lpと互いに素であることから

\displaystyle p^{2r}\frac{F_{4z(p)p^{2(k+r)}p^rnl}}{F_{4z(p)p^{2(k+2r)}}}  \equiv p^rn \pmod{p^{k+r}}

を得る。従って、

\displaystyle \mathrm{ord}_p \left( \frac{F_{4z(p)p^{2(k+r)}p^rnl}}{F_{4z(p)p^{2(k+2r)}}}-p^{-r}n \right) \geq k-r

が示された。k, r, nは任意だったので、任意のp^{-r}nという形の有理数にはいくらでも近いところにQ(\mathcal{F})の元がいることがわかった(ただし、今までの議論ではn \neq 0)。 0のいくらでも近いところにもQ(\mathcal{F})の元がいることは補題4、5よりわかる。よって、補題6より証明が完了する。 Q.E.D.

*1:S. R. Garcia, F. Luca, Quotients of Fibonacci numbers, Amer. Math. Monthly, Vol. 123, Mp. 10, (2016), pp. 1039-1044.

*2:L_nはLucas数: integers.hatenablog.com

*3:\displaystyle \frac{k}{j}\binom{k-j-1}{j-1}=\binom{k-j}{j}+\binom{k-j-1}{j-1}は整数。

*4:n < kなら\displaystyle \binom{n}{k}=0とする。