2018年12月23日 | ブログ記事

素数のアレコレつめあわせ

youjo_tape

本記事は、traP アドベントカレンダー 2018 の 60日目 の記事です。
明後日が最終日らしいので、たぶん traP におけるクリスマスは 12/62 なんでしょうね。

当初、この記事では J 言語の話をしようと思ってたのですが、難解なリファレンスを読み切れずに断念しました……

そこで、この記事ではわたし youjo_tape が知っている 素数 に関する雑学を書き並べます。
需要とかそういうのは知りません

1. 日付ネタ

今日は 12/23 ですね。1223 は小さい方から数えて 200 番目 の素数です。
このように mmdd の形式で記述したときに素数になる日付は、今年はあと 1229, 1231 の 2 個だけです。
これに関連して(?)、10000 以下の素数の個数が 1229 個だったりします。

ところで、アドベントカレンダーといえば、本来は「来たるクリスマス(12/25)を迎えるまでの日数を数えるため」のものでした。
1225 といえば、やはり 平方数 で有名ですよね。1225=3521225 = 35^2 です。
しかし実は、1225 は 三角数 でもあります。

三角数とは、その数だけ点を並べるとちょうど三角形がつくれるような数です。
小さい順に書けば、1,3,6,10,1, 3, 6, 10, \cdots となりますね。それぞれ、以下の三角形に対応します:

o   o     o       o
   o o   o o     o o
        o o o   o o o
               o o o o

この図から察せるように、nn 番目の三角数は i=1ni=n(n+1)2\displaystyle \sum_{i=1}^n i = \frac{n(n+1)}2 と表せますね。
したがって、1225=49×5021225 = \dfrac{49 \times 50}2 なので、12251225 は 49 番目の三角数とわかります。

ちなみに、平方数かつ三角数であるような数は 平方三角数 と呼ばれることがあります。なんとも珍しそうに思えますが、平方三角数は無限に存在することがわかっています。具体的に、nn 番目の平方三角数は

132((1+2)2n(12)2n)2\frac1{32}\left(\left(1+{\sqrt 2}\right)^{2n}-\left(1-{\sqrt 2}\right)^{2n}\right)^2

で与えられることを、あの Euler さんが示していました。

素数に話を戻しますが、今日は 2018/12/23 ですね。
なんと、20181223 も素数です! ちなみに、この次の素数は 20181229 で、これも yyyymmdd 形式の日付と解釈できますね。

2. フェルマーの二平方定理

とは、以下のような定理です:

素数 pp は、44 で割って 11 余るならば、ある自然数 x,yx, y が存在して p=x2+y2p = x^2 + y^2 と表せる。[1]

証明の方法は様々ですが、そのひとつに Zagier さんが与えた以下のようなものがあります:

有限集合 S={(x,y,z)N3x2+4yz=p}S = \{(x,y,z) \in \mathbb N^3 \mid x^2 + 4yz = p\} 上の対合

