オイラーの規準 証明

ウィキペディア

オイラーの規準

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/06/03 01:07 UTC 版)

証明

この証明は素数を法とする剰余のクラスが体であることを使用する。詳細は素体の記事(en:Characteristic (algebra)#Case of fields)参照。

法が素数であるため、ラグランジュの定理が適用される。次数 k の多項式は最大で k 個の根しか持つことができない。特に、x² ≡ a (mod p) は各 a に対して最大2つの解を持つ。このことは0の他にpを法とする少なくともp − 1/2個の異なる平方剰余があることを即座に意味する。x の p − 1 個の可能な値の各々は、同じ剰余を与えるために互いに付随することしかできない。

実際に、$(p-x)^{2}\equiv x^{2}{\pmod {p}}$である。これは$(p-x)^{2}\equiv p^{2}-{2}{x}{p}+x^{2}\equiv x^{2}{\pmod {p}}$であるからである。 よって、${\tfrac {p-1}{2}}$ 個の別個の平方剰余は $1^{2},2^{2},...,({\tfrac {p-1}{2}})^{2}{\pmod {p}}$である。

a は p と互いに素であるため、フェルマーの小定理により

$a^{p-1}\equiv 1{\pmod {p}},$

となり、これは

$\left(a^{\tfrac {p-1}{2}}-1\right)\left(a^{\tfrac {p-1}{2}}+1\right)\equiv 0{\pmod {p}}.$

と書くことができる。 p を法とする整数は体を形成するため、それぞれの a についてこれらの因数のいずれかがゼロでなければならない。

ここで a が平方剰余 a ≡ x² であるとすると

$a^{\tfrac {p-1}{2}}\equiv {(x^{2})}^{\tfrac {p-1}{2}}\equiv x^{p-1}\equiv 1{\pmod {p}}.$

となる。よって平方剰余 (mod p) により第1の因数がゼロになる。

ラグランジュの定理を再度適用すると、第1の因数をゼロにするaの値は p − 1/2 より多くはないことに留意する。しかし、最初に述べたように少なくとも p − 1/2 個の異なる平方剰余 (mod p) がある（0以外）。よって、これらはきっかりと第1の因数をゼロにする剰余クラスである。もう1つの p − 1/2 個の剰余クラス（非剰余）は2番目の因数がゼロである必要があり、そうでないとフェルマーの小定理を満たさない。これがオイラーの規準である。