平方剰余の補充法則



≫『大学への数学』最新号
≫ 挑戦問題 PS-19 が入りました。

 定理 F11 を再掲します。

 $p$ を奇素数、$(a,\:p)=(b,\:p)=1$ とするとき、
\[\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\,\left(\frac{b}{p}\right)\]

 一般の正負の整数 $n$ は、$q_1,\:q_2,\:,\cdots$ を奇素数、$s,\:t_1,\:t_2,\:\cdots$ を $0$ 以上の整数として
 
\[n=\pm\,2^sq_1^{t_1}q_2^{t_2}\cdots\]
のように表せるので、整数が平方剰余であるかどうかは
 
\[\left(\frac{n}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{2}{p}\right)^s\left(\frac{q_1}{p}\right)^{t_1}\left(\frac{q_2}{p}\right)^{t_2}\cdots\]
を計算して判定することができます。すなわち任意の整数について、素因数分解によって奇素因数 $q_i$ をすべて求めて
 
\[\left(\frac{-1}{p}\right),\:\left(\frac{2}{p}\right),\:\left(\frac{q_i}{p}\right)\]
を計算すれば、その整数の平方剰余/平方非剰余を判定することができるということです。

平方剰余の第1補充法則

 $\displaystyle\left(\frac{-1}{p}\right)$ は前々回記事で扱った オイラーの判定条件

[定理 F9 オイラーの判定条件]
 $p$ を奇素数、$(a,\:p)=(b,\:p)=1$ とするとき、
\[\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\quad (\mathrm{mod}\:p)\]

において $a=-1$ とすればよいだけで、平方剰余の第1補充法則 とよばれています:

[定理 F13 平方剰余の第1補充法則]
 $p$ を奇素数とするとき、
\[\left(\frac{-1}{p}\right)= (-1)^{\frac{p-1}{2}}\]

 ここで $p$ を $4$ で割ったときの余り ($\mathrm{mod}\:4$) で分類すると、$p=4k+1$ あるいは $p=4k+3$ のいずれかになります( $4k$ や $4k+2$ は偶数なので $p$ として不適)。それぞれの場合について上の第1補充法則に入れて計算してみると、
 
\[\left(\frac{-1}{p}\right)= (-1)^{2k}=1,\quad \left(\frac{-1}{p}\right)= (-1)^{2k+1}=-1\]
となるので、
 
\[x^2\equiv -1\quad (\mathrm{mod}\:p)\]
が解をもつのは、$p=4k+1$ の形の素数のときだけです。たとえば、
 
\[x^2\equiv -1\quad (\mathrm{mod}\:5)\]
すなわち
 
\[x^2\equiv 4\quad (\mathrm{mod}\:5)\]
は解をもつということです。実際に確認してみましょう。
 
\[1^2,\:2^2,\:3^2,\:4^2,\:5^2\]
を $5$ で割ってみると

\[1,\:4,\:,\:4,\:1,\:0\]
となって、確かに余り $4$ が現れています。すなわち
 
\[x\equiv 2,\:3\quad (\mathrm{mod}\:5)\]
が解となります。
 

平方剰余の第2補充法則

 次は $a=2$ の場合です。これもオイラーの判定条件に当てはめて
 
\[\left(\frac{2}{p}\right)\equiv 2^{\frac{p-1}{2}}\quad (\mathrm{mod}\:p)\]
によって判定することもできますが、たとえば $p=17$ とすると
 
\[\left(\frac{2}{11}\right)\equiv 2^8\quad (\mathrm{mod}\:17)\]
を計算しなくてはならず、少し面倒です。右辺が $(-1)^t$ の形になっていれば、$t$ の偶奇によってすぐに平方剰余/非剰余を判定できます。そこで登場するのが次の 平方剰余の第2補充法則 です。

[定理 F14 平方剰余の第2補充法則]
 $p$ を奇素数とするとき、
\[\left(\frac{2}{p}\right)= (-1)^{\frac{p^2-1}{8}}\]

 この定理の証明の準備として、前回記事で扱った ガウスの補題 を少し噛み砕いた表現に直しておきます(意味は同じです)。

 $p$ が奇素数、$(a,\:p)=1$ であるとき、
\[1a,\:2a,\:3a,\:\cdots,\:\frac{p-1}{2}a\]を $p$ で割って余りを並べて、$p/2$ より大きな数が $t$ 個あるならば、
\[\left(\frac{a}{p}\right)=(-1)^t\]が成り立ちます。

 さらに $a=2$ とすると、$(2,\:p)=1$ なので

 $p$ を奇素数とすると、
\[2,\:4,\:6,\:\cdots,\:p-3,\:p-1\]を $p$ で割って余りを並べて、$p/2$ より大きな数が $t$ 個あるならば、
\[\left(\frac{2}{p}\right)=(-1)^t\]が成り立ちます。

 第2補充法則の証明にはこの定理を用いますが、一般的な証明は少し難しいので、まずは $p=11$ として具体的に調べてみます。
 
\[2,\:4,\:6,\:8,\:10\]
を $11$ で割って余りを並べると、
 
\[2,\:4,\:6,\:8,\:10\tag{1}\]
というように同じ数が並びます。このなかに $p/2=5.5$ より大きな数は $3$ 個あるので、ガウスの補題により
 
\[\left(\frac{2}{11}\right)=(-1)^3=-1\]
となって、$x^2\equiv 2\:(\mathrm{mod}\:11)$ が解をもたないことがすぐにわかります。しかし後の一般的証明のために、この $t=3$ を別の方法で数えてみます。(1) になかで $p/2=5.5$ より大きな余りは
 
\[6,\:8,\:10\tag{2}\]
です。これらの数を $11$ から引くと
 
\[5,\:3,\:1\tag{3}\]
というように $5.5$ より小さな奇数が並びます。つまり $p/2=5.5$ より大きな数の個数は $5.5$ より小さな奇数の個数に等しくなります。これは
 
\[t\equiv 1+3+5\quad (\mathrm{mod}\:2)\]
のように表すこともできます。$\mathrm{mod}\:2$ で考えているので、これに偶数をいくつ足しても合同ですから、
 
\[t\equiv 1+2+3+4+5\quad (\mathrm{mod}\:2)\]
と書き換えることもできます。以上を踏まえて一般的な証明を記述します。

[定理 F14 の証明]
 $2,\:4,\:6,\:\cdots,\:p-2,\:p-1$ を $11$ で割って余りを並べると、
 
\[2,\:4,\:6,\:\cdots,\:p-2,\:p-1\tag{4}\]
となります。このなかに $p/2$ より大きな数 $r$ が $t$ 個あると仮定します。$r$ は偶数なので $p-r$ は奇数です。$r\gt p/2$ なので、
 
\[p-r\lt\frac{p}{2}\]
となります。つまり $t$ は $p/2$ より小さな奇数の個数と一致するので
 
\[t\equiv 1+3+5+\cdots +\frac{p-1}{2}\quad (\mathrm{mod}\:2)\]
 これに偶数をいくつ加えても合同なので、等差級数の公式を用いて
 
\[\begin{align*}t\equiv& 1+2+3+4+5+\cdots +\frac{p-1}{2}\\[6pt]
\equiv& \frac{1}{2}\,\frac{p-1}{2}\left(1+\frac{p-1}{2}\right)=\frac{p^2-1}{8}\quad (\mathrm{mod}\:2)\end{align*}\]
が得られます(証明終)。 ≫ 平方剰余の相互法則 ≫ 整数論入門講座

スポンサーリンク
スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

メールアドレスが公開されることはありません。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください