フィボナッチ数論から見た平方剰余相互法則

非負の整数 𝒏 にたいし, 線型漸化式によって定義される多項式列, \begin{align} (L_n)=2,\ x,\ x^2+2,\ x^3+3x,\ \ldots\\ A,\ B,\ xB+A,\ \ldots \end{align} に関して, 素数の法 𝒑 の下で, 𝑳𝒑 ≡ 𝒙ᵖ が成りたつ.

この記事は, 以下を目標として記したものです.

リュカ多項式および終結式の性質から, 平方剰余の相互法則を導く方法を紹介する.

前提知識

平方剰余の基礎理論, 代数学の基本定理, 対称式の基本定理

平方剰余相互法則の証明
Euler の規準の証明
文献

平方剰余相互法則の証明

この章では, Matt Baker (マット・ベイカー) 氏のブログ記事「Lucas 多項式を用いた平方剰余相互法則の証明」[文献 1] の内容をご紹介したいと思います. 途中で用いる Fermat の小定理および Euler の規準は, 次の章で証明を書きます.

終結式の性質

複素数を係数とするモニック多項式, \begin{align} f(x)&=x^m+a_{m{-}1}x^{m{-}1}+\cdots+a_0,,\\ g(x)&=x^n+b_{n{-}1}x^{n{-}1}+\cdots+b_0 \end{align} を一次式に分けたときの因数分解を, 次のように表します. \begin{align} f(x)&=\prod_{1\leqslant i\leqslant m}(x-\alpha_i),\\ g(x)&=\prod_{1\leqslant j\leqslant n}(x-\beta_j). \end{align}

定義 1.1 (終結式) 一次以上のモニック多項式 $\ f\$ と $\ g\$ にたいして, その終結式 resultant を \begin{align} \mathrm{res}\,(f,g)=\prod_{\substack{1\leqslant i\leqslant m\\1\leqslant j\leqslant n}}(\alpha_i-\beta_j) \end{align} によって定義する. $\ f\$ または $\ g\$ が〈モニックな定数〉即すなわち $\ 1\$ である場合は, $\ \mathrm{res}\,(f,g)=1\$ と定める.

明白に, これらの性質があります.

$\ \text{(R3)}\$ $\ \mathrm{res}\,(f,g)=\prod_{1\leqslant i\leqslant m}g(\alpha_i).\$

$\ \text{(R4)}\$ $\ \mathrm{res}\,(f,g)=(-1)^{mn}\mathrm{res}\,(g,f).\$

対称式の基本定理によると, 終結式は $\ a_i\$ および $\ b_j\$ の整数係数多項式になります. 例えば, \begin{align} \prod^{\substack{1\leqslant i\leqslant1\\1\leqslant j\leqslant2}}(\alpha_i-\beta_j)=\;&\alpha_1^2-(\beta_1+\beta_2)\alpha_1+\beta_1\beta_2\\=\;&a_0^2-b_1a_0+b_2,\\\prod^{\substack{1\leqslant i\leqslant2\\1\leqslant j\leqslant2}}(\alpha_i-\beta_j)=\;&(\alpha_1^2-(\beta_1+\beta_2)\alpha_1+\beta_1\beta_2)\\&\quad\cdot(\alpha_2^2-(\beta_1+\beta_2)\alpha_2+\beta_1\beta_2)\\=\;&\cdots. \end{align}

具体的に, 終結式を或ある行列の行列式として表示することができますけれども, この場で証明する必要はありません. これを Sylvester 行列 (シルヴェスター行列) といいます.

命題 1.2 (証明不要) $\ x,\$ $(a_i)_{i=1}^{i=m{-}1},\$ $(b_j)_{j=1}^{j=n{-}1}\$ および $\ (\alpha_i)_{i=1}^{i=m},\$ $(\beta_j)_{j=1}^{j=n}\$ を不定元として, 等式 \begin{align} x^m+a_{m{-}1}x^{m{-}1}+\cdots+a_0&=\prod_{1\leqslant i\leqslant m}(x-\alpha_i),\\ x^n+b_{n{-}1}x^{n{-}1}+\cdots+b_0&=\prod_{1\leqslant j\leqslant n}(x-\beta_j). \end{align} を仮定する. そのとき, 次の等式が成りたつ.

\begin{align} \prod_{\substack{1\leqslant i\leqslant m\\1\leqslant j\leqslant n}}(\alpha_i-\beta_j)=\left|\begin{array}{ccccccc} 1&a_{m{-}1}&\cdots&\cdots&a_0&&\\ &\ddots&\ddots&&&\ddots&\\ &&1&a_{m{-}1}&\cdots&\cdots&a_0\\ 1&b_{n{-}1}&\cdots&b_0&&&\\ &\ddots&\ddots&&\ddots&&\\ &&\ddots&\ddots&&\ddots&\\ &&&1&b_{n{-}1}&\cdots&b_0 \end{array}\right|. \end{align}

