　ここで、 $a_j (j=1,\cdots,N)$ はそれぞれ独立な乱数で、 $(-W/2,W/2)$ の間に一様に分布しているものとする。今回は、 $W$ の値として $W=0.02,2,20$ を取った。乱数を変えたときの零点の分布をまとめてみるために、 $N$ 次方程式を繰り返し生成し、零点を計算した。 $N$ 毎に、零点の総数が3000個になるように多項式の個数を用意し、計算を行った。

$W=2$ の場合

　まずは、乱数の値がとる幅を $W=2$ にして、２次方程式から５次方程式の零点の分布を見てみよう。画像中の「Seeds=」は方程式の総数を表していて、「N=」は多項式の次数を表している。

f:id:FoxQ:20181022123050p:plain

f:id:FoxQ:20181022123137p:plain

f:id:FoxQ:20181022123156p:plain

f:id:FoxQ:20181022123220p:plain

　実軸上を走る零点はどの次数の場合にもあるが、その他の零点は次数が上がるにつれて、円形に近づいて行っているように見える。そこで、次数を $N=10,20,30$ まで上げてみた。

f:id:FoxQ:20181022123425p:plain

f:id:FoxQ:20181022123440p:plain

f:id:FoxQ:20181022123458p:plain

　以上のように多項式の次数を上げていくと、円形に分布する零点が現れることがわかった。

$W=0.02$ の場合、

　次にやったのは、乱数の幅を小さくとることだった。 $W=0.2$ の場合もやったのだが、 $W=0.02$ の場合の方が零点の分布がより特徴的で最も面白かったので、そちらを載せることにする。 $W=2$ の場合との大きな違いは、多項式の次数が小さい場合に顕著に表れる。

　それでは、次数が $N=2,3,4,5$ の場合を見ていこう。

f:id:FoxQ:20181022123909p:plain

f:id:FoxQ:20181022123922p:plain

f:id:FoxQ:20181022123932p:plain

f:id:FoxQ:20181022123941p:plain

　明らかに、 $W=2$ の場合とは異なる零点の分布が見て取れる。 $N$ 次多項式の場合、 $2N-2$ 個の塊が零点の分布として現れるのだ。そして、中央の「空白」は円形になっているように見える。なんとも不思議である。このような分布が現れる理由を説明できる方がいたらぜひ教えてください。
　 $N=10,20,30$ の場合も見ていく。すぐ下にあるように、 $N=10$ の場合は、なんとか、上下に9個ずつの塊があるのが見える。

f:id:FoxQ:20181022124137p:plain

f:id:FoxQ:20181022124146p:plain

f:id:FoxQ:20181022124157p:plain

　そして、次数を増やしていくと、零点の分布はやはり円形に近づいていく。

$W=20$ の場合

　最後に、おまけとして、 $W=20$ の場合もやってみた。 $N=2$ 次から $5$ 次までをまずはみてみたが、この場合は最初から円形に近い分布が見て取れた。(縦横の比が違うので、楕円っぽくみえますが値はおおよそ円です。)

f:id:FoxQ:20181022124514p:plain

f:id:FoxQ:20181022124525p:plain

f:id:FoxQ:20181022124534p:plain

f:id:FoxQ:20181022124543p:plain

　最後に、次数をさらに大きくした場合を見て終わりにする。

f:id:FoxQ:20181022124738p:plain

f:id:FoxQ:20181022124748p:plain

f:id:FoxQ:20181022124801p:plain

次数を上げると、だんだん零点の分布が原点に絞り込まれていく傾向があることがわかった。また、ここまでを通して、 $W$ が小さいときに見られた円の内部の空白が、 $W=20$ では埋まってしまうこともわかった。

2018-10-12

【修正版】3が合同数でないことの初等的証明

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

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

追記(2018/10/13):(10)式で計算ミスをしており、 $a^2$ ではなく、 $a^4$ でした。そのため、原始ピタゴラス数の3つ組が $(a^2,6b,c)$ となり、不等式の評価で矛盾を導けなくなってしまいました。いつかうまくいったら、更新します。

