2016-11-30

ブログ移転しました。

ブログをlivedoorからhatenaに移転しました。
引き続きよろしくお願いします。

2016-11-13

問題コーナー（第2回）解答

問題コーナー幾何

では解答発表です。

三角形$ABC$の外心を$O$とし、辺$BC,CA,AB$の中点をそれぞれ$M_A,M_B,M_C$とする。
このとき三角形$AOM_A,BOM_B,COM_C$の外接円は点$O$以外の1点で交わることを示せ。

円に関する反転を用いた解法です。

点$M_A,M_B,M_C$をそれぞれ三角形$ABC$の外接円で反転させます。
このとき、点$M_A,M_B,M_C$はそれぞれ図の点$A',B',C'$に移ります。
（点$A',B',C'$は、直線$B'C',C'A',A'B'$がそれぞれ点$A,B,C$で三角形$ABC$の外接円に接するような点）

なぜなら、たとえば$M_A$に注目するとき、
$\angle OM_AB=\angle OAB$より$\triangle OM_AB\simeq \triangle OAB$だから
$OM_A\cdot OA'=OB^2$となるからです。 $M_A,M_B$についても同様です。

よって、三角形$AOM_A,BOM_B,COM_C$の外接円は、反転によって
それぞれ直線$AA',BB'CC'$に移ります。

そして、
\[\frac{A'B}{BB'} \cdot \frac{B'A}{AC'} \cdot \frac{C'C}{CA'} = 1\]
であるので、チェバの定理の逆により、この3つの直線は1点で交わります。

よって、反転する前の元の図形、三角形$AOM_A,BOM_B,COM_C$の外接円は1点で交わります。

2016-10-18

マスターデーモンに挑戦

整数論

数学界で「マスターデーモン」というともうあれしかない、恐ろしい奴です。

1990 IMO 問3

$\cfrac{2^n+1}{n^2}$が整数となるような1より大きい整数$n$をすべて求めよ。

見た目はシンプルで、中学生も簡単に理解できる問題なのに、
世界中の高校生を悩ませた、デーモン的な存在。

これの攻略をしていきます。

思考過程

まずは、$n$に$2,3,4,5,\cdots$と代入していきます。

そうすると、$n$が偶数だとダメだということが見えてきます。（分子が奇数、分母が偶数となるため）

$n=15$くらいまで計算しても、$n=3$のときしか整数とならないので、

これが答えかな…？という見当をつけておきます。

しかし分母が$n^2$というのは考えにくいなあ。。。

ここで

su-hai.hatenablog.com

を使うことを考えると、

$n$が3の倍数であることを示せばいいのではという見当がつきます。

なぜなら、$n$は奇数だということが分かっているので、

$2^n+1=2^n+(-1)^n$であり、LTEの補題を適用するには

$2-(-1)=3$の倍数であることが必要だからです。

ここから、こういう発想を思いつくことが難しいのですが、

$n$の最小の素因数$p$を取ります。（$n$は奇数なので$p \geq 3$です。）

このとき、$\frac{2^n+1}{n^2}$が整数なので

$2^n \equiv -1 \pmod p$、そして

$4^n \equiv 1 \pmod p$であることがわかります。

また、フェルマーの小定理より

$4^{p-1} \equiv 1 \pmod p$

よって、$n$と$p-1$の公約数が4の位数となるわけですが、

$p$は$n$の最小の素因数なので、$\gcd(n,p-1)=1$です。

ここが少しわかりにくいと思うので、解説します。

もし$n$と$p-1$が2以上の公約数を持ったとすると、

それは$p-1$の約数なので$p$より小さいことになりますが、

$p$は$n$の最小の素因数なので、そんな$n$の約数は存在しないからです。

したがって$\gcd(n,p-1)=1$なので、これが4の位数となり、

すなわち$4 \equiv 1 \pmod p$が成り立つので、$p=3$です。

これで$n$が3の倍数であることがいえました。

というわけで、LTEの補題を使います。

${\rm ord}_p (x^n-y^n) = {\rm ord}_p (x-y)+{\rm ord}_p n$