但ただし空所には $\ 0\$ があるものと考える. 従って右辺は対角成分に $\ 1\$ が $\ n\$ 個, $\ b_0\$ が $\ m\$ 個配列された $\ m+n\$ 次行列である.

解と係数の関係によって, $\ a_i\$ および $\ b_j\$ は $\ \alpha_i,\$ $b_j\$ の多項式に表すことができる. 故に, 行列 \begin{align} A=\left[\begin{array}{ccccccc} 1&a_{m{-}1}&\cdots&\cdots&a_0&&\\ &\ddots&\ddots&&&\ddots&\\ &&1&a_{m{-}1}&\cdots&\cdots&a_0\\ 1&b_{n{-}1}&\cdots&b_0&&&\\ &\ddots&\ddots&&\ddots&&\\ &&\ddots&\ddots&&\ddots&\\ &&&1&b_{n{-}1}&\cdots&b_0 \end{array}\right] \end{align} について $\ |A|\$ は $\ \alpha_i\$ と $\ \beta_j\$ との多項式であり, 各 $\ \alpha_i\$ に関する次数は $\ n\$ 以下, 各 $\ \beta_j\$ に関する次数は $\ m\$ 以下である.
これから, 変数 $\ \alpha_i\$ に $\ \alpha_i=\beta_j\$ を代入した場合に, 必ず $\ |A|=0\$ になることを証明する. 為ために便宜上 $\ \alpha_i=\beta_j=t\$ の表記を用いる. 先まず, 仮定の式によって \begin{align} &t^m+a_{m{-}1}t^{m{-}1}+\cdots+a_0=0,\\ &t^n+b_{n{-}1}t^{n{-}1}+\cdots+b_0=0 \end{align} であるから, 列ベクトル $\ \vec{x}={}^{\top\!}(t^{m{+}n{-}1},\ldots,t,1)\$ について, \begin{align} A\vec{x}=\vec{0} \end{align} が成りたち, この連立方程式は $\ \vec{0},\$ $\vec{x}\$ の二解を有する. 従って, $\ |A|=0\$ でなければならない.
因数定理によって, 多項式 $\ |A|\$ は $\ mn\$ 個の一次式 $\ \alpha_i-\beta_j\$ を因数に有する. 由よって \begin{align} |A|=c\prod_{\substack{1\leqslant i\leqslant m\\1\leqslant j\leqslant n}}(\alpha_i-\beta_j) \end{align} を充たす複素数 $\ c\$ が存在して, $\ \beta_1^m\beta_2^m\cdots \beta_n^m\$ の係数から $\ c=1\$ が明らかになる. $\ \Box\$

ここから, 以下二つの事実が判明します.

命題 1.3 $\ \text{(R1)}\$ 多項式 $\ f\$ および $\ g\$ が整数係数を有するならば, $\ \mathrm{res}\,(f,g)\$ は整数である.

命題 1.4 $\ \text{(R2)}\$ 整数係数のモニック多項式 $\ f(x),\$ $g(x),\$ $h(x)\$ があって, 或る正の整数 $\ d\$ について \begin{align} g(x)\equiv h(x)\ \ (\mathrm{mod}.d) \end{align} を充たすならば, \begin{align} \mathrm{res}\,(f,g)\equiv\mathrm{res}\,(f,h)\ \ (\mathrm{mod}.d) \end{align} が成りたつ.

最後に, 多項式の合同との関係を示します.

命題 1.5 $\ \text{(R5)}\$ 複素数係数のモニック多項式 $\ f(x),\$ $g(x),\$ $r(x)\$ とモニックとは限らない $\ q(x)\$ があって, \begin{align} f(x)=g(x)q(x)\pm r(x) \end{align} を充たすならば, \begin{align} \mathrm{res}\,(g,f)=\pm\mathrm{res}\,(g,r) \end{align} が成りたつ. 上記にあって, 二つの複号 ( $\pm$ ) は合一.

証明. 複号が $\ +\$ である場合, 終結式の定義を代入すれば, \begin{align} \mathrm{res}\,(g,f)&=\prod_{1\leqslant j\leqslant n}f(\beta_j)\\ &=\prod_{1\leqslant j\leqslant n}r(\beta_j)\\ &=\mathrm{res}\,(g,r). \end{align} 故に命題が成りたつ. 複号が $\ -\$ である場合も同様である.

