この連続記事では以下を目標として記します.
(1) の記事 :
Fp が p の倍数であるような素数 p の決定問題 (1) 部分的解決 - Arithmetica 算術ノート
振りかえり
前回の記事において「が素数の倍数に成るのはどのようなときか. 」という問を立てるところから始めて, 「任意のに対しとの内少なくとも一方はで割り切れるであろう. 」と予想し, 方程式がにおいて解を持つようなについてのみ証明を与えました. なるが存在しない場合の証明は諦めていましたが, 今回では, 別の剰余の世界に目を向けることによって, の解が存在しない場合の証明をしようと思います. そのため, 以降では, と書けば
方程式がにおいて解を持たないような素数
を表すものとします.
では, 前回の議論の中で, 最も解決を阻んでいたと考えられる要因は何なのでしょう. それは, 紛れもなくの平方根の扱いに在ります. 確かに, 一般項の構成のさいにの代役となる剰余を探すためには, 通常のと全く同様の定義を用いる必要が有りました. 所が, の世界においては, の値によってはとなるが存在しない状況が生じてしまい, 単純な議論のみで解決することができなかったのです.
そこで今回の証明では, 整数の剰余の世界とは一風変わった, 別の剰余の世界において議論を進めていきたいと思います.
問題はの代役として働く概念をどのように定義するかということですが, 先ず, と同様にを充たしている必要があります. 言いかえれば, \begin{align}X^2-(5\ \mbox{に対応する数}\ ) \end{align} は零と同等なものとして認識されなければ成りません. 更に, に何かを掛けた積の値も, 零と同等なものに成っているはずです.
このような都合の良いを有する世界を定義したいのですが, 新しい数の世界を定義して, その上で条件を満たすを見つけようとしても, 前回のように上手く定義できないケース(成りたっていて欲しい条件を充たすものが存在しない状況)が生じえます. そこで, 定義が難しいであろうを先ず置いておき, そのを基盤として新しい世界を考えるという順序に切りかえ, が零の役目を果たすような, と新しい剰余構造とを探します. では, 数の全体集合が定まっていない状態で, をどのように扱えば良いのでしょうか......
整数係数多項式の割り算
そこで, 以下では存在を二乗するとになる「よくわからないもの」として扱います.
今回の解法では, 多項式をある多項式で割った剰余を利用します. 具体的には, 変数(不定元)を取り, それぞれの多項式をで割った余りを扱う, の世界です. 実際, における合同式では, \begin{align} X^2=(X^2-\overline{5})+\overline{5}\equiv\overline{5}\\ \end{align} であるので, 確かに変数をに見たてることができます. 多項式を定義する際は, それが整数係数なのか, 実数係数なのか, 係数の集合を明示しなければなりませんが, 今後「の倍数か否か」を判定するに当たりの倍数は特別な扱いを受けている方が解りやすいので, ここでは「法の剰余」係数の多項式を使います (先ほどから数字に上線を付しているのはそのため). 二次式で割った余りを見ているので, この世界に登場するあらゆる多項式は, 何らかの一次式か定数で表すことができます. 例えば, \begin{align} X^3+X^2+X+\overline{1}&=(X+\overline{1})(X^2-\overline{5})+\overline{6}X+\overline{6}\\&\equiv\overline{6}X+\overline{6}\ \ ({\rm mod}\ ???)\\ X^8=(X^2)^4&\equiv\overline{5}^4\equiv\overline{625}\ \ ({\rm mod}\ ???) \end{align} といった具合です. この多項式の剰余の世界を記号でと書きあらわすことにします. 整数にを使った上で, 変数を添加し, 更にを取ったということです.
具体例を挙げると, のとき \begin{align} &\overline{3}X+\overline{1}\equiv\overline{0}X+\overline{1}\equiv\overline{1}\ \ ({\rm mod}\ 3,X^2-\overline{5})\\&X^2-X-\overline{1}\equiv -X+\overline{4}\equiv\overline{2}X+\overline{1}\ \ ({\rm mod}\ 3,X^2-\overline{5}) \end{align} が成りたちます.
前回と同様, 多項式をで還元したものをと表すことにします. 例えばにおいて上の式を書きかえると \begin{align} \overline{X}^2-\overline{X}-\overline{1}=-\overline{X}+\overline{4}=\overline{2}\times\overline{X}+\overline{1} \end{align} と成ります. においても通常の合同式と同じように, 還元をしても, もとの加法や乗法の計算は保持されることが証明できます.
「体」の拡大
先ほども述べたように, で割った余りの世界では, あらゆる多項式が何らかの一次式か定数かに表されます. 変数の導入によって, 議論の舞台であるところの代数構造 (集合とその上の加法, 乗法の組) は \begin{align} \left\{\overline{aX+b}\mid \overline{a},\overline{b}\mbox{は (前回の) 剰余の世界の元}\right\},\ +,\ \times \end{align} という環境に「拡大」されたということです. 更に, がに等しいことから, (仮に分数が定義されたとすると) 次のような計算ができます. \begin{align} \frac{\overline{1}}{\overline{aX+b}}&=\frac{\overline{aX-b}}{\overline{a^2X^2-b^2}}\\ &=\frac{\overline{aX-b}}{\overline{5a^2-b^2}}\\ &=\frac{\overline{a}}{\overline{5a^2-b^2}}\overline{X}+\frac{\overline{b}}{\overline{5a^2-b^2}} \end{align} ここで, 単なるでの剰余, 今回で言う所の「定数」どうしの割り算は前回の記事で定義していたので, 上式の右辺は左辺と違って計算が可能な剰余です. 由ってにゼロ除算以外の割り算が導入できます. このように加減乗除の計算を行える規則を持った集合は体 (たい, field) と呼ばれ, ある体から, それを含む体を得ることを体の拡大と言います.
ここで, 逆数の定義式の分母に現れている定数が零に成ることを危惧されるかも知れませんが, それは有り得ません. これを確認するために, 若し \begin{align} 5a^2-b^2\equiv0\ \ ({\rm mod}\ p) \end{align} の方程式が解を持つとすれば, と考えてみましょう. の内何れか一方でもと合同であれば他方も零に合同であるので, そのときが零でないという仮定に矛盾します. 故にもも零と合同ではなく, 前回の議論からにおいての「逆数」に相当する役割を持つ整数が存在するので, \begin{align} 5\equiv(ba')^2\ \ ({\rm mod}\ p) \end{align} の式が出来ます. これは, を「方程式がにおいて解を持たないような素数」としていた前提によって, 不成立であることが言えるので, 分母が零であるとした仮定は誤りです. 故に上記の定義はしっかりと「未定義の記号を今在るもので言いかえる」役割を果たしていることが判ります. 少しややこしいですが, これで定義の正当化が完了しました.
一般項の構成
代役
分数および平方根の問題は既に解消しましたので, の代わりをするような剰余の列を構成することができます.
前回と同様にして, このがを還元したものに等しいことが証明できます.
累乗
続いては累乗の処理についてです. を取っていたので, 次のようにを展開することができます.
証明. 二項定理を用いて展開すると \begin{align} (\overline{a}+\overline{b})^p=\sum_{i=0}^p\overline{\binom{p}{i}}\times\overline{a}^i\times\overline{b}^{p-i}\\ \left(\binom{p}{i}=\frac{p!}{i!(p-i)!}\right). \end{align} ここで, のときの分子のは約分されずに残り, はの倍数と成るので, 以外の項は全てに簡約され, 右辺にはのみが留まる.
もう一つ, 次の補題を用意しておきます.
証明. は素数としていたから, 前回の記事にて証明した Fermat の小定理により, 個の定数 \begin{align} \overline{0},\ \overline{1},\ \overline{2},\ \ldots,\ \overline{p-1} \end{align}はの解である.
今考えている代数構造は体であって割り算を行うことができ, 複素数の成す体での多項式 (複素数係数の多項式) と同様, 因数定理が成立する. 故に \begin{align} \overline{t}^p-\overline{t}=\overline{t}(\overline{t}-\overline{1})\cdots(\overline{t}-\overline{p-1}) \end{align} であるから, 方程式の解はこれらの個で尽くされている.
以上の二つを用いれば, 一般項の類似式に現れていた定数でない剰余 \begin{align} \overline{\alpha}=\frac{\overline{1+X}}{\overline{2}},\ \overline{\beta}=\frac{\overline{1-X}}{\overline{2}} \end{align} の累乗を計算することができます. それが次の命題です.
証明. 上記のが二次方程式の解であることを警告する. 補題 2.3 を用いて \begin{align} &\left(\overline{\alpha}^2\right)^p+(-\overline{\alpha})^p+(-\overline{1})^p=(\overline{\alpha}^2-\overline{\alpha}-\overline{1})^p=\overline{0},\\ &\left(\overline{\beta}^2\right)^p+(-\overline{\beta})^p+(-\overline{1})^p=(\overline{\beta}^2-\overline{\beta}-\overline{1})^p=\overline{0} \end{align} あるいは \begin{align} &(\overline\alpha^p)^2-\overline\alpha^p-\overline1=\overline0,\\ &(\overline\beta^p)^2-\overline\beta^p-\overline1=\overline0 \end{align} が成立することが判る*1ので, は全て \begin{align} \overline{x}^2-\overline{x}-\overline{1}=\overline{0} \end{align} の解である. 所が, 二次方程式の解は二個以下あるので, はそれぞれの何れかに等しい. 補題 2.4 から定数でないは乗により変化する. 従って \begin{align} (\overline{\beta}^p,\overline{\alpha}^p)=(\overline{\alpha},\overline{\beta}) \end{align} でなければ成らない.
証明
以上の結果を使ってを計算します.
証明. 上で考える. 補題 2.5 から \begin{align} \overline{\alpha}^{p+1}=\overline{\alpha}\overline{\beta}=\overline{\beta}^{p+1} \end{align} であるので,
由ってはの倍数である.
Legendre の記号を用いるとこれまでの結果は次のように纏められ, Fibonacci 数列の隣りあう二項が互いに素であったことから, 問題は解決されたことに成ります. 但し, Legendre 記号は, のとき零, のとき方程式がを法として解を持つなら, そうでないならを取ると定義されます.
全体を通して見れば, このは黄金比のに由来していたということに成ります. 更に, 平方剰余の相互法則という Legendre と Gauss による定理を適用すると \begin{align} \left(\frac{5}{p}\right)=\left(\frac{p}{5}\right)= \begin{cases} 1&(p\equiv1,4\ \ ({\rm mod}\ 5))\\ -1&(p\equiv2,3\ \ ({\rm mod}\ 5)) \end{cases} \end{align} が成りたつことが判るので,
のときはの倍数である.
のときはの倍数である.
のように書くこともできます.
別解
Euler の規準を使った証明
以下, 幾つかの代数的整数論の知識を仮定します.
本文においては上での代役となる元を探す方法を取りましたが, 二次体の整数環を用いれば, 黄金比をそのまま整数として扱うことができます. と置くと, の元のうち代数的整数であるものの全体(整数環)は \begin{align} \mathcal{O}_K=\left\{\frac{x+y\sqrt{5}}{2}\;\middle|\;x,y\in\mathbb{Z},x\equiv y\ \ ({\rm mod}\ 2)\right\} \end{align} と表すことができます.
上の合同式をに対し \begin{align} \alpha\equiv\beta\ \ ({\rm mod}\ p)\ \Longleftrightarrow\ p\mid\alpha-\beta \end{align} と定義すると, が有理素数のとき二項定理によりが成りたちます. このように定義すれば, Fibonacci 数列の一般項および Fermat の小定理, 平方剰余に関する Euler の規準によって,
のとき
のときも同じようにして
と計算することができます.
演習問題
参考文献
[1] D.D.Wall (1960), "FIBONACCI SERIES MODULO ". American Mathematical Monthly, Vol. 67, No. 6; pp. 525-532.
*1:を法とする場合は前回で証明しましたので, 今回扱っているは奇数であることに注意してください.