Arithmetica

フィボナッチ数と平方数, 記数法.

Arithmetica 算術ノート

トップ > フィボナッチ数 > Fp が p の倍数であるような素数 p の決定問題 (1) 　部分的解決

Fp が p の倍数であるような素数 p の決定問題 (1) 　部分的解決

フィボナッチ数 合同式

Fibonacci 数列の第 𝒑 項が 𝒑 の倍数になるような素数 𝒑 は 5 のみに限る.

この連続記事では以下を目標として記します.

  • \ {\rm mod}\ p\ や, さらに複雑な剰余の世界において分数や累乗, 平方根などの概念を定義し, Fibonacci 数列の一般項を整数論的に応用する.



前提知識

合同式, ユークリッド (Euclid, エウクレイテス) の互除法, フィボナッチ (Fibonacci) 数列の一般項など



(2) の記事 :

Fp が p の倍数であるような素数 p の決定問題 (2) 完全証明 - Arithmetica 算術ノート







導入

今回の記事および次回の記事で扱う問題は, 「 Fibonacci 数\ F_p\ がインデックス\ p\ の倍数になるのはどのようなときか. 」という至って純粋な問です. 議論の複雑化を防ぐため, 以下\ p\ の範囲は素数の全体に限定して話を進めていきます.


先ずは具体値で実験をして様子を探り, 証明のために必要な性質を集めていきます. 正整数\ n\ に対する Fibonacci 数列\ \{F_n\}\ とは, 次のような数列のことでした（インデックスとの関係が見やすいように表に纏めておきました）.

\begin{align} \begin{array}{c|cccccccccccccc} \ \ n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & \cdots\ \ \\\hline \ \ F_n & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & 89 & 144 & 233 & 377 & \cdots\ \ \end{array} \end{align}

この表を用いて, 以下の事実を確認してみてください.

  • \ p=2\ のとき\ F_2\ は\ 2\ の倍数ではない.
  • \ p=3\ のとき\ F_3\ は\ 3\ の倍数ではない.
  • \ p=5\ のとき\ F_5\ は\ 5\ の倍数である.
  • \ p=7\ のとき\ F_7\ は\ 7\ の倍数ではない.
  • \ p=11\ のとき\ F_{11}\ は\ 11\ の倍数ではない.
  • \ p=13\ のとき\ F_{13}\ は\ 13\ の倍数ではない.

......何か気づきましたか？


実は, \ F_p\ が\ p\ の倍数に成ることは滅多に有りませんが, どのような\ p\neq5\ に対しても, \ F_{p+1}\ と\ F_{p-1}\ の何れか一方が\ p\ の倍数に成っています. ここで, Euclid の互除法によって

\begin{align} (F_{n+1}\ \mbox{と}\ F_n\ \mbox{の最大公約数})&=(F_n+F_{n-1}\ \mbox{と}\ F_n\ \mbox{の最大公約数})\\ &=(F_{n-1}\ \mbox{と}\ F_n\ \mbox{の最大公約数})\\ &=(F_n\ \mbox{と}\ F_{n-1}\ \mbox{の最大公約数})\\ &=\cdots\\ &=(F_2\ \mbox{と}\ F_1\ \mbox{の最大公約数})\\ &=1 \end{align}

であることが判るので, \ p\neq5\ において\ F_{p+1}\ と\ F_{p-1}\ の少なくとも一方が\ p\ で割りきれることが証明されれば, \ F_p\ は\ p\ を約数に持たないことが導かれ, 冒頭の命題が直ちに証明されることに成ります. 由って, 以下では\ p\neq5\ において\ F_{p+1}\ と\ F_{p-1}\ の少なくとも一方が\ p\ で割りきれることの証明について考えます.


