2016-08-24

平方剰余の相互法則の証明（６）

整数論

これがラスト。

更新が遅れてしまったが、
平方剰余の相互法則を証明しよう。

$p,q$を互いに異なる奇素数とする。そのとき、
\[\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\]が成り立つ。

これは格子を使った照明が一番簡明である。

上の図の正方格子において$x$軸上に$OA=\frac{p+1}{2}$を、$y$軸上に$OB=\frac{q+1}{2}$をとって長方形$OACB$の内部の格子点を考察する。いま、直線$\frac{y}{x}=\frac{q}{p}$を$OL$とする。横線$OM=x$に対応する$OL$上の点を$P$とすれば、$MP=\frac{qx}{p}$。
ゆえに$x$を$1,2,\cdots,\frac{p-1}{2}$とするとき、$qx$を$p$で割った剰余が$\frac{p}{2}$よりも大きいのは、$\frac{qx}{p}$の分数部分が$\frac{1}{2}$よりも大きいときで、すなわち$P$を通る縦線上で$P$から$\frac{1}{2}$の距離にある格子点が$OL$の上側にあるときに限る。ゆえに$\left(\frac{q}{p}\right)=(-1)^n$における$n$は$OL$とそれを$y$軸の向きに$\frac{1}{2}$だけ平行に移動した$GG'$とにはさまれる平行四辺形$OGG'L$の内部にある格子点の数である。
同様に$\left(\frac{p}{q}\right)=(-1)^m$における$m$は$OL$とそれを$x$軸の向きに$\frac{1}{2}$だけ平行に移動した$HH'$とにはさまれる平行四辺形$OHH'L$の内部にある格子点の数である。
すなわち$\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1)^{m+n}$における$m+n$はこれら2つの平行四辺形の内部にある格子点の総数であるが、図に示すように格子点$C\left(\frac{p+1}{2},\frac{q+1}{2}\right)$を一頂点とする、一辺が$\frac{1}{2}$である小正方形 ${CG'LH'}$ を付け加えて六角 ${OGG'CH'H}$ を作れば、その内部にある格子点の数はやはり$m+n$である。
さて$OC$の中点$\left(\frac{p+1}{4},\frac{q+1}{4}\right)$はこの六角形の対称の中心で、格子点はこの点に関して2つずつ互いに対称であることは作図によって明白である。ゆえに$m+n$が奇数であるか、偶数であるかは、中心$\left(\frac{p+1}{4},\frac{q+1}{4}\right)$それ自身が格子点であるか、または格子点でないかによって決定される。
ゆえに$\frac{p+1}{4},\frac{q+1}{4}$がともに整数、すなわち$p,q$がともに$4t-1$の形の素数であるときに限って、$m+n$が奇数、したがって
\[\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=-1\]
である。すなわち平方剰余の相互法則が証明された。
あるいはまた三角形$GG'B,HH'A$は同数の格子点を含むから、それを$k$とすれば、長方形$OACB$の内部の格子点の総数は$m+n+2k$である。しかるに長方形の内部には明らかに
\[\frac{p+1}{2}\cdot\frac{q+1}{2}\]
の格子点があるから
\[\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1)^{m+n}=(-1)^{m+n+2k}=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\]

（参考：初等整数論講義）

2016-07-30

広中杯2016ファイナル3問目

幾何

この問題、本番では全然解けず、
しかし家でやってみたら解けてしまったという
悔しい問題。

問題
へこみのない四角形ABCDの対角線ACとBDは点Eにおいて垂直に交わっていて、
∠EBC=12°, ∠EAB=∠CDE=33°, BE+EC=1
となっている。
このとき、△ABEの面積と△CDEの面積の差を求めよ。

この問題は、BE+EC=1という条件をどのように使うかが難しい。
とある有名問題に結び付けられるか。
（この解き方はほんの一例。）

解答

辺BDを軸として点Cに対称な点をPとする。
そして、辺AB上に∠BPQ=90°となる点Qをとる。

