エレファント・コンピューティング調査報告

極限に関する順序を論理プログラミングの手法を使って指定することを目指すブロクです。

平方剰余の相互法則(6)

前回の【命題2】を前に使った図を使って見ていきます。

【命題2】

 p q 2ではない異なる素数のとき、
 \begin{eqnarray*}
 & & \left[\cfrac{q}{p}\right] + \left[2 \cdot \cfrac{q}{p}\right] + \cdots + \left[\cfrac{p-1}{2} \cdot \cfrac{q}{p}\right] \\
 & & + \left[\cfrac{p}{q}\right] + \left[2 \cdot \cfrac{p}{q}\right] + \cdots + \left[\cfrac{q-1}{2} \cdot \cfrac{p}{q}\right] \\
 & = & \cfrac{(p-1)(q-1)}{4}
\end{eqnarray*}
が成り立ちます。

図は  p = 23,  q = 17

01 △▲[017/23] = 00 △▲■[017/23+1/2] = 01 ■[017/23+1/2]-[017/23] = 01
02 △▲[034/23] = 01 △▲■[034/23+1/2] = 01 ■[034/23+1/2]-[034/23] = 00
03 △▲[051/23] = 02 △▲■[051/23+1/2] = 02 ■[051/23+1/2]-[051/23] = 00
04 △▲[068/23] = 02 △▲■[068/23+1/2] = 03 ■[068/23+1/2]-[068/23] = 01
05 △▲[085/23] = 03 △▲■[085/23+1/2] = 04 ■[085/23+1/2]-[085/23] = 01
06 △▲[102/23] = 04 △▲■[102/23+1/2] = 04 ■[102/23+1/2]-[102/23] = 00
07 △▲[119/23] = 05 △▲■[119/23+1/2] = 05 ■[119/23+1/2]-[119/23] = 00
08 △▲[136/23] = 05 △▲■[136/23+1/2] = 06 ■[136/23+1/2]-[136/23] = 01
09 △▲[153/23] = 06 △▲■[153/23+1/2] = 07 ■[153/23+1/2]-[153/23] = 01
10 △▲[170/23] = 07 △▲■[170/23+1/2] = 07 ■[170/23+1/2]-[170/23] = 00
11 △▲[187/23] = 08 △▲■[187/23+1/2] = 08 ■[187/23+1/2]-[187/23] = 00
□■[023/17] = 01 □■▲[023/17+1/2] = 01 ▲[023/17+1/2]-[023/17] = 00
□■[046/17] = 02 □■▲[046/17+1/2] = 03 ▲[046/17+1/2]-[046/17] = 01
□■[069/17] = 04 □■▲[069/17+1/2] = 04 ▲[069/17+1/2]-[069/17] = 00
□■[092/17] = 05 □■▲[092/17+1/2] = 05 ▲[092/17+1/2]-[092/17] = 00
□■[115/17] = 06 □■▲[115/17+1/2] = 07 ▲[115/17+1/2]-[115/17] = 01
□■[138/17] = 08 □■▲[138/17+1/2] = 08 ▲[138/17+1/2]-[138/17] = 00
□■[161/17] = 09 □■▲[161/17+1/2] = 09 ▲[161/17+1/2]-[161/17] = 00
□■[184/17] = 10 □■▲[184/17+1/2] = 11 ▲[184/17+1/2]-[184/17] = 01

■は  qx/p < y < qx/p + 1/2
▲は  py/q < x < py/q + 1/2
□は  y > qx/p + 1/2
△は  x > py/q + 1/2

 p, q は異なる素数 x = 1, 2, 3, … , p-1 y = 1, 2, 3, … , q-1 として  qx/p = y とすると、 qx = py となり、 x p の倍数、 y q の倍数になってしまいます。 y = qx/p + 1/2 とすると、 2py = 2qx + p となり、 x p の倍数になってしまいます。 qx/p = y となることも  y = qx/p + 1/2 となることもありません。 x y p q を入れ替えて考えると  py/q = x となることも  x = py/q + 1/2 となることもありません。
 qx/p ≦ y ≦ qx/p + 1/2
 py/q ≦ x ≦ py/q + 1/2
 y ≧ qx/p + 1/2
 x ≧ py/q + 1/2
