2018-10-07

3が合同数でないことの初等的証明

プチ研究数学 Mathpower2018 追記あり、一部未完成

追記(2018/10/07):(14)式から(15)式に移るのに飛躍があったので、証明には修正が必要なようです。うまくいったら、また更新します。

合同数とは

直角三角形の斜辺を $z$ 、その他２つの斜辺を $x,y$ とする。
このとき、 $x,y,z$ が全て有理数で、かつ、その直角三角形の面積が自然数となったとき、その自然数を合同数という。
　例えば、 $x=3,y=4,z=5$ とすると、三平方の定理

$3^2+4^2=5^2$ ……(1)

が成り立つので、これらの辺の長さを持つ三角形は直角三角形で、その面積は、

$\frac{3\times4}{2}=6$ ……(2)

となるので、 $6$ は合同数である。

Mathpower2018で聞いた宿題

現在、絶賛開催中のMathpower2018の「意欲的な中高生に贈る数学の話」でこの合同数の話題が取り上げられた。そこで、以前「数理空間トポス」の宿題として、

「3が合同数でないことを(初等的に)証明せよ。」……(3)

という問題が出題されたということだ。今回の記事では、これを大人げなく解いてみる。
　もし、間違いなどあれば優しく指摘してくださるとありがたいです。

3が合同数でないことの初等的証明

背理法を用いる。3が合同数であったと仮定する。すなわち、面積が3になるような直角三角形で、三辺の長さ $x,y,z$ が有理数であるものが存在したと仮定する。即ち、

$z^2=x^2+y^2$ ……(4)
$\frac{xy}{2}=3 \iff xy=6$ ……(5)

を満たす有理数 $x,y,z$ が存在したと仮定する。(4)(5)式の両辺を $x^2$ で割って、

$(\frac{z}{x})^2 = 1 + (\frac{y}{x})^2$ ……(6)
$\frac{y}{x}=\frac{6}{x^2}$ ……(7)

を得る。(7)式を(6)式に代入して整理すると、

$(\frac{z}{x})^2 = 1 + \frac{6^2}{x^4}$
$x^2 z^2 = x^4 + 6^2$ ……(7)

となる。ここで、 $x,z$ を既約分数で表す。つまり、

$x=\frac{a}{b}$ ……(8)
$z=\frac{c}{d}$ ……(9)

とする。ここで、 $a$ と $b$ 、 $c$ と $d$ は互いに素な自然数である。つまり、

$\gcd (a,b)=1$ ……(10)
$\gcd (c,d)=1$ ……(11)

とする。(7)式の両辺に $b^4 d^2$ をかけると、

$a^2 b^2 c^2 = a^4 d^2 + 6^2 b^4 d^2$
$\iff (abc)^2 = (a^2d)^2 + (6b^2d)^2$ ……(12)

ここで、右辺が $d^2$ の倍数であるので、左辺も $d^2$ の倍数であり、両辺を $d^2$ で割っても自然数の項のみが現れる。
同様に、

$(abc)^2 - (a^2d)^2 = (6b^2d)^2$ ……(13)
$(abc)^2 - (6b^2d)^2 = (a^2d)^2$ ……(14)

などと変形してやると、(13)(14)式の右辺がそれぞれ、 $a^2,b^2$ の倍数であることがわかる。結局、(12)式の各項は $a^2 b^2 d^2$ で割り切れることがわかる。したがって、

$(\frac{c}{d})^2 = (\frac{a}{b})^2 + (6 \frac{b}{a})^2$ ……(15)

という自然数のみからなる等式を得る。特に、 $a,b$ が互いに素であることから、

$\frac{a}{b}が自然数$ ……(16)

より、

$b=1$ ……(17)

を得る。また、

$6 \frac{b}{a}=\frac{6}{a}が自然数$ ……(18)

であるので、 $a$ の値の候補を

$a=1,2,3,6$ ……(19)

と絞り込める。そして、

$(\frac{c}{d})^2が自然数$
$\iff (\frac{c}{d})^2は平方数$ ……(20)

であることも注意しておく。
　後は、これら全ての $a$ の値について、矛盾を導けば証明は完成する。

(i) $a=1$ の場合、(15)式から

$(\frac{c}{d})^2 = 1^2 +6^2 =37$ ……(21)

となるが、37は平方数でないので矛盾。

(ii) $a=2$ の場合、(15)式から、

$(\frac{c}{d})^2 = 2^2 +3^2 =13$ ……(22)

となるが、13は平方数でないので矛盾。

(iii) $a=3$ の場合も、同様に、

$(\frac{c}{d})^2 = 3^2 +2^2 =13$ ……(23)

となり、矛盾。

(iv) $a=6$ の場合も、同様に、

$(\frac{c}{d})^2 = 6^2 +1^2 =37$ ……(21)

となり、矛盾。

　以上より、全ての場合について矛盾が得られたので、背理法の仮定が偽であったことになり、3は合同数でないことが示された。

2018-10-06

対数関数を多項式で近似したときの零点の話【無限乗積展開!?】

プチ研究プログラミング数学オリジナル

Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴

数学関連の絶版本・品切れ本をコチラから購入できます！

対数関数のテイラー展開と多項式近似

　前回の記事で指数関数を多項式で近似した場合に零点がどのように分布するのかについて調べた。

sky-time-math.hatenablog.jp

　指数関数を調べたついでに対数関数の場合も調べてみようと思ったので、やってみた、というのが今回のお話です。*1
　ついでとは言ったが、対数関数 $\log (1+x)$ が指数関数とでは、 $x=-1$ で負の無限大に発散するという決定的に異なる点がある。そのため、「このことが多項式近似の零点分布にどのような影響を及ぼすのだろうか？」という疑問もモチベーションになっている。

　さて、対数関数は、次の形でのテイラー展開ができる。

$\log (1+x) = - \sum_{n=1}^{\infty} \frac{(-1)^n}{n}x^n$ ……(1)

$x=0$ が零点であることは自明なので、両辺を $x$ で割って、 $\log (1+x)$ を多項式で近似した場合の非自明な零点を調べたい。つまり、次の多項式で近似したときの零点を調べる。

$\frac{\log (1+x)}{x} \simeq \sum_{n=0}^{N} \frac{(-1)^n}{n+1} x^n$ ……(2)

　プログラムは前回の指数関数の多項式近似の零点を調べたときと、同様のものを使用した。つまり、多項式(2)の零点をnumpy.rootsで計算した。また、計算の精度を確認するため、計算した零点を持つ多項式を復元し、元の多項式と比較して、係数の最大値と最小値が十分小さいことをチェックしてある。

零点の分布

まずは、多項式(2)の次数 $N$ が小さいところから見ていこう。 $N=4,6,8,10$ の場合は次のようになる。

f:id:FoxQ:20181006100849p:plain

f:id:FoxQ:20181006100857p:plain

f:id:FoxQ:20181006100906p:plain

f:id:FoxQ:20181006100913p:plain

　なんとなく円形にならんでいるように見える。ここからは、一気に次数を増やしてみてる。 $N=20,50,70,100$ の場合は、次のようになる。*2

f:id:FoxQ:20181006100928p:plain

f:id:FoxQ:20181006100935p:plain

f:id:FoxQ:20181006100947p:plain

f:id:FoxQ:20181006100958p:plain

　次数を増やしていくと、思いっきり円形に並んでいることがわかった。また、次数を増やしていくと円(楕円?)の半径が1に近づいていくことも分かった。

零点の絶対値の最大・最小

　指数関数の場合と同様に、零点の絶対値の最大値と最小値も調べてみた。
　まず、次数 $N=1 \sim 15$ までを見てみる。赤線が零点の絶対値の最大値で、青線が最小値だ。

f:id:FoxQ:20181006101347p:plain

次数が増えるにつれて、円(楕円?)の半径が単調に減少にしていることがわかる。次に、 $N=100$ までを見てみる。

f:id:FoxQ:20181006101613p:plain

　次数が十分大きくなると、零点の分布が半径1の円に漸近していっているように見える。おそらく、 $N \rightarrow \infty$ の極限をとると半径1の円になるのだろう。半径が1になっている理由は、 $\log (1+x)$ が $x=-1$ で $- \infty$ に発散することに関係しているためかと思われる。
　これらの零点が $N \rightarrow \infty$ の極限で元の対数関数と何らかの関係を持ち得るか？という素朴な疑問が上がってくる。率直に考えるなら、

$\log(1+x) = x \prod_{x_0 \in \Gamma} (1-\frac{x}{x_0})$ ……(3)

という無限乗積展開のようなものがあるようにも思えてくる。ここで、 $x_0$ は半径1の円上の点で、 $\Gamma$ は半径1の円のなんらかの部分集合である*3。
　しかしながら、対数関数 $\log (1+x)$ の零点は $x=0$ のみであるはずなので、このような無限乗積展開に意味を与えるのはどうにも難しそうである。
　さて、今回はここまでです。みなさんはどう考えますか？

*1:指数関数だけやって、対数関数を仲間外れにするのもどうかと思ったので。

*2:今回は、 $N=110$ で多項式の復元時の誤差が無視できなくなったので、 $N=100$ までを計算することとなった。

*3:高々加算個であるかどうかすらわからないが……

2018-10-05

exp(x)を多項式で近似したときの零点の話

プチ研究数学プログラミング追記あり、一部未完成 twitter オリジナル

Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴

数学関連の絶版本・品切れ本をコチラから購入できます！

twitterで見かけた指数関数の話

　twitterでtsujimotterさんが、指数関数について以下のようなツイートをしていた。

ふと思った疑問。指数関数のテイラー展開って、有限項で打ち切った多項式の零点と指数関数の零点ってどういう関係になっているだろう。
— tsujimotter (@tsujimotter) September 30, 2018

　これが少し気になったので、Wolfram alphaを使って10次の多項式まで計算してみたところ零点が放物線っぽく並んでいるのを見つけた。もっと高い次数まで計算してみたかったのだが、Wolfram alpha(無料版)は10次までしか相手してくれなかった。

　そこで、勉強中のPythonを使って計算してみることにした、というのが今回するお話です。

指数関数の多項式近似とスケーリング

　指数関数を $N$ 次の多項式で近似すると、次のようになる。

$exp(x) \simeq \sum_{n=0}^{N} \frac{x^n}{n!}$ ……(1)

　PythonのNumpyには、多項式の零点を計算してくれる便利な関数numpy.rootsがあるので今回はそれを使うことにした。ところが、このまま計算すると、 $N$ 次の項が小さくなり過ぎて桁落ちする恐れがあるので、スターリングの公式(スターリングの近似 - Wikipedia)を参考にして、

$x=\frac{Ny}{e}$ ……(2)

と置き換えて、変数のスケールを事前に変えておく。つまり、

$\sum_{n=0}^{N} \frac{(N/e)^n}{n!} y^n$ ……(3)

という多項式の零点を数値計算する。こうすることで、 $N$ 次の項が極端に小さくなることを回避できる。このスケールした多項式の零点が $y_0$ と求まったら、元の多項式(1)の零点は、

$x_0=\frac{N}{e} y_0$ ……(4)

と求まることになる。

　大量の零点を計算することになるので、ちゃんと計算できているかどうかのチェックが必要になる。そこで、求まった零点からそれらの零点を持つ多項式を逆に再計算して、定数項を1になるように規格化し、元の多項式と比較を行った。今回の記事に載せる計算結果は、すべて、元の多項式と零点から復元した多項式の最大の係数が、有効数字で8桁以上で一致することを確認してある。

零点の分布

　まずは、次数 $N$ が小さい方から多項式(1)の零点の分布をみていく。まずは、Wolfram Alphaでやったやつの再計算結果から。

f:id:FoxQ:20181005111524p:plain

f:id:FoxQ:20181005111547p:plain

f:id:FoxQ:20181005111555p:plain

f:id:FoxQ:20181005111600p:plain

このように、無事再現できた。

　次は、次数を20から60まで一気に増やしていく。 $N=60$ に近づくにつれて、放物線というよりは、馬蹄形のようになっていることがわかった。

f:id:FoxQ:20181005111740p:plain

f:id:FoxQ:20181005111747p:plain

f:id:FoxQ:20181005111752p:plain

　さらに、次数を増やす。すると妙なことが起こった。
追記(2018/10/07)：後日、これ以降の次数の数値計算に数値誤差があることが判明しました。きちんと計算できているのは、 $N=60$ くらいまでのようです。

