インテジャーズ

読者です 読者をやめる 読者になる 読者になる

インテジャーズ

数、特に整数に関する記事。

5882353:この数は面白い

この記事は
www.adventar.org
の10番目の記事として寄稿しています。

9番目の記事は遠藤 逸ノ城さんの「内積とフーリエ解析」でした。
end01nojo.hatenablog.com

日曜数学者を「日曜に数学する者」と安直に定義するならば、私は、月曜日から土曜日までも数学をしますが、日曜数学者です。また、日曜数学者tsujimotter氏による定義

定義 (tsujimotter)
日曜数学とは「興味の赴くままに趣味として数学を探求すること」である。また、こうした行為を日常的に行っている人のことを、「日曜数学者」と呼ぶ。

に則れば、やはり私は日曜数学者です。

数学はとても大切かつ重要な学問です。「数」学という名前が付いているため、数学という言葉を聞くと「数やその計算」が頭に思い浮かぶ人は多いと思います。また、初等教育で習う数学は実際にそのような内容のため、そこで躓いてしまって数学と縁を切った人はなおさらそのようなイメージをもっていることと思います。しかし、数学という学問は「数や計算」に限定しない、非常に自由で豊かな学問です。数学は英語ではMathematicsであり、Numberという言葉は入っていません。英語圏の人々は実際の経験から日本人と同じような印象を数学に抱いているとは想像しますが、言葉の本来の意味を考えるとア・プリオリには全く「数」の要素は見られません。
Mathematicsという言葉の由来はギリシャ語μάθημα(科学、知識、学ぶことの意)およびμαθηματικός(学ぶことを好むこと)とされています。言葉の由来を考えると、学問の中の一分野として数学があるのではなく、「学問とはすなわち数学である」といってもよいぐらいの意味だったのです。もちろん、現代において「数学=学問」という認識は流石にありません。数学は学問全体における、ある一部分をさしています。しかし、「数を学ぶこと」よりは遥かに広く、豊かで、自由な、そして極めて重要な学問であることには間違いありません。例えば、Wikipediaには「数学は量(数)、構造、空間、変化などを研究する学問である」とあります。「数学」という文字から最初は「数やその計算」が頭に浮かぶ人は多いと思うと主張しましたが、実際には高校数学まで勉強すれば「数学は数、量、空間、変化などを研究する学問である」ぐらいまではイメージをもっている人が多いと思います。ここで、私が強調したいことはそれよりももっと数学は広いということです。「構造」が増えることによってだいぶ現代数学に近い、自由度の増した数学の説明となっています。しかしながら、私はこれでも数学の定義としては狭いと考えます。構造主義だけでは扱えない数学も現れつつあるように感じます*1

ここまでの主張をまとめると、「数学の定義を確認しよう」ということではなく、

「数学は数の研究に限定しない、自由な学問である」

ということです*2

さて、広く自由な学問「数学」において、私が最も好きな分野があります。それは

「数の研究」

です。私の人生で出会ったものの中で、「」ほど魅力的な存在はありません。当ブログでは「数の魅力を伝える」ことを目的として、様々な数のもつ魅力的な性質を解説させて頂こうと考えております。

日曜数学としての活動における題材としても、「面白い数を探求する」ことはお勧めです。ある数が他の数とは異なる性質をもっていることを知ったとき、その数に対する愛情が生まれます。時には、その発見が深い数学的理論の発見につながることさえもあります。

お勧めするだけで終わってはもったいないので、この記事でも一つ面白い数を紹介します。深い数学的理論につながる気配は今のところ全くないですが、面白い数であることには違いありません。その数とは 5882353 です(題名に書いてあります(笑) )。

5882353は素数です。これだけでも私は嬉しくなってしまいますが、素数は無数に存在するので、「5882353よ。私の全てをあなたに捧げよう。」といった感情までは起きないと思います。
もう少し眺めてみると4で割った余りが1であることが分かります。「二平方和の定理」の登場です。

integers.hatenablog.com

tsujimotter.hatenablog.com

二平方和の定理によれば、4で割った余りが1であるような素数は必ず二つの平方数の和で表すことができます。残念ながら具体的にどのような和になるかは教えてくれないので個別に計算しなければなりません。5882353の場合に具体的な表示を与えると


