ラグランジュの定理

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

$n$ 次合同方程式

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

$m\mid /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(\mathrm{mod}p)$$
というように次数が１つ落ちて $n-1$ 次合同方程式になってしまいます。

ラグランジュの定理

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

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

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

$n-1$ のときに定理が成り立つと仮定します。すなわち、$n-1$ 次合同方程式の解の個数は $n-1$ 個を超えないものとします。$f(x)$ を $n$ 次式として
$$f(x)\equiv 0(\mathrm{mod}p)$$
という合同方程式を考えます。このとき根が１つもないならば定理は成り立ちます。もし１つ以上あって、そのうちの１つを $\alpha$ とすると
$$f(\alpha )\equiv 0(\mathrm{mod}p)$$
が成り立ちます。ここで $g(x)$ を $n-1$ 次式として
$$f(x)=(x-\alpha )g(x)+r$$
とおくと、合同方程式は
$$(x-\alpha )g(x)+r\equiv 0(\mathrm{mod}p)$$
となります。$x=\alpha$ を代入すると
$$r\equiv 0(\mathrm{mod}p)$$
となるので、合同方程式の左辺から省くことができて
$$(x-\alpha )g(x)\equiv 0(\mathrm{mod}p)$$
上の合同方程式が $\alpha$ とは異なる根 $x=\beta$ をもつとすると
$$(\beta -\alpha )g(\beta )\equiv 0(\mathrm{mod}p)$$
$\beta -\alpha \ne \equiv 0$ かつ $p$ は素数なので
$$g(\beta )\equiv 0(\mathrm{mod}p)$$
すなわち $\beta$ が $\alpha$ と異なる根であるということは
$$g(x)\equiv 0(\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⟹a^{p-1}\equiv 1(\mathrm{mod}p)$$
が常に成り立ちます。$a=1,2,\cdots ,p-1$ はすべて $p$ と互いに素なので
$$\begin{array}{rlr}& 1^{p-1}\equiv 1& (\mathrm{mod}p)\\ & 2^{p-1}\equiv 1& (\mathrm{mod}p)\\ & \cdots \cdots \cdots \cdots \cdots \\ & (p-1{)}^{p-1}\equiv 1& (\mathrm{mod}p)\end{array}$$
がすべて成り立つことになります。ラグランジュの定理によると、$p-1$ 次の合同方程式の解は最大で $p-1$ 個ですから、$a^{p-1}\equiv 1$ の解はこれですべて出揃っていることになります。したがって
$$a^{p-1}-1\equiv (a-1)(a-2)\cdots (a-(p-1))(\mathrm{mod}p)$$
のように因数分解することができます。