f:id:FoxQ:20181005111908p:plain

　謎の分岐が発生した。さらに、次数を増やしていく。

f:id:FoxQ:20181005111952p:plain

f:id:FoxQ:20181005112006p:plain

f:id:FoxQ:20181005112032p:plain

f:id:FoxQ:20181005112040p:plain

f:id:FoxQ:20181005112051p:plain

　 $N=170$ まで計算したところで、多項式の復元時の誤差が有効数字8桁程度になったり、 $N=180$ でプログラムがエラーを吐いたのでここで計算を打ち切った。

　最終的に、零点の分布が描いたのは、二つの弧とその間にぽつぽつとした点があり、それらの弧に二本のツノを引っ付けたような図形となった。
最初の放物線っぽい形から予想できるような、単純な形にはならなかったのである。

零点の絶対値の範囲

　また、twitterでtaketo1024さんが(1)の多項式の零点の絶対値の範囲の見積もりがあることを教えてくれた。

気になって調べたら、このノートに指数関数の n 次近似式の零点は n/e^2 < |z| < n なる範囲にあることの証明が載ってました😆https://t.co/JLUzrBQe2M
— さのたけと (@taketo1024) September 30, 2018

　ノートによると、この不等式は $N$ が十分大きいところで成立するらしい。

　そこで、今回私が計算した零点の絶対値をとり、その最大値と最小値をプロットしてみた。青色の線が零点の絶対値の最小値で、赤色が最大値である。また、ピンクと水色の線は、上記のツイートのノートに書いてあった最大値と最小値である。

$N=100$ までの図をひとまず見ると、不等式の範囲内にあることがわかる。

f:id:FoxQ:20181005113053p:plain

　ところが、 $N=170$ までを見ると、不等式の下限を下回ってしまった。

f:id:FoxQ:20181005113106p:plain

　これが、numpyの限界なのか、 $N$ の大きさが十分でないためなのかは、はっきりとしない。現状、 $N=60 \sim 70$ 付近で、なぜか零点の絶対値の最小値が頭打ちになっているようにも見える。これはちょうど、零点の分布の図で２個目の『弧』が現れ始めたところである。

追記(2018/10/07):この最小値が頭打ちになっているあたりから数値誤差が強く出ているようです。正しい零点の極限分布について、以下のサイトにまとめを見つけたので、そちらを見てください。

数学の散歩道の「３．指数関数が定める多項式のゼロ点集合の極限形」

http://www.eonet.ne.jp/~kotani/sanpo.html

　このような現象がなぜおきるのか？数学的にありうることなのか？単に数値計算による誤差などの限界から来るものなのか？

　いずれもよくわからない、というのが今の感想だ。みなさんは、どう思いますか？

2018-07-28

【解の構成方法】マスターデーモンの一般化

プチ研究数学オリンピック数学オリジナル

Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴

数学関連の絶版本・品切れ本をコチラから購入できます！

マスターデーモンの一般化

　今回の記事では、マスターデーモンの一般化について考える。
「自然数rが与えられたとき、２以上の $n$ で
$\frac{r^n+1}{n^2}$ ……(1)
が整数となるものを全て求めよ。」

　結論から言うと、(1)式が整数になるような任意の $n$ を構成するアルゴリズムを求めることはできた。ところが、一般の自然数 $r$ に対して、 $n$ を一般的に表す公式を求めるのは極めて困難である。そのため、(1)式を満たす解が無限に存在するかどうかすらも難しい。この難しさは、素因数分解の難しさに関連するものなので、相当な「武器」を持ってこないと太刀打ちできないだろう。
　また、この記事では、自然数は $1$ 以上の整数であるとする。

今回の話のアウトライン

今回の記事のアウトラインは、次の通りである。

①: $n$ が偶数にならないこと
②: $n$ の最小の素因数が、 $r+1$ の奇数の素因数のいずれかに一致すること
③: $n$ の最小の素因数の指数は、 $r+1$ の対応する素因数の指数以下であること
④と⑤:③の証明
⑥:一般化されたマスターデーモンの解を構成するアルゴリズム

①②③を繰り返し用いることで、(1)式が整数になる $n$ を構成するアルゴリズムが得られる。

① $n$ が偶数にならないこと

　 $r$ が偶数のときは、(1)式の分子が奇数になるので、(1)式の分母は偶数ではない。よって、 $n$ も偶数でない。
　 $r$ が奇数の時、 $n$ が偶数と仮定する。すると、(1)式の分母は $4$ の倍数になるので、(1)式が整数になるなら分子 $r^n+1$ も $4$ の倍数である。従って、

$r^n+1\equiv 0 (\bmod 4)$ ……(2)

　ところが、 $r$ は奇数なので、

$r\equiv \pm 1 (\bmod 4)$ ……(3)

であるので、これを(2)式に代入すると、 $n$ を偶数と仮定したことから、

$(\pm 1)^n+1 \equiv 1+1 \equiv 2$
$\therefore 2 \equiv 0 (\bmod 4)$ ……(4)
となるので、矛盾である。背理法により、 $r$ が奇数のときも、 $n$ は偶数ではない。
　よって、(1)式が整数になるならば、 $n$ は偶数ではない。

② $n$ の最小の素因数が、 $r+1$ の奇数の素因数のいずれかに一致すること

　 $n(\ge 2)$ の最小の素因数を $q$ とし、その指数を $k$ とする。すると、 $n$ は、 $p$ と互いに素な自然数 $N$ を用いて、

$n=q^k N$ ……(5)

と表せる。(1)式の分母が $q$ の倍数になるので、

$r^n+1\equiv 0 (\bmod q)$ ……(6)

である必要がある。フェルマーの小定理より、

$r^n+1\equiv r^{q^k N}+1 \equiv r^N +1 \equiv 0 (\bmod q)$ ……(8)
$r^{2N}\equiv 1(\bmod q)$ ……(9)

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

$r^{q-1}\equiv 1 (\bmod q)$ ……(10)

ここで、法を $q$ としたときの $r$ の位数は、 $\gcd(2N,q-1)$ の約数になるが、 $N$ は $q$ より小さい素因数を持たないので、

$\gcd(2N,q-1)=2$ ……(11)

である。よって、

