すうがくなどについてのメモ

数学を教えたり、調べたり、考えたりしたことのメモです

今日の授業

今日の授業ではトポロジーの話題についてあれこれ話しているうちに、正$4g$角形の辺をうまく繋げると種数$g$の閉曲面ができる、という話になり、正$40$角形から種数$10$の閉曲面を作る次の動画に辿り着いた↓

 

www.youtube.com

 

この動画、「$40$角形はやりすぎでしょw」と思いながら見始めたのだが、見ていると「なるほどそういうことか」という感じで$4g$角形から種数$g$の閉曲面を作る方法が分かってくる。おすすめです。

 

 

 

 

今日の授業

今日の授業では、Gauss-Bonnetの定理の多面体バージョンとも言える(不足角についての)デカルトの定理について話した。この定理はとても好きな定理なので、面白さが伝わってくれると嬉しい。

 

また、先日書いた素数大富豪アドベントカレンダーで使ったpythonのコードについて生徒さんに見せたところ、修正を行ってくれて効率が大幅に改善された(私はプログラミング力が低く生徒さんからよく教わっている)。これ以外にも生徒さんが数学について考えていることが少し話してくれて、その視点の面白さにとても感心した。

$3$は$5$以上のフェルマー素数の原始根

この記事は インテジャーズのadvent calendar 7日目の記事です。

昨日の記事はコロちゃんぬさんによる「インテジャーズと私」というとても面白い記事でした。カスタマーレビューという発想が素晴らしかったです!

 

こちらの記事では、今年のmathpowerの耐久企画「正$65537$角形の作図」に関連した話題として、フェルマー素数の原始根について書きます。

 

ご存知のように、素数$p$がフェルマー素数の時、正$p$角形は作図可能です(←インテジャーズ文体を真似したつもりです)。

 

現在知られているフェルマー素数は$3,5,17,257,65537$の$5$個ですが、これらの$p$について正$p$角形の作図をしようとすると、($p=17$くらいから)$\mathbb{F}_p$の原始根を一つ固定して考えたくなる状況が発生します。

 

正65537角形の作図方法についてUさんと検討していた時に、こんな感じの会話がありました。

Uさん「$p=17$の原始根って何でしょうね?(計算スラスラ)あー$3$は原始根ですね」

Uさん「$p=257$の原始根って何でしょうね?(PCカタカタ)あ、これも$3$がとれますね」

私「$3$優秀ですねww」

Uさん「じゃあ$p=65537$の原始根はどうなりますかね?」

私「まさか$3$なわけ、、」

Uさん「(PCカタカタ)おっ、これも$3$がとれますね」

 私「ええ!?まじですか…!」

 

実際、$p=17$の時に$3^n \text{ mod }p$は

$$3^1 \equiv 3, 3^2 \equiv 9, 3^3 \equiv 10, 3^4 \equiv 13, 3^5 \equiv 5, 3^6 \equiv 15, 3^7 \equiv 11, 3^8 \equiv 16,$$

$$3^9 \equiv 14, 3^{10} \equiv 8, 3^{11} \equiv 7, 3^{12} \equiv 4, 3^{13} \equiv 12, 3^{14} \equiv 2, 3^{15} \equiv 6, 3^{16} \equiv 1  $$

となっていて、$3$が原始根であることが比較的簡単に確認できます。

その他のフェルマー素数でも計算では確かめられるわけですが、この現象が「偶然なのか、理由があるのか」については、単に計算しただけでははっきりしません。

さて、その後調べ物をしているうちに、この現象には理由が付けられることが分かりました。一般に次の事実が成り立つことが知られています。

 

定理

$p$が$5$以上のフェルマー素数のとき、$(\mathbb{Z}/p\mathbb{Z})^{\times}$の生成元(原始根)として常に$3$が取れる。

 

常に、と書きましたが、現在知られている$5$以上のフェルマー素数は$5,17,257,65537$のたった$4$個です。これらの$4$個について$3$が原始根であることは(上記のように)計算すれば確かめられます。