前回の失敗から

前回の記事では、３が合同数でないことを初等的に証明しようとしたが、証明に飛躍があり見事に失敗した。(自然数 $n$ が合同数であるとは、全ての辺の長さが有理数で、面積が $n$ の直角三角形が存在することと定義されている。)
sky-time-math.hatenablog.jp

今回の記事では、証明の修正に成功できたと思うので、３が合同数でないことを改めて証明することに挑戦する。

背理法からピタゴラス数へ

　前回と同様に、背理法を用いる。復習のため、あえてもう一度書く。
　3が合同数であると仮定する。すなわち、ある有理数 $x,y,z$ が存在して、

$x^2+y^2=z^2$ ……(1)
$xy=6$ ……(2)

と仮定する。*1上式を $x^2$ で割って、

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

(4)式を(3)式に代入して、

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

ここで、有理数 $x,z$ を

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

と表す。ただし、 $a$ と $b$ 、 $c$ と $d$ は互いに素であるとする*2。
　(5)式に、 $b^4 d^2$ をかけて、

$(abc)^2 = d^2 (a^4+6^2 b^4)$ ……(9)

を得る。両辺を $a^2 b^2$ で割ると、

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

を得る。ここで、 $c$ と $d$ が互いに素であるためには、 $ab$ が $d$ の倍数でなければいけない。すなわち、ある自然数 $k$ が存在して、

$dk=ab$ ……(11)

と表せる。(10)式の両辺に $k^2$ をかけて整理すると、

$(ck)^2=a^2+6b^2$ ……(12)

を得る。
　ところで、(12)式より、 $a$ と $b$ が互いに素であるためには、 $k$ と $a$ 、 $k$ と $b$ がそれぞれ互いに素でなければいけない。このことと、(11)式より、 $d$ が $ab$ の倍数であることがわかるので、結局、

$k=1$ ……(14)
$d=ab$ ……(15)
$c^2=a^2+(6b)^2$ ……(16)

が言える。まずは、このように合同数の問題が、ピタゴラス数の問題へと書き換わる。

ピタゴラス数から原始ピタゴラス数へ

　次のステップに進むために、(16)式に現れる $a,6b,c$ がそれぞれ互いに素であること、つまり原始ピタゴラス数になっていることを示す。 $c$ が $a$ と互いに素でないと仮定すると、(16)式より明らかに、 $a$ と $b$ が互いに素でなくなり、矛盾する。よって、

$c$ と $a$ は互いに素である。

同様に、

$c$ と $b$ も互いに素である。

　次に、(16)式に現れる数『6』の取扱いがポイントとなる。
　そこで、 $\gcd (a,6) \neq 1$ と仮定してみると、 $a$ は2,3,6のいずれかの倍数となる。これに対応して、(16)式より、 $c$ も2,3,6のいずれかの倍数になる。ところが、(15)式より、 $d$ が $a$ の倍数なので、 $d$ も2,3,6のいずれかの対応する倍数になる。このことは、 $c$ と $d$ が互いに素であったことに矛盾する。従って、

$\gcd (a,6) = 1$ ……(17)

が言えた。さらに、 $\gcd (c,6) \neq 1$ と仮定すると、(16)式より、 $\gcd(a,6) \neq 1$ となり矛盾するので、

$\gcd (c,6) =1$ ……(18)

も従う。以上より、(16)式に現れる

$a,6b,c$ は原始ピタゴラス数である

ことがわかった。

原子ピタゴラス数の表し方

　任意の原始ピタゴラス数を表す公式があり、(16)式は、互いに素な奇数 $s,t (s \gt t \ge 1)$ を用いて、

$a=st$ ……(19)
$6b=\frac{s^2-t^2}{2}$ ……(20)
$c=\frac{s^2+t^2}{2}$ ……(21)