$r\equiv 1 (\bmod q)$ または $r^2\equiv 1(\bmod q)$
$\iff r\equiv \pm 1(\bmod q)$ ……(12)

である。 $r \equiv 1(\bmod q)$ とすると、(8)式より、

$1^N+1\equiv 2 \equiv 0 (\bmod q)$ ……(13)

となるので矛盾である。従って、

$r\equiv -1 (\bmod q)$
$\therefore r+1 \equiv 0(\bmod q)$ ……(14)

である。
　よって、 $n$ の最小の素因数 $q$ は、 $r+1$ の奇数の素因数のいずれかに一致する。

③ $n$ の最小の素因数の指数は、 $r+1$ の対応する素因数の指数以下であること

　 $r+1$ が次のように素因数分解されたとする。

$r+1=2^{e_0} p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t}$ ……(15)

ここで、 $t$ は１以上のある自然数で、 $e_j(j=0,1,\cdots,t)$ は０以上の整数で、 $e_j$ の内少なくとも１つは $0$ ではない。

　②より、 $n$ の最小の素因数は、ある $j(=1,2,\cdots,t)$ に対して

$q=p_j$ ……(16)
である。 $n=q^k N$ なので、 $r^n$ は次の形に因数分解できる。

$r^{q^k N}+1=(r+1)f_q(r)f_q(r^q)f_q(r^{q^2}) \cdots f_q(r^{q^{k-1}})f_N(r^{q^k})$ ……(17)

ここで、 $f_m(x)$ は、奇数 $m$ に対して、

$f_m(x)=\frac{r^m+1}{r+1}=1-r+r^2-\cdots+ r^{m-1}$ ……(18)

と定義している。このように因数分解したとき、 $j=0,1,\cdots,k-1$ に対して、

$f_q(r^{q^j})\equiv 0 (\bmod q)$ ……(19)
$f_q(r^{q^j})\not\equiv 0 (\bmod q^2)$ ……(20)
$f_N(r^{q^k})\not\equiv 0 (\bmod q)$ ……(21)

であることが示せる(後で、④,⑤で示す)。従って、 $f_q(r^{q^j})$ は、 $q$ でちょうど１回だけ割り切れるので、(15),(17)式より、

$r^n+1$ は $q=p_j$ で $e_j+k$ 回だけ割り切れる……(22)

(1)式の分母は、 $q$ で $2k$ 回割り切れるので、(1)式が整数であるためには、

$e_j+k \ge 2k$
$\iff k \le e_j$
$\therefore k=1,2,\cdots, e_j$ ……(23)

である必要がある。
　特に、
$n=q^k(k=1,2,\cdots,e_j)$

は一般化されたマスターデーモンの１つの解となっている。
　それでは、(19),(20),(21)式を示そう。

④ $f_q(r^{q^j})\equiv 0 (\bmod q)$ 、 $f_N(r^{q^k})\not\equiv 0 (\bmod q)$ であること

　フェルマーの小定理より、 $j=0,1,\cdots,k-1$ に対して、

$f_q(r^{q^j})\equiv f_q(r) (\bmod q)$ ……(24)
$f_N(r^{q^k})\equiv f_N(r) (\bmod q)$ ……(25)

である。(14),(18)式より、 $N$ と $q$ が互いに素であることに注意して、

$f_q(r)\equiv 1-(-1)+(-1)^2-\cdots (-1)^{q-1}\equiv q \equiv 0 (\bmod q)$ ……(26)
$f_N(r)\equiv 1-(-1)+(-1)^2-\cdots (-1)^{N-1}\equiv N \not\equiv 0 (\bmod q)$ ……(27)

よって、(19),(21)式が成立する。

⑤ $f_q(r^{q^j})\not\equiv 0 (\bmod q^2)$ であること

　まず、 $r+1\equiv 0 (\bmod q)$ より、

$(r+1)^2\equiv r^2+2r+1\equiv 0 (\bmod q^2)$
$r^2 \equiv -2r-1 (\bmod q^2)$ ……(28)

であるので、 $q$ を法とするとき、 $f_q(r^{q^j}$ は $r$ の１次式で表せることに着目する。 $j$ を自然数とするとき、

$r^j \equiv a_j r + b_j$ ……(29)

と置くと、(29)式に $r$ をかけて、(28)式を用いることで、 $a_j,b_j$ の漸化式を得る。

$a_{j+1}=b_j-2a_j$ ……(30)
$b_{j+1}=-a_j$ ……(31)

(31)式を(30)式に用いて、

$a_{j+1}=-2a_j -a_{j-1}$ ……(32)

となるので、 $a_j$ の一般解は、

$a_j=(-1)^j(\alpha j +\beta)$ ……(33)

と表せる。 $a_1=1,a_2=-2$ となることから、 $\alpha,\beta$ を求めた後、

$a_j=(-1)^{j+1} j$ ……(34)
$b_j=(-1)^{j-1}(j-1)$ ……(35)

を得る。これより、

$f_q(r)=1+\sum_{j=1}^{q-1} r^j$
$\equiv 1-(\sum_{j=1}^{q-1} (-1)^j j)r +(\sum_{j=1}^{q-1} (-1)^{j-1} (j-1)) (\bmod q^2)$
$\equiv \frac{1-q}{2} r + \frac{3-q}{2}$ ……(36)

ここで、 $f_q(r)\equiv 0 (\bmod q^2)$ と仮定すると、

$\frac{1-q}{2} r + \frac{3-q}{2} \equiv 0 (\bmod q^2)$
$q(1-q)r - q(q-3) \equiv 0(\bmod q^2)$
$q (r+3) \equiv 0 (\bmod q^2)$
$\therefore r\equiv -3 (\bmod q)$ ……(37)

となるが、 $r\equiv -1 (\bmod q)$ であったので矛盾。よって、

$f_q(r)\not\equiv 0 (\bmod q^2)$ ……(38)

　次にオイラーの定理より*1、

$r^{\varphi(q^2)}\equiv r^{q(q-1)} \equiv1(\bmod q^2)$
$\therefore r^{q^2}\equiv r^q (\bmod q^2)$ ……(39)

であるので、

$j=1,\cdots,k-1$ に対して、

$f_q(r^{q^j})\equiv f_q(r^q) (\bmod q^2)$ ……(40)

が言えるので、 $f_q(r^{q^j})\not\equiv 0 (\bmod q^2)$ を示すには、

$f_q(r^q) \not\equiv 0 (\bmod q^2)$ ……(41)

を示せば十分である。 $f_q(r)\not\equiv 0 (\bmod q^2)$ を示したときと同様にして、

$f_q(r^q)\equiv - \frac{q^2-q}{2} r - \frac{q^2-q-2}{2} (\bmod q^2)$ ……(42)

を得る。 $f_q(r^q) \equiv 0 (\bmod q^2)$ となったと仮定すると、(42)式に $2$ をかけて、

$(-q^2+q)r \equiv q^2 -q -2 (\bmod q^2)$
$qr \equiv -q-2 (\bmod q^2)$
$0\equiv q^2 r \equiv -2q$
$\therefore 2q\equiv 0 (\bmod q^2)$ ……(43)

これを満たす奇素数 $q$ は存在しないので、矛盾。よって、

$f_q(r^q)\not\equiv 0 (\bmod q^2)$ ……(44)

　以上をまとめて、 $j=0,1,\cdots,k-1$ に対して、

$f_q(r^{q^j}) \not\equiv 0 (\bmod q^2)$ ……(45)

が示せた。

⑥:一般化されたマスターデーモンの解を構成するアルゴリズム

　①～③を繰り返し用いることにより、一般化されたマスターデーモンの解を構成するアルゴリズムが得られる。

$r_1=r$ とおき、(15)式のように、
$r_1+1=2^{e_0} p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t}$ ……(46)
と素因数分解できたとき、ある $p_j$ を１つとり、