LTEの補題に、$p=3,x=2,y=-1$を代入して

${\rm ord}_3 (2^n-(-1)^n) = {\rm ord}_3 (2-(-1))+{\rm ord}_3 n$

${\rm ord}_3 (2^n+1) = {\rm ord}_3 n + 1$

また、${\rm ord}_3 n^2 = 2{\rm ord}_3 n$

$\frac{2^n+1}{n^2}$が整数なので、

${\rm ord}_3 (2^n+1) \geq {\rm ord}_3 n^2$より

${\rm ord}_3 n + 1 \geq 2{\rm ord}_3 n$

$1 \geq {\rm ord}_3 n$

また$n$は3の倍数なので${\rm ord}_3 n \leq 1$であることから、

${\rm ord}_3 n = 1$がわかります。

これで$n$に結構な制約ができました。

こっからどうすればいいのか、僕は手が止まりましたが…。

同じようなステップを進めてみましょう。

$n=3$のときは問題の条件を満たすので、$n>3$と仮定します。

$n$の2番目に小さい素因数$q$を取ります。$q \geq 5$です。

$4^n \equiv 1 \pmod q, 4^{q-1} \equiv 1 \pmod q$

がそれぞれ成り立ち、$n$と$q-1$の公約数が4の位数となるわけですが、（$p=3$の証明と同様）

$\gcd(n,q-1)=1 or 3$が成り立ちます。（$q$は2番目に小さい$n$の素因数なので）

しかし$\gcd(n,q-1)=1$のときは$4 \equiv 1 \pmod q$となり$q=3$となってしまい、

これはおかしい。

なので$\gcd(n,q-1)=3$がわかります。

$4^3\equiv 1\pmod q$より$q$は63の素因数、このうち$q>3$を満たすのは$q=7$のみです。

しかし$n$は3の倍数なので$p=3k$（$k$は整数）とおけ、

$2^n+1\equiv 2^{3k}+1 \equiv 8^k+1 \equiv 1+1 \equiv 2 \pmod 7$

となり、これは$2^n+1$が$n^2$で割り切れることに矛盾します。

よって$n>3$という仮定が間違っていることがわかり、背理法で

解は$n=3$のみということがわかります。

結論。
難しい。

実際、LTEの補題を使う問題は中~高難度のものばかりです。
もしあなたが高レベルに到達したいと思っているのならば、
これは知っていて損はありません。

2016-10-15

LTEの補題

整数論

2019.06.25 追記：LTEの補題について新しい記事を書きました。

こちらもぜひ読んでください。

dama-solved.hatenablog.com

更新が遅れました。
学園祭、定期試験などあり、少し忙しかったので。。。すいません。

LTEといっても、Long Term Evolution（携帯電話の通信規格）ではありません。

Lifting The Exponent Lemmaです。

これは整数論の定理で、痒いところに手が届くような便利な定理です。僕は結構気に入ってます。

整数論はmodulo演算が基本ですが、それだけではやややりにくいことをこの定理はやってくれるので、
知ってると絶対プラスになると思います。（特に数オリ）

１：オーダーについて

1.1 オーダーの定義

オーダーとは、簡単に言えば「何回割れるか」。しっかり定義を書くと、

0でない整数$n$と素数$p$に対して、次を見たす非負整数$d$が存在する。

$n$は$p^d$では割り切れるが、$p^{d+1}$では割り切れない。
この$d$のことを素数$p$に関する$n$のオーダーといい、${\rm ord}_p n$と書く。

というものです。

1.2 オーダーのちょっとした性質

${\rm ord}_p (mn)={\rm ord}_p m + {\rm ord}_p n$
${\rm ord}_p (m+n) \geq \min \{ {\rm ord}_p m, {\rm ord}_p n \}$

これが関係してくる問題の場合、普通にmodulo演算で$\bmod p$で考えると0になって、何回割れるかわからない…ということが多々あります。

そんなときにLTEの補題が使えるかもしれません。

2:LTEの補題