この問題の解決に取りかかるに当たり, 必ず Fibonacci 数\ F_n\ とインデックス\ n\ の関係についての考察を経ることに成ります. これら二者の関係を記述するものとして最も直接的なものは, 恐らく, \ F_n\ を\ n\ の式で表現した Fibonacci 数列の一般項でしょう. 然しながら, Fibonacci 数列の漸化式\ F_{n+2}=F_{n+1}+F_n, F_1=F_2=1\ から得られる一般項は \begin{align} F_n=\frac{\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n}{\sqrt{5}} \end{align} という形で, \ p\ の倍数か否かの判定や, \ {\rm mod}\ p\ を取る操作には不向きなもので在ります. 何故ならば, この式は分数や平方根, \ n\ 乗といった (合同式では) 直接的に扱いにくい要素を全面に含んでいるからです. そこで今回は, これらの類似概念を\ {\rm mod}\ p\ 上で定義し, より扱いやすい数列\ \{f_n\}\ （但し\ f_n\equiv F_n\ \ ({\rm mod}\ p)\ ）を\ {\rm mod}\ p\ において構成することで, 議論を進めてゆこうと思います.

通常の\ F_n\ は整数の全体\ \mathbb{Z}\ において定義されていた数列であるのに対し, 今回の証明において構成する\ f_n\ は\ {\rm mod}\ p\ の世界（剰余環の記号で書けば\ \mathbb{Z}/p\mathbb{Z}\ ）において定義される数列であるという点に注意してください.





mod p 上の一般項の構成

先ず, \ {\rm mod}\ p\ 上の数を扱いやすくするために記号を導入します. 即ち, 整数\ n\ を\ {\rm mod}\ p\ で「還元」したものを\ \overline{n}\ で表すことにします. 「還元」という言葉を使いましたが, 詳しく説明すると「\ p\ で割った余りが同じ（\ {\rm mod}\ p\ で合同な）整数は, 全て同一の数と見なす」という考え方のことです. 例えば, \ p=5\ のとき \begin{align} \overline{1}=\overline{6}=\overline{-4} \end{align} が成りたちます. 合同式における加法, 乗法と全く同じ原理で, \ \overline{m}, \overline{n}\ の和や積を考えることができ, これを\ +,\ \times\ を用いて表します. 例えば, \ {\rm mod}\ 5\ において \begin{align} \overline{2}+\overline{4}=\overline{6}&=\overline{1}\\ \overline{2}\times\overline{4}=\overline{8}&=\overline{3} \end{align} といった具合です. \ n\ 個の\ \overline{a}\ の積を\ \overline{a}^n\ と書きあらわすのも同様で, \begin{align} \overline{a\times b}&=\overline{a}\times\overline{b}\\ \overline{a^n}&=\overline{a}^n \end{align} が成立します. 式どうしを等号\ =\ で結んでいますが, 合同式における合同\ \equiv\ と同じ役割です.

それぞれの\ \overline{n}\ のことを（\ n\ を代表元とする）剰余類と言います. 実は剰余類\ \overline{n}\ は集合として定義される*1のですが, その振るまいは\ {\rm mod}\ p\ における普通の整数と大して変わらないので, 今回の記事では一つの数として捉えます. 二項関係として\ \equiv\ ではなく\ =\ を用いるのは, 集合どうしの相等を\ =\ で表すから, ということで理解していただいても障りは有りません.

導入の項において持ちだした, 今回の目標である数列\ f_n\ も, 以降では\ \overline{f_n}\ と表すことにします.



分数

整数の全体\ \mathbb{Z}\ では除法を行うことはできませんでしたが, \ {\rm mod}\ p\ の世界ではどのようになるのでしょうか. \ {\rm mod}\ p\ の一般項を合理的に構成するためには, \ {\rm mod}\ p\ 上での分数は有理数上での分数と同じ役割を果たしていなければ成りません. そこで, 有理数の場合と同じ定義を用いることにします. 詰まり, \ \overline{a}\neq\overline{0}\ に対し, \ \overline{a}\times\overline{x}=\overline{b}\ を充たすような\ \overline{x}\ を\ \overline{b}/\overline{a}\ , あるいは\ \dfrac{\overline{b}}{\overline{a}}\ と書きしるすことにします. 例えば\ {\rm mod}\ 5\ に着目したとき\ \overline{2}\times\overline{4}=\overline{3}\ であったので \begin{align} \overline{4}=\frac{\overline{3}}{\overline{2}},\ \overline{2}=\frac{\overline{3}}{\overline{4}} \end{align} です. この定義における\ \overline{b}/\overline{a}\ が\ \overline{a}\neq\overline{0}\ において恒に存在すること, そして, それが唯一であること*2を証明します.