{\large 5882353=588^2+2353^2}


となります!これは中々面白い!「だから何?」と言われればお終いなのですが、「数遊び」あるいは「パズル」としては中々面白いと思います*3

「数マニア」がこういう面白い数に出会うと、次は決まってこうです:



「他にもこんな数あるの??」



ありまぁす!



\begin{align}101 &= 10^2+1^2\\ 1233 &= 12^2+33^2\end{align}



次はこうです:「無数にあるの?それとも有限個?」



無数にありまぁす!!




定義 d \colon \mathbb{N} \to \mathbb{N}を自然数の(10進法表記における)桁を返す写像とする。
例) d(127) = 3.

定理 方程式 x^2+y^2=x\cdot 10^{N}+y, \ N=d(y)は自然数解(x, y, N)を無数にもつ。

証明. 濱中裕明氏のブログに書かれている手法で証明する5882353の謎 | 低次元日記
NN\equiv 4 \pmod{16}を満たす任意の自然数とする(そのようなNは無数に存在する)。Fermatの小定理によって10^N \equiv 10^4 \equiv 4 \pmod{17}が成り立つ。そこで、\displaystyle x:= \frac{10^N-4}{17} \in \mathbb{N}とする。また、y:=4x+1とする。このとき、

\begin{equation}\begin{split}
x^2+y^2 &= x^2+(4x+1)^2 = 17x^2+4x+4x+1\\
&=x(17x+4)+(4x+1) = x\cdot 10^N+y\end{split}\end{equation}

が成り立つ。また、

\displaystyle y=4x+1=\frac{4(10^N-4)}{17}+1 = \frac{4\cdot 10^N+1}{17}

であり、

17\cdot 10^{N-1} \leq 4\cdot 10^N+1 < 17\cdot 10^N

なので、N=d(y)が成り立つ。 Q.E.D.

この証明の構成法から、例えば

\begin{equation}\begin{split}&588235294117647058823529411764705882353 \\ &=5882352941176470588^2+23529411764705882353^2\end{split}\end{equation}

が得られます。

無限個存在することがわかると、次なる疑問として

1015882353は素数であるが、1233588235294117647058823529411764705882353は素数でない。素数に限定すると、このような数はどれだけあるか?

が生じます。

ちなみに素因数分解は

1233=3^2\times 137

\begin{equation}\begin{split}&588235294117647058823529411764705882353\\ &=5070721\times 5882353\times 19721061166646717498359681\end{split}\end{equation}

です。

なんと、答えは

「このような素数はこの世に101と5882353しか存在しない」

です。101は小さい数なので多数の性質をもっており、既に愛着が湧いている人も多いことと思います。しかし、5882353に特別な感情を抱いていた人は少なかったのではないでしょうか?少なくとも、私はこの事実をもって、すっかり「5882353」のファンになってしまいました*4

それでは、この事実を数学的な定理として定式化して証明しましょう(Jean Claude RosaによるPuzzle 180. Primes as a sum of squares)。

定理 pp \equiv 1 \pmod{4}なる素数とする。二平方和の定理によってp=x^2+y^2なる自然数x, yが存在する。このとき、p=x\cdot 10^{d(y)}+yが成立するようなp1015882353に限る。

いくつか補題を用意します。

補題1自然数n, mに対してd(nm) = d(n)+d(m)またはd(nm)=d(n)+d(m)-1が成り立つ。

証明. d(n) = N \Longleftrightarrow 10^{N-1}\leq n < 10^Nに注意すれば容易に示せる。 Q.E.D.

補題2 r \in \mathbb{Q}かつ r^2 \in \mathbb{Z}ならばr \in \mathbb{Z}.

証明. 有理数に対する素因数分解を考える。このとき、r \in \mathbb{Q}に対してr \in \mathbb{Z} \Longleftrightarrow \mathrm{ord}_p(r) \geq 0 ({}^{\forall}p : \text{素数})に注意する。r^2\in \mathbb{Z}ならば、任意の素数pに対して\mathrm{ord}_p(r^2)=2\mathrm{ord}_p(r) \geq 0なので、r \in \mathbb{Z}がわかる。 Q.E.D.