もしフェルマー素数がこれ以降無いことが証明されてしまうと、この定理は威力を発揮しないまま終わってしまう悲しい状態になってしまうので、この事実を知って以降私はフェルマー素数はもっとたくさん存在して欲しいと思うようになりました。もしなんらかの方法で新たなフェルマー素数が発見された時、原始根として計算するまでもなく$3$が取れるのです!

(ただし後述するとおり、この逆に近い事実が成り立っており、これを用いてフェルマー数$F_n=2^{2^n}+1$が素数かどうかの判定を行うこともあるようです(Pépin's test))

 

ということでこの定理の証明を以下に行います。

(証明)

一般に素数$p$について、$(\mathbb{Z}/p\mathbb{Z})^{\times}$の原始根が常に存在する。それを一つとって$g$とする。任意の$a \in (\mathbb{Z}/p\mathbb{Z})^{\times}$に対して$a = g^{\nu (a)} $なる$\nu (a)$がmod $p-1$で一意に定まり、

$$\left( \frac{a}{p} \right) = (-1)^{\nu (a)} $$

と書ける。ここで $\left( \frac{a}{p} \right)$ は平方剰余記号。

 

さて、$g$は原始根だから、$g^{\frac{p-1}{2}} \equiv -1 $ mod $p$が成り立ち、

$$\left( \frac{a}{p} \right) = (-1)^{\nu (a)} \equiv (g^{\frac{p-1}{2}})^{\nu (a)}= (g^{\nu (a)})^{\frac{p-1}{2}} = a^{\frac{p-1}{2}} \text{  mod }  p $$

が成り立つ(いわゆるEulerの規準)。

 

さて、$3$が原始根であることを言うには、$3^{\frac{p-1}{2}} \equiv -1 \text{  mod }  p$を言えば良いが、上記により

$$\left( \frac{3}{p} \right) = -1 $$

を言えば良いことになる。ここで平方剰余の相互法則が使えて

$$\left( \frac{3}{p} \right) = (-1)^{\frac{3-1}{2}\frac{p-1}{2}} \left( \frac{p}{3} \right) = (-1)^{\frac{p-1}{2}} \left( \frac{p}{3} \right) $$

が成り立つが、今 $p = 2^{2^n}+1 \hspace{3mm} (n \geq 1)$より$\frac{p-1}{2} = 2^{2^n-1}$は偶数だから

$$\left( \frac{3}{p} \right) =  \left( \frac{p}{3} \right) $$

となる。また、$p = 2^{2^n}+1 \equiv (-1)^{2^n}+1 =2 \text{  mod }  3$だから結局

$$\left( \frac{3}{p} \right) =  \left( \frac{2}{3} \right) =-1 $$

となる。以上より

$$3^{\frac{p-1}{2}} \equiv -1 \text{  mod }  p$$が言えた。よって$3$は原始根である。

(証明終了) 

 

さて、以上が証明になりますが、もう少し調べると(といってもwikipediaに書いてる事実だったのですが)、この逆に近いことも言えることが分かりました。すなわち

定理

$n \geq 1$に対し、$F_n$を$F_n=2^{2^n}+1$と定める。$F_n$が素数であることと、$3^{\frac{F_n-1}{2}} \equiv -1 \text{  mod }  F_n$が成り立つことは同値。

 

$3$はフェルマー素数ととても関係が深い数だったのですね!

 

と興奮気味に書きましたが、この証明は簡単です。必要性は上記の証明の中で示しています。十分性について書きます。

(十分性の証明)

$3^{\frac{F_n-1}{2}} \equiv -1 \text{  mod }  F_n$が成り立つならば、$3^{F_n-1} \equiv 1 \text{  mod }  F_n$だから$3$の$(\mathbb{Z}/F_n\mathbb{Z})^{\times}$における位数は$F_n-1=2^{2^n}$の約数であり、$2^k$の形。しかし、$k=2^n-1$では$3^{2^k} = 3^{(F_n-1)/2} \equiv -1 \text{  mod }  F_n$だから、$3$の位数はちょうど$2^{2^n}$になる。これは$(\mathbb{Z}/F_n\mathbb{Z})^{\times}$の位数が$2^{2^n}$であることを言っているので、$F_n$は素数である。

(証明終了)

 

なお、wikipediaを見るとこの事実を用いて$F_n$が$n=7, 8, 10, 13, 14, 20, 22, 24$でフェルマー素数でないことの証明に用いられたことが書いてあります(Pépin's test - Wikipedia)。 

 

以上で終わりとします。ここまでお読みいただきありがとうございます。

明日の記事はせきゅーんさんの記事「Szemerédi3」です!お楽しみに!!

 

 

 

お前はすでに詰んでいる ~素数大富豪において素数が作れない手札の研究~

この記事は素数大富豪のアドベントカレンダー 7日目の記事です。

昨日は二世さんの「たかが山札、されど山札」でした。

 

素数大富豪を始めてから、これまで数え切れないほど素数大富豪で遊んでいるのですが、一向に強くなれないのがちょっとした悩みです。

 

ただ、なぜ強くなれないか、というと理由は単純で素数を覚えられないから」、そして「計算をよく間違えるから」です。具体的には、3枚出しくらいから素数がなかなか覚えられません。また、いまだに3の倍数をしょっちゅう出してしまうくらい計算間違えも多いです。

 

その代わりといってはなんですが、勝負所で「素数っぽい数」を勘で出すことに関しては、けっこう成功率が高いと思っています(ただし、他人と比べたことはない)。

 

素数大富豪では上級者は素数かどうか分からない数を出すことはあまりないですが、素数かどうか分からない数を一か八か出して「素数と出会う」楽しさも素数大富豪の大きな魅力ですよね?

・・・でも待ってください。実はあなたが「素数かも」と勘で出そうとしているその手札、一見素数が作れる可能性がある気がするけど、実はどう組み合わせても素数が作れないかもしれないですよ?

 

例えば、3枚出しの場で自分の手札も残り3枚、その内訳が9, Q, Kだったとしましょう。正直に言って私にはこの組み合わせから素数が作れるか知りませんでした。なんとなく作れそうな感じもありますし、ここで素数が出せれば上がりなので、こういう場合たいてい私は素数っぽい数を作って一か八かを狙います。

ところが、9, Q, Kをどう並び替えても、素数は作れないのです。つまり、このうち明らかに素数でないことがわかるQを最後に持ってくる場合を除いた4パターン、つまりQK9, Q9K, KQ9, 9QK もいずれも素数ではありません!

 

実際、これらの数は次のような素因数分解を持ちます:

$$12139=61 \times 199$$

$$12913=37 \times 349$$

$$13129=19 \times 691$$

$$91213=53 \times1721$$

 

つまり、 9, Q, K と言う組み合わせは、素数が作れそうだけど実はどう頑張っても作れない手札なのです。でも、実戦の場でこの4つの数を全て素数でないと判断するのは困難だと思います。

 

そこで今回は、そんな「お前はすでに詰んでいる」状態を避けるために、「一見素数が作れそうだけど、実はどう並べても素数が作れない手札」、名付けて「詰んでるセット」を探してみました!!

 

ここで、今回の「詰んでるセット」の定義は以下の通りとしています。

 ①偶数および5のみからなる手札でない

 ②手札を足して3の倍数になっていない

 ③しかし、どう並び替えても素数を作れない

 ①、②のコンセプトは「比較的すぐに素数が作れないと判断できるケースは除外する」というものです。このへんは計算能力により人により違いがあると思いますが、個人的な感覚で決めました。また、これは良い条件ではないかもしれませんが今回は

 ④手札が全て異なる

と言う条件も定義に入れておきます。

 

途中の計算は省略しますが、pythonを用いて計算した結果、 3枚の「詰んでるセット」はこうなりました:

「詰んでるセット」(3枚)

(1, 3, 13),  (1, 4, 8),  (1, 4, 12),  (1, 5, 8),  (1, 7, 8),  (2, 4, 7),  (2, 4, 13),  (2, 5, 9),  (2, 5, 13),  (2, 7, 10),  (2, 8, 13),  (3, 4, 10),  (3, 4, 12),  (3, 5, 12),  (3, 10, 12),  (3, 12, 13),  (4, 5, 11),  (4, 6, 9),  (4, 6, 13),  (4, 8, 11),  (5, 6, 11),  (5, 7, 13),  (5, 10, 11),  (5, 11, 13),  (6, 7, 10),  (6, 7, 12),  (6, 8, 9),  (6, 8, 11),  (8, 10, 11),  (8, 11, 12),  (9, 12, 13)

  

確かに一見素数が作れそうにも思える組み合わせが多いですね!

ただ、組み合わせの個数も結構あり(数えたら31個でした)、正直なところ

これを覚えるんだったら最初から素数を覚えたほうが良いのでは?

という気持ちが若干芽生えました。 当初の予定では「詰んでるセット」はもっと少ないと思っていたのですが、意外と多かったのが誤算でした。

 

しかし、4枚の「詰んでるセット」を探してみると、個人的にはちょっと嬉しい結果になりました。

「詰んでるセット」(4枚)

(2, 4, 6, 13),  (2, 5, 12, 13),  (2, 7, 8, 12),  (4, 5, 11, 12),  (5, 8, 10, 11)

 

なんと、4枚の「詰んでるセット」は(私の計算が間違っていなければ)5組しかないのです! 手札4枚で「ぱっと見素数が作れるか分からない組み合わせ」は相当多そうですが、この結果から、上記の5組に該当しなければ、素数を出せる望みがある、ということが分かりました!

 

そもそも4枚出しは覚えるのが大変なので勘で出すことが多くなりますが、今回の結果は「手札をうまく並べればたいていの場合素数は作れる」ということを言っています。これは「素数と出会いたい」人にとっては朗報ではないでしょうか?

 

この調子で5枚はどうなっているかも計算したかったのですが、時間が足りずとりあえずここまでとさせていただきます。お読みいただきありがとうございます。

 

明日の記事は菅原響生くんの予定です。お楽しみに!!

 

 

 

 

 

昨日の授業

昨日の授業では射影平面$P^2(\mathbb{R})$の話をしようとしたが、定義を話したところで生徒さんが$P^2(\mathbb{R})$が一点(無限遠点)と直線(無限遠直線)と平面に分解できることに気づき、そこから球面やトーラスを点、直線、平面に分解したらどうなるかや、そういった分解とオイラーの公式との関連へと話が脱線していった。

 

当初話そうと思っていた内容は話せなかったが、あれこれ話しながら幾何の楽しさに触れてもらえたようなので、自分の話したいことを一方的に話すより良かったと思う。

mathpower打ち上げ

昨日は10/7,8に行われた数学イベントmathpowerの打ち上げに参加した。

去年から始まったmathpower、今年もいくつかの企画に関わらせて頂いたが、個人的には企画段階から去年よりもパワーアップしていると感じていたし、実際大盛況だったと思う。

 

打ち上げでは普段なかなか話せない方々とお話できて、とても楽しい時間を過ごせた。

数論幾何の勉強

知人のUさんから月に一回くらいのペースで数論幾何について教えてもらっている。今日はその日。

$L/K$:Galois、$X = \text{Spec } K$、$U = \text{Spec } L$とする。今日の内容は、$X$上のetale $\mu$-torsor $F$で、$U$で自明化されるものはどんなものか?というもの。ここで$\mu$はAbel群に値をとる定数層。

こういったすごく幾何っぽい問題設定が数論的な話につながり、まさしく数論幾何、という感じがして興奮した。