で上の長方形のすべての場所を埋めることができることはすぐにわかりますが、=の場合は起こらないので
■:  qx/p < y < qx/p + 1/2
▲:  py/q < x < py/q + 1/2
□:  y > qx/p + 1/2
△:  x > py/q + 1/2
で上の長方形のすべての場所を埋めることができます。

△と▲の合計の個数は、 py/q < x となるものの個数ですから、各  x に対しては  y < qx/p である  y、すなわち  y 1, 2, 3, … , [qx/p] [qx/p] 個となります。

△と▲と■の合計の個数は、 y < qx/p + 1/2 となるものの個数ですから、各  x に対しては  y < qx/p + 1/2 である  y、すなわち  y 1, 2, 3, … , [qx/p + 1/2] [qx/p + 1/2] 個となります。

□と■の合計の個数は、 qx/p < y となるものの個数ですから、各  y に対しては  x < py/q である  x、すなわち  x 1, 2, 3, … , [py/q] [py/q] 個となります。

□と■と▲の合計の個数は、 x < py/q + 1/2 となるものの個数ですから、各  y に対しては  x < py/q + 1/2 である  x、すなわち  x 1, 2, 3, … , [py/q + 1/2] [py/q + 1/2] 個となります。

△と▲の合計の個数は  \left[\cfrac{q}{p}\right] + \left[2 \cdot \cfrac{q}{p}\right] + \cdots + \left[\cfrac{p-1}{2} \cdot \cfrac{q}{p}\right] 個、
□と■の合計の個数は  \left[\cfrac{p}{q}\right] + \left[2 \cdot \cfrac{p}{q}\right] + \cdots + \left[\cfrac{q-1}{2} \cdot \cfrac{p}{q}\right]
となります。
△と▲と□と■の合計の個数は長方形の全体なので、 \cfrac{(p-1)(q-1)}{4} 個、
よって
 \begin{eqnarray*}
 & & \left[\cfrac{q}{p}\right] + \left[2 \cdot \cfrac{q}{p}\right] + \cdots + \left[\cfrac{p-1}{2} \cdot \cfrac{q}{p}\right] \\
 & & + \left[\cfrac{p}{q}\right] + \left[2 \cdot \cfrac{p}{q}\right] + \cdots + \left[\cfrac{q-1}{2} \cdot \cfrac{p}{q}\right] \\
 & = & \cfrac{(p-1)(q-1)}{4}
\end{eqnarray*}
となります。

続いて上の図と「ガウス補題」について
ガウス補題」により
■の個数が偶数 ⇔  \left(\cfrac{q}{p}\right) = 1
▲の個数が偶数 ⇔  \left(\cfrac{p}{q}\right) = 1
よって
■の個数と▲の個数の合計が偶数 ⇔  \left(\cfrac{q}{p}\right) \left(\cfrac{p}{q}\right) = 1
となっていました。
■の個数と▲の個数の合計
 \begin{eqnarray*}
 & = & \left[\cfrac{q}{p} + \cfrac{1}{2} \right] + \left[2 \cdot \cfrac{q}{p} + \cfrac{1}{2} \right] + \cdots + \left[\cfrac{p-1}{2} \cdot \cfrac{q}{p} + \cfrac{1}{2} \right] \\
 & & - \left( \left[\cfrac{q}{p}\right] + \left[2 \cdot \cfrac{q}{p}\right] + \cdots + \left[\cfrac{p-1}{2} \cdot \cfrac{q}{p}\right] \right) \\
 & & + \left[\cfrac{p}{q} + \cfrac{1}{2} \right] + \left[2 \cdot \cfrac{p}{q} + \cfrac{1}{2} \right] + \cdots + \left[\cfrac{q-1}{2} \cdot \cfrac{p}{q} + \cfrac{1}{2} \right] \\
 & & - \left( \left[\cfrac{p}{q}\right] + \left[2 \cdot \cfrac{p}{q}\right] + \cdots + \left[\cfrac{q-1}{2} \cdot \cfrac{p}{q}\right] \right)
\end{eqnarray*}
ですが、これを図で考えるとどうなるのかはよくわかりません。

この証明は本に従って書いたと思うのですがよくわからない部分があるので今後考えてみたいと思います。