補題3 nを自然数とする。このとき、10^{2^n}+1の素因数はある自然数kを用いて、必ずk\cdot 2^{n+1}+1と書ける。

証明. p10^{2^n}+1の素因数とする。このとき、pは奇素数であるが、5でもないことに注意する。10^{2^n}\equiv -1 \pmod{p}なので、10は法pで位数2^{n+1}である。よって、Fermatの小定理から10^{p-1}\equiv 1 \pmod{p}なので、2^{n+1}p-1の約数であることがわかる。
integers.hatenablog.com
におけるFermat数に対するLucasの定理の証明と対比せよ(こちらの方が弱い主張なので、証明は簡単になっている)。 Q.E.D.


定理の証明. p=x^2+y^2=x\cdot 10^{d(y)}+yが成り立っていると仮定して、p1015882353でなければならないことを示す。

p=101は例外ケース

まず、y=1の場合を考えよう。このとき、x^2+1=10x+1が成り立つので、x=10, \ p=101となる。よって、以下y \neq 1, p \neq 101と仮定し、p=5882353でなければならないことを示す。

p10^{2N}+1の素因数である

N:=d(y)とおく。\displaystyle 10^N=\frac{p-y}{x}なので、

\displaystyle \begin{equation}\begin{split}
10^{2N}+1 &= \left( \frac{p-y}{x} \right)^2 +1 = \frac{p^2-2py+y^2+x^2}{x^2}= \frac{p(p-2y+1)}{x^2} \\
&= p\frac{x^2+y^2-2y+1}{x^2} = p\left\{ 1+\left( \frac{y-1}{x} \right)^2 \right\} \end{split}\end{equation}

と計算できる。定義より明らかにpxは互いに素である。よって、\displaystyle \frac{p(p-2y+1)}{x^2} \in \mathbb{Z}から\displaystyle \frac{p-2y+1}{x^2} \in \mathbb{Z}が言える。故に、p10^{2N}+1の素因数であり、補題2からxy-1を割り切ることがわかる。

pは桁の大きい数である

p=x\cdot 10^N+yなので、yは奇数である。特に、y \neq 10^{N-1}。よって、d(y)=d(y-1)=Nであり、補題1から

d(y(y-1))=2N \ \text{or} \ 2N-1

である。定義からx(10^{N}-x)=y(y-1)と変形できるので、

d(x(10^N-x))=2N \ \text{or} \ 2N-1

を得る。ここで、x=y-1とはなり得ないことを確認しよう。もし、x=y-1なら10^N-1=2xとなって、左辺は奇数、右辺は偶数と矛盾する。これとxy-1を割り切ることを合わせると\displaystyle x \leq \frac{y-1}{2}がわかる。よって、

\displaystyle x \leq \frac{y-1}{2} < \frac{10^N-1}{2} \leq 10^N-10^{N-1}

なので、d(10^N-x)=Nが従う。故に、補題1から

d(x(10^N-x))=d(x)+N \ \text{or} \ d(x)+N-1

となる。先ほど得た結果と比較することにより、d(x)=N \ \text{or} \ N-1である。こうして、pの桁がコントルールされる:

d(p)=d(x\cdot 10^{N}+y) = d(x)+d(y) = 2N \ \text{or} \ 2N-1.

余因子の条件

pの桁のコントロールから次の主張が成り立つ:

主張 10^{2N}+1=pMと因数分解されているとする。このとき、d(M)=2 \ \text{or} \ 3である。

主張の証明. もし、M=1ならば

2N+1 = d(10^{2N}+1) = d(p) = 2N \ \text{or} \ 2N-1

となって矛盾である。よって、M \neq 1。また、Mは一桁の素因数をもたない。実際、10^{2N}+12, 3, 5で割り切れないことは容易にわかる。\bmod{7}で考えると10^{2N}+1 \equiv 2^N+1であり、\{ 2^n \pmod{7} \} \equiv \{ 1, 2, 4 \}なので、やはり7でも割れないことがわかる。一方、d(p)=2N \ \text{or} \ 2N-1d(10^{2N}+1)=2N+1および補題1より、d(M) \leq 3がわかる。 主張の証明終わり。

Nが奇数の場合

Nが奇数ならば、因数分解公式:

x^N+1=(x+1)(x^{N-1}-x^{N-2}+\cdots -x+1)