$q_1=p_j$ ……(47)

とおく。すると、①～③より、次の $e_j$ 個の自然数は一般化されたマスターデーモンの解になる。

$n=n_1=q_1^{k_1} (k_1=1,2,\cdots,e_j)$ ……(48)

ここで、(48)式のそれぞれの解に対して、

$r_2=r_1^{q_1^{k_1}}$ ……(49)

とおく。

　ここまでを最初のステップとして、一般化されたマスターデーモンの全ての一般解は、以下のようなアルゴリズムにより構成できる。

　 $r_m(m \ge 1)$ が与えられ、

$r_m+1=2^{e_0} p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t}$ ……(50)

と素因数分解できたする。(ここでは、式の見やすさの便宜上、(46)式と同じ記号 $p_j,e_j$ を用いているだけで、(50)(51)式の素因数とその指数は(46)式とは別に定まるものである。そして、以下に現れる $p_j,e_j$ は全て(50)式のものである。)

　このとき、 $p_j \gt q_{n-1}$ となる素因数を1つ選び、

$q_{m+1}=p_j$ ……(51)

とおく。そして、 $k_{m+1}=1,2,\cdots,e_j$ に対して、

$n=n_{m+1}=n_m q_{m+1}^{k_{m+1}}$ ……(52)

とおく。すると、

$r^{n_m q_m^{k_{m+1}}}\equiv -1 \; (\bmod q_m)$

であれば、①～③より、(52)式で構成される全ての $n$ は一般化されたマスターデーモンの解となる。
　最後に、

$r_{m+1}=(r_m)^{q_{m+1}^{k_{m+1}}}$ ……(53)

とおき、同じアルゴリズムを繰り返すことで、一般化されたマスターデーモンの全ての解が得られる。(このことは、rを(53)式で繰り返し与え直して、①～③を繰り返し適用できることからわかる。)
　このアルゴリズムが有限回で終われば、一般化されたマスターデーモンは有限個の解しか持たない。このアルゴリズムが有限回で終わるためには、 $k_1,k_2,\cdots$ のあらゆ取り方によって構成され得る任意の自然数の系列

$r_1+1,r_2+1,\cdots,r_m+1,\cdots$ ……(54)

に現れる素因数の種類が有限であればいい。(これは素因数分解を前提にした話になっているので、これ以上立ち入って一般論を展開するのはかなり困難だと思う。)

　特に、 $r=2$ のときは、

$2+1=3$
$2^3+1=9=3^2$

となるので、上記のアルゴリズムは１回目で終了し、 $r=2$ のときの解が3しか存在しないことがわかる。他にもいくつかの $r$ で試してみる。

　 $r=3$ の場合は、

$r+1=4=2^2$

なので、解は存在しない。

　 $r=4$ の場合は、

$4+1=5$
$4^5+1=1025=5^2\times 41$

より、 $n=5,205(=5\times41)$ などが解になるが、(54)式の系列に現れる素因数の種類が有限であるかは自明でないので、解の個数も自明ではない。

　 $r=5$ の場合は、

$5+1=6=2 \times 3$
$5^3+1=126=2\times 3^2 \times 7$

より、 $n=3,21(=3\times 7)$ などが解になるが、これもまた、(54)式の系列に現れる素因数の種類が有限であるかは自明でないので、解の個数も自明ではない。

　 $r=20$ の場合も考えてみると、

$20+1=21=3\times 7$

より、 $n=3,7$ などが解になることがわかる。この場合も解の個数は非自明である。

　最後に、以上のアルゴリズムから次の系が導かれることを指摘しておく。

(i) $r+1$ が奇数の素因子を持たないとき、一般化されたマスターデーモンは解を待たない。
(ii) $r+1$ が奇数の素因子を持つとき一般化されたマスターデーモンは解を持ち、そのうち最小の解は、 $r+1$ の最小の奇数の素因子 $p$ に一致する。

*1: $r \equiv -1 (\bmod q)$ より、 $r$ と $q$ は互いに素なので、 $r$ と $q^2$ も互いに素。

2018-07-23

マスターデーモンがついに解けました

数学オリンピック数学追記あり、一部未完成

Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴

整数論の絶版本・品切れ本をコチラから購入できます！

追記(2018/07/25):計算ミスがあり、証明も冗長だったので、少し修正しました。

マスターデーモン

　マスターデーモンとは、1990年IMO中国大会の第3問で出題された次の問題である。

「2以上の自然数 $n$ で
$\frac{2^n+1}{n^2}$ ……(1)
が整数となるものを全て求めよ。」

　この問題、かなり前に挑戦したが、解けなくてしばらく放置していた。

sky-time-math.hatenablog.jp