定理：
$p$を奇素数とする。$x,y$を、$x \equiv y \pmod p$であるが両方とも$p$の倍数ではない整数とする。このとき、正の整数$n$ に対して、

${\rm ord}_p (x^n-y^n) = {\rm ord}_p (x-y)+{\rm ord}_p n$

パッと見では、うーん、というか、だから何？、という感じだと思います。
まあ、今回は紹介だけして、次の記事でバーンと使います。楽しみにしていてください。

3:証明

おもに3ステップで証明します。

3.1 $n$が$p$で割り切れないとき

$x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\cdots+y^{n-1})$
と因数分解できます。

おっと、$(x-y)$が出ましたね。LTEの補題にするために、その右側について考えます。

$x \equiv y \pmod p$なので、
$(x^{n-1}+x^{n-2}y+\cdots+y^{n-1}) \equiv ny^{n-1} \pmod p$
そして、$n$も$y$も$p$で割り切れないので、
${\rm ord}_p (x^{n-1}+x^{n-2}y+\cdots+y^{n-1})=0$
これで、右側のほうもわかりました。

よって、
\begin{eqnarray}
{\rm ord}_p (x^n-y^n) & = & {\rm ord}_p (x-y)(x^{n-1}+x^{n-2}y+\cdots+y^{n-1}) \\
& = & {\rm ord}_p (x-y) + {\rm ord}_p (x^{n-1}+x^{n-2}y+\cdots+y^{n-1}) \\
& = & {\rm ord}_p (x-y) + 0 \\
& = & {\rm ord}_p (x-y)+{\rm ord}_p n
\end{eqnarray}
が成り立ちます。（最後に、$n$が$p$で割り切れないことを使いました）

3.2 $n=p$のとき

ここが少し難しい。

3.1と同じようにして、
$x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+\cdots+y^{n-1})$
と因数分解し、$x^{n-1}+x^{n-2}y+\cdots+y^{n-1}$について考えます。

で、ここから大変なんですけど、
$x^{n-1}+x^{n-2}y+\cdots+y^{n-1}$をむりやり$x-y$で割ります。

そうすると
$x^{n-1}+x^{n-2}y+\cdots+y^{n-1}=(x-y)(x^{p-2}+2x^{p-3}y+\cdots+(p-2)xy^{p-3}+(p-1)y^{p-2})+py^{p-1}$
となります。
なぜこうなるのか？これは、自分で展開してみるのが一番早いと思いますが、「右側が1ずつ大きくなっているが、うまく引かれて結局1が残る」という感じです。

$x \equiv y \pmod p$より、
\begin{eqnarray}
&& x^{p-2}+2x^{p-3}y+\cdots+(p-2)xy^{p-3}+(p-1)y^{p-2} \\
& \equiv & \{1+2+\cdots +(p-1)\}y^{p-2} \pmod p\\
& = & \frac{p(p-1)}{2}y^{p-2}
\end{eqnarray}

$p$は奇素数なので、$\cfrac{p-1}{2}$は整数となり、 $\cfrac{p(p-1)}{2}y^{p-2}$は$p$の倍数です。

つまり、$x^{p-2}+2x^{p-3}y+\cdots+(p-2)xy^{p-3}+(p-1)y^{p-2}$は$p$の倍数です。

では、
$x^{n-1}+x^{n-2}y+\cdots+y^{n-1}=(x-y)(x^{p-2}+2x^{p-3}y+\cdots+(p-2)xy^{p-3}+(p-1)y^{p-2})+py^{p-1}$
の式に戻りましょう。

$x \equiv y \pmod p$より、$x-y$は$p$の倍数。
また$x^{p-2}+2x^{p-3}y+\cdots+(p-2)xy^{p-3}+(p-1)y^{p-2}$も$p$の倍数なので、
$(x-y)(x^{p-2}+2x^{p-3}y+\cdots+(p-2)xy^{p-3}+(p-1)y^{p-2})$は$p^2$の倍数です。