より10^{2N}+1101で割りきれ、

\displaystyle A:=\frac{10^{2N}+1}{101} = 10^{2(N-1)}-10^{2(N-2)}+\cdots +1

とすると、d(A)=2N-2である。今、p \neq 101なる仮定よりpAの素因数なので、

2N-1 \leq d(p) \leq d(A) = 2N-2

となって矛盾する。すなわち、Nが奇数のケースは起こり得ない。

N=2^km \ (k\geq 1, \ m\geq 3 \ \text{奇数})の場合

このケースも因数分解公式を用いることにより、10^{2N}+1 = (10^{2^{k+1}}+1)Bと因数分解される。もし、pBの素因数であるならば、d(M) \geq d(10^{2^{k+1}}+1) \geq d(10001)=5となって、d(M)=2 \ \text{or} \ 3に矛盾する。よって、p10^{2^{k+1}}+1の素因数でなければならない。このケースは次のケースの証明に帰着される。

N=2^k \ (k\geq 1)の場合

以下の素因数分解データを眺める(Factorization of 100...001を参照した):

10^4+1 = 73 \times 137
10^8+1  = 17 \times 5882353
10^{16}+1 = 353 \times 449 \times 641 \times 1409 \times 69857
10^{32}+1 = 19841 \times 976193 \times 6187457 \times 834427406578561
\begin{equation}\begin{split}10^{64}+1 &= 1265011073 \times 15343168188889137818369 \\ & \ \ \ \times 515217525265213267447869906815873\end{split}\end{equation}
10^{128}+1 = 257 \times 15361 \times 453377 \times 558711876337536212257...(116\text{桁})
\begin{equation}\begin{split}10^{256}+1 &= 10753 \times 8253953 \times 9524994049\times 73171503617\\ & \ \ \ \times 1616596633...(225\text{桁})\end{split}\end{equation}

ここに現れる素因数であってd(M)=2 \ \text{or} \ 3を満たすものは 73, 137, 5882353しかない。17=4^2+1^2, 137=4^2+11^2は題意を満たさない。よって、1\leq k \leq 8の場合はpの候補が5882353しかないことが示された。

最後にk\geq 9の場合であるが、10^{2^{k+1}}+1の最小の素因数をqとしよう。そうすると、補題3より、ある自然数\ellが存在してq=\ell \cdot 2^{k+2}+1が成り立つため、

d(q) = d(\ell \cdot 2^{k+2}+1) \geq d(2^{10}+1) = d(1025) = 4

となる。これは、d(M) = 2 \ \text{or} \ 3とはなり得ないことを意味する。 Q.E.D.

以上で、定理が証明されました。他に考えられる問題として

  1. 一般にb進法で同様の素数を考えるとやはり有限個しか存在しないのではないか?
  2. 他の進法で5882353のような例を探す。
  3. 合成数の場合に構成法を一つ紹介したが、一般解は求めることができるか?
  4. 三乗+三乗で似たような数があるか?などを思いつきました。このように、一つ面白い題材があると、どんどん問題が広がっていきます。皆さんもこうした問題を見つけて楽しく日曜数学していきましょう。

追記)
integers.hatenablog.com


明日の日曜数学Advent CalenderはToshiki Takahashiさんの「チューリングの波動関数」です。

*1:当然、数学にはここでは語りつくすことのできない、様々な特徴や側面がありますが、数学の重要な一つの特徴として「正しい数学的主張には証明を伴う必要がある」というものがあります。逆に言えば「証明された主張(定理)は正しい」という特徴をもっています。この「正しさ」と数学の「自由性(広さ)」を合わせて考えると、例えば物理学の法則が数学を用いて解き明かされていくことは全く不思議ではなく、当然の事であると私には思えます。

*2:大学の数学の授業で出てきた数が0と1だけだったなんてことはよくあります。

*3:数遊びを馬鹿にしてはいけません。二平方和の定理だって始まりは数遊び、しかし類体論という大理論まで発展したという歴史があります。かの有名なFermatの最終定理も数遊びですが、それを解くために開発された数学は極めて重要なものばかりです。数遊びが数学を豊かにしてきたといっても過言ではありません。

*4:5882353 「ゴーヤは兄さん降参」なんてどうでしょう。