$\Box$

Lucas 多項式の性質

Lucas 多項式の定義は次の通りです.

定義 1.6 整数 $\ n\$ にたいして, 整数係数多項式 $\ L_n=L_n(x)\$ を次の漸化式と初期値によって定義する. \begin{align}\left(\begin{array}{l}L_0=2,\ L_1=x\\\ \\L_{n+2}=xL_{n+1}+L_n.\end{array}\right.\end{align} これを Lucas 多項式という.

$\ x=1\$ を代入すると, 通常の Lucas 数 $\ \ldots\ 2,\ 1,\$ $3,\ 4,\ \ldots\$ が得られます.

\begin{align}\begin{array}{cc}\mbox{表 1.}\ L_n(x)\\\ \\\begin{array}{|r|c|}\hline \vdots\ &\vdots\\ -3&-x^3-3x\\ -2&x^2+2\\ -1&-x\\ 0&2\\ 1&x\\ 2&x^2+2\\ 3&x^3+3x\\ 4&x^4+4x^2+2\\ 5&x^5+5x^3+5x\\ \vdots\ &\vdots \\\hline\end{array}\end{array}\end{align}

幾いくつか簡単な性質を挙げます. 証明の大部分は帰納法によります.

$\ L_{-n}=(-1)^nL_n\$ が成りたつ.
$\ L_n\$ の次数は $\ |n|\$ に等しい.
$\ n\$ が偶数であるならば $\ L_n(x)=L_n(-x)\$ が成りたち, 奇数であるならば $\ L_n(x)=-L_n(-x)\$ が成りたつ. 換言すれば, 偶数 $\ n\$ にたいする $\ L_n(x)$ , および奇数 $\ n\$ にたいする $\ L_n(x)/x\$ は, 必ず $\ x^2\$ の多項式である.
$\ n\gt0\$ の場合, $\ L_n\$ はモニック多項式である.
$\ L_n\$ の末まつ尾び項の係数は, $\ n\$ が偶数であるならば $\ 2\$ に等しく, 奇数であるならば $\ n\$ に等しい. 特に, 奇数 $\ n\$ にたいして \begin{align} L_n(x)/x=H_n(x^2) \end{align} と置けば, $\ n\$ の正負によらず $\ H_n(0)=n\$ が成りたつ.
特性多項式 $\ \lambda^2=x\lambda+1\$ の二つの根を, \begin{align} \alpha&=\frac{x+\sqrt{x^2+4}}{2},\\ \beta&=\frac{x-\sqrt{x^2+4}}{2} \end{align} と置けば, あらゆる整数において \begin{align} L_n=\alpha^n+\beta^n \end{align} が成りたつ.

命題 1.7 あらゆる素数 $\ p\$ について, \begin{align} L_p\equiv x^p\ \ (\mathrm{mod}.p) \end{align} が成りたつ.

証明. 二項定理によって,

\begin{align} L_p&=\frac{1}{2^p}\left[(x+\sqrt{x^2+4})^p+(x-\sqrt{x^2+4})^p\right]\\ &=\frac{1}{2^p}\sum_{0\leqslant i\leqslant p}\binom{p}{i}x^{p-i}\left[(\sqrt{x^2+4})^{i}+(-\sqrt{x^2+4})^{i}\right]\\ &=\frac{1}{2^{p{-}1}}\!\!\sum_{0\leqslant j\leqslant p/2}\!\!\binom{p}{2j}x^{p-2j}(x^2+4)^j. \end{align}

$\ 0\lt n\lt p\$ ならば $\ \binom{p}{n}\$ は $\ p\$ によって割りきれ, また Fermat の小定理によって, $\ 2^{p-1}\equiv1\ \ (\mathrm{mod}.p)\$ が成りたつ. 故に, \begin{align} L_p\equiv x^p\ \ (\mathrm{mod}.p) \end{align} である.

$\Box$

$\ p\$ を奇素数として $\ L\$ を $\ H\$ に書きかえると, \begin{align} H_p\equiv x^{(p-1)/2}\ \ (\mathrm{mod}.p) \end{align} の合同式になり, 右辺に Euler の規準の形が現れます.

命題 1.8 (積和等式) あらゆる整数 $\ m,\$ $n\$ にたいして, \begin{align} L_{m{+}n}+(-1)^nL_{m{-}n}=L_mL_n \end{align} が成りたつ. 特に, $\ m\$ および $\ n\$ が非負であるとき, 多項式 $\ L_{m+n}\$ を $\ L_m\$ によって除した余りは, 符号の相違を除けば, 必ずまた Lucas 多項式になる.

証明. 一般項の表示式によって, \begin{align} L_mL_n&=\alpha^{m+n}+\alpha^{m}\beta^n+\alpha^n\beta^m+\beta^{m+n}. \end{align} また $\ \alpha\beta=-1\$ であるので,

\begin{align} L_{m+n}+(-1)^nL_{m-n}&=L_{m+n}+(\alpha\beta)^nL_{m-n}\\ &=\alpha^{m+n}+\beta^{m+n}+\alpha^m\beta^n+\alpha^n\beta^m. \end{align}

故に両辺は等しい多項式である.

$\Box$

今の恒等式は, 余弦函数 \begin{align} \cos{(x)}=\frac{e^{\sqrt{-1}x}+e^{-\sqrt{-1}x}}{2} \end{align} について成立する積和等式と同じ形をしています. \begin{align} \cos{(x+y)}+\cos{(x-y)}=2\cos{(x)}\cos{(y)}. \end{align}

相互法則の証明

補題 1.9 あらゆる正の奇数 $\ m,\ n\$ にたいして, $\ m\neq n\$ であり, かつ $\ m\$ と $\ n\$ とが互いに素であるならば, $\ \mathrm{res}\,(H_m,H_n)\$ は $\ \pm1\$ に等しい.

証明. $\ m\lt n\$ の場合のみを証明しても同じである. $\ n\$ に関する帰納法を適用する.

$\ n=3\$ ならば, $\ m=1\$ であり, $\ H_m(x)\$ が定数になるから明白. 次に, \begin{align} L_n\pm L_{|n-2m|}=L_{n-m}L_m \end{align} 即ち \begin{align} H_n\pm H_{|n-2m|}=L_{n-m}(\sqrt{x})H_m \end{align} の等式によれば, \begin{align} \mathrm{res}\,(H_m,H_n)=\pm\mathrm{res}\,(H_m,H_{|n-2m|}) \end{align} が成りたつ. 上式の $\ n-2m\$ は奇数であり, かつ $\ m\$ と互いに素である. 然しかも \begin{align} |n-2m|=\begin{cases}n-2m\lt n\\2m-n\lt2n-n=n\end{cases} \end{align} の大小関係が成立するので, 帰納法の仮定によって, $\ \mathrm{res}\,(H_m,H_n)=\pm1\$ である.

$\Box$

補題 1.10 あらゆる奇素数 $\ p,\ q\$ にたいして, $\ p\neq q\$ であるならば, $\ \mathrm{res}\,(H_p,H_q)=\left(\!\frac{\,q\,}{\,p\,}\!\right)\$ が成りたつ.

証明. 法 $\ \mathrm{mod}.p\$ に従って, \begin{align} \mathrm{res}\,(H_p,H_q)&\equiv\mathrm{res}\,(x^{(p-1)/2},H_q)\\ &\equiv H_q(0)^{(p-1)/2}\\ &\equiv q^{(p-1)/2}\equiv\left(\!\frac{\,q\,}{\,p\,}\!\right). \end{align} 但だし最後に Euler の規準を用いた. $\ \mathrm{res}\,(H_p,H_q)\$ は $\ \{\pm1\}\$ に属するから, $\ \mathrm{res}\,(H_p,H_q)=\left(\!\frac{\,q\,}{\,p\,}\!\right)\$ である.

$\Box$

定理 1.11 (平方剰余の相互法則) あらゆる奇素数 $\ p,\ q\$ にたいして, \begin{align} \left(\!\frac{\,p\,}{\,q\,}\!\right)=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}\left(\!\frac{\,q\,}{\,p\,}\!\right) \end{align} が成りたつ.

