ガウスの補題 (数論)のソースを表示

{{About|数論におけるガウスの補題|その他|ガウスの補題}}
[[数論]]における'''ガウスの補題'''（ガウスのほだい、{{lang-en-short|Gauss' lemma}}）は[[整数]]が[[平方剰余]]であるための条件を与える。計算的には有用ではないが、理論的には重要であり、{{仮リンク|平方剰余の相互法則の証明|label=平方剰余の相互法則のいくつかの証明|en|proofs of quadratic reciprocity}}で使われる。

ガウスの補題は[[平方剰余の相互法則]]の[[カール・フリードリヒ・ガウス]]の3番目の証明 (1808)<ref name="Untersuchungen">{{citation
  | last1 = Gauss  | first1 = Carl Friedrich
  | translator = H. Maser
  | title = Untersuchungen uber hohere Arithmetik (Disquisitiones Arithmeticae & other papers on number theory)
  | edition = 2nd
  | language = German
  | publisher = Chelsea
  | location = New York
  | year = 1965
  | isbn = 0-8284-0191-8}}</ref>{{rp|458–462}} において初めて現れ、5番目の証明 (1818)<ref name="Untersuchungen" />{{rp|496–501}} において彼は再びそれを証明した。

== 補題の主張 ==
任意の奇素数 {{math|''p''}} に対して、{{math|''a''}} を {{mvar|p}} と[[互いに素 (整数論)|互いに素]]な整数とする。

整数
:<math>a,\, 2a,\, 3a,\, \dots,\, \frac{p-1}{2}a</math>
と、それらを {{mvar|p}} で割った（正の）余りを考える。（これらの余りはすべて相異なるので、全部で ({{math|''p'' &minus; 1)/2}} 個ある。）

その余りが {{math|''p''/2}} よりも大きいものの個数を {{math|''n''}} とする。このとき
:<math>\left(\frac{a}{p}\right) = (-1)^n</math>
となる。ただし <math>\left(\frac{a}{p}\right)</math> は[[ルジャンドル記号]]である。

=== 例 ===
{{math|1=''p'' = 11}} および {{math|1=''a'' = 7}} とすると、考える整数列は
: 7, 14, 21, 28, 35
であり、{{math|11}} で割った余りは、
: 7, 3, 10, 6, 2
となる。このうち3つ（すなわち 6, 7, 10）が 11/2 よりも大きいので、{{math|1=''n'' = 3}} である。したがってガウスの補題により
: <math>\left(\frac
{7}{11}\right) = (-1)^3 = -1</math>
であるはずである。7 は 11 の平方剰余ではないので、これは実際正しい。

上の余りの列
: 7, 3, 10, 6, 2
は
: &minus;4, 3, &minus;1, &minus;5, 2
とも書ける。この形では、11/2 よりも大きい整数は負の数として現れる。余りの絶対値が余り
: 1, 2, 3, 4, 5
の置換であることも明らかである。

== 証明 ==
初等整数論のどんな教科書も補題の証明を書いている。[[フェルマーの小定理]]の最も簡単な{{仮リンク|フェルマーの小定理の証明|label=証明|en|proofs of Fermat's little theorem}}の1つを想起させるかなり簡単な証明<ref name="Untersuchungen" />{{rp|458–462}} は、積
: <math>Z = a \cdot 2a \cdot 3a \cdot \cdots \cdot \frac{p-1}2 a</math>
を {{mvar|p}} で割った余りを2つの異なる方法で計算することにより得られる。まず、
: <math>Z = a^{(p-1)/2} \left(1 \cdot 2 \cdot 3 \cdot \cdots \cdot \frac{p-1}2 \right)</math>
である。次に、{{mvar|x}} が {{mvar|p}} で割った 0 でない余りのとき、{{mvar|x}} の“絶対値”を次のように定義する：
: <math>|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}</math>
{{mvar|n}} は後者の範囲に属するような倍数 {{math|''ka''}} の個数を数え、このとき {{math|&minus;''ka''}} は前者の範囲に入るから、
: <math>Z \equiv (-1)^n \left(|a| \cdot |2a| \cdot |3a| \cdot \cdots \cdots \left|\frac{p-1}2 a\right|\right)</math>
となる。

さて値 {{math|&#124;''ra''&#124;}} が {{math|''r'' &#61; 1, 2, …, (''p'' &minus; 1)/2}} に対して相異なることを見る。実際、{{mvar|a}} は {{mvar|p}} と互いに素であるから、
:<math>
\begin{align}
|ra| &\equiv |sa| \pmod{p} \\
\implies ra &\equiv \pm sa \pmod{p} \\
\implies r &\equiv \pm s \pmod{p}
\end{align}
</math>
となり、{{math|1=''r'' = ''s''}} を得る。

しかし、“絶対値”の取る値もちょうど {{math|(''p'' &minus; 1)/2}} 個であるから、それらは整数 {{math|1, 2, …, (''p'' &minus; 1)/2}} を並べ替えたものとなる。したがって
: <math>Z \equiv (-1)^n \left(1 \cdot 2 \cdot 3 \cdot \cdots \cdot \frac{p-1}2\right)</math>
となる。

2つの計算を比較して、{{mvar|p}} の倍数でない因子
: <math>1 \cdot 2 \cdot 3 \cdot \cdots \cdot \frac{p-1}2</math>
を消すと、
: <math>a^{(p-1)/2} \equiv (-1)^n </math>
を得る。[[オイラーの規準]]によって左辺はルジャンドル記号 <math>\left (\frac{a}{p}\right )</math> の別の表現であるから、求める結果を得る。

== 応用 ==
ガウスの補題は、[[平方剰余の相互法則]]の知られている証明のうち、決してすべてではないが、多くで<ref name="Lemmermeyer">{{citation
  | last1 = Lemmermeyer  | first1 = Franz
  | title = Reciprocity Laws: from Euler to Eisenstein
  | publisher = [[Springer Science+Business Media|Springer]]
  | location = Berlin
  | year = 2000
  | isbn = 3-540-66957-4}}</ref>{{rp|Ch. 1,&nbsp;}}<ref name="Lemmermeyer" />{{rp|9}} 使われる。

例えば、[[フェルディナント・ゴットホルト・マックス・アイゼンシュタイン|ゴットホルト・アイゼンシュタイン]]<ref name="Lemmermeyer" />{{rp|236}} はガウスの補題を用いて {{mvar|p}} が奇素数のときに
:<math>\left(\frac{a}{p}\right)=\prod_{n=1}^{(p-1)/2}\frac{\sin{(2\pi an/p)}}{\sin{(2\pi n/p)}}</math>
となることを証明し、この式を用いて平方剰余の相互法則を証明した。[[三角関数|円関数]]ではなく[[楕円関数]]を使うことで、彼は{{仮リンク|三次の相互法則|label=三次|en|cubic reciprocity}}や{{仮リンク|四次の相互法則|en|quartic reciprocity}}を証明した<ref name="Lemmermeyer" />{{rp|Ch. 8}}。

[[レオポルト・クロネッカー]]<ref name="Lemmermeyer" />{{rp|Ex. 1.34}} は補題を用いて
:<math>\left(\frac{p}{q}\right)=\sgn\prod_{i=1}^{\frac{q-1}{2}}\prod_{k=1}^{\frac{p-1}{2}}\left(\frac{k}{p}-\frac{i}{q}\right)</math>
を示した。{{math|''p''}} と {{math|''q''}} を入れ替えることで直ちに平方剰余の相互法則を得る。

「第二補充法則」のおそらく最も簡単な証明 においても用いられる：
:<math>\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}</math><!--
Gauss's lemma can be used to prove the following statement, and the reverse is true too.

eh? are you implyng that one can deduce GL from the formula?

I'm removing this statement till someone can provide a reference, and moving the formula to the top of the section 
-->

==高次の冪==
{{empty section|date=Jan. 2017}}
<!--
Generalizations of Gauss's lemma can be used to compute higher power residue symbols. In his second monograph on biquadratic reciprocity,<ref name="GaussBQ">
{{citation
  | last1 = Gauss  | first1 = Carl Friedrich
  | title = Theoria residuorum biquadraticorum, Commentatio secunda
  | publisher = Comment. Soc. regiae sci
  | volume = 7
  | location = Göttingen
  | year = 1832}}</ref>{{rp|§§69&ndash;71}} Gauss used a fourth-power lemma to derive the formula for the biquadratic character of {{math|1 + ''i''}} in {{math|'''Z'''[''i'']}}, the ring of [[Gaussian integers]]. Subsequently, Eisenstein used third- and fourth-power versions to prove [[cubic reciprocity|cubic]] and [[quartic reciprocity]].<ref name="Lemmermeyer" />{{rp|Ch. 8}}

===''n''th power residue symbol===
{{main article|Power residue symbol}}
Let ''k'' be an [[algebraic number field]] with [[ring of integers]] <math>\mathcal{O}_k,</math> and let <math>\mathfrak{p} \subset \mathcal{O}_k </math> be a [[Number field#Prime ideals|prime ideal]]. The [[ideal norm]] <math> \mathrm{N} \mathfrak{p} </math> of <math>\mathfrak{p}</math> is defined as the cardinality of the residue class ring. Since <math>\mathfrak{p} </math> is prime this is a [[finite field]] <math>\mathcal{O}_k / \mathfrak{p}</math>, so the ideal norm is <math> \mathrm{N} \mathfrak{p} = |\mathcal{O}_k / \mathfrak{p}|</math>.

Assume that a primitive {{math|''n''}}th [[root of unity]] <math>\zeta_n\in\mathcal{O}_k,</math> and that {{math|''n''}} and <math>\mathfrak{p} </math> are [[coprime]] (i.e. <math>n\not\in \mathfrak{p}</math>). Then no two distinct {{math|''n''}}th roots of unity can be congruent modulo <math>\mathfrak{p}</math>.

This can be proved by contradiction, beginning by assuming that <math>\zeta_n^r\equiv\zeta_n^s</math> mod <math>\mathfrak{p}</math>, {{math|0 < ''r'' < ''s'' &le; ''n''}}. Let {{math|''t'' &#61; ''s'' &minus; ''r''}} such that <math>\zeta_n^t\equiv 1</math> mod <math>\mathfrak{p}</math>, and {{math|0 < ''t'' < ''n''}}. From the definition of roots of unity, 
:<math>x^n-1=(x-1)(x-\zeta_n)(x-\zeta_n^2)\dots(x-\zeta_n^{n-1}),</math>
and dividing by {{math|''x'' &minus; 1}} gives 
:<math>x^{n-1}+x^{n-2}+\dots +x + 1 =(x-\zeta_n)(x-\zeta_n^2)\dots(x-\zeta_n^{n-1}).</math>

Letting {{math|''x'' &#61; 1}} and taking residues mod <math>\mathfrak{p}</math>,
:<math>n\equiv(1-\zeta_n)(1-\zeta_n^2)\dots(1-\zeta_n^{n-1})\pmod{\mathfrak{p}}.</math>

Since  {{math|''n''}} and <math> \mathfrak{p}</math> are coprime, <math> n\not\equiv 0</math> mod <math>\mathfrak{p},</math> but under the assumption, one of the factors on the right must be zero. Therefore, the assumption that two distinct roots are congruent is false.

Thus the residue classes of <math> \mathcal{O}_k / \mathfrak{p}</math> containing the powers of {{math|ζ<sub>''n''</sub>}} are a subgroup of order {{math|''n''}} of its (multiplicative) group of units, <math>(\mathcal{O}_k/\mathfrak{p}) ^\times  = \mathcal{O}_k /\mathfrak{p}- \{0\}.</math> Therefore, the order of <math>(\mathcal{O}_k/\mathfrak{p})^ \times</math> is a multiple of {{math|''n''}}, and 
:<math>
\begin{align}
\mathrm{N} \mathfrak{p} &= |\mathcal{O}_k / \mathfrak{p}| \\
                        &= \left |(\mathcal{O}_k / \mathfrak{p} )^\times \right| + 1 \\
                        &\equiv 1 \pmod{n}.
\end{align}</math>

There is an analogue of Fermat's theorem in <math>\mathcal{O}_k</math>. If <math>\alpha \in \mathcal{O}_k</math> for <math>\alpha\not\in \mathfrak{p}</math>, then<ref name="Lemmermeyer" />{{rp|Ch. 4.1}} 
:<math>\alpha^{\mathrm{N} \mathfrak{p} -1}\equiv 1 \pmod{\mathfrak{p} },</math>
and since <math>\mathrm{N} \mathfrak{p} \equiv 1 </math> mod {{math|''n''}},
:<math>\alpha^{\frac{\mathrm{N} \mathfrak{p} -1}{n}}\equiv \zeta_n^s\pmod{\mathfrak{p} }</math>
is well-defined and congruent to a unique {{math|''n''}}th root of unity &zeta;<sub>''n''</sub><sup>''s''</sup>.

This root of unity is called the '''{{math|''n''}}th-power residue symbol for <math>\mathcal{O}_k,</math>''' and is denoted by
:<math>
\begin{align}
\left(\frac{\alpha}{\mathfrak{p} }\right)_n &= \zeta_n^s \\
                                            &\equiv \alpha^{\frac{\mathrm{N} \mathfrak{p} -1}{n}}\pmod{\mathfrak{p}}.
\end{align}
</math>

It can be proven that<ref name="Lemmermeyer" />{{rp|Prop. 4.1}}
:<math>\left(\frac{\alpha}{\mathfrak{p} }\right)_n= 1</math>
if and only if there is an <math>\eta \in\mathcal{O}_k</math> such that {{math|''&alpha;'' ≡ ''&eta;<sup>n</sup>''}} mod <math>\mathfrak{p}</math>.

===1/''n'' systems===
Let <math>\mu_n = \{1,\zeta_n,\zeta_n^2,\dots,\zeta_n^{n-1}\} </math> be the multiplicative group of the {{math|''n''}}th roots of unity, and let <math>A=\{a_1, a_2,\dots,a_m\}</math> be representatives of the cosets of <math>(\mathcal{O}_k / \mathfrak{p})^\times/\mu_n.</math> Then {{math|''A''}} is called a '''{{math|1/''n''}} system''' mod <math>\mathfrak{p}.</math><ref name="Lemmermeyer" />{{rp|Ch. 4.2}}

In other words, there are <math>mn=\mathrm{N} \mathfrak{p} -1 </math> numbers in the set <math>A\mu=\{ a_i \zeta_n^j\;:\; 1 \le i \le m, \;\;\;0 \le j \le n-1\},</math> and this set constitutes a representative set for <math>(\mathcal{O}_k / \mathfrak{p})^\times.</math>

The numbers {{math|1, 2, … (''p'' &minus; 1)/2}}, used in the original version of the lemma, are a 1/2 system (mod {{math|''p''}}).

Constructing a {{math|1/''n''}} system is straightforward: let {{math|''M''}} be a representative set for <math>(\mathcal{O}_k / \mathfrak{p})^\times.</math> Pick any <math>a_1\in M </math> and remove the numbers congruent to <math>a_1, a_1\zeta_n, a_1\zeta_n^2, \dots, a_1\zeta_n^{n-1}</math> from {{math|''M''}}. Pick  {{math|''a''<sub>2</sub>}} from {{math|''M''}} and remove the numbers congruent to <math>a_2, a_2\zeta_n, a_2\zeta_n^2, \dots, a_2\zeta_n^{n-1}</math> Repeat until {{math|''M''}} is exhausted. Then {{math|{{mset|''a''<sub>1</sub>, ''a''<sub>2</sub>, … ''a''<sub>m</sub>}}}} is a {{math|1/''n''}} system mod <math>\mathfrak{p}.</math>

===The lemma for ''n''th powers===
Gauss's lemma may be extended to the {{math|''n''}}th power residue symbol as follows.<ref name="Lemmermeyer" />{{rp|Prop. 4.3}} Let <math>\zeta_n\in \mathcal{O}_k </math> be a primitive {{math|''n''}}th root of unity, <math>\mathfrak{p} \subset \mathcal{O}_k </math> a prime ideal, <math>\gamma \in \mathcal{O}_k, \;\;n\gamma\not\in\mathfrak{p},</math> (i.e. <math>\mathfrak{p}</math> is coprime to both {{math|''γ''}} and {{math|''n''}}) and let {{math|''A'' &#61; {{mset|''a''<sub>1</sub>, ''a''<sub>2</sub>, …, ''a''<sub>''m''</sub>}}}} be a  {{math|1/''n''}} system mod <math>\mathfrak{p}.</math>

Then for each {{math|''i''}}, {{math|1 ≤ ''i'' ≤ ''m''}}, there are integers {{math|''π''(''i'')}}, unique (mod {{math|''m''}}), and {{math|''b''(''i'')}}, unique (mod {{math|''n''}}),  such that
:<math>\gamma a_i \equiv \zeta_n^{b(i)}a_{\pi(i)} \pmod{\mathfrak{p}},</math>
and the {{math|''n''}}th-power residue symbol is given by the formula
:<math>\left(\frac{\gamma}{\mathfrak{p} }\right)_n = \zeta_n^{b(1)+b(2)+\dots+b(m)}.</math>

The classical lemma for the quadratic Legendre symbol is the special case {{math|''n'' &#61; 2}}, {{math|''ζ''<sub>2</sub> &#61; &minus;1}}, {{math|''A'' &#61; {{mset|1, 2, …, (''p'' &minus; 1)/2}}}}, {{math|''b''(''k'') &#61; 1}} if {{math|''ak'' > ''p''/2}}, {{math|''b''(''k'') &#61; 0}} if {{math|''ak'' < ''p''/2}}.

====Proof====
The proof of the {{math|''n''}}th-power lemma uses the same ideas that were used in the proof of the quadratic lemma.

The existence of the integers {{math|''π''(''i'')}} and {{math|''b''(''i'')}}, and their uniqueness  (mod {{math|''m''}}) and (mod {{math|''n''}}), respectively, come from the fact that {{math|''Aμ''}} is a representative set.

Assume that {{math|''π''(''i'')}} = {{math|''π''(''j'')}} = {{math|''p''}}, i.e.
:<math>\gamma a_i \equiv \zeta_n^r a_p \pmod{\mathfrak{p}}</math>
and
:<math>\gamma a_j \equiv \zeta_n^s a_p \pmod{\mathfrak{p}}.</math>
Then
:<math>\zeta_n^{s-r}\gamma a_i \equiv \zeta_n^s a_p \equiv \gamma a_j\pmod{\mathfrak{p}}</math>
Because {{math|''γ''}} and <math>\mathfrak{p}</math> are coprime both sides can be divided by {{math|''γ''}}, giving 
:<math>\zeta_n^{s-r} a_i \equiv a_j\pmod{\mathfrak{p}},</math>
which, since {{math|''A''}} is a {{math|1/''n''}} system, implies {{math|''s'' &#61; ''r''}} and {{math|''i'' &#61; ''j''}}, showing that {{math|''π''}} is a permutation of the set {{math|{{mset|1, 2, …, ''m''}}}}.

Then on the one hand, by the definition of the power residue symbol,
:<math>
\begin{align}
(\gamma a_1)(\gamma a_2)\dots(\gamma a_m) &= \gamma^{\frac{\mathrm{N} \mathfrak{p} -1}{n}} a_1 a_2\dots a_m \\
                                          &\equiv \left(\frac{\gamma}{\mathfrak{p} }\right)_n a_1 a_2\dots a_m \pmod{\mathfrak{p}},
\end{align}
</math>
and on the other hand, since {{math|''π''}} is a permutation,
:<math>
\begin{align}
(\gamma a_1)(\gamma a_2)\dots(\gamma a_m) 
&\equiv 
{\zeta_n^{b(1)}a_{\pi(1)}} {\zeta_n^{b(2)}a_{\pi(2)}}\dots{\zeta_n^{b(m)}a_{\pi(m)}} 
&\pmod{\mathfrak{p}}\\
&\equiv
\zeta_n^{b(1)+b(2)+\dots+b(m)}a_{\pi(1)} a_{\pi(2)}\dots a_{\pi(m)}
&\pmod{\mathfrak{p}}\\
&\equiv
\zeta_n^{b(1)+b(2)+\dots+b(m)} a_1 a_2\dots a_m
&\pmod{\mathfrak{p}},
\end{align}
</math>
so
:<math>
\left(\frac{\gamma}{\mathfrak{p} }\right)_n a_1 a_2\dots a_m \equiv \zeta_n^{b(1)+b(2)+\dots+b(m)} a_1 a_2\dots a_m
\pmod{\mathfrak{p}},
</math>
and since for all {{math|1 ≤ ''i'' ≤ ''m''}}, {{math|''a''<sub>''i''</sub>}} and <math>\mathfrak{p}</math> are coprime, {{math|''a''<sub>1</sub>''a''<sub>2</sub>…''a''<sub>m</sub>}} can be cancelled from both sides of the congruence,
:<math>\left(\frac{\gamma}{\mathfrak{p} }\right)_n \equiv \zeta_n^{b(1)+b(2)+\dots+b(m)} 
\pmod{\mathfrak{p}},
</math>
and the theorem follows from the fact that no two distinct {{math|''n''}}th roots of unity can be congruent (mod <math>\mathfrak{p}</math>).

-->

== 群論の移送との関係 ==

{{mvar|G}} を {{math|'''Z'''/''p'''''Z'''}} の 0 でない剰余類のなす乗法群 {{math|('''Z'''/''p'''''Z'''){{sup|&times;}}}}とし、{{math|''H''}} を部分群 {{math|{{mset|+1, &minus;1}}}} とする。{{mvar|G}} における {{mvar|H}} の剰余類の次の代表系を考える：
:<math>1, 2, 3, \dots, \frac{p-1}{2}.</math>

この代表系の集合に[[移送 (群論)|移送]]のからくりを施して、移送準同型
:<math>\phi \colon G \to H</math>
を得るが、これは {{mvar|a}} を {{math|(&minus;1)<sup>''n''</sup>}} に送る写像であることが分かる、ただし {{math|''a''}} と {{math|''n''}} は補題の主張のとおりとする。するとガウスの補題は、この準同型を二次剰余指標として明示的に同一視する計算と見ることができる。

== 関連項目 ==

素数を法とした平方数の2つの他の特徴づけは[[オイラーの規準]]と{{仮リンク|ゾロタレフの補題|en|Zolotarev's lemma}}である。

==参考文献==
{{reflist}}

{{DEFAULTSORT:かうすのほたい すうろん}}
[[Category:合同算術]]
[[Category:補題]]
[[Category:証明を含む記事]]
[[Category:平方剰余]]
[[Category:数学に関する記事]]