非専門的シンギュラリティー研究所

無限に動き続けるシステムを表す方法を AI なども使って考えていきます。

証明路開発支援システム(17)

証明路開発支援システム

「平方剰余の相互法則(3)」をツリーのように書き直します。

「平方剰余の相互法則(3) - 非専門的シンギュラリティー研究所」より

F_p^* = \{1, 2, 3, … , p-1\} は巡回群になります。 r を F_p^* の生成元とします。 F_p^* = \{r^i | i = 0, 1, 2, … , p-2\}、 r^{ \frac{p-1}{2} }= -1 となります。

【ガウスの補題】

F_p^* の部分集合 \{1, 2, 3, … , \frac{p-1}{2}\} を S とおきます。 a を S の元とすると、

  • ax∈F_p^*-S となるような x∈S の個数が偶数 ⇔ a は法 p に関する平方剰余

[証明]

  • f: F_p^*→\{0, 1\} を
    • x∈S のとき f(x) = 0、
    • そうでないとき f(x) = 1
    とします。
  • g: F_p^*→S を
    • x∈S のとき g(x) = x、
    • そうでないとき g(x) = -x
    とします。
  • すると
    • x = (-1)^{f(x)}・g(x)、
    • g(x) = (-1)^{f(x)}・x
    となります。
  • h: S→S を h(x) = g(ax) とおくと h は全単射となります。
    • なぜなら h(x) = h(y) とすると
      • g(ax) = g(ay)、
      • (-1)^{f(ax)}・ax = (-1)^{f(ay)}・ay、
      • (-1)^{f(ax)-f(ay)}・ax = ay
      x, y \in S なので f(ax) = f(ay) かつ x = y となります。
    • h は単射となります。 S は有限集合なので h は全単射となります。
  • よって \displaystyle \prod_{x \in S} g(ax) = \prod_{x \in S} x となります。
  • よって
    \displaystyle \prod_{x \in S} ax = \prod_{x \in S} \left( (-1)^{f(ax)}・g(ax) \right) = \prod_{x \in S} \left( (-1)^{f(ax)} \right)・\prod_{x \in S} g(ax) = \prod_{x \in S} \left( (-1)^{f(ax)} \right)・\prod_{x \in S} x
    となります。
  • よって
    \displaystyle \prod_{x \in S} \left( (-1)^{f(ax)} \right) = \left(\prod_{x \in S} ax \right)/\left(\prod_{x \in S} x \right) = a^{\frac{p-1}{2}}
    となります。
  • F_p^* の元 x に対して x = r^{e(x)} となるように e(x) を決めます。
  • \displaystyle \prod ( (-1)^{f(ax)}) = a^{\frac{p-1}{2}} = (r^{e(a)})^{\frac{p-1}{2}} = (r^{\frac{p-1}{2}})^{e(a)} = (-1)^{e(a)} となります。
  • よって
    \{x∈S | f(ax) = 1\} の元の個数が偶数 ⇔ e(a) は偶数
    となって主張が成り立ちます。
[証明終わり]

【平方剰余の相互法則】

p, q が 2ではない異なる素数のとき、 \left(\cfrac{q}{p}\right) \left(\cfrac{p}{q}\right) = (-1)^{ \frac{(p-1)(q-1)}{4} }
が成り立ちます。

[証明]
「整数論」(共立講座 21世紀の数学)のやり方で証明します。縦に x = 1, 2, … , \frac{p-1}{2}、横に y = 1, 2, … , \frac{q-1}{2} をとって格子の位置に以下の記号を記入します。

  • ■は \frac{q}{p}x < y < \frac{q}{p}x + \frac{1}{2}
  • ▲は \frac{p}{q}y < x < \frac{p}{q}y + \frac{1}{2}
  • □は y > \frac{q}{p}x + \frac{1}{2}
  • △は x > \frac{p}{q}y + \frac{1}{2}

の位置に記入します。