ラグランジュの定理

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

$n$ 次合同方程式

数論における $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)\]
というように次数が１つ落ちて $n-1$ 次合同方程式になってしまいます。

ラグランジュの定理

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

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

[証明] 数学的帰納法で証明します。
$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)\]
という合同方程式を考えます。このとき根が１つもないならば定理は成り立ちます。もし１つ以上あって、そのうちの１つを $\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)\]
のように因数分解することができます。