証明. $\ p=q\$ の場合は明らかである. そうでないとき, 補題 1.10 を用いて, \begin{align} \left(\!\frac{\,p\,}{\,q\,}\!\right)&=\mathrm{res}\,(H_q,H_p)\\ &=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}\mathrm{res}\,(H_p,H_q)\\ &=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}\left(\!\frac{\,q\,}{\,p\,}\!\right). \end{align} 即ち定理が証明されたのである.

$\Box$

また, 第一補充則 \begin{align} \left(\!\frac{-1}{p}\!\right)=(-1)^{\frac{p-1}{2}} \end{align} を Euler の規準から導出することができるのは, 周知されている通りです. 第二補充則 \begin{align} \left(\!\frac{\,2\,}{\,p\,}\!\right)=(-1)^{\frac{p^2-1}{8}} \end{align} の新しい証明法は思いつかないので, 今回は保留としておきます.

Euler の規準の証明

$\ (F_n)_{n\in\mathbb{Z}}\$ を $\ F_0=0\$ および $\ F_1=1\$ を初期値に持つ Fibonacci 数列としますと, 後述の命題により, あらゆる素数 $\ p\$ について \begin{align} F_{p-\left(\!\frac{\,5\,}{\,p\,}\!\right)}\equiv0\ \ (\mathrm{mod}.p) \end{align} という合同式が成りたちます. 上に書いた $\ \left(\!\frac{\,5\,}{\,p\,}\!\right)\$ は, 法 $\ p\$ の下で $\ 5\$ が平方剰余であるか否かを表現する Legendre 記号です. こちらの定理は, 有名な Fermat の小定理, 詰まり $\ a\$ を $\ p\$ の倍数でない整数とした場合に \begin{align} a^{p-1}-1\equiv0\ \ (\mathrm{mod}.p) \end{align} が成立することの類似として捉えられます.