命題 1.1 \ a,\ b\ を任意の整数とするとき, \ a\not\equiv0\ \ ({\rm mod}\ p)\ ならば, 合同方程式 \begin{align} ax\equiv b\ \ ({\rm mod}\ p) \end{align} は\ 0\le x\lt p\ の範囲に唯だ一つの整数解を持つ.

証明. \ p\ 個の整数 \begin{align} 0a\ (=0),\ 1a\ (=a),\ 2a,\ \ldots,\ (p-1)a \end{align} を考え, これらを\ p\ で割った余りが相異なることを論ずる. これらの内\ sa\ と\ ta\ (0\le s\lt t\lt p)\ が\ {\rm mod}\ p\ において合同であったと仮定すると, その差\ ta-sa=(t-s)a\ は\ p\ で割りきれなければ成らない. 所が, \ 0\lt t-s\lt p\ により\ t-s\ は\ p\ で割りきれず, かつ\ a\ も\ p\ で割りきれないので矛盾が生じる. 由って\ p\ 個の数 \begin{align} 0a\ (=0),\ 1a\ (=a),\ 2a,\ \ldots,\ (p-1)a \end{align} を\ p\ で割った余りは相異なり, \ 0\ から\ p-1\ までの整数が一度ずつ現れる. その中に唯だ一つ存在する\ b\ と合同なものを\ xa\ と置けば\ xa\equiv b\ \ ({\rm mod}\ p)\ が成立する.

\Box

 

系 1.2 \ a,\ b\ を任意の整数とするとき, \ \overline{a}\neq\overline{0}\ ならば, 等式 \begin{align} \overline{a}\times\overline{x}=\overline{b} \end{align} を満たす\ \overline{x}\ が存在し, かつそれは唯一である.

証明. 命題 1.1 より自明.

\Box

 

定義 1.3 系 1.2 における\ \overline{x}\ を\ \overline{b}/\overline{a}\ または\ \dfrac{\overline{b}}{\overline{a}}\ と表す.



累乗

次は累乗について考えましょう. こちらは特に新しい定義が必要という訳でもなく, もともと合同式において定義されてありましたので, 必要な性質を集めてゆくことが目的に成ります. \ F_n\ の一般項では\ (1+\sqrt{5})/2\ であった部分が, \ \overline{f_n}\ の一般項では何らかの\ \overline{a}\ に置きかわることに成るので, \ F_{p-1}\ や\ F_{p+1}\ を計算する際には, \ \overline{a}^{p-1}\ または\ \overline{a}^{p+1}\ という形の累乗を処理する必要が有りそうです. そこで, \ p=5\ や\ p=7,\ p=11\ を法にとって具体的に\ \overline{a}^{p\pm1}\ を計算してみます.

  • \ {\rm mod}\ 5\ に着目したとき \begin{align} \begin{array}{c|ccccc} \ \ \overline{a} & \overline{0} & \overline{1} & \overline{2} & \overline{3} & \overline{4}\ \ \\\hline \ \ \overline{a}^{p-1} & \overline{0} & \overline{1} & \overline{1} & \overline{1} & \overline{1}\ \ \\\ \ \overline{a}^{p+1} & \overline{0} & \overline{1} & \overline{4} & \overline{4} & \overline{1}\ \ \end{array} \end{align}
  • \ {\rm mod}\ 7\ に着目したとき \begin{align} \begin{array}{c|ccccccc} \ \ \overline{a} & \overline{0} & \overline{1} & \overline{2} & \overline{3} & \overline{4} & \overline{5} & \overline{6}\ \ \\\hline \ \ \overline{a}^{p-1} & \overline{0} & \overline{1} & \overline{1} & \overline{1} & \overline{1} & \overline{1} & \overline{1}\ \ \\\ \ \overline{a}^{p+1} & \overline{0} & \overline{1} & \overline{4} & \overline{2} & \overline{2} & \overline{4} & \overline{1}\ \ \end{array} \end{align}