このとき、簡単な計算で∠PBQ=45°がわかるので、
△BPQは直角二等辺三角形である。よってBP=PQ。
また、BC=BPより、BC=PQである。

そして、簡単な計算で∠APQ=∠DBC=12°、
∠AQP=∠DCB=135°がなので、
BC=PQとあわせると、△AQP≡△DCBということがわかる。

ここで、△ABEの面積と△CDEの面積の差は
△ABCの面積と△DBCの面積の差に等しく、
それは四角形QBCPの面積に等しい。（△AQP≡△DCBより）

では次に、四角形QBCPの面積を求めるのだが、
これは有名問題の変化形である。

その有名問題というのが、

略解はこれ。こたえは1/4である。

もうわかっただろう。四角形QBCPの面積は、1/2である。
有名問題の図形を2倍にしたものであることがわかるだろう。

というわけで、こたえは1/2である。

2016-07-16

平方剰余の相互法則の証明（５）

整数論

今回は平方剰余の相互法則を証明する前に、補充法則を証明する。

第１補充法則
\[\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}\]
第２補充法則
\[\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}\]
また、これは名前がついているかわからないのだが、重要な定理。
（一応、ここでは「平方剰余の積の法則」とでも呼んでおこう。）
\[\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\]

それぞれの証明を見ていこう。

第１補充法則

補題２（オイラーの基準）より明らか。（$n=-1$を代入すれば直ちに得られる。）

第２補充法則

$2,4,6,\cdots ,p-5,p-3,p-1$のうち$\frac{p}{2}$より大きいものの個数を$n$とすると、
$n$は$1,3,5,\cdots$の中で$\frac{p}{2}$より小さいものの個数にもなる。
補題３（ガウスの予備定理）より、（$a=2$を代入）
$n$の奇遇が判定できれば、$\left(\frac{2}{p}\right)$が求められる。
$1,3,5,\cdots$はすべて奇数なので、
$1+3+5+\cdots +\frac{p-1}{2}$が偶数ならば、$n$は偶数となり、
$1+3+5+\cdots +\frac{p-1}{2}$が奇数ならば、$n$は奇数となる。
$1+3+5+\cdots +\frac{p-1}{2}=\frac{1}{2} \frac{p-1}{2} \left(\frac{p-1}{2}+1\right)=\frac{p^2-1}{8}$
より、$\frac{p^2-1}{8}$と$n$の奇遇は一致する。
よって
\[\left(\frac{2}{p}\right)=(-1)^n=(-1)^{\frac{p^2-1}{8}}\]

平方剰余の積の法則

これも補題２（オイラーの基準）より明らかである。
\[\left(\frac{ab}{p}\right)\equiv (ab)^\frac{p-1}{2} =a^\frac{p-1}{2} b^\frac{p-1}{2}\equiv \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\]また一番左の辺と一番右の辺は両方$\pm 1$だから、
\[\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\]

2016-07-09

平方剰余の相互法則の証明（４）

整数論

補題3（ガウスの予備定理）
$p$を奇素数、$(a,p)=1$とする。このとき
\[1\cdot a,2\cdot a,\cdots ,\frac{p-1}{2}\cdot a\]
のうち、$p$で割った余りが$\frac{p}{2}$より大きいものの個数を$n$とするとき、
\[\left(\frac{a}{p}\right)=(-1)^n\]
が成立する。