よって
\begin{eqnarray}
x^{n-1}+x^{n-2}y+\cdots+y^{n-1}&=&(x-y)(x^{p-2}+2x^{p-3}y+\cdots+(p-2)xy^{p-3}+(p-1)y^{p-2})+py^{p-1} \\
& \equiv & py^{p-1} \pmod{p^2}
\end{eqnarray}
となり、$y^{p-1}$は$p$の倍数ではないので、
${\rm ord}_p (x^{n-1}+x^{n-2}y+\cdots+y^{n-1}) = 1$です。

よって
\begin{eqnarray}
{\rm ord}_p (x^n-y^n) & = & {\rm ord}_p (x^p-y^p) \\
& = & {\rm ord}_p (x-y)(x^{p-1}+x^{p-2}y+\cdots+y^{p-1}) \\
& = & {\rm ord}_p (x-y) + {\rm ord}_p (x^{n-1}+x^{n-2}y+\cdots+y^{n-1}) \\
& = & {\rm ord}_p (x-y) + 1 \\
& = & {\rm ord}_p (x-y)+{\rm ord}_p p \\
& = & {\rm ord}_p (x-y)+{\rm ord}_p n
\end{eqnarray}

3.3 $n$が一般のとき

${\rm ord}_p n$で数学的帰納法を使います。

$n=ap^m$（ただし、$a$は$p$で割り切れない整数）とおき、

${\rm ord}_p (x^n-y^n) = {\rm ord}_p (x-y)+m$　　　　…①

となることを証明します。（${\rm ord}_p n=m$より）

$n$が$p$で割り切れない場合は3.1で証明したので、
$m=0$のとき、①は成り立ちます。

そして、$m=k$のとき①が成り立ったら
$m=k+1$のときも①が成り立つことを証明します。

$n=ap^{k+1}$とおきます。
このとき、
$x^n-y^n=x^{ap^{k+1}}-y^{ap^{k+1}}=(x^{ap^k})^p-(y^{ap^k})^p$
です。なんか3.2が使えそうな感じがします。

実際、$x^k-y^k$は$x-y$で割り切れ、しかも$x-y$は$p$で割り切れるので、
$x^k-y^k$は$p$で割り切れます。
これは、3.2が使えることを意味します。

よって、
\begin{eqnarray}
{\rm ord}_p (x^n-y^n) & = & {\rm ord}_p ((x^{ap^k})^p-(y^{ap^k})^p) \\
& = & {\rm ord}_p (x^{ap^k}-y^{ap^k}) +1\\
& = & {\rm ord}_p (x-y) + {\rm ord}_p k +1\\
& = & {\rm ord}_p (x-y) +k+1 \\
& = & {\rm ord}_p (x-y)+{\rm ord}_p ap^{k+1}\\
& = & {\rm ord}_p (x-y)+{\rm ord}_p n
\end{eqnarray}

となり、(m=k\)のとき①が成り立ったら$m=k+1$のときも①が成り立つので
証明が完了しました。

4 まとめ

けっこう大変だったと思いますが、最後まで読んでいただきありがとうございます。
使用例は次の記事で紹介しようと思っているので楽しみにしてください。

2016-09-24

ブログを初めて1年。

ブログを初めて約1年がたちました。

早かったような、短かったような…。

これからも徘徊していく予定です。

2016-09-02

問題コーナー

問題コーナー幾何

ほんっと久しぶり。前は12月だったかな。

なんとなく三角形や円を描いていたらできた問題。
僕の解き方だとまだ回りくどいと思うので、
エレガントな解答をお願いします。

簡単だったらごめんなさいm(_ _)m

というわけで、早速問題。

三角形$ABC$の外心を$O$とし、辺$BC,CA,AB$の中点をそれぞれ$M_A,M_B,M_C$とする。
このとき三角形$AOM_A,BOM_B,COM_C$の外接円は点$O$以外の1点で交わることを示せ。

解答はコメント欄にてお願いします。

（追記）
三角形$ABC$は二等辺三角形でないという条件を付けてください。
つけ忘れていました。すいません。

また、期限は10月31日までとします。

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}}\]

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

数学徘徊記

自由な数学ブログ。