もう何と無く幾つかの法則性が見えてきましたが, 一応\ p=11\ も確認しておきます.

  • \ {\rm mod}\ 11\ に着目したとき
    \begin{align} \begin{array}{c|ccccccccccc} \ \ \overline{a} & \overline{0} & \overline{1} & \overline{2} & \overline{3} & \overline{4} & \overline{5} & \overline{6} & \overline{7} & \overline{8} & \overline{9} & \overline{10}\ \ \\\hline \ \ \overline{a}^{p-1} & \overline{0} & \overline{1} & \overline{1} & \overline{1} & \overline{1} & \overline{1} & \overline{1} & \overline{1} & \overline{1} & \overline{1} & \overline{1}\ \ \\\ \ \overline{a}^{p+1} & \overline{0} & \overline{1} & \overline{4} & \overline{9} & \overline{5} & \overline{3} & \overline{3} & \overline{5} & \overline{9} & \overline{4} & \overline{1}\ \ \end{array} \end{align}


以上の結果から, 素数\ p\ と互いに素な整数\ a\ , 詰まり\ \overline{a}\neq\overline{0}\ なる\ \overline{a}\ について \begin{align} \overline{a}^{p-1}=\overline{1} \end{align} が予想されます. \ \overline{a}^{p+1}\ の方には, これと言って著しい性質は無いように思えるかも知れませんが, \ \overline{a}^{p+1}=\overline{a}^{p-1}\times\overline{a}^2=\overline{a}^2\ なので簡約することができた, ということにしておきます.

少々ねたばらしをすると, 結局\ \overline{a}^{p+1}\ の方は今回の証明の計算式に出てくることは有りません.
定理 1.4（Fermat の小定理） 任意の\ \overline{a}\neq\overline{0}\ に対し, \ \overline{a}^{p-1}=\overline{1}.\

証明. 命題 1.1 の証明中の議論から, \ p-1\ 個の数 \begin{align} 1a\ (=a),\ 2a,\ \ldots,\ (p-1)a \end{align} を\ p\ で割った余りは相異なり, \ 1\ から\ p-1\ までの整数が一度ずつ現れる. それら全ての積を考えると \begin{align} a\times2a\times\cdots\times(p-1)a\equiv 1\times2\times\cdots\times(p-1)\ \ ({\rm mod}\ p). \end{align} ここで, \ (p-1)!\not\equiv0\ \ ({\rm mod}\ p)\ であるから\ (p-1)!\ の逆元が存在する. それを乗じて \begin{align} a^{p-1}\equiv1\ \ ({\rm mod}\ p). \end{align} 詰まり\ \overline{a}^{p-1}=\overline{1}\ が得られる.

\Box

 

先ほどの表において, \ \overline{a}^{p+1}\ の段は\ \overline{0}\ を除いて左右対称に成っていたのですが, \ \overline{a}^{p+1}=\overline{a}^2\ に注意すると
\begin{align} \overline{(p-a)}^2=\overline{(-a)}^2=\overline{a}^2 \end{align}
なので当たり前です.



平方根

最後に平方根\ \sqrt{5}\ についてです. 分数のときと同様, 一般項の構成において通常の\ \sqrt{5}\ と同様な役割を持たせる必要があるので, 通常の\ \sqrt{5}\ の定義をそのまま輸入してくるのが無難です.

定義 1.5 法\ p\neq5\ において, \ \overline{x}^2=\overline{5}\ なる\ \overline{x}\ が存在するとき, その内の一つを選んで\ \overline{\sqrt{5}}\ と定義する.

「その内の一つ」と書いたのは, \ \overline{a}\ が\ \overline{a}^2=\overline{5}\ を充たすならば, \begin{align} (\overline{p}-\overline{a})^2=\overline{(-a)}^2=\overline{a}^2=\overline{5} \end{align} により\ \overline{p}-\overline{a}\ も二乗して\ 5\ に成るからです. 有理数の世界で言う所の, 方程式\ x^2=5\ の解が\ x=\sqrt{5},\ -\sqrt{5}\ の二つであることと似ていますね. 今回はこれらを区別する理由が無いので, 何れか片方を\ \sqrt{5}\ と書くことにしています.


