feature image

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

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

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

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

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

1. 日付ネタ

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

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

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

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

この図から察せるように、 番目の三角数は と表せますね。
したがって、 なので、 は 49 番目の三角数とわかります。

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

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

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

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

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

素数 は、 で割って 余るならば、ある自然数 が存在して と表せる。[1]

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

有限集合 上の対合

は必ず一個の不動点を持つから、集合 の元の個数は奇数であり、対合 も不動点を持つ。

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

「有限集合

を満たすような は明らかに高々有限個しかありません。大雑把に見ても が必要ですもんね。
したがって、 は確かに有限集合です。

「… 上の対合 …」

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

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

をよく見てみましょう。常に であるので、この場合分けは直感的には「 および と比較したときに、 はどこにいるのか」という風に解釈できます。
しかし、範囲の重複こそないものの、 または のときに が定まっていないように見えますね。ですが、

であるので、これらの場合には が素数になる、すなわち が成り立つことはありません。この対偶をとれば、 上では常に かつ であることがわかるので、確かに 上の写像として well-defined であることが従います。

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

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

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

変換 の不動点とは、変換により変化しない(すなわち、 となる)点のことです。
これより、対合 の不動点を求めるには、 を解けばよいことになります。

ここで、 の不動点 は、(存在すれば)必ず を満たします。

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

写されてしまうことがわかりました。ということは、「 かつ 」となることはあり得ないので、このいずれの場合も は成り立ちません。

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

したがって、 としてよく、このとき

となります。さらに、 上の点でなければならないことから、

が必要です。したがって、 であるので、 が素数である ことを考えると でなければなりません。
以上をまとめると、 の不動点は唯一で:

と求まります。 で割って 余る素数 なので、 は自然数であり、たしかにこの点が に含まれていることがわかりますね。

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

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

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

ただし、 の不動点 だけは、いわば "自分自身とペアをなしている" ことになります。

不動点:
single

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

「対合 も不動点を持つ」

文脈を汲み取ると、この対合は 上で考えているものでしょうね。
すなわち、これをもう少し丁寧に記述するならば、「対合 」となるでしょうか。

という条件が に関して対称になっていることから、「 を入れ替える」写像である 上の変換になっていることがわかります。また、 が対合であることも明らかですね。

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

「。」

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

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

がわかります。そして、 が不動点であることから、とくに であることも従うので、

すなわち、 が成り立ちます。これが求める表現です。■


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

3. 素数の無限性

素数は無限に存在する。

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

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

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

集合 に対し、その部分集合の集合 上の 位相 であるとは、以下の 3 条件を満たすことを言います:

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

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

さて、「開集合」があるなら、とうぜん「閉集合」もあります。
が( の)閉集合 であるとは、その補集合 が開集合であることをいいます。

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

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


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

まず、 に対し、 と表記することにします。
特に の場合は、単に とだけ書くことにしましょう。

例えば、、みたいな感じです。

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

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

いったんこれは置いといて、 を、「集合 の任意個(0 個でもよい)の元の和集合全体」とします。
「0 個の集合の和集合」って何だよ、って思われるかもしれませんが、これは「空和」という考え方により であると約束されています。

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

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

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

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

さて、 の定め方より、 の元は を除いてはすべて無限集合であることがわかります。ということは、 は開集合ではありませんね。
であれば、(*) の左辺 閉集合ではありません

一方で、このとき、任意の に対して、 は閉集合となります。なぜならば、 に注意すれば、

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

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

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


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

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


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

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

    が挙げられますね。 ↩︎

youjo_tape icon
この記事を書いた人
youjo_tape

'17 / 37 / 養生テープ

この記事をシェア

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

関連する記事

2017年11月14日
IBIS2017参加報告
Keijan icon Keijan
ERC20トークンを用いた宝探しゲーム(真)の提案【アドベントカレンダー2018 10日目】 feature image
2018年11月3日
ERC20トークンを用いた宝探しゲーム(真)の提案【アドベントカレンダー2018 10日目】
Azon icon Azon
2021年4月18日
ベズー係数とN項の拡張ユークリッドの互除法
0214sh7 icon 0214sh7
2018年12月12日
多重スリーブの世界と,各種進捗報告。
Silviase icon Silviase
2018年12月23日
LogicProXでのサラウンド設定,オーケストラ用テンプレ作成,その他の小ネタ
SolunaEureka icon SolunaEureka
2018年12月16日
ICPCアジア地区横浜大会参加記【アドベントカレンダー2018 52日目】
eiya icon eiya
記事一覧 タグ一覧 Google アナリティクスについて