ガウスの補題 (数論)

テンプレート:About 数論におけるガウスの補題（ガウスのほだい、テンプレート:Lang-en-short）は整数が平方剰余であるための条件を与える。計算的には有用ではないが、理論的には重要であり、テンプレート:仮リンクで使われる。

ガウスの補題は平方剰余の相互法則のカール・フリードリヒ・ガウスの3番目の証明 (1808)テンプレート:Rp において初めて現れ、5番目の証明 (1818)テンプレート:Rp において彼は再びそれを証明した。

補題の主張

任意の奇素数 テンプレート:Math に対して、テンプレート:Math を テンプレート:Mvar と互いに素な整数とする。

整数

$a,2a,3a,\dots ,\frac{p-1}{2}a$

と、それらを テンプレート:Mvar で割った（正の）余りを考える。（これらの余りはすべて相異なるので、全部で (テンプレート:Math 個ある。）

その余りが テンプレート:Math よりも大きいものの個数を テンプレート:Math とする。このとき

$\left(\frac{a}{p}\right)=(-1{)}^n$

となる。ただし $\left(\frac{a}{p}\right)$ はルジャンドル記号である。

例

テンプレート:Math および テンプレート:Math とすると、考える整数列は

7, 14, 21, 28, 35

であり、テンプレート:Math で割った余りは、

7, 3, 10, 6, 2

となる。このうち3つ（すなわち 6, 7, 10）が 11/2 よりも大きいので、テンプレート:Math である。したがってガウスの補題により

$\left(\frac{7}{11}\right)=(-1{)}^3=-1$

であるはずである。7 は 11 の平方剰余ではないので、これは実際正しい。

上の余りの列

7, 3, 10, 6, 2

は

−4, 3, −1, −5, 2

とも書ける。この形では、11/2 よりも大きい整数は負の数として現れる。余りの絶対値が余り

1, 2, 3, 4, 5

の置換であることも明らかである。

証明

初等整数論のどんな教科書も補題の証明を書いている。フェルマーの小定理の最も簡単なテンプレート:仮リンクの1つを想起させるかなり簡単な証明テンプレート:Rp は、積

$Z=a\cdot 2a\cdot 3a\cdot \cdots \cdot \frac{p-1}{2}a$

を テンプレート:Mvar で割った余りを2つの異なる方法で計算することにより得られる。まず、

$Z=a^{(p-1)/2}(1\cdot 2\cdot 3\cdot \cdots \cdot \frac{p-1}{2})$

である。次に、テンプレート:Mvar が テンプレート:Mvar で割った 0 でない余りのとき、テンプレート:Mvar の“絶対値”を次のように定義する：

$|x|=\{\begin{array}{cc}x& \text{if }1\le x\le \frac{p-1}{2},\\ p-x& \text{if }\frac{p+1}{2}\le x\le p-1.\end{array}$

テンプレート:Mvar は後者の範囲に属するような倍数 テンプレート:Math の個数を数え、このとき テンプレート:Math は前者の範囲に入るから、

$Z\equiv (-1{)}^n(|a|\cdot |2a|\cdot |3a|\cdot \cdots \cdots \left|\frac{p-1}{2}a\right|)$

となる。

さて値 テンプレート:Math が テンプレート:Math に対して相異なることを見る。実際、テンプレート:Mvar は テンプレート:Mvar と互いに素であるから、

$\begin{array}{cc}|ra|& \equiv |sa|(\mathrm{mod}p)\\ ⟹ra& \equiv \pm sa(\mathrm{mod}p)\\ ⟹r& \equiv \pm s(\mathrm{mod}p)\end{array}$

となり、テンプレート:Math を得る。

しかし、“絶対値”の取る値もちょうど テンプレート:Math 個であるから、それらは整数 テンプレート:Math を並べ替えたものとなる。したがって

$Z\equiv (-1{)}^n(1\cdot 2\cdot 3\cdot \cdots \cdot \frac{p-1}{2})$

となる。

2つの計算を比較して、テンプレート:Mvar の倍数でない因子

$1\cdot 2\cdot 3\cdot \cdots \cdot \frac{p-1}{2}$

を消すと、

$a^{(p-1)/2}\equiv (-1{)}^n$

を得る。オイラーの規準によって左辺はルジャンドル記号 $\left(\frac{a}{p}\right)$ の別の表現であるから、求める結果を得る。

応用

ガウスの補題は、平方剰余の相互法則の知られている証明のうち、決してすべてではないが、多くでテンプレート:Rpテンプレート:Rp 使われる。

例えば、ゴットホルト・アイゼンシュタインテンプレート:Rp はガウスの補題を用いて テンプレート:Mvar が奇素数のときに

$\left(\frac{a}{p}\right)=\prod _{n=1}^{(p-1)/2}\frac{\sin (2\pi an/p)}{\sin (2\pi n/p)}$

となることを証明し、この式を用いて平方剰余の相互法則を証明した。円関数ではなく楕円関数を使うことで、彼はテンプレート:仮リンクやテンプレート:仮リンクを証明したテンプレート:Rp。

レオポルト・クロネッカーテンプレート:Rp は補題を用いて

$\left(\frac{p}{q}\right)=\mathrm{sgn}\prod _{i=1}^{\frac{q-1}{2}}\prod _{k=1}^{\frac{p-1}{2}}(\frac{k}{p}-\frac{i}{q})$

を示した。テンプレート:Math と テンプレート:Math を入れ替えることで直ちに平方剰余の相互法則を得る。

「第二補充法則」のおそらく最も簡単な証明 においても用いられる：

$\left(\frac{2}{p}\right)=(-1{)}^{(p^2-1)/8}=\{\begin{array}{c}+1\text{ if }p\equiv \pm 1(\mathrm{mod}8)\\ -1\text{ if }p\equiv \pm 3(\mathrm{mod}8)\end{array}$

群論の移送との関係

テンプレート:Mvar を テンプレート:Math の 0 でない剰余類のなす乗法群 テンプレート:Mathとし、テンプレート:Math を部分群 テンプレート:Math とする。テンプレート:Mvar における テンプレート:Mvar の剰余類の次の代表系を考える：

$1,2,3,\dots ,\frac{p-1}{2}.$

この代表系の集合に移送のからくりを施して、移送準同型

$\varphi :G\to H$

を得るが、これは テンプレート:Mvar を テンプレート:Math に送る写像であることが分かる、ただし テンプレート:Math と テンプレート:Math は補題の主張のとおりとする。するとガウスの補題は、この準同型を二次剰余指標として明示的に同一視する計算と見ることができる。

関連項目

素数を法とした平方数の2つの他の特徴づけはオイラーの規準とテンプレート:仮リンクである。