初等整数論/べき剰余のソースを表示

{{Nav}}

== 平方剰余 ==
<math>p</math> を奇素数、<math>a</math> を <math>p</math> で割り切れない数、<math>x^2 \equiv a \pmod{p}</math> としたときに解を持つ、持たないにしたがって <math>a</math> を <math>p</math> の'''平方剰余'''、'''平方非剰余''' という。

<math>a \not\equiv 0</math> のとき <math>a</math> が平方剰余、非剰余にしたがって

<math>\left( \frac{a}{p} \right) = 1, \, -1</math> とする。また、便宜上 <math>\left(\frac{kp}{p}\right)=0</math> とする。これを'''ルジャンドル記号'''と呼ぶ。

したがって <math>\left(\frac{a}{p}\right)</math> は <math>a</math> の属する剰余類にのみ依存する。そして <math>\left(\frac{a}{p}\right)=-1</math> ならば <math>kp+a</math> の形の平方数は存在しない。

'''例''' <math>\left(\frac{2}{3}\right)=\left(\frac{3}{4}\right)=\left(\frac{3}{5}\right)=-1, \left(\frac{4}{5}\right)=1</math> である。

'''補題 1'''
<math>r</math> を <math>p</math> の原始根とする。[[初等整数論/原始根と指数#定理 2.3.4|定理 2.3.4]] から <math>x^2 \equiv a \pmod{p}</math> が解を持つのと <math>{\rm Ind}_r \, a</math> が <math>(2, p-1) = 2</math> で割り切れるというのは同値である。したがって

<math>\left( \frac{a}{p} \right) = (-1)^{{\rm Ind}_r \, a}.</math>

====== 定理 2.10 ======
<math>a \equiv a' \pmod{p}</math> ならば <math>\left( \frac{a}{p} \right) = \left( \frac{a'}{p} \right)</math>

'''証明'''<br />
合同の推移性、または補題 1 によって明白。

====== 定理 2.11 ======
<math>\left( \frac{abc\cdots}{p} \right) = \left( \frac{a}{p} \right) \left( \frac{b}{p} \right) \left( \frac{c}{p} \right) \cdots</math>

'''証明'''<br />
補題 1 より <math>\left( \frac{abc\cdots}{p} \right) = (-1)^{{\rm Ind}_r \, abc\cdots}</math>

