つぎに、平方剰余に関する次の補題を証明する。これは「オイラーの基準」と呼ばれている。
補題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月号）
平方剰余の相互法則の証明（２）
まずこの補題を証明する。この補題は、平方剰余の相互法則だけではなく、いろいろな定理の補題としてよく使われる定理である。
補題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}\)で割り切れないからである。\(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})\)だから、。よって、\(g(x_{1})\equiv 0 \pmod p\)。つまり、\(x_{0}\)と異なる(1)の解は\(n-1\)次の合同方程式\(g(x)\equiv 0 \pmod p\)の解となる。ここで、帰納法の仮定を用い、(1)に高々\(n\)個の解しかないことがわかる。
平方剰余の相互法則の証明（１）
あ、最近整数論やってない…。
というわけで整数論の記事を書く。
今回はシリーズものにする。題して「平方剰余の相互法則シリーズ」である。
まず、平方剰余の相互法則を語るうえで必要な記号について説明する。
\(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\)である。
そして、平方剰余の相互法則がこちら。
この定理の完全な証明はガウスが与えた。
このシリーズでは、この定理の証明について解説する。
（参考：数学セミナー2016年2月号）
というわけで整数論の記事を書く。
今回はシリーズものにする。題して「平方剰余の相互法則シリーズ」である。
まず、平方剰余の相互法則を語るうえで必要な記号について説明する。
\(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\)である。
そして、平方剰余の相互法則がこちら。
\(p,q\)を互いに異なる奇素数とする。そのとき、
\[\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\]が成り立つ。
この定理の完全な証明はガウスが与えた。
このシリーズでは、この定理の証明について解説する。
（参考：数学セミナー2016年2月号）
広中杯2016トライアル受けてきた
広中杯2016トライアル受けてきた。
ファイナルは用事があるため残念ながらいけない。
問題を公表するのはなんかモラルに反しそうなので、やめておく。
I-(1)
「クマモトガンバレ」の文字が。問題作成者の声が聞こえた。
場合分けすれば簡単。
I-(2)
「1以下」を見落とすという大失態。
I-(3)
面積を使えば割と簡単に求められる。
（追記：ひどいうっかりミスをした）
I-(4)
え！？自明じゃない？
I-(5)
くっそめんどくさそうなので、6!=720と書いたが、間違っているのだろうか。
II-(1)
なんだこの条件は！？さすがに汚いだろ！？
しかし条件に近づけるようにして式変形させて解いた。
II-(2)
ひらめきが肝心。終了１０分前にひらめいた。
II-(3)
まためんどくさそうな問題。整数論だから解きたいなと。
自信のない解答を書いた。
II-(4)
これもめんどくさそう。やってない。
問題３
これも白紙。
点数はどうなるのか…。
追記（6/14)
解答が発表された。
本当にうっかりミスが痛い。
ファイナルは用事があるため残念ながらいけない。
問題を公表するのはなんかモラルに反しそうなので、やめておく。
I-(1)
「クマモトガンバレ」の文字が。問題作成者の声が聞こえた。
場合分けすれば簡単。
I-(2)
「1以下」を見落とすという大失態。
I-(3)
面積を使えば割と簡単に求められる。
（追記：ひどいうっかりミスをした）
I-(4)
え！？自明じゃない？
I-(5)
くっそめんどくさそうなので、6!=720と書いたが、間違っているのだろうか。
II-(1)
なんだこの条件は！？さすがに汚いだろ！？
しかし条件に近づけるようにして式変形させて解いた。
II-(2)
ひらめきが肝心。終了１０分前にひらめいた。
II-(3)
まためんどくさそうな問題。整数論だから解きたいなと。
自信のない解答を書いた。
II-(4)
これもめんどくさそう。やってない。
問題３
これも白紙。
点数はどうなるのか…。
追記（6/14)
解答が発表された。
本当にうっかりミスが痛い。
等角共役点の証明
等角共役点とはこのようなものだ。
等角共役点：三角形ABCと点 P がある。
角の頂点を通る直線 l と角の二等分線に関して対称な直線 m を l の等角共役線という。
AP,BP,CP の等角共役線は一点で交わり，これを P の等角共役点という。
この、「一点で交わる」という部分の証明はいろいろあるのだが、
ここでは先日思いついた証明を書く。
角度を円に対して使うことで、角度を辺の長さとして扱えることを用いた証明だ。
まず次の定理を証明する。
弦に対するチェバの定理
円周上の点A,B,C,D,E,Fに対し、直線AD,BE,CFがどれも点Xをとおるとき、
\[\frac{AB}{BC} \cdot \frac{CD}{DE} \cdot \frac{EF}{FA}=1\]
が成り立つ。
証明
\(\frac{AB}{DE}=\frac{XA}{XE},\frac{BC}{EF}=\frac{XC}{XE},\frac{CD}{FA}=\frac{XC}{XA}\)より
\(\frac{AB}{DE}\cdot \frac{BC}{EF}\cdot \frac{CD}{FA}=\frac{XA}{XE}\cdot \frac{XC}{XE}\cdot \frac{XC}{XA}=1\)
よって\(\frac{AB}{BC} \cdot \frac{CD}{DE} \cdot \frac{EF}{FA}=1\)がなりたつ。
ちなみに、これは逆も成り立つ。
では本題の証明。
弦に対するチェバの定理より、
\(\frac{BD}{DC} \cdot \frac{CF}{FA} \cdot \frac{AH}{HB}=1\)
また、弦に対する角が等しいからBD=EC,BE=DC,CG=FA,CF=GA,AI=HB,AH=IB
よって\(\frac{EC}{BE} \cdot \frac{GA}{CG} \cdot \frac{IB}{AI}=1\)
チェバの定理の逆より、AP,BP,CP の等角共役線は一点で交わる。□
この定理は意外と有用なので、知っておくべき。
等角共役点：三角形ABCと点 P がある。
角の頂点を通る直線 l と角の二等分線に関して対称な直線 m を l の等角共役線という。
AP,BP,CP の等角共役線は一点で交わり，これを P の等角共役点という。
この、「一点で交わる」という部分の証明はいろいろあるのだが、
ここでは先日思いついた証明を書く。
角度を円に対して使うことで、角度を辺の長さとして扱えることを用いた証明だ。
まず次の定理を証明する。
弦に対するチェバの定理
円周上の点A,B,C,D,E,Fに対し、直線AD,BE,CFがどれも点Xをとおるとき、
\[\frac{AB}{BC} \cdot \frac{CD}{DE} \cdot \frac{EF}{FA}=1\]
が成り立つ。
証明
\(\frac{AB}{DE}=\frac{XA}{XE},\frac{BC}{EF}=\frac{XC}{XE},\frac{CD}{FA}=\frac{XC}{XA}\)より
\(\frac{AB}{DE}\cdot \frac{BC}{EF}\cdot \frac{CD}{FA}=\frac{XA}{XE}\cdot \frac{XC}{XE}\cdot \frac{XC}{XA}=1\)
よって\(\frac{AB}{BC} \cdot \frac{CD}{DE} \cdot \frac{EF}{FA}=1\)がなりたつ。
ちなみに、これは逆も成り立つ。
では本題の証明。
弦に対するチェバの定理より、
\(\frac{BD}{DC} \cdot \frac{CF}{FA} \cdot \frac{AH}{HB}=1\)
また、弦に対する角が等しいからBD=EC,BE=DC,CG=FA,CF=GA,AI=HB,AH=IB
よって\(\frac{EC}{BE} \cdot \frac{GA}{CG} \cdot \frac{IB}{AI}=1\)
チェバの定理の逆より、AP,BP,CP の等角共役線は一点で交わる。□
この定理は意外と有用なので、知っておくべき。
円の反転とオイラーの不等式
オイラーの不等式とは、
三角形ABCにおいて、外接円の半径をR、内接円の半径をrとおくとR≧2rが成り立つ。
というものである。
これの円の反転を使ったきれいな証明を見つけたので、書いておく。
まず次の補題を使う。
補題：半径の等しい3つの円が1点で交わるとき、2つの円が交わる交点3つをとおる円は、元の3つの円の半径に等しい。
証明は略するが、図にヒントが書かれてあるので、参考にしてほしい。
では本題の証明。
三角形ABCの外接円を\(\Gamma_{1}\)、内接円を\(\Gamma_{2}\)とし、
\(\Gamma_{2}\)と辺BC,CA,ABの接点をそれぞれD,E,Fとする。
このとき\(\Gamma_{2}\)を反転円として辺BC,CA,ABを反転すると、
これらはそれぞれ点Iと点D,E,Fを直径とする円になる。（上図参照）
このとき円どうしの交点を上図のように名前を付けると、
点Aは点A'に、点Bは点B'に、点Cは点C'に対応される。
よって\(\Gamma_{2}\)を反転円として\(\Gamma_{1}\)を反転すると、
点A',B',C'をとおる円になる。
補題よりこの円の半径はr/2である。
これからR≧2rを示すのは割と簡単なので、考えてみてほしい。
三角形ABCにおいて、外接円の半径をR、内接円の半径をrとおくとR≧2rが成り立つ。
というものである。
これの円の反転を使ったきれいな証明を見つけたので、書いておく。
まず次の補題を使う。
補題：半径の等しい3つの円が1点で交わるとき、2つの円が交わる交点3つをとおる円は、元の3つの円の半径に等しい。
証明は略するが、図にヒントが書かれてあるので、参考にしてほしい。
では本題の証明。
三角形ABCの外接円を\(\Gamma_{1}\)、内接円を\(\Gamma_{2}\)とし、
\(\Gamma_{2}\)と辺BC,CA,ABの接点をそれぞれD,E,Fとする。
このとき\(\Gamma_{2}\)を反転円として辺BC,CA,ABを反転すると、
これらはそれぞれ点Iと点D,E,Fを直径とする円になる。（上図参照）
このとき円どうしの交点を上図のように名前を付けると、
点Aは点A'に、点Bは点B'に、点Cは点C'に対応される。
よって\(\Gamma_{2}\)を反転円として\(\Gamma_{1}\)を反転すると、
点A',B',C'をとおる円になる。
補題よりこの円の半径はr/2である。
これからR≧2rを示すのは割と簡単なので、考えてみてほしい。
ハフマン符号をExcelでやってみる
最近「なんでファイルが圧縮できるんだ？」って思ったので、
Wikipediaでいろいろ調べてみると、
「ハフマン符号」というものがあった。
ハフマン符号 - Wikipedia
どういうものかは上の記事を見てもらえばわかる。
やはり自分は
「Excelでやってみたいなあ」
と思った。
しかしコードを組んでいったところ
バグが大量発生し本当に大変だった。
どんなアルゴリズムでやったのかをまず説明する。
まず1と0からできた文字を、4けたごとに区切ってまとめる（つまり16進法にする）。
そうすると0から15までの整数の数列になる。
そして、0はいくつか、1はいくつか…と、0から15までの整数が
それぞれいくつあるかをカウントする。
まあここまでは下ごしらえだ。
そしてここからハフマン符号をつけていくのだが、
これが意外とプログラムを組むのがムズい。
ハフマン符号のつけ方はWikiに書いてあるが、これを実装するのがきつかった。
努力の結果、VBAソースコードが出来上がった。
ソースコード
バグが次から次へとあらわれたので、意外と時間がかかった。
Excelファイルも上げておく。
HuffmanCording.xlsm
前述のとおりこれは圧縮するために用いるものだ。
このファイルでいろいろ実験してみると、
0と1の偏りが大きい場合によく圧縮されるということが分かった。
Wikipediaでいろいろ調べてみると、
「ハフマン符号」というものがあった。
ハフマン符号 - Wikipedia
どういうものかは上の記事を見てもらえばわかる。
やはり自分は
「Excelでやってみたいなあ」
と思った。
しかしコードを組んでいったところ
バグが大量発生し本当に大変だった。
どんなアルゴリズムでやったのかをまず説明する。
まず1と0からできた文字を、4けたごとに区切ってまとめる（つまり16進法にする）。
そうすると0から15までの整数の数列になる。
そして、0はいくつか、1はいくつか…と、0から15までの整数が
それぞれいくつあるかをカウントする。
まあここまでは下ごしらえだ。
そしてここからハフマン符号をつけていくのだが、
これが意外とプログラムを組むのがムズい。
ハフマン符号のつけ方はWikiに書いてあるが、これを実装するのがきつかった。
努力の結果、VBAソースコードが出来上がった。
ソースコード
バグが次から次へとあらわれたので、意外と時間がかかった。
Excelファイルも上げておく。
HuffmanCording.xlsm
前述のとおりこれは圧縮するために用いるものだ。
このファイルでいろいろ実験してみると、
0と1の偏りが大きい場合によく圧縮されるということが分かった。