(x,y,z){(x+2z,z,yxz)(x<yz)(2yx,y,xy+z)(yz<x<2y)(x2y,xy+z,y)(2y<x)(x, y, z) \mapsto \begin{cases} (x+2z, z, y-x-z) & (x < y-z) \\ (2y-x, y, x-y+z) & (y-z < x < 2y) \\ (x-2y, x-y+z, y) & (2y < x) \end{cases}

は必ず一個の不動点を持つから、集合 SS の元の個数は奇数であり、対合 (x,y,z)(x,z,y)(x, y, z) \mapsto (x, z, y) も不動点を持つ。

この一文で証明が完結しています。
しかし、行間が広すぎて、いったいどこがどう証明になっているのかすらサッパリですね。
順を追って行間を埋めていきましょう。

「有限集合 S={}S = \{\cdots\}

x2+4yz=px^2 + 4yz = p を満たすような (x,y,z)N3(x, y, z) \in \mathbb N^3 は明らかに高々有限個しかありません。大雑把に見ても x,y,z<px, y, z < p が必要ですもんね。
したがって、SS は確かに有限集合です。

「… 上の対合 …」

対合とは、ざっくりと言えば「2 回変換するともとげんに戻るような変換」です。
証明中で定められている対応を f:SSf \colon S \to S とおいて、これが正しく対合になっているか確認してみましょう:

まず、ff写像 として well-defined であるかどうかの確認からしなければなりませんね。定義中の 3 つの場合分け:

x<yz,   yz<x<2y,   2y<xx < y-z,\ ~~ y-z < x < 2y,\ ~~ 2y < x

をよく見てみましょう。常に yz<2yy-z < 2y であるので、この場合分けは直感的には「yzy-z および 2y2y と比較したときに、xx はどこにいるのか」という風に解釈できます。
しかし、範囲の重複こそないものの、x=yzx = y-z または x=2yx = 2y のときに ff が定まっていないように見えますね。ですが、

であるので、これらの場合には x2+4yzx^2 + 4yz が素数になる、すなわち x2+4yz=px^2 + 4yz = p が成り立つことはありません。この対偶をとれば、SS 上では常に x̸=yzx \ne y-z かつ x̸=2yx \ne 2y であることがわかるので、確かに ffSS 上の写像として well-defined であることが従います。

では次に、ff変換 ならびに 対合 になっているか確認しましょう。3 つの場合に分けて調べればよいですね:

以上より、確かに ffSS 上の対合であることが示せました。

「… は必ず一個の不動点を持つから、」

変換 φ\varphi の不動点とは、変換により変化しない(すなわち、φ(a)=a\varphi(a) = a となる)点のことです。
これより、対合 ff の不動点を求めるには、f(x,y,z)=(x,y,z)f(x, y, z) = (x, y, z) を解けばよいことになります。

ここで、ff の不動点 (x,y,z)(x, y, z) は、(存在すれば)必ず yz<x<2yy-z < x < 2y を満たします。

理由を述べます。先ほど ff が対合であることを示したとき、

写されてしまうことがわかりました。ということは、「x<yzx < y-z かつ 2y<x2y < x」となることはあり得ないので、このいずれの場合も (x,y,z)=(x,y,z)(x, y, z) = (x', y', z') は成り立ちません。

不動点は「ff による変換で条件が変わらない場所」にしか存在しえないよね、ということです:
fixed

したがって、yz<x<2yy-z < x < 2y としてよく、このとき

f(x,y,z)=(x,y,z)(2yx,y,xy+z)=(x,y,z){2yx=xy=yxy+z=zx=y\begin{aligned} f(x, y, z) = (x, y, z) &\Longleftrightarrow (2y-x, y, x-y+z) = (x, y, z) \\ &\Longleftrightarrow \begin{cases} 2y-x = x \\ y = y \\ x-y+z = z \end{cases} \\ &\Longleftrightarrow x = y \end{aligned}

となります。さらに、(x,y,z)(x, y, z)SS 上の点でなければならないことから、

x2+4yz=px2+4xz=px(x+4z)=p\begin{aligned} x^2 + 4yz = p &\Longleftrightarrow x^2 + 4xz = p \\ &\Longleftrightarrow x(x+4z) = p \end{aligned}

が必要です。したがって、x+4z>1x + 4z > 1 であるので、pp が素数である ことを考えると x=1, x+4z=px = 1,\ x + 4z = p でなければなりません。
以上をまとめると、ff の不動点は唯一で:

(1,1,p14)\left(1, 1, \dfrac{p-1}4 \right)

と求まります。pp44 で割って 11 余る素数 なので、p14\dfrac{p-1}4 は自然数であり、たしかにこの点が SS に含まれていることがわかりますね。

「集合 SS の元の個数は奇数であり、」

SS の元は、対合 ff によってペアをなしています。

不動点ではない点たち:
pair

ただし、ff の不動点 (1,1,p14)\left(1, 1, \dfrac{p-1}4 \right) だけは、いわば "自分自身とペアをなしている" ことになります。

不動点:
single

ff の不動点がちょうど 1 つだけ存在することは先ほど示していたので、SS が有限集合であることも踏まえると、SS の元は奇数個であることがわかりますね。

「対合 (x,y,z)(x,z,y)(x, y, z) \mapsto (x, z, y) も不動点を持つ」

文脈を汲み取ると、この対合は SS 上で考えているものでしょうね。
すなわち、これをもう少し丁寧に記述するならば、「対合 g:S(x,y,z)(x,z,y)Sg \colon S \ni (x, y, z) \mapsto (x, z, y) \in S」となるでしょうか。

x2+4yz=px^2 + 4yz = p という条件が y,zy, z に関して対称になっていることから、「y,zy, z を入れ替える」写像である ggSS 上の変換になっていることがわかります。また、gg が対合であることも明らかですね。

さて、この gg が不動点を持たないと仮定します。すると、SS の元は すべて 対合 gg により「2元1組の」ペアにすることができます。すると、SS は有限集合であったので、SS の元は偶数個ということになりますが、先ほど「SSの元は奇数個」と示したので、矛盾が生じます。
ゆえに、gg は不動点を持ちます。

「。」

証明文はここで終わりですが、「pp が 2 つの平方数の和で表せる」という結論にはまだ達していませんね。「後はわかるでしょ?」とばかりに省略されてしまったのです。

仕方がないので、最後の行間を埋めましょう。
gg が不動点を持つということなので、不動点のひとつを (x,y,z)(x, y, z) とおきます。すると、不動点の定義より、

g(x,y,z)=(x,y,z)(x,z,y)=(x,y,z){x=xz=yy=zy=z\begin{aligned} g(x, y, z) = (x, y, z) &\Longleftrightarrow (x, z, y) = (x, y, z) \\ &\Longleftrightarrow \begin{cases} x = x \\ z = y \\ y = z \end{cases} \\ &\Longleftrightarrow y = z \end{aligned}

がわかります。そして、(x,y,z)=(x,y,y)(x, y, z) = (x, y, y) が不動点であることから、とくに (x,y,y)S(x, y, y) \in S であることも従うので、

x2+4y2=px^2 + 4y^2 = p

すなわち、x2+(2y)2=px^2 + (2y)^2 = p が成り立ちます。これが求める表現です。■


丁寧に記述したら、めっちゃ長くなってしまいました。
しかし、なんでこんな証明を思いつくに至ったのでしょうね。対合 ff とかどっから出てきたのよ。

3. 素数の無限性

素数は無限に存在する。

言わずと知れた有名な定理ですね。これにも様々な証明があります。

ところで、唐突に話を位相空間論に移すのですが、みなさん「位相」ってご存知ですか?
知らない方には申し訳ないのですが、この項は「位相を知ってる人」向けの内容になっています。

とはいえ、完全に突き放すのも申し訳ないので、主要な定義だけ書いておきますね:

集合 XX に対し、その部分集合の集合 OP(X)\mathcal O \subset \mathcal P(X)XX 上の 位相 であるとは、以下の 3 条件を満たすことを言います:

  1. ,XO\emptyset, X \in \mathcal O
  2. U1,U2OU1U2OU_1, U_2 \in \mathcal O \Longrightarrow U_1 \cap U_2 \in \mathcal O
  3. UλO  (λΛ)λΛUλOU_\lambda \in \mathcal O ~ ~(\forall \lambda \in \Lambda) \Longrightarrow \displaystyle \bigcup_{\lambda \in \Lambda} U_\lambda \in \mathcal O

2 番目の条件は「O\mathcal O 内の 有限個の 共通部分は O\mathcal O 内に収まる」、3 番目の条件は「O\mathcal O 内の 任意個の 和集合は O\mathcal O 内に収まる」、ということをそれぞれ言っています。[2]

位相 O\mathcal O に属する集合 UU は、XX開集合 と呼ばれます。この名前からわかるように、「位相」というのは、ユークリッド空間なんかにおける「開集合」の一般化となっています。
たとえば、1 次元ユークリッド空間 X=RX = \mathbb R の開集合全体を O\mathcal O とすれば、上に示した 3 条件が成り立っていることが示せます。

さて、「開集合」があるなら、とうぜん「閉集合」もあります。
SXS \subset X が(XX の)閉集合 であるとは、その補集合 Sc=XSS^c = X \setminus S が開集合であることをいいます。

そして、補集合全体の集合を F\mathcal F とおくと、F\mathcal F に対して次の 3 条件が成り立っています:

  1. ,XF\emptyset, X \in \mathcal F
  2. F1,F2FF1F2FF_1, F_2 \in \mathcal F \Longrightarrow F_1 \cup F_2 \in \mathcal F
  3. FλF  (λΛ)λΛFλFF_\lambda \in \mathcal F ~ ~(\forall \lambda \in \Lambda) \Longrightarrow \displaystyle \bigcap_{\lambda \in \Lambda} F_\lambda \in \mathcal F

さっきのとの違いは、,\cup, \cap がひっくり返っていることですね。


詳しい説明は位相幾何学に関する書籍や講義に譲るとして、本題に移ります。
なんと、「位相」の概念を用いることで、素数の無限性を証明できる のです!

まず、a,bZ (a̸=0)a, b \in \mathbb Z ~(a \ne 0) に対し、aZ+b:={an+bnZ}a \mathbb Z + b \coloneqq \{an + b \mid n \in \mathbb Z\} と表記することにします。
特に b=0b = 0 の場合は、単に aZa \mathbb Z とだけ書くことにしましょう。

例えば、3Z+1={,5,2,1,4,7,}3 \mathbb Z + 1 = \{\cdots, -5, -2, 1, 4, 7, \cdots\}、みたいな感じです。

さて、これを用いると、P\mathbb P を素数全体の集合として、

Z{±1}=pPpZ()\mathbb Z \setminus \{\pm 1\} = \bigcup_{p \in \mathbb P} p \mathbb Z \hspace{20pt} \cdots (\ast)

が成り立ちます。±1\pm 1 以外の任意の整数は、ある素数で割り切ることができるためですね。

いったんこれは置いといて、O\mathcal O を、「集合 {aZ+b (Z)a,bZ, a̸=0}\{ a \mathbb Z + b ~(\subset \mathbb Z) \mid a, b \in \mathbb Z,\ a \ne 0 \} の任意個(0 個でもよい)の元の和集合全体」とします。
「0 個の集合の和集合」って何だよ、って思われるかもしれませんが、これは「空和」という考え方により \emptyset であると約束されています。

余談ですが、空和の考え方はプログラミングなんかにも現れますね。例えば、よくある「総和を求めるプログラム」は、

int sum = 0;
for(int i = 0; i < 100; i ++) sum += i;

のように記述されますが、この冒頭で int sum = 0; としているのもコレです。

さて、こうして定められた O\mathcal O は、Z\mathbb Z 上の位相になっています。
実際に示してみましょう…… と言いたいところなのですが、2. とか結構面倒なので、証明は読者にお任せします。

さて、O\mathcal O の定め方より、O\mathcal O の元は \emptyset を除いてはすべて無限集合であることがわかります。ということは、{±1}\{\pm 1\} は開集合ではありませんね。
であれば、(*) の左辺 Z{±1}\mathbb Z \setminus \{\pm 1\}閉集合ではありません

一方で、このとき、任意の aZ{0}a \in \mathbb Z \setminus \{0\} に対して、aZa \mathbb Z は閉集合となります。なぜならば、aZ=aZa \mathbb Z = |a| \mathbb Z に注意すれば、

(aZ)c=(aZ)c=k=1a1aZ+k(a \mathbb Z)^c = (|a| \mathbb Z)^c = \bigcup_{k=1}^{|a|-1} |a| \mathbb Z + k

であり、この右辺は aZ+ba \mathbb Z + b という形をした集合の和集合になっている、すなわち O\mathcal O の元であるためです。
ということは、(*) の右辺は 閉集合の「素数個の」和集合、ということになります。

以上より、閉集合の 素数個の 和集合が閉集合でない、という状況が発生しました。
閉集合の性質 2. より、閉集合の 有限個の 和集合は 常に 閉集合です。

すなわち、素数は無限に存在しなければならないのです!


以上です。
時間と寿命が許せばあと "素数個は" 書けるんですが、今回はこれくらいにしておきます

traP アドベントカレンダー 2018、明日(61 日目)の担当は @e-suke @Sigma1023 です。


  1. 逆も成り立ちますが、ここでは触れないことにします ↩︎

  2. 2 番目の条件が「有限個」に制限されているのは、我々は「無限個の開集合の共通部分が開集合とならない」例を知っているからです。一例として、1 次元ユークリッド空間における

    n=1(1n,1n)={0}\bigcap_{n=1}^\infty \left( -\frac1n, \frac1n \right) = \{0\}

    が挙げられますね。 ↩︎

この記事を書いた人
youjo_tape

'17 / 37 / 養生テープ

この記事をシェア

このエントリーをはてなブックマークに追加

関連する記事

2018年12月15日
○△□
phi16
2018年12月25日
コミックマーケット95に参加します!
Yosotsu
2018年12月24日
DubstepDance
Sigma1023
2018年12月24日
冬っぽい曲
e-suke
2018年12月23日
LogicProXでのサラウンド設定,オーケストラ用テンプレ作成,その他の小ネタ
SolunaEureka
2018年12月23日
線形解読法
nari

活動の紹介

カテゴリ

タグ