[[初等整数論/原始根と指数#定理 2.3.4|定理 2.3.4]] より 、これは

:<math>
(-1)^{{\rm Ind}_r \, a \ + {\rm Ind}_r \  b \ + {\rm Ind}_r \, c \ + \cdots} (-1)^{{\rm Ind}_r \, a} \ (-1)^{{\rm Ind}_r \, b} \ =(-1)^{{\rm Ind}_r \, c} \cdots
</math>

に等しい。ここで再び補題 1 より、これは

<math>= \left( \frac{a}{p} \right) \left( \frac{b}{p} \right) \left( \frac{c}{p} \right) \cdots</math>

に等しい。

====== 定理 2.12 (オイラーの規準) ======
<math>\left( \frac{a}{p} \right) \equiv a^{\frac{p-1}{2}} \pmod{p}</math>

'''証明 1'''<br />
[[初等整数論/原始根と指数#定理 2.3.4|定理 2.3.4]] から <math>x^2 \equiv a \pmod{p}</math> が解を持つ、つまり <math>\left( \frac{a}{p} \right) = 1</math> のとき、

<math>f = \frac{p-1}{(2, p-1)}, \ \ a^f \equiv 1 \pmod{p}.</math>

ここで、<math>(2, p-1) = 2</math> より、<math>a^{\frac{p-1}{2}} \equiv 1 \pmod{p}</math>

したがって <math>\left( \frac{a}{p} \right) \equiv 1 \pmod{p}.</math>

逆に <math>\left( \frac{a}{p} \right) = -1</math> 、つまり <math>x^2 \equiv a \pmod{p}</math> が解を持たないとき、再び定理 2.3.4 から

<math>a^{\frac{p-1}{2}} \not\equiv 1 \pmod{p}.</math> このとき[[初等整数論/フェルマーの小定理#フェルマーの小定理|フェルマーの小定理]]より

<math>(a^{\frac{p-1}{2}})^2 = a^{p-1} \equiv 1 \pmod{p}.</math>

よって <math>a^{\frac{p-1}{2}} \equiv -1 \equiv \left( \frac{a}{p} \right) \pmod{p}.</math>

以上より定理は証明される。

'''証明 2'''<br />
[[初等整数論/ユークリッドの互除法#定理 1.8|定理 1.8]] より、<math>A = \{ 0, a, 2a, \cdots , (p-1)a \}</math> は剰余系をなすので、この中の任意の数 <math>r</math> について <math>rs \equiv a \pmod{p}</math> となる <math>s \in A</math> がただ一つ存在する。これを <math>r</math> の'''配偶'''と呼ぶことにする。

ここで <math>\left( \frac{a}{p} \right) = 1</math> のとき <math>r</math> を <math>x^2 \equiv a \pmod{p}</math> の解とすれば、<math>r</math> の配偶はそれ自身である。また、

<math>(p-r)^2 = p^2 - 2pr + r^2 \equiv r^2 \pmod{p}</math> より <math>p-r</math> も方程式の解である。このとき <math>r = p-r</math> とすると <math>p = 2r</math> となり、奇素数であるという仮定に反する。したがって <math>r \neq p-r.</math>

[[初等整数論/合同式#合同方程式の基本定理|合同方程式の基本定理]]から、上の方程式の解を満たすもの、すなわち配偶が自身であるものは <math>r, p-r</math> の2つであり、他の <math>p-3</math> 個の数は2個ずつ配偶があって、それらの積は

<math>\equiv a^{\frac{p-3}{2}} \pmod{p}</math>

であるから、

<math>
\begin{align}
(p-1)! & \equiv r \cdot (p-r) \cdot a^{\frac{p-3}{2}} \\
& \equiv -r^2 \cdot a^{\frac{p-3}{2}} \\
& \equiv -a \cdot a^{\frac{p-3}{2}} = -a^{\frac{p-1}{2}} \pmod{p}. \\
\end{align}</math>

以上より <math>\left( \frac{a}{p} \right) = 1 \Rightarrow (p-1)! \equiv -a^{\frac{p-1}{2}} \pmod{p}</math>

次に <math>\left( \frac{a}{p} \right) = -1</math> のときは上の <math>r, p-r</math> のような数はないので配偶が <math>\frac{p-1}{2}</math> ペアできて

<math>(p-1)! \equiv a^{\frac{p-1}{2}} \pmod{p}</math>

<math>a = 1</math> は自明に前に属すので <math>(p-1)! \equiv -1 \pmod{p}</math>（すなわち[[初等整数論/フェルマーの小定理#ウィルソンの定理|ウィルソンの定理]]）。したがって、

*<math>\left( \frac{a}{p} \right) = 1 \Rightarrow a^{\frac{p-1}{2}} \equiv 1 \pmod{p}</math>
*<math>\left( \frac{a}{p} \right) = -1 \Rightarrow a^{\frac{p-1}{2}} \equiv -1 \pmod{p}</math>

これがオイラーの規準である。

== 平方剰余の相互法則 ==
<math>p, q</math> を相異なる奇素数としたときに

# <math>\left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}</math>
# <math>\left( \frac{-1}{p} \right) = (-1)^{\frac{p-1}{2}}</math>
# <math>\left( \frac{2}{p} \right) = (-1)^{\frac{p^2 - 1}{8}}</math>

2, 3 をそれぞれ'''第一補充法則'''、'''第二補充法則'''という。まずはそれぞれの意味を説明する。

1 は、<math>p, q</math> のどちらかが <math>4n + 1</math> の形のとき <math>\left( \frac{p}{q} \right) = \left( \frac{q}{p} \right)</math> で、どちらとも <math>4n + 3</math> の形のときに限り <math>\left( \frac{p}{q} \right) = - \left( \frac{q}{p} \right)</math> である、という意味である。

2 は、<math>x^2 \equiv -1 \pmod{p}</math> に解がある <math>\iff p \equiv 1 \pmod{4}</math>

3 は、<math>p = 8n + 1, \, 8n + 7</math> のとき <math>\left( \frac{p}{q} \right) = 1</math> で、<math>p = 8n + 3, \, 8n + 5</math> のとき <math>\left( \frac{p}{q} \right) = -1</math> である。つまり <math>x^2 \equiv 2 \pmod{p}</math> に解がある <math>\iff p \equiv 1, 7 \pmod{8}.</math> 

'''証明'''<br />
2 から証明する。

オイラーの規準より、<math>\left( \frac{-1}{p} \right) \equiv (-1)^{\frac{p-1}{2}} \pmod{p}.</math>

どちらも <math>\pm 1</math> の値を取り、<math>p</math> は奇素数なので <math>\left( \frac{-1}{p} \right) = (-1)^{\frac{p-1}{2}}.</math>

さて、3 であるが、これにはガウスの補題を用いる。

====== ガウスの補題 ======
<div style="padding: 20px; border: 1px #ccc solid;">
<math>\gcd (a, p) = 1</math> のとき、<math>A = \left\{ a, 2a, 3a, \cdots , \frac{p-1}{2} a \right\}</math> をそれぞれ <math>p</math> で割ったときの余りが <math>\frac{p}{2}</math> より大きい数が <math>n</math> 個あったとき、

<math>\left( \frac{a}{p} \right) = (-1)^n.</math>

'''証明'''<br />
ある数を <math>p</math> で割った余りが <math>\frac{p}{2}</math> よりも大きいならば、それから <math>p</math> を引くと <math>-\frac{p}{2}</math> よりも大きい負の余りを得る。つまり、絶対最小剰余である。上の <math>n</math> というのは負の絶対最小剰余の個数である。

<math>A</math> の任意の2つの数 <math>ax, ay \ (x \neq y)</math> について、

<math>(a, p) = 1, \ \frac{1-p}{2} \leqq x \pm y \leqq \frac{p+1}{2}</math> であり、<math>x \pm y \neq 0</math> より、<math>A</math> の中には絶対最小剰余として等しいもの、また絶対最小剰余として符号が逆なものも存在しない。すなわち全体として符号を無視すれば

<math>\left\{ 1, 2, 3, \cdots , \frac{p-1}{2} \right\}</math> に合同で、そのうち負の数の個数が <math>n</math> である。したがって

<math>a \cdot 2a \cdot 3a \cdots \frac{p-1}{2}a \equiv (-1)^n\cdot 1 \cdot 2 \cdot 3 \cdots \frac{p-1}{2}</math>

だが、 1, 2, ..., <math>\frac{p-1}{2}</math> はいずれも <math>p</math> と互いに素なので

<math>a^{\frac{p-1}{2}} \equiv (-1)^n</math>

を得る。オイラーの規準によって

<math>\left( \frac{a}{p} \right) \equiv (-1)^n \pmod{p}.</math>

どちらも <math>\pm 1</math> に等しく、<math>p</math> は奇素数なので

<math>\left( \frac{a}{p} \right) = (-1)^n.</math>

</div>

さて 3 の証明だが、

<math>2, 4, 6, \cdots , p-1</math>

の中で <math>\frac{p}{2}</math> より多いものの個数が <math>n</math> である。


(i) <math>p = 8n + 1</math> のとき

<math>\frac{p}{2} = 4n + \frac{1}{2}, \ p-1 = 8n</math> なので、この間にある偶数の数は <math>\frac{8n-4n}{2} = 2n</math> であり、<math>\left( \frac{2}{p} \right) = (-1)^{2n} = 1</math>

また <math>\frac{p^2-1}{8} = 8n^2 + 2n</math> より、<math>(-1)^{\frac{p^2-1}{8}} = 1</math> で、

<math>\left( \frac{2}{p} \right) = (-1)^{\frac{p^2-1}{8}}.</math>


(ii) <math>p = 8n + 3</math> のとき

<math>\frac{p}{2} = 4n + \frac{3}{2}, \ p-1 = 8n + 2</math> なので、この間にある偶数の数は <math>\frac{(8n + 2) - (4n + 2)}{2} + 1 = 2n + 1</math> であり、<math>\left( \frac{2}{p} \right) = (-1)^{2n + 1} = -1.</math>

また <math>\frac{p^2-1}{2} = 8n^2 + 6n + 1</math> より、<math>(-1)^{\frac{p^2-1}{8}} = -1</math> で、

<math>\left( \frac{2}{p} \right) = (-1)^{\frac{p^2-1}{8}}.</math>


(iii) <math>p = 8n + 5</math> のとき

<math>\frac{p}{2} = 4n + \frac{5}{2}, \ p-1 = 8n + 4</math> なので、この間にある偶数の数は <math>\frac{(8n+4) - (4n + 2)}{2} = 2n+1</math> であり、<math>\left( \frac{2}{p} \right) = (-1)^{2n + 1} = -1.</math>

また <math>\frac{p^2-1}{2} = 8n^2 + 10n + 3</math> より、<math>(-1)^{\frac{p^2-1}{8}} = -1</math> で、

<math>\left( \frac{2}{p} \right) = (-1)^{\frac{p^2-1}{8}}.</math>


(iv) <math>p = 8n + 7</math> のとき

<math>\frac{p}{2} = 4n + \frac{7}{2}, \ p-1 = 8n + 6</math> なので、この間にある偶数の数は <math>\frac{(8n+4) - (4n + 4)}{2} = 2n</math> であり、<math>\left( \frac{2}{p} \right) = (-1)^{2n} = -1.</math>

また <math>\frac{p^2-1}{2} = 8n^2 + 14n + 3</math> より、<math>(-1)^{\frac{p^2-1}{8}} = -1</math> で、

<math>\left( \frac{2}{p} \right) = (-1)^{\frac{p^2-1}{8}}.</math>


以上により 3 が証明される。


最後に相互法則であるが、[[初等整数論/平方剰余の相互法則の証明]]に譲る。

'''例 1''' <math>\left(\frac{31}{103}\right)</math> を求めよ。

相互法則より

<math>\left(\frac{31}{103}\right)=(-1)^{15\cdot 51} \left(\frac{103}{31}\right)=-\left(\frac{10}{31}\right)=-\left(\frac{2}{31}\right)\left(\frac{5}{31}\right)</math>

となる。ここで、第二補充法則と相互法則を用いて

<math>\left(\frac{2}{31}\right)=1, \left(\frac{5}{31}\right)=\left(\frac{31}{5}\right)=\left(\frac{1}{5}\right)=1</math>

を得るから

<math>\left(\frac{31}{103}\right)=-1</math>

とわかる。

'''例 2''' <math>p</math> が奇素数のとき

<math>\left(\frac{5}{p}\right) = \left(\frac{p}{5}\right) =
\begin{cases} 1 (p\equiv 1, 4\pmod{5}), \\ -1 (p\equiv 2, 3\pmod{5}) \end{cases}</math>

が成り立つ。

{{Nav}}

{{DEFAULTSORT:しよとうせいすうろん へきしようよ}}
[[Category:初等整数論|へきしようよ]]