数学徘徊記

自由な数学ブログ。

平方剰余の相互法則の証明(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}\)で割り切れないから{(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月号)

平方剰余の相互法則の証明(1)

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

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


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

\(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)
ひらめきが肝心。終了10分前にひらめいた。

II-(3)
まためんどくさそうな問題。整数論だから解きたいなと。
自信のない解答を書いた。

II-(4)
これもめんどくさそう。やってない。

問題3
これも白紙。

点数はどうなるのか…。


追記(6/14)
解答が発表された。
本当にうっかりミスが痛い。

等角共役点の証明

等角共役点とはこのようなものだ。

等角共役点:三角形ABCと点 P がある。
角の頂点を通る直線 l と角の二等分線に関して対称な直線 m を l の等角共役線という。
AP,BP,CP の等角共役線は一点で交わり,これを P の等角共役点という。
kyoyaku1

この、「一点で交わる」という部分の証明はいろいろあるのだが、
ここでは先日思いついた証明を書く。

角度を円に対して使うことで、角度を辺の長さとして扱えることを用いた証明だ。

まず次の定理を証明する。
弦に対するチェバの定理
円周上の点A,B,C,D,E,Fに対し、直線AD,BE,CFがどれも点Xをとおるとき、
\[\frac{AB}{BC} \cdot \frac{CD}{DE} \cdot \frac{EF}{FA}=1\]
が成り立つ。

証明kyoyaku3
\(\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\)がなりたつ。

ちなみに、これは逆も成り立つ。


 では本題の証明。
kyoyaku2
弦に対するチェバの定理より、
\(\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つの円の半径に等しい。
kyoei2
証明は略するが、図にヒントが書かれてあるので、参考にしてほしい。

では本題の証明。
BlogPaint
三角形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の偏りが大きい場合によく圧縮されるということが分かった。

2015ジュニア広中杯の問題について

2015年ジュニア広中杯の問題4番。
2015の倍数で、どの桁の数字も奇数であるものを一つ求めよ。ただし、12桁以内のものに限る。
という問題があった。

答えを言ってしまうと、最少は155155(=2015x77)、次は179335(=2015x89)である。
この問題、桁数を8桁までとしても252個あるので、
答えはものすごくたくさんあり、いい問題とは言えない。

しかしこのように一般化して考えるとおもしろい。
任意の奇数nの倍数で、どの桁の数字も奇数であるものは存在するか?

この問題の回答では、任意の奇数nの倍数で、どの桁の数字も奇数であるものの上界が
低ければ低い解答ほど、なおよいのだが。

まあ考えてみよう。
実はこの問題、問題文で「奇数」を「偶数」と変えた問題のほうは簡単である。
2k以下の任意の自然数nの倍数で、k桁以下でどの桁の数字も偶数であるものが存在することが簡単に示せる。
たとえばk=2の場合、次のような数の集合を考える。
{88,68,66,46,44,24,22,2,0}
鳩ノ巣原理より、nのあまりは9個あるので互いに等しいものが存在する。
その2つの差をとればnの倍数となるが、これはどの桁の数字も偶数である。
よって示せた。この方法はkがどのような値でも使える。

しかし奇数で同じ方法を使おうとすると、うまくいかない。
5の倍数でないのなら、
1,11,111,…のなかに必ずnの倍数はあるのだが、
5の倍数のときもうまくいくうまい方法はあるのか…。

一応数表作ってみた。
数表

何かわかったらコメントお願いします。