証明
$1\cdot a,2\cdot a,\cdots ,\frac{p-1}{2}\cdot a$の各々を$p$で割った余りを$r$とすると、$0\leq r<p$である。そこで、$\frac{p}{2}<r<p$なら$r-p=r'$,$0\leq r \leq \frac{p}{2}$なら$r=r'$とおけば、$-\frac{p}{2}<r \leq \frac{p}{2}$である。この$r'$を絶対値最小の余りという。したがって、$n$は$r'$が負であるようなものの個数と一致する。そこで、
\[A=\{a,2a,\cdots,\frac{p-1}{2}a\},\]
\[B=\{\pm 1,\pm 2,\cdots,\pm \frac{p-1}{2}\}\]
とおく。$A,B$はともに、$p$と互いに素で法$p$に関して互いに合同でない数からなっている。したがって、$A$の各元は$B$のただ１つの元と$p$を法として合同であり、$A$の元$ka$が$B$の元$b$と合同なら$-b$と合同な$A$の元は存在しない。実際、
\[ka\equiv b, la\equiv -b,\]
\[1\leq k,l \leq \frac{p-1}{2}\]
ならば、$(k+l)a\equiv 0$で$(a,p)=1$だから、$k+l\equiv 0$。これは、$2\leq k+l\leq p-1$に反する。よって、
\[a\cdot 2a\cdot \cdots \cdot \frac{p-1}{2}a\equiv (-1)^n 1\cdot 2\cdot \cdots \cdot \frac{p-1}{2}\]
つまり
\[\left(\frac{p-1}{2}\right)!a^{\frac{p-1}{2}}\equiv (-1)^n \left(\frac{p-1}{2}\right)\]
ここで、$\left(\left(\frac{p-1}{2}\right)!,p\right)$だから、
\[a^{\frac{p-1}{2}}\equiv (-1)^n\]
一方、補題２より、$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}$であったから、両者をあわせて
\[\left(\frac{a}{p}\right)\equiv (-1)^n\]
が成立し、$p$は奇素数だから結論を得る。
（参考：数学セミナー2016年2月号）

2016-06-28

平方剰余の相互法則の証明（３）

整数論

つぎに、平方剰余に関する次の補題を証明する。これは「オイラーの基準」と呼ばれている。
補題2
\[\left(\cfrac{a}{p}\right)\equiv a^{\frac{p-1}{2}} \pmod p\]
これはかなりきれいな式といえるだろう。

証明
以下、合同式はすべて $p$ を法としたものである。

$A=\{1,2,\cdots ,p-1\}$ とおく。

補題1.1より、 $r\in A$ に対し $sr\equiv a$ となる $A$ の元 $s$ がただ1つある。

また、 $r\cdot r^{-1}\equiv 1$ となる $A$ の元 $r^{-1}$ も存在するため、
$A$ の元 $k,l$ が $kr\equiv lr$ を満たすとき、
$krr^{-1}\equiv lrr^{-1}$ より $k\equiv l$ である。

よって、対応 $r\mapsto s$ は単射である。この $s$ と $r$ を互いの同伴数と呼ぶ。

(1)
$\left(\frac{a}{p}\right)=1$ のとき、 $x^2\equiv a$ は解 $x=r$ をもつ。
このことは、 $r$ が $r$ 自身と同伴であることを示す。
$(p-r)^2\equiv a$ だから、 $p-r$ も自分自身と同伴である。
$r$ と $p-r$ は $p$ を法として合同でないから、
補題1より、２次合同方程式 $x^2\equiv a$ の解は $r$ と $p-r$ の２個のみである。
したがって、 $A$ の元の残り $p-3$ 個は互いに同伴なものの組に分かれる。ゆえに
\begin{eqnarray}
1\cdot2\cdot\cdots\cdot(p-1)=(p-1)!&\equiv& r(p-r)a^{\frac{p-3}{2}}
&\equiv&-a^{\frac{p-1}{2}}
\end{eqnarray}
となる。よって
$(p-1)!\equiv -a^{\frac{p-1}{2}}$

(2)
$\left(\frac{a}{p}\right)=-1$ のとき、 $x^2\equiv a$ は解をもたないから、(1)と同様にして
$(p-1)!\equiv a^{\frac{p-1}{2}}$

ここで、 $\left(\frac{1}{p}\right)=1$ だから(1)より $(p-1)!\equiv -1$
よって、 $\left(\frac{a}{p}\right)=1$ なら $a^{\frac{p-1}{2}}\equiv 1$ 、 $\left(\frac{a}{p}\right)=-1$ なら $a^{\frac{p-1}{2}}\equiv -1$ となり結論を得る。
（参考：数学セミナー2016年2月号）