　ひさびさに問題を見てみるとなんだか解ける感触がしたので、やってみたらついに解けました。そこで、今回は自分がたどり着いた解法を記事にまとめておきます。フェルマーの小定理と合同式さえしっていれば、普通の高校生でも理解できるように書いたつもりです。最近暑くて頭の回転が鈍っているので、うっかりどこかを間違えているかもしれませんが、そのときは優しく指摘してくれると助かります。

追記(2018/07/28):一般化されたマスターデーモンの解を与えるアルゴリズムも作りました。興味がある方は以下の記事を参考にしてください。

sky-time-math.hatenablog.jp

解答のアウトライン

　 $n$ が偶数なら、与式の分母が偶数、分子が奇数となるので題意の式は整数にならない。以後、 $n$ は奇数とする。
　 $n=3$ が求める解の内の一つであることはすぐにわかる。そして、解がこれしかないことを示したい。
　今回、自分が使ったアプローチは「因数分解」による方法だ。
$n$ がある素因数 $p( \ge 3)$ を $k(\ge 1)$ 個もつとき、すなわち $n=p^k N$ ( $N$ は奇数で、 $N$ と $p$ は互いに素。)とあらわせるとき、 $r^n+1$ は次の形に因数分解できる。( $r$ を自然数)

$r^n+1=(r+1) \cdot \frac{r^p+1}{r+1} \cdot \frac{r^{p^2}+1}{r^p+1} \cdots \frac{r^{p^k}+1}{r^{p^{k-1}}+1}\cdot \frac{r^{p^{k} N}+1 }{r^{p^k}+1}$ ……(2)

といっても、このままでは見づらいので、少し記号を用意する。 $m$ を奇数、 $x$ を自然数とするとき、自然数 $f_m(x)$ を

$f_m(x)=\frac{x^m+1}{x+1}=1-x+x^2-\cdots+x^{m-1}$ ……(3)

とおくと、(2)式は次のように書き直せる。

$r^n+1=(r+1) f_p(r) \cdot f_p(r^p) \cdot f_p(r^{p^2}) \cdots f_p(r^{p^{k-1}}) \cdot f_N(r^{p^k})$ ……(4)

このような因数分解が $n$ の各素因子ごとに存在するので、これをうまく使って問題を解いていく。証明は、次の２つのパートに分かれる。

① $n$ に素因数 $3$ がいくつ含まれるか？
$n=3^kN$ と表される場合を考えて、(4)式で $r=2$ , $p=3$ とすると、 $f_p(r^{p^l})$ ( $l=0,1,2,\cdots,k$ )が $3$ でちょうど一回だけ割れることを示す。そのことから、 $2^n+1$ が素因数 $3$ を $k+1$ 個だけ持つことがわかる。分母には素因子 $3$ が $2k$ 個現れるので、 $n=3^kN$ に現れる指数は $k=0,1$ でなければならないことがわかる。

② $n$ が $3$ より大きい素因数を持たないこと。
$n$ が $3$ の次に大きい素因子 $p$ を持つと仮定として、その指数を $m$ とする。つまり、 $n=3^k p^m M$ ( $k=0,1$ )と表せる場合を考える。このとき、 $8\equiv 1 (\bmod 7)$ のため、 $k=1$ の場合、

$2^n+1\equiv 8^{p^m M}+1 \equiv 2 \not\equiv 0 (\bmod 7)$

よって、 $k=1$ の場合、(1)式の分子は7の倍数ではないので、 $n$ は $7$ を素因数に持たない。
　最後に、 $2^n+1\equiv 8^{p^m M}+1$ が素因数 $p$ を持たないことを背理法により示す。

　①②から、題意を満たす $n$ が $3$ のみであることがわかる。

① $n$ に素因数 $3$ がいくつ含まれるか？

$n=3^kN$ と表される場合を考える。(4)式で $r=2$ , $p=3$ 、 $l=0,1,2,\cdots,k$ として、

$f_p(r^{p^l})=f_3(2^{3^l})=1-2^{3^l}+2^{2\cdot 3^l}$ ……(5)

ここで、 $2 \equiv -1 (\bmod 3)$ より、

$f_p(r^{p^l}) \equiv 1-(-1)^{3^l}+(-1)^{2\cdot 3^l} \equiv 1+1+1 \equiv 0 (\bmod 3)$

また、 $9=3^2$ を法として考えると、
$f_p(r)=1-2+4 =3 \not\equiv 0 (\bmod 9)$ ……(6)

であり、 $l=1,2,\cdots,k$ として、
$f_p(r^{p^l})=1-2^{3^l}+2^{2\cdot 3^l}=1-8^{3^{l-1}}+8^{2\cdot3^{l-1}}$ ……(7)

であるが、 $8\equiv -1 (\bmod 9)$ なので、

$f_p(r^{p^l}) \equiv 1-(-1)^{3^{l-1}}+(-1)^{2\cdot3^{l-1}} =1 +1+1 =3 \not\equiv 0 (\bmod 9)$ ……(8)

従って、 $f_p(r^{p^l})$ は素因数 $3$ をちょうど１つだけ持つ。

続いて、 $f_N(r^{p^k})$ が $3$ で割れないことを確認する。

$f_N(r^{p^k})=f_N(2^{3^k})=1-2^{3^k}+2^{2 \cdot 3^k} - \cdots + 2^{(N-1) \cdot 3^k}$ ……(9)

再び、 $2 \equiv -1 (\bmod 3)$ なので、

$f_N(r^{p^k}) \equiv 1 - (-1)^{3^k} + \cdots +(-1)^{(N-1)\cdot 3^k} (\bmod 3)$
$\equiv 1+1+\cdots+1=N (\bmod 3)$ ……(10)

ところで、 $N$ は $3$ と互いに素なので、 $N$ は $3$ の倍数でない。よって、

$f_N(r^{p^k}) \equiv N \not\equiv 0 (\bmod 3)$ ……(11)

以上より、(4)式で $r=2$ , $p=3$ とすることで、 $2^n+1$ は素因数 $3$ を $k+1$ 個持つことがわかった。したがって、分母に現れる素因数 $3$ の個数が $2k$ 個なので、(1)式が整数となるためには、

$k+1 \ge 2k$
$k =0,1$ ……(12)

