ガウスの補題 (数論)

数論におけるガウスの補題（ガウスのほだい、英: Gauss' lemma）は整数が平方剰余であるための条件を与える。計算的には有用ではないが、理論的には重要であり、平方剰余の相互法則のいくつかの証明で使われる。

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

補題の主張

任意の奇素数 p に対して、a を p と互いに素な整数とする。

整数

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

と、それらを p で割った（正の）余りを考える。（これらの余りはすべて相異なるので、全部で (p − 1)/2 個ある。）

その余りが p/2 よりも大きいものの個数を n とする。このとき

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

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

例

p = 11 および a = 7 とすると、考える整数列は

7, 14, 21, 28, 35

であり、11 で割った余りは、

7, 3, 10, 6, 2

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

$\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つを想起させるかなり簡単な証明 は、積

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

を p で割った余りを2つの異なる方法で計算することにより得られる。まず、

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

である。次に、x が p で割った 0 でない余りのとき、x の“絶対値”を次のように定義する：

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

n は後者の範囲に属するような倍数 ka の個数を数え、このとき −ka は前者の範囲に入るから、

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

となる。

さて値 |ra| が r = 1, 2, …, (p − 1)/2 に対して相異なることを見る。実際、a は p と互いに素であるから、

${\begin{aligned}|ra|&\equiv |sa|{\pmod {p}}\\\implies ra&\equiv \pm sa{\pmod {p}}\\\implies r&\equiv \pm s{\pmod {p}}\end{aligned}}$

となり、r = s を得る。

しかし、“絶対値”の取る値もちょうど (p − 1)/2 個であるから、それらは整数 1, 2, …, (p − 1)/2 を並べ替えたものとなる。したがって

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

となる。

2つの計算を比較して、p の倍数でない因子

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

を消すと、

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

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

応用

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

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

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

となることを証明し、この式を用いて平方剰余の相互法則を証明した。円関数ではなく楕円関数を使うことで、彼は三次や四次の相互法則を証明した。

レオポルト・クロネッカー は補題を用いて

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

を示した。p と q を入れ替えることで直ちに平方剰余の相互法則を得る。

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

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

群論の移送との関係

G を Z/pZ の 0 でない剰余類のなす乗法群 (Z/pZ)^×とし、H を部分群 {+1, −1} とする。G における H の剰余類の次の代表系を考える：

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

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

$\phi \colon G\to H$

を得るが、これは a を (−1)ⁿ に送る写像であることが分かる、ただし a と n は補題の主張のとおりとする。するとガウスの補題は、この準同型を二次剰余指標として明示的に同一視する計算と見ることができる。

関連項目

素数を法とした平方数の2つの他の特徴づけはオイラーの規準とゾロタレフの補題である。