わざわざ「\ \overline{x}\ が存在するならば」といって注釈を加えましたが, これは, 存在しないケイスが存在するからです. 分数のときは（\ \overline{a}\neq\overline{0}\ ならば）\ \overline{a}\times\overline{x}=\overline{b}\ なる\ \overline{x}\ が必ず存在することが言えたのですが, 平方根については, \ p\ の値によって\ \overline{x}^2=\overline{5}\ の解が存在しないということも起こりえます. 例えば\ p=7\ のとき, \begin{align} \overline{0}^2=\overline{0},\ &\overline{1}^2=\overline{1},\ \overline{2}^2=\overline{4},\ \overline{3}^2=\overline{2},\ \\ &\overline{4}^2=\overline{2},\ \overline{5}^2=\overline{4},\ \overline{6}^2=\overline{1} \end{align} なので, どのような\ \overline{x}\ を取っても\ \overline{x}^2\neq\overline{5}\ と成ります. 何らか代数的な方法によってこの問題を解消することもできるのですが, 今回は諦めることにしましょう. \ \overline{x}^2=\overline{5}\ の解が存在しない場合の証明については, 次回の記事で扱います.





部分的解決

以上で定義したものを用いて, \ {\rm mod}\ p\ 上での Fibonacci 数列の一般項を構成します.

命題 1.6 法\ p\neq5\ における方程式\ \overline{x}^2=\overline{5}\ が解を持つとき,
\begin{align} \overline{f_n}=\frac{\overline{\alpha}^n-\overline{\beta}^n}{\overline{\sqrt{5}}}\quad\left(\overline{\alpha}=\frac{\overline{1}+\overline{\sqrt{5}}}{\overline{2}},\ \overline{\beta}=\frac{\overline{1}-\overline{\sqrt{5}}}{\overline{2}}\right) \end{align}
によって定められる\ \overline{f_n}\ は, 任意の\ n\ について\ \overline{f_n}=\overline{F_n}\ を充たす.

詰まる所, この数列\ \{\overline{f_n}\}\ は

  • \ {\rm mod}\ p\ の世界では\ F_n\ を\ p\ で割った余りと全く同じ値を取る.
  • \ {\rm mod}\ p\ の世界の数のみで構成されており, 合同式の計算ができる.

という都合の良い性質を兼ね備えているということです.


証明の要訣は, \ \{\overline{f_n}\}\ が\ {\rm mod}\ p\ 上で\ F_n\ と同じ漸化式を充たしていることを確認することです.

証明. \ \overline{\sqrt{5}}\ の定義から, \ \overline{\alpha},\ \overline{\beta}\ は方程式 \begin{align} (\overline{2}\times\overline{x}-\overline{1})^2=\overline{5}\qquad\overline{x}^2=\overline{x}+\overline{1} \end{align} を充たす解\ \overline{x}\ である. このとき\ \overline{\alpha}^2=\overline{\alpha}+\overline{1}\ および\ \overline{\beta}^2=\overline{\beta}+\overline{1}\ の両辺にそれぞれ\ \overline{\alpha}^{n},\ \overline{\beta}^{n}\ を乗じると \begin{align} \overline{\alpha}^{n+2}&=\overline{\alpha}^{n+1}+\overline{\alpha}^n\\ \overline{\beta}^{n+2}&=\overline{\beta}^{n+1}+\overline{\beta}^n \end{align} と成る. 第一式から第二式を辺々引き, その両辺を\ \overline{\sqrt{5}}\neq\overline{0}\ で割ると \begin{align} \frac{{\overline{\alpha}}^{n+2}-{\overline{\beta}}^{n+2}}{\overline{\sqrt{5}}}=\frac{{\overline{\alpha}}^{n+1}-{\overline{\beta}}^{n+1}}{\overline{\sqrt{5}}}+\frac{{\overline{\alpha}}^n-{\overline{\beta}}^n}{\overline{\sqrt{5}}} \end{align} 詰まり\ \overline{f_{n+2}}=\overline{f_{n+1}}+\overline{f_n}\ が成りたつ. 更に, 計算により \begin{align} \overline{f_1}=\frac{\overline{\alpha}-\overline{\beta}}{\overline{\sqrt{5}}}=\frac{\overline{\sqrt{5}}}{\overline{\sqrt{5}}}=\overline{1}\\ \overline{f_2}=\frac{{\overline{\alpha}}^2-{\overline{\beta}}^2}{\overline{\sqrt{5}}}=\frac{\overline{\sqrt{5}}}{\overline{\sqrt{5}}}=\overline{1} \end{align} が確かめられるので, \ \overline{f_n}\ は\ F_n\ を\ {\rm mod}\ p\ で還元したものである.

