ラグランジュの定理

 新しい章に入ります。この章では主に平方剰余を扱いますが、その準備として $n$ 次合同方程式を定義し、ラグランジュの定理 を証明しておきます。

$n$ 次合同方程式

 数論における $n$ 次方程式を次のように定義します。

[定義 F1] $n$ を正整数、$a_0\neq 0$ とします。$a_0$ が $m$ で割り切れないときに、
\[a_0\,x^n+a_1\,x^{n-1}+\,\cdots\,+a_{n-1}x+a_n\equiv 0\quad (\mathrm{mod}\:p)\]を $n$ 次合同方程式と定義します。

 $m\mid \hspace{-.67em}/\,a_0$ という条件がありますが、もし $a_0$ が $m$ で割り切れるのであれば、最初の項が $m$ で割り切れるので、合同式の性質から
 
\[a_1\,x^{n-1}+a_2\,x^{n-2}+\,\cdots\,+a_{n-1}x+a_n\equiv 0\quad (\mathrm{mod}\:p)\]
というように次数が1つ落ちて $n-1$ 次合同方程式になってしまいます。
 

ラグランジュの定理

 ラグランジュ (Lagrange) はフランスの数学者・物理学者です。物理を学んでいる人であれば、ラグランジュ点やラグランジアンなどでお馴染みですね。その扱う分野の幅広さから、彼の名を冠した定理はあちこちで見かけますが、数論にも「ラグランジュの定理」があります。

[定理 F1 ラグランジュの定理] 素数 $p$ を法とする $n$ 次合同方程式
\[a_0\,x^n+a_1\,x^{n-1}+\,\cdots\,+a_{n-1}x+a_n\equiv 0\quad (\mathrm{mod}\:p)\]の根の個数は $n$ 個を超えない。

 合同方程式の根はまったく存在しないかもしれないし、あるいは $n-2$ 個かもしれませんが、最大でも $n$ 個までという意味です。

[定理 F1 の証明] 数学的帰納法で証明します。
 $n=1$ のときは 1 次合同方程式
 
\[ax\equiv b\quad (\mathrm{mod}\:p)\]
となり、$(a,\:p)=1$ なので解は 1 つだけ存在します。つまり定理は成り立っています。

 $n-1$ のときに定理が成り立つと仮定します。すなわち、$n-1$ 次合同方程式の解の個数は $n-1$ 個を超えないものとします。$f(x)$ を $n$ 次式として
 
\[f(x)\equiv 0\quad (\mathrm{mod}\:p)\]
という合同方程式を考えます。このとき根が1つもないならば定理は成り立ちます。もし1つ以上あって、そのうちの1つを $\alpha$ とすると
 
\[f(\alpha)\equiv 0\quad (\mathrm{mod}\:p)\]
が成り立ちます。ここで $g(x)$ を $n-1$ 次式として
 
\[f(x)=(x-\alpha)\,g(x)+r\]
とおくと、合同方程式は
 
\[(x-\alpha)\,g(x)+r\equiv 0\quad (\mathrm{mod}\:p)\]
となります。$x=\alpha$ を代入すると
 
\[r\equiv 0\quad (\mathrm{mod}\:p)\]
となるので、合同方程式の左辺から省くことができて
 
\[(x-\alpha)\,g(x)\equiv 0\quad (\mathrm{mod}\:p)\]
 上の合同方程式が $\alpha$ とは異なる根 $x=\beta$ をもつとすると
 
\[(\beta-\alpha)\,g(\beta)\equiv 0\quad (\mathrm{mod}\:p)\]
 $\beta-\alpha\neq\equiv 0$ かつ $p$ は素数なので
 
\[g(\beta)\equiv 0\quad (\mathrm{mod}\:p)\]
 すなわち $\beta$ が $\alpha$ と異なる根であるということは
 
\[g(x)\equiv 0\quad (\mathrm{mod}\:p)\]
の根であるということです。仮定により $n-1$ 次式 $g(x)\equiv 0$ の根の個数は $n-1$ を超えないので、$f(x)\equiv 0$ の根は $x=\alpha$ と合わせても最大で $n$ 個だということになります。(証明終)
 

$a^{p-1}-1$ の因数分解

 ラグランジュの定理を用いて $a^{p-1}-1$ を因数分解してみます。
 フェルマーの小定理 によると素数 $p$ について

\[(a,\:p)=1\quad\Longrightarrow\quad a^{p-1}\equiv 1\quad (\mathrm{mod}\:p)\]
が常に成り立ちます。$a=1,\;2,\;\cdots,\;p-1$ はすべて $p$ と互いに素なので
 
\[\begin{align*}&1^{p-1}\equiv 1&\quad (\mathrm{mod}\:p)\\[6pt]
&2^{p-1}\equiv 1&\quad (\mathrm{mod}\:p)\\[6pt]
&\cdots\cdots\cdots\cdots\cdots\\[6pt]
&(p-1)^{p-1}\equiv 1&\quad (\mathrm{mod}\:p)\end{align*}\]
がすべて成り立つことになります。ラグランジュの定理によると、$p-1$ 次の合同方程式の解は最大で $p-1$ 個ですから、$a^{p-1}\equiv 1$ の解はこれですべて出揃っていることになります。したがって
 
\[a^{p-1}-1\equiv (a-1)\,(a-2)\,\cdots\,(a-(p-1))\quad (\mathrm{mod}\:p)\]
のように因数分解することができます。

エクセルや数学に関するコメントをお寄せください