と表せる。この公式の導出は、例えば、『はじめての数論（原著第3版）』の定理2.1等に書いてある。また、英語版のwikipediaのPythagorean triple - Wikipediaの2.3にも書いてある。(ちなみに、上記wikiの2の冒頭の公式から(19)～(21)式を導くには、 $s=m+n,t=m-n$ とおけばいい。)

はじめての数論原著第3版発見と証明の大航海‐ピタゴラスの定理から楕円曲線まで

作者: Joseph H. Silverman,鈴木治郎
出版社/メーカー: 丸善出版
発売日: 2014/05/13
メディア: 単行本（ソフトカバー）
この商品を含むブログ (1件) を見る

　ここで、原子ピタゴラス数の表式から次のステップに進む前に、ある不等式の評価をしておく。

合同数が3の場合に成り立つ不等式

　(10)式に相加・相乗平均の式を用いて、次のように不等式を得る。

$c^2=d^2 ( (\frac{a}{b})^2 + (6 \frac{b}{a})^2 )$
$\ge 2 d^2 \sqrt { (\frac{a}{b})^2 (6 \frac{b}{a})^2}$
$\ge 12d^2$ ……(22)

　 $c,d$ は正の数なので、目的の不等式

$c \ge 2 \sqrt {3} d \gt 3 d$ ……(23)

を得る。これが、今回の証明の鍵となる。

証明の完了へ

　(20)式より、

$b=\frac{s^2-t^2}{12}$ ……(24)

また、(15)(19)式より、

$d=ab=\frac{st(s^2-t^2)}{12}$
$=\frac{1}{12} st (s+t)(s-t)$ ……(25)

ところで、(17)式に書いたように $a$ と6は互いに素なので、 $a=st$ と表されていることを考慮すると、

$s,t \equiv \pm 1 (\mod 6)$ ……(26)

と表されることがわかる。このことから、 $s-t$ が最小になるのは、ある整数 $l$ によって、 $s,t$ が

$s=6l+1$ ……(27)
$t=6l-1$ ……(28)

と表される場合であることが言える。すなわち、

$s-t \ge 2$ ……(29)

である。これを(25)式にあてはめると、

$d \ge \frac{1}{6} st (s+t)$
$\iff 3d \ge \frac{s^2 t+t^2 s}{2}$ ……(30)

を得る。ところが、(26)式を満たす奇数 $s,t$ は、

$s \ge 5$ ……(31)
$t \ge 1$ ……(32)

以上となる。したがって、(30)式は、

$3d \ge \frac{s^2 + 5t^2}{2}$ ……(31)

となる。ここで、(21)式より

$c=\frac{s^2+t^2}{2}$ ……(21)

であったので、明らかに、

$3d \gt c$ ……(32)

が導かれる。ところが、(23)式より、 $c \gt 3d$ であったので、これは矛盾である。
　以上より、一番最初の背理法の仮定が偽であることが言える。すなわち、3は合同数ではないことが証明できた。

*1: $z$ が直角三角形の斜辺の長さになる。

*2:つまり、 $x,z$ が既約分数とする。

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/10/13):(10)式で計算ミスをしており、ではなく、でした。そのため、原始ピタゴラス数の3つ組がとなり、不等式の評価で矛盾を導けなくなってしまいました。いつかうまくいったら、更新します。

前回の失敗から

背理法からピタゴラス数へ

ピタゴラス数から原始ピタゴラス数へ

原子ピタゴラス数の表し方

合同数が3の場合に成り立つ不等式

証明の完了へ

合同数とは

Mathpower2018で聞いた宿題

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

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

零点の分布

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

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

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

零点の分布

零点の絶対値の範囲

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

今回の話のアウトライン

①が偶数にならないこと

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

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

④、であること

⑤であること

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

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

マスターデーモン

「2以上の自然数で……(1)が整数となるものを全て求めよ。」

解答のアウトライン

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

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

$W=2$ の場合

$W=0.02$ の場合、

$W=20$ の場合

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

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

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

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

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

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

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

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