流れる空の中で数学を。

とある数学好きの「手作りすうがく」と「気ままな雑記」。

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

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

前回の失敗から

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

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

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

 前回と同様に、背理法を用いる。復習のため、あえてもう一度書く。
 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)

と表す。ただし、abcdは互いに素であるとする*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)

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

dk=ab……(11)

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

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

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

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

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

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

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

caは互いに素である。

同様に、

cbも互いに素である。

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

 \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等に書いてある。また、英語版のwikipediaPythagorean triple - Wikipediaの2.3にも書いてある。(ちなみに、上記wikiの2の冒頭の公式から(19)~(21)式を導くには、s=m+n,t=m-nとおけばいい。)

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

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

 

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

合同数が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が既約分数とする。

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

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

合同数とは

直角三角形の斜辺をz、その他2つの斜辺を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)

とする。ここで、abcdは互いに素な自然数である。つまり、

 \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は合同数でないことが示された。

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

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

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

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:高々加算個であるかどうかすらわからないが……

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

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

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

  これが少し気になったので、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=100までの図をひとまず見ると、不等式の範囲内にあることがわかる。

f:id:FoxQ:20181005113053p:plain

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

f:id:FoxQ:20181005113106p:plain

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

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

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

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

 

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

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

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

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

 今回の記事では、マスターデーモンの一般化について考える。
自然数rが与えられたとき、2以上の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+14の倍数である。従って、

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)の約数になるが、Nqより小さい素因数を持たないので、

\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は1以上のある自然数で、e_j(j=0,1,\cdots,t)は0以上の整数で、e_jの内少なくとも1つは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でちょうど1回だけ割り切れるので、(15),(17)式より、

r^n+1q=p_je_j+k回だけ割り切れる……(22)

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

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

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

は一般化されたマスターデーモンの1つの解となっている。
 それでは、(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)式より、Nqが互いに素であることに注意して、

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の1次式で表せることに着目する。j自然数とするとき、

r^j=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)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) - 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)

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

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を1つとり、

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)式の素因数とその指数は(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)

とおく。すると、①~③より、(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

となるので、上記のアルゴリズムは1回目で終了し、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に一致する。

 

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

追記(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は奇数で、Npは互いに素。)とあらわせるとき、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の各素因子ごとに存在するので、これをうまく使って問題を解いていく。証明は、次の2つのパートに分かれる

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が素因数3k+1個だけ持つことがわかる。分母には素因子32k個現れるので、n=3^kNに現れる指数はk=0,1でなければならないことがわかる。

n3より大きい素因数を持たないこと。
n3の次に大きい素因子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の倍数ではないので、n7を素因数に持たない。
 最後に、2^n+1\equiv 8^{p^m M}+1が素因数pを持たないことを背理法により示す。

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

nに素因数3がいくつ含まれるか?

n=3^kNと表される場合を考える。(4)式でr=2,p=3l=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をちょうど1つだけ持つ。

 続いて、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)

ところで、N3と互いに素なので、N3の倍数でない。よって、

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

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

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

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

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

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

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

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

p \neq 7……(14)

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

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)より大きいので、(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+1pで割れないことが示された

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

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

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

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

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

 

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

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

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

まずは観察と実験から

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

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)

が成り立つ。

 ここで、51から順にべき乗していったときに、はじめて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)式より、2qp-1は共に\lambdaの倍数である。したがって、ある正の整数k,lにより、

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

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

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

ここで、q素数なので、kまたはp-1を割り切る。ところが、仮定よりp-1 \lt p \le qなので、qp-1を割り切らず、kqの倍数であることが言える。よって、ある正の整数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)

これを満たす素数pp=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 群論入門 (代数学シリーズ)

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

 

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

群論への30講 (数学30講シリーズ)

群論への30講 (数学30講シリーズ)

 

 

*1:q \ge p=3は奇数より。

*2:p-1q-1が、必ずしもそのような最小の正の整数になっているとは限らないことに注意!!

*3: (7)、(8)式を満たす整数が少なくとも1つ存在することは(3)、(4)式よりわかっているので、このような数が存在することがわかる。

*4:このことの証明は、着目する数が倍数でないと仮定して、その数\lambda,\muで割ったときの余りに着目するといい。背理法により、矛盾が導ける。

*5:群論では、ラグランジュの定理(ラグランジュの定理 (群論) - Wikipedia)で説明される。