Fibonacci 数列を一般化するために, $\ P\$ および $\ Q\neq0\$ を任意の整数としまして, 漸化式 \begin{align} U_0=0,\ U_1=1,\ U_{n+2}=PU_{n+1}-QU_n \end{align} により整数列 $\ (U_n)_{n\geqslant0}\$ を定義します. これに対応する特性多項式 \begin{align} X^2-PX+Q \end{align} にたいする二つの根を, \begin{align} \alpha=\frac{P+\sqrt{\Delta}}{2},\quad\beta=\frac{P-\sqrt{\Delta}}{2},\\\Delta=P^2-4Q\neq0 \end{align} と置けば, 一般項を \begin{align} U_n=\frac{\alpha^n-\beta^n}{\alpha-\beta} \end{align} の形に表示することができます. ここで若もし比 $\ \alpha/\beta\$ が $\ 1\$ の冪べき根になれば, 列 $\ (U_n)\$ は $\ U_0\$ 意外にも $\ 0\$ を含むので, 普通 $\ \alpha/\beta\$ は $\ 1\$ の冪根でないことを要請しますが, ここでは要請が破れても構わないものとします. この $\ (U_n)\$ は第二種 Lucas 数列と呼ばれる Fibonacci 数列の一般化であります. これから, 奇素数 $\ p\$ について成りたつ二つの事実を証明して, そこから Euler の規準を導出する過程をお見せしたいと思います.

(事実 1) 平方剰余の記号について, $\ \mathrm{mod}.p\$ の下で $\ U_{p-\left(\!\frac{\,\Delta\,}{\,p\,}\!\right)}\equiv0\$ である.
(事実 2) $\ \mathrm{mod}.p\$ の冪剰余について, $\ \Delta^{\frac{p-1}{2}}\equiv1\$ ならば $\ U_{p-1}\equiv0\$ であり, $\ \Delta^{\frac{p-1}{2}}\equiv-1\$ ならば $\ U_{p+1}\equiv0\$ である.

判別式 $\ \Delta=P^2-4Q\$ は, $\ 0\$ を除いたあらゆる $\ 4\$ の倍数を取り得うるので, 後述しますように, ここから $\ a^{\frac{p-1}{2}}\equiv\left(\!\frac{\,a\,}{\,p\,}\!\right)\$ の証明が得られます.

平方剰余記号に関する事実

ここでは組みあわせ論を使って, 前記の事実 1 を示したいと思います. 以後, $\ p\$ を法とするときの剰余の全体を, \begin{align} \mathbb{F}_p=\{0,1,2,\ldots,p-1\} \end{align} と表記します. 本来 $\ \mathbb{F}_p\$ は整数の部分集合ではありませんが, 今だけ整数の集まりと解釈して頂いても問題は生じません.

定義 2.1 $\ a,\ b\in\mathbb{F}_p\$ にたいして, 数列 $\ (w_n)=(w_n^{(a,b)})_{n\geqslant0}\$ を \begin{align} w_0=a,\ w_1=b,\ w_{n+2}=Pw_{n+1}-Qw_n \end{align} によって定義する.

明らかに, 法 $\ p\$ の下で $\ (w_n\ \mathrm{mod}.p)\$ は周期数列になります. そこで, 次の条件を充たす正の整数 $\ t\$ の中で, 最も小さいものを $\ t(a,b)\$ と書くことにします.
　条件. 或る $\ 0\$ でない $\ s\in\mathbb{F}_p\$ が存在して, 法 $\ p\$ の下で $\ w_t\equiv sw_0\$ かつ $\ w_{t+1}\equiv sw_1\$ が成りたつ.
$\ s,\$ $t\$ がそのような条件を充たすなら, 当然あらゆる整数 $\ n\geqslant0\$ において $\ w_{n+t}\equiv sw_n\ \ (\mathrm{mod}.p)\$ になります.