2016-06-24

平方剰余の相互法則の証明（２）

整数論

まずこの補題を証明する。この補題は、平方剰余の相互法則だけではなく、いろいろな定理の補題としてよく使われる定理である。

補題1：$p$を素数とする。そのとき、$n$次合同方程式
\[f(x)\equiv 0 \pmod p　\hspace{1cm}\cdots (1) \]は解をもってもその個数は$n$個以下である。

この証明に次の補題を使う。（補題の補題ってなんなんだ…。）

補題1.1:$a$と$m$が互いに素なとき、1次合同方程式
\[ax \equiv b \pmod m\]はただ1つの解を持つ。

証明:$a$と$m$が互いに素だから$ax_{0}+my_{0}=1$となる$x_{0},y_{0} \in \mathbb{Z}$がある。(この記事参照。)よって、
\[a\cdot bx_{0}-b=m\cdot (-by_{0})\]
したがって、$x=bx_{0}$は$ax \equiv b \pmod m$の解である。
$x_{1},x_{2}$を$ax \equiv b \pmod m$の2つの解とすると、$ax_{1} \equiv ax_{2} \pmod m$。
ここで、$a$と$m$が互いに素だから$x_{1} \equiv x_{2} \pmod m$となる。

補題1の証明

$n$に関する帰納法で示す。まず、
\[f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{0}\]とすれば、$p$は$a_{n}$で割り切れないから ${(p,a_{n})=1}$ である。$n=1$のときは、補題1.1より正しい。つぎに(1)が解$x_{0}$を持ったとする。このとき、
\[f(x)=(x-x_{0})g(x)+f(x_{0})\]ここで、$g(x)$は$a_{n}x^{n-1}$を最高次の項とする$n-1$次の整数係数の多項式を表す。したがって、(1)は次の合同方程式
\[(x-x_{0})g(x)\equiv 0 \pmod p\]と同一の解をもつ。そこで、(1)に$x_{0}$と異なる解がなければそれで補題は成立するので、$x_{0}$と異なる解$x_{1}$があったとする。そのとき、
\[(x-x_{0})g(x_{1})\equiv 0 \pmod p\]$p \mid \hspace{-.67em}/ (x_{1}-x_{0})$だから、 ${(p,(x_{1}-x_{0}))=1}$ 。よって、$g(x_{1})\equiv 0 \pmod p$。つまり、$x_{0}$と異なる(1)の解は$n-1$次の合同方程式$g(x)\equiv 0 \pmod p$の解となる。ここで、帰納法の仮定を用い、(1)に高々$n$個の解しかないことがわかる。

□

（参考：数学セミナー2016年2月号）

2016-06-18

平方剰余の相互法則の証明（１）

整数論

あ、最近整数論やってない…。
というわけで整数論の記事を書く。

今回はシリーズものにする。題して「平方剰余の相互法則シリーズ」である。

まず、平方剰余の相互法則を語るうえで必要な記号について説明する。

$p$を奇素数、$a$を$p$と互いに素な整数とする。2次の合同方程式
\[x^2\equiv a \pmod p\]が解を持つとき、$a$は$p$を法として平方剰余であるといい、
$\left(\frac{a}{p}\right)=1$と書く。
そうでないときは、$a$は$p$を法として平方非剰余であるといい、
$\left(\frac{a}{p}\right)=-1$と書く。
この記号$\left(\frac{a}{p}\right)$をルジャンドルの平方剰余記号という。

たとえば、2次合同方程式$x^2\equiv 4 \pmod 5$は、
$x\equiv 2,4$という解があるため、$\left(\frac{4}{5}\right)=1$である。
2次合同方程式$x^2\equiv 3 \pmod 5$は解をもたないため、
$\left(\frac{3}{5}\right)=-1$である。

そして、平方剰余の相互法則がこちら。