\Box

 

定理 1.7 法\ p\neq5\ における方程式\ \overline{x}^2=\overline{5}\ が解を持つとき, \ F_{p-1}\ は\ p\ の倍数である.

証明. 命題 1.6 の数列\ \{\overline{f_n}\}\ を用いて計算すると, \ {\rm mod}\ p\ において \begin{align} \overline{F_{p-1}}&=\overline{f_{p-1}}=\frac{\overline{\alpha}^{p-1}-\overline{\beta}^{p-1}}{\overline{\sqrt{5}}}\\ &=\frac{\overline{1}-\overline{1}}{\overline{\sqrt{5}}}=\overline{0} \end{align} と成る. 但し, 二行目の初めの等号で Fermat の小定理（定理 1.4 ）を用いた.

\Box


次回の記事では, 法\ p\neq5\ における方程式\ \overline{x}^2=\overline{5}\ が解を持たない場合の証明を紹介しようと思います.





*1:具体的には, \ \overline{a}=\{x\in\mathbb{Z}\mid x\equiv a\ \ ({\rm mod}\ p)\}\ と定義されます.

*2:\ \overline{x}=\overline{b}/\overline{a}\ ならば\ \overline{x+p}=\overline{b}/\overline{a}\ や\ \overline{x-2p}=\overline{b}/\overline{a}\ も成りたちますので, \ \overline{a}\times\overline{x}=\overline{b}\ なる\ x\ は整数としては無数に存在しますが, \ \overline{x}\ としては（全て同一のものなので）唯一と言えます.

[tex: ]


ALIA VERITAS AD ALIAM SEMPER VIAM STERNIT
ひとつの真理の考究は, かならずまたひとつの真理への道を拓く


フィボナッチ数とは, 黄金比の冪を √5 を用いて表示したときに, 無理数部に現れる分数の二倍である.

\begin{align} (F_n)_{n\geqslant0}=\;&0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ 89,\ 144,\ 233,\ 377,\ 610,\ 987,\ \\&1597,\ 2584,\ 4181,\ 6765,\ 10946,\ 17711,\ 28657,\ 46368,\ 75025,\ \ldots. \end{align}



平方数とは, 或る整数の平方に等しい数である.

\begin{align} (n^2)_{n\geqslant0}=\;&0,\ 1,\ 4,\ 9,\ 16,\ 25,\ 49,\ 64,\ 81,\ 100,\ 121,\ 144,\ 169,\ 196,\ 225,\ 256,\ \\&289,\ 324,\ 361,\ 400,\ 441,\ 484,\ 529,\ 576,\ 625,\ \ldots. \end{align}



pic-Arithmetica

算 術 ノ ー ト

Arithmētica はラテン語の第一変化名詞で, 算術や初等的な整数論を意味します. 当ブログでは, 算術と整数論, 特にフィボナッチ数や平方数に関する事柄, 面白いと感じた問題, そして数論における定理について, 気ままに記事を投稿します. 記事の内容に関する誤植や新しい発見などが有りましたら, 私の Twitter アカウント (@Numerus_A) までご報告頂けますと幸いに思います.

読者になる