命題 2.2 $\ b^2-Pab+Qa^2\not\equiv0\ \ (\mathrm{mod}.p)\$ であるならば, $\ t(a,b)=t(0,1)\$ が成りたつ.

証明. 帰納法によって, $\ w_n=w_n^{(a,b)}\$ と $\ U_n=w_n^{(0,1)}\$ との間に成りたつ次の等式を確認することができる ( $U_2=P\$ と $\ w_2=Pb-Qa\$ とに要注意). \begin{align} \left(\begin{array}{l}w_n={a}U_{n+1}+(b-aP)U_n\\\ \\(b^2-Pab+Qa^2)U_n=-aw_{n+1}+bw_n\end{array}\right.. \end{align} 従って, $\ p\$ が $\ b^2-Pab+Qb^2\$ と互いに素であるとき, $\ t(a,b)\geqslant t(0,1)\$ かつ $\ t(a,b)\leqslant t(0,1)\$ であり, $\ t(a,b)=t(0,1)\$ が成りたつ.

$\Box$

定理 2.3 $\ p\$ は $\ Q\$ および $\ \Delta\$ を割りきらない奇素数であるとする. 法 $\ p\$ に従って, $\ U_{p-\left(\!\frac{\,\Delta\,}{\,p\,}\!\right)}\equiv0\$ が成りたつ.

実際は $\ p\$ が $\ \Delta\$ の素因子である場合にも正しい式になりますが, 証明は致しません.

証明. $\ \mathbb{F}_p\$ の要素二個から成る対つい $\ (a,b)\$ を集めた集合として, \begin{align} \mathcal{L}_p=\{(a,b)\mid b^2-Pab+Qa^2\not\equiv0\ \ (\mathrm{mod}.p)\} \end{align} を定義する. $\ \left(\!\frac{\,\Delta\,}{\,p\,}\!\right)=-1\$ であるとき, $\ \mathcal{L}_p\$ は $\ (0,0)\$ を除いた $\ p^2-1\$ 個の剰余対から成りたつ集合である. $\ \left(\!\frac{\,\Delta\,}{\,p\,}\!\right)=1\$ であるとき, 二次合同式 \begin{align} E:\ x^2-Px+Q\equiv0\ \ (\mathrm{mod}.p)\end{align} が二つの異なる解を有するので, その二解を $\ r_k\in\mathbb{F}_p\$ $(k=1,2)\$ と置く. その場合, $\ Q\$ に関する前提のために $\ r_k\not\equiv0\ \ (\mathrm{mod}.p)\$ である.

集合 $\ \mathcal{L}_p\$ に関して, 次の事実を示す.

　事実. $\ (a,b)\not\in\mathcal{L}_p\$ であることは, 或る $\ E\$ の解 $\ r_k\$ が存在して, $\ (w_n^{(a,b)}\ \mathrm{mod}.p)\$ が公比 $\ r_k\$ の幾何数列になることと同値である.
　論拠. 自明な場合を始めに除外して, $\ a\not\equiv0\$ かつ $\ b\not\equiv0\$ とする. 第一に $\ (a,b)\not\in \mathcal{L}_p\$ の場合, 集合 $\ \mathcal{L}_p\$ の定義から, $\ b/a\equiv r_k\$ であることを要する. 幾何数列 $\ (r_k^n\ \mathrm{mod}.p)\$ は $\ (w_n\ \mathrm{mod}.p)\$ と同じ漸化式, 即ち \begin{align} r_k^{n+2}-Pr_k^{n+1}+{Q}r_k^n\equiv0\ \ (\mathrm{mod}.p)\end{align} を充たすので, 帰納的に $\ (w_n)\equiv(ar_k^n)\ \ (\mathrm{mod}.p)\$ が成りたつ. 第二に, $\ (w_n\ \mathrm{mod}.p)\$ が公比 $\ r_k\$ の幾何数列である場合, $\ (w_n)\$ の漸化式によって $\ a^2r_1^2-Pa^2r_1+a^2Q\equiv0\$ であるから, $\ (a,ar_1)\not\in\mathcal{L}_p\$ を得る. (論拠終)

次に, $\ \mathcal{L}_p\$ 上の関係 (同値関係) $\ \sim\$ を, 次の通りに規定する.

　定義. $\ \mathcal{L}_p\$ に属する $\ (a,b)\$ および $\ (a',b')\$ について, 或る $\ 0\$ でない $\ s\in\mathbb{F}_p\$ と整数 $\ t\geqslant0\$ とが存在して, $\ \mathrm{mod}.p\$ において \begin{align} w_0^{(a,b)}\equiv sw_t^{(a',b')},\ w_1^{(a,b)}\equiv sw_{t+1}^{(a',b')} \end{align} が成りたつとき, $\ (a,b)\sim(a',b')\$ と記す.

加えて, $\ \mathcal{L}_p\$ の中で, 或る要素 $\ (a,b)\$ と $\ \sim\$ の関係にある全部の要素を一つの類るいに纏まとめて, これを \begin{align} [a,b]=\{(x,y)\in \mathcal{L}_p\mid(x,y)\sim(a,b)\} \end{align} とし, そのときに生ずる類の総数を, $\ k\$ によって表す. かくして, $\ \mathcal{L}_p\$ の要素は $\ k\$ 種の類に分別される.

$\ (a,b)\in \mathcal{L}_p\$ にたいして, 次の等式を証明する.

\begin{align} [a,b]=\left\{(sw_n^{(a,b)}\ \mathrm{mod}.p,\ sw_{n+1}^{(a,b)}\ \mathrm{mod}.p)\;\middle|\;\!\begin{array}{c}s\in\mathbb{F}_p,\ s\neq0,\\0\leqslant n\lt t(0,1)\end{array}\!\right\}. \end{align}

$\ [a,b]\$ の要素が右辺の形に表されることは, 定義から自明である. 反対に, 右辺の集合の要素が $\ [a,b]\$ に属することを示すためには, それが $\ \mathcal{L}_p\$ に属することを示すべきである. 若し或る $\ (sw_n^{(a,b)}\ \mathrm{mod}.p,\$ $sw_{n+1}^{(a,b)}\ \mathrm{mod}.p)\$ が $\ \mathcal{L}_p\$ に属しない対であるとすれば, 前述の事実によって, 非負の整数 $\ l\$ に関して $\ w_{n+l+1}\equiv r_kw_{n+l}\$ であるが, これは $\ b\equiv r_ka\$ を導くので, $\ (a,b)\in \mathcal{L}_p\$ に矛盾むじゅんする. 従って, 上記の相等が成りたつ.

然しからば, 各類の要素数は $\ (p-1)t(0,1)\$ で一定であり, $\ \mathcal{L}_p\$ の要素数 $\ \# \mathcal{L}_p\$ に関して \begin{align} \# \mathcal{L}_p=(p-1)t(0,1)k. \end{align} 第一に $\ \left(\!\frac{\,\Delta\,}{\,p\,}\!\right)=1\$ である場合は, $\ \mathcal{L}_p\$ に属しない剰余対の総数は $\ 2(p-1)+1=2p-1\$ であるから, 要素数は $\ \# \mathcal{L}_p=(p-1)^2\$ と表され, $\ p-1=t(0,1)k\$ が得られる. 故に, $\ U_{p-1}\equiv0\ \ (\mathrm{mod}.p)\$ である.

第二に $\ \left(\!\frac{\,\Delta\,}{\,p\,}\!\right)=-1\$ である場合は, $\ \# \mathcal{L}_p=p^2-1\$ であり, これと $\ p+1=t(0,1)k\$ とを合わせて, $\ U_{p+1}\equiv0\ \ (\mathrm{mod}.p)\$ が得られる. 即ち, 何れの場合も, 定理が示されたのである.

$\Box$

比率 $\ \left(p-\left(\!\frac{\,\Delta\,}{\,p\,}\!\right)\right)/t(0,1)\$ の組みあわせ論的な意味が明らかになる点は, この証明法のおもしろい特徴であると思います.

系 2.4 (Fermat の小定理) $\ p\$ の倍数でない整数 $\ a\$ にたいして, $\ a^{p-1}\equiv1\ \ (\mathrm{mod}.p)\$ が成りたつ.

証明. $\ (P,Q)=(a+1,a),\$ $\Delta=(a-1)^2\$ について定理 2.3 を適用すれば, \begin{align} \frac{a^{p-1}-1^{p-1}}{a-1}\equiv0\ \ (\mathrm{mod}.p). \end{align} ここから Feramt の小定理が得られる.

$\Box$

冪剰余に関する事実

これから一般項の式を整数範囲で応用するので, 二項展開を施して $\ \sqrt{\Delta}\$ を消すための計算をします.

\begin{align} U_n&=\frac{1}{2^n\sqrt{\Delta}}\left[(P+\sqrt{\Delta})^n-(P-\sqrt{\Delta})^n\right]\\ &=\frac{1}{2^n\sqrt{\Delta}}\sum_{0\leqslant i\leqslant n}\binom{n}{i}P^{n-i}\left[(\sqrt{\Delta})^i-(-\sqrt{\Delta})^i\right]\\ &=\frac{1}{2^{n-1}}\!\!\sum_{0\leqslant j\leqslant(n-1)/2}\!\!\binom{n}{2j+1}P^{n-2j-1}\Delta^j. \end{align}

$\ 2^{n-1}\$ を掛ければ, 各辺は整数になります.

命題 2.5 $\ p\$ は $\ Q\$ および $\ \Delta\$ を割りきらない奇素数であるとする. 法 $\ p\$ の剰余について, $\ \Delta^{\frac{p-1}{2}}\equiv1\$ ならば $\ U_{p-1}\equiv0\$ が成りたち, また $\ \Delta^{\frac{p-1}{2}}\equiv-1\$ ならば, $\ U_{p+1}\equiv0\$ が成りたつ.

証明. $\ \mathrm{mod}.p\$ における二項係数の性質, \begin{align} \binom{p}{i}&\equiv\begin{cases}1&(i=0,\ p)\\0&(0\lt i\lt p)\end{cases},\\&\\ \binom{p+1}{i}&\equiv\begin{cases}1&(i=0,\ 1,\ p,\ p+1)\\0&(1\lt i\lt p) \end{cases} \end{align} を用いる. 前述の等式によれば, 法 $\ p\$ の下で, \begin{align} U_p&\equiv\!\!\sum_{0\leqslant j\leqslant(p-1)/2}\!\!\binom{p}{2j+1}P^{p-2j-1}\Delta^j\\ &\equiv\Delta^{\frac{p-1}{2}},\\ 2U_{p+1}&\equiv\!\!\sum_{0\leqslant j\leqslant(p-1)/2}\!\!\binom{p+1}{2j+1}P^{p-2j}\Delta^j\\ &\equiv P+P\Delta^{\frac{p-1}{2}}. \end{align} 第一に $\ \Delta^{\frac{p-1}{2}}\equiv-1\$ であるとき, $\ U_{p+1}\equiv0\$ は明白である. 第二に $\ \Delta^{\frac{p-1}{2}}\equiv1\$ である場合も, 漸化式を用いると, \begin{align} -2QU_{p-1}&=2(U_{p+1}-PU_p)\\ &\equiv P-P\Delta^{\frac{p-1}{2}}\equiv0. \end{align} 故に命題が成立する.

$\Box$

Euler の規準の証明

定理 2.6 (Euler の規準) $\ p\$ は奇素数であるとする. あらゆる整数 $\ a\$ にたいして, 平方剰余の記号 $\ \left(\!\frac{\,a\,}{\,p\,}\!\right)\$ は, $\ p\$ を法とするときの冪 $\ a^{\frac{p-1}{2}}\$ の絶対最小剰余に等しい. 即ち, \begin{align} \left(\!\frac{\,a\,}{\,p\,}\!\right)\equiv a^{\frac{p-1}{2}}\ \ (\mathrm{mod}.p). \end{align}

証明. $\ a\equiv0,\ 1\ \ (\mathrm{mod}.p)\$ を始めに除外する. それ以外の $\ a\$ にたいして, $\ (P,Q)=(2,1-a)\$ と置けば, \begin{align} \left(\!\frac{\,\Delta\,}{\,p\,}\!\right)&=\left(\!\frac{P^2-4Q}{p}\!\right)=\left(\!\frac{4a}{p}\!\right)=\left(\!\frac{\,a\,}{\,p\,}\!\right),\\ \Delta^{\frac{p-1}{2}}&=4^{\frac{p-1}{2}}a^{\frac{p-1}{2}}\equiv a^{\frac{p-1}{2}} \end{align} であり, かつ $\ P,\$ $Q\$ および $\ \Delta\$ は $\ p\$ によって割りきれない整数である. 故に, $\ a^{\frac{p-1}{2}}\$ の絶対最小剰余を $\ (a\mid p)\$ と書くならば, \begin{align} U_{p-\left(\!\frac{\,a\,}{\,p\,}\!\right)}\equiv U_{p-(a\mid p)}\equiv0\ \ (\mathrm{mod}.p). \end{align} ここにおいて, 若し仮に $\ U_{p+1}\equiv U_{p-1}\equiv0\$ とすれば, 漸化式によって $\ U_1\equiv0\$ が導かれるけれども, これは不合理である. 故に上記の合同式から, \begin{align} \left(\!\frac{\,a\,}{\,p\,}\!\right)=(a\mid p) \end{align} の相等が得られて, 定理の証明が完成する.