2017-02-25

フィボナッチ数とp進数

定理解説

$F_n$ を $n$ 番目の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$ で稠密である。

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

準備

補題１ $m \mid n \Longrightarrow F_m \mid F_n$ .

証明. これは30：Lucas数列と原始的約数 - INTEGERSに書いてある一般的な命題をFibonacci数に適用したもの。 Q.E.D.

補題２ $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.

補題２と $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$ が偶数であるための必要十分条件は $n$ が $3$ の倍数であることだったので、 $z(2)=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.

補題４ $p$ を奇素数とする。このとき、任意の正の整数 $k, i$ に対して

$\mathrm{ord}_p(F_{kz(p)p^i}) = \mathrm{ord}_p(F_{kz(p)})+i$

が成り立つ。

証明. 補題３において $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.

補題５ 任意の正の整数 $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$ を仮定する。

144：フィボナッチ平方数 - INTEGERSの補題１とリュカ数の記事で紹介した $L_{2n}=L_n^2+(-1)^{n-1}\cdot 2$ より、

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

が成り立つ。また、 $F_3=2$ なので、補題１より $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$ の記事の補題１より $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.

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

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

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

と書けているとする( $a_j$ は $0$ から $p-1$ の整数)。 $N$ を $N\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.

補題７ 任意の素数 $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$ が奇素数のときは補題４より、 $p=2$ の場合は補題５より $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.

補題８ 任意の素数 $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$ が奇素数の場合は補題４、 $p=2$ の場合は補題５より従う。 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}$

ここで、左辺の分数が補題１によって有理整数であることと補題７を用いたことに注意。また、補題８より $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}}$

となり、 $l$ が $p$ と互いに素であることから

$\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})$ の元がいることは補題４、５よりわかる。よって、補題６より証明が完了する。 Q.E.D.