でなければならないことがわかった。よって、題意を満たす $n$ は $n=3^k N$ ( $k=0,1$ )と表せる。

② $n$ が $3$ より大きい素因数を持たないこと

　 $n$ が $3$ の次に大きい素因子 $p$ を持つと仮定として、その指数を $m$ とする。つまり、

$n=3^k p^m M$ ( $k=0,1$ )……(13)

と表せる場合を考える。ここで、解答のアウトラインで書いたように、 $k=1$ のとき、 $p$ は $7$ ではない。

$p \neq 7$ ……(14)

$2^n+1$ が $p$ を素因数に持たないことを示したい。背理法で示したいので、 $2^n+1$ が $p$ で割り切れたと仮定する。まず

$R=2^{3^k}$ ……(15)

とおくと、 $k=0,1$ なので、

$R=2,8$ ……(16)

である。法を $p$ としてフェルマーの小定理を使うと、 $R^p\equiv R(\bmod p)$ なので、

$2^n+1=R^{p^m M}+1\equiv R^M+1 (\bmod p)$ ……(17)

となる。仮定より、 $2^n+1\equiv 0(\bmod p)$ なので、

$R^M +1 \equiv 0 (\bmod p)$ ……(18)
$R^{2M}\equiv 1 (\bmod p)$ ……(19)

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

$R^{p-1}\equiv 1 (\bmod p)$ ……(20)

であった。ここで、

$R^{\mu}\equiv 1(\bmod p)$ ……(21)

が成り立つ最小の自然数を $\mu$ とすると、(19),(20)式より、ある自然数 $s,t$ が存在して、

$2M=s \mu$ ……(22)
$p-1=t \mu$ ……(23)

と表せる。(22)式の両辺に $t$ をかけると、

$2Mt=s (p-1)$ ……(24)

ここで、(13)式に戻り、 $M$ の定義に立ち戻ると、 $M$ の素因子はすべて $p (\gt p-1)$ より大きいか、または $M=1$ なので、(24)式からある自然数 $u$ が存在して、

$s=Mu$ ……(25)

となる。これを(22)式に代入して整理すると、

$2=u \mu$ ……(26)

従って、

$\mu=1,2$ ……(27)

である。(16)式より $R=2,8$ であったので、

(i) $R=2$ の場合、(21)式から

$2 \equiv 1 (\bmod p)$ または $2^2 \equiv 1(\bmod p)$

$\Rightarrow 1\equiv 0(\bmod p)$ または $3 \equiv 0 (\bmod p)$ ……(28)

となるが、これを満たす素数 $p (\ge 5)$ は存在しないので矛盾。

(ii) $R=8$ の場合も、(21)式から

$8 \equiv 1(\bmod p)$ または $8^2 \equiv 1 (\bmod p)$

$\Rightarrow 7\equiv 0(\bmod p)$ または $63 =3^2\times7 \equiv 0 (\bmod p)$ ……(29)

となる。これを満たす素数 $p (\ge 5)$ は $7$ のみであるが、 $R=8$ のとき $k=1$ であり、この場合、(14)式に書いたように $p\neq 7$ なので矛盾。

　以上より、背理法の仮定が偽であることが言えたので、

$2^n+1$ は $p$ で割れないことが示された。

　以上より、 $n$ が $3$ より大きな素因数を持つとすると、 $2^n+1$ は $p$ で割れきれず、(1)式の分母 $n^2$ が素因数 $p$ を持つので、(1)式は整数にならない。従って、 $n$ は $3$ より大きい素因数を持たない。

よって、(1)式が整数になるような整数 $n (\ge 2)$ は、 $n=3$ に限ることが言えた。

2018-07-18

【素数p,q】5^p+1がqで割り切れ、5^q+1はpで割り切れる

twitter 数学整数問題bot②

数学関連の絶版本・品切れ本をコチラから購入できます！

整数問題bot②で見かけた良問

　昨日(今日)の深夜に整数問題bot②で、ある問題がふと目についた。次のツイートである。

素数の組(p,q)であって, 5^p+1がqで割り切れ, かつ5^q+1がpで割り切れるようなものを全て求めよ.
(出典はヒ・ミ・ツ(^_-)❤)
— 整数問題bot② (@handmade_math) 2018年7月17日

「出典はヒ・ミ・ツ♡」とか書いてあるのがお茶目で、すごく気になったのだ。
この問題、最初はどこから手を付けるかやや悩んだ。(深夜で頭の回転が鈍っていたのかもしれないが……)

　この問題を解き終わったとき、少し前に勉強した群論の知識がうまく使えて、本で勉強した知識を再確認でき、理解が一歩研ぎ澄まされた感じがした。つまり、群論を少し勉強した人にとって、この問題は良問だと思うので紹介してみたい。

　ここでの解説は、群論の知識が無い高校生でも読めるように書いてみるので、整数問題が好きな高校生でも楽しめると思う。

まずは観察と実験から

　まとまった解答は後で書くことにして、まずは問題を見て最初にやってみたことから紹介していこうと思う。このブログでは単に解答を紹介するだけじゃなくて、問題を解くときのライブ感も伝えてみたいからだ。この問題、初見ではどこから手をつけたらいいかすぐにはわからないだろう。そこで、具体的な小さな数で試してみる。解ける兆しが見えていないときでも、自分の手で一歩一歩問題に取り組むのが大切で、もし解けなくても「今の自分がどこまで行けるのか」を知ることが次の挑戦・成長にきっと繋がるからだ。

$p \le q$ として一般性を失わないので、 $p=2,3,5$ の場合をまずは試してみよう。

問題の式は、

$5^p+1 \equiv 0 (\bmod q)$ ……(1)
$5^q+1 \equiv 0 (\bmod p)$ ……(2)

と書ける。

まず、 $p=2$ のとき、 $5 \equiv 1 (\bmod 2)$ より、

$5^q+1 \equiv 1+1 \equiv 0 (\bmod 2)$
$5^2+1 \equiv 26 = 2 \times 13 \equiv 0 (\bmod q)$

よって、 $(p,q)=(2,2),(2,13)$ が解の一つであることがわかる。

次に、 $p=3$ のとき、 $5 \equiv -1 (\bmod 3)$ より、

$5^q+1 \equiv (-1)^q+1 = 0 (\bmod p)$ *1
$5^3+1 \equiv 126 = 2 \times 3^2 \times 7 \equiv 0 (\bmod q)$

よって、 $(p,q)=(3,3),(3,7)$ も解である。

$p=5$ のときは、 $5 \equiv 0 (\bmod 5)$ より、

$5^q+1 \equiv 1 (\bmod 5)$

となるので題意を満たさない。

　ここまでやってみて、見つかった解に規則性らしきものがなさそうに感じられるので、ひょっとしたら、 $p \ge 5$ の解は存在しないんじゃないかという気がしてくる。
実際、 $p=2,3$ 以外に解が無いことは後になってわかるが、前に進むために(1)、(2)式を少し変形してみる。

$5^p \equiv -1 (\bmod q)$ ……(1')
$5^q \equiv -1 (\bmod p)$ ……(2')

この式をしばらく見つめてみる。すると、右辺が $-1$ だから取扱いにくいのかなと思えてくる。そこで、(1')、(2')式の両辺を二乗して右辺を $1$ にしてみることにした。

$5^{2p} \equiv 1 (\bmod q)$ ……(3)
$5^{2q} \equiv 1 (\bmod p)$ ……(4)

　ここで、上の式がフェルマーの小定理(フェルマーの小定理 - Wikipedia)に似ていることに気づく。フェルマーの小定理を書き出してみると、 $p,q \not\equiv 5$ のとき、

$5^{q-1} \equiv 1 (\bmod q)$ ……(5)
$5^{p-1} \equiv 1 (\bmod p)$ ……(6)

が成り立つ。

　ここで、 $5$ を $1$ から順にべき乗していったときに、はじめて $1$ になるのはいつだろうかと考えてみることにした。*2このようなアイデアに自然に行き着いたのは、群論を勉強していたおかげだと思う。ともかく、

$5^\lambda \equiv 1 (\bmod p)$ ……(7)
$5^\mu \equiv 1 (\bmod q)$ ……(8)

を満たす最小の正の整数 $\lambda,\mu$ を考える。*3　このとき、(3)(4)(5)(6)式の指数は、それぞれ対応する $\lambda,\mu$ の倍数であることがわかる。*4 *5

もし、(7),(8)を満たす $\lambda,\mu$ が具体的に求まれば、 $p-1$ 乗や $q-1$ 乗といった考えにくい式は扱わなくてすむだろう。そんなわけで、この問題を解く方針が定まった。それでは、解答に移ろう。

解答

$p \le q$ として一般性を失わない。題意より、

$5^p+1 \equiv 0 (\bmod q)$ ……(1)
$5^q+1 \equiv 0 (\bmod p)$ ……(2)

であるが、これを変形して、

$5^{2p} \equiv 1 (\bmod q)$ ……(3)
$5^{2q} \equiv 1 (\bmod p)$ ……(4)

を得る。 $p,q \equiv 5$ の場合、(3)(4)式は明らかに成立しないので、以下 $p,q \not\equiv 5$ として考える。すると、フェルマーの小定理より、

$5^{q-1} \equiv 1 (\bmod q)$ ……(5)
$5^{p-1} \equiv 1 (\bmod p)$ ……(6)

が成り立つ。次に、

$5^\lambda \equiv 1 (\bmod p)$ ……(7)
$5^\mu \equiv 1 (\bmod q)$ ……(8)

を満たす最小の正の整数を $\lambda,\mu$ とおくと、(4)(6)(7)式より、 $2q$ と $p-1$ は共に $\lambda$ の倍数である。したがって、ある正の整数 $k,l$ により、

$2q=k \lambda$ ……(9)
$p-1=l \lambda$ ……(10)

この２つの式より、(9)式の両辺を $l$ 倍して、

$2 q l = k l \lambda = k(p-1)$ ……(11)

ここで、 $q$ は素数なので、 $k$ または $p-1$ を割り切る。ところが、仮定より $p-1 \lt p \le q$ なので、 $q$ は $p-1$ を割り切らず、 $k$ が $q$ の倍数であることが言える。よって、ある正の整数 $m$ が存在して、

$k=mq$ ……(12)

が得られる。これを(9)式に代入すると、

$2q=mq \lambda$
$2=m \lambda$ ……(13)

となり、 $m,\lambda$ が正の整数であることから、

$\lambda=1,2$ ……(14)

であることがわかった。

① $\lambda=1$ の場合、

(7)式より、

$5^1\equiv 1 (\bmod p)$ ……(15)

これを満たす素数 $p$ は $p=2$ のみである。

② $\lambda=2$ の場合、

(7)式より、

$5^2=25 \equiv 1 (\bmod p)$ ……(16)
$5^1 \not\equiv 1 (\bmod p)$ ……(17)

ここで、(16)式を満たす素数 $p$ は、 $p=2,3,\cdots$ と調べていくことで、 $p=2,3$ のみであることがわかる。 $p=2$ は(15)式を満たすので、(17)式を満たさない。よって、 $\lambda=2$ の場合、 $p=3$ となる。

　以上より、題意を満たす素数 $p(\le q)$ は、 $p=2,3$ しか存在しないことが分かった。よって、求める解は、 $p \le q$ の条件を取り除くと、

$(p,q)=(2,2),(2,13),(13,2),(3,3),(3,7),(7,3)$

だけであることがわかる。

最後に本の紹介

今回の問題が解けたのは、群論を雪江先生の本で勉強していたことが大きかったと思う。そこで、群論に興味がある人のために、以下の本をおススメしておく。

代数学1　群論入門 (代数学シリーズ)

作者: 雪江明彦
出版社/メーカー: 日本評論社
発売日: 2010/11/17
メディア: 単行本（ソフトカバー）
購入: 1人クリック: 21回
この商品を含むブログを見る

自分で読んだときは、数か所証明が分からないところもあったが、主要な部分は独学でも一通り理解できたので親切な良書だといえるだろう。ページ数も150ページ程度なので、頑張れば１～２週間くらいで読めるだろう。定理に対して例も豊富だが、ところどころ証明の要点があっさり書かれすぎている印象をいくらか受けた。数学科の優等生はこれで問題ないのだろうが、ここでつまづく人や独学の人は志賀先生の「群論への30講」を先に読んでみるのもいいと思う。ちなみに、こちらは少し頑張れば5~7日くらいで読めると思う。