tsujimotterのノートブック

日曜数学者 tsujimotter の「趣味で数学」実践ノート

(a○+b)×(a△+b)=(a□+b)になるa,bの条件と中国剰余定理

数学ファンの鯵坂もっちょさんがツイートしていた問題が面白かったので、今日はその問題について考えてみたいと思います。


もっちょさんの問題は、任意の  a\text{○}+b, \; a\text{△}+b という形の数の積

 (a\text{○}+b) \times (a\text{△}+b)

が再び

 a\text{□}+b

と表せるような整数  a, b の条件は?という問題ですね。


この問題、見た目以上に広がりがある問題だと思います。「中国剰余定理」や「天に向かって続く数」にもつながったりします。お楽しみに!

続きを読む

フェルマー商

今日は整数論の面白概念の一つである フェルマー商 を紹介したいと思います。


まず、フェルマーの小定理という、合同式を考える上で大変有用な定理から話を始めます。

定理(フェルマーの小定理)
 a p で割り切れない任意の整数とする。このとき
 a^{p-1} \equiv 1 \pmod{p} \tag{1}

が成り立つ。


つまり、この定理は  p と互いに素な  a について、 a^{p-1} - 1 が必ず  p で割り切れると言っているわけですね。

 \bmod{p} の剰余も十分面白いのですが、今回はさらに話を進めて  \bmod{p^2} の合同式を考えてみたいと思います。

続きを読む

自由研究:レピュニットが素数で何回割れるのか問題

一つ前の記事で「LTEの補題(指数持ち上げ補題)」という有名な補題について勉強しました。せっかくなので、この補題を何か他のネタにも使えないかと考えました。

LTEの補題とは、こんな主張の補題でした:

LTEの補題(指数持ち上げ補題)
 p を奇数の素数とする。 p で割り切れない相異なる整数  x, y x\equiv y \pmod{p} なる関係を満たすとき、任意の正の整数  n に対して次が成り立つ:
 \operatorname{ord}_p(x^n - y^n) = \operatorname{ord}_p(x - y) + \operatorname{ord}_p(n)

これ自体の証明は、たとえば INTEGERSの記事 をご覧になってください。


色々考えていくうちに、レピュニットに応用できそうだ というところに思い至ったので、そのことについてまとめたのがこちらの記事です。

今回紹介するレピュニットの性質については、なかなか面白いと思います! なにせ、私はこの性質が載っているサイトを見たことがありません。

よかったらぜひ楽しんでいってください!

2021.05.26 公開後の追記:
公開後に調べていたら、どうも定理3の話は東大の入試問題になっていたようです。東大すごいですね。(記事末尾にリンクを記載しています。)

続きを読む

線形合同法(擬似乱数生成法)の周期

世の中の現象の中には「ランダム」な現象が多々あります。たとえば、サイコロを振るのは分かりやすいランダムな現象の例です。他にも天気や地震、ギャンブルなども分かりやすいランダムな現象の例です。

一方で、コンピュータの中で行われる計算は、一定のアルゴリズムにより定められた計算が順次実行されることになるため、原理的にはランダムになることはありません。

このことはコンピュータ内でランダムな現象をシミュレーションするにあたって問題になります。そこで「決められた手順によって生成されるランダムっぽく振る舞う数列」をいかにして作るかが重要になるわけですね。このような数列を擬似乱数と言います。

コンピュータによって擬似乱数を生成する手法は、これまでもさまざまな手法が提案されています。今回は、その中でも特に有名な手法である 線形合同法 について考えたいと思います。

最近はもっと良い疑似乱数の生成法が発見されているので、線形合同法はあまり使われていないと聞きます。しかし、一昔前のC言語等の乱数生成には、この方法が普通に使われていました。


簡単に線形合同法について説明しましょう。線形合同法とは次のようなアルゴリズムです。

整数の3つ組  (a, b, M) を考えます。とくに、 a > 0, \; b \geq 0, \; M > 0 とし、 a < M, \; b < M としておきます。

 x_0 0 \leq x_0 \leq M-1 であるような整数とし、整数  x_1, x_2, x_3, \ldots を次の漸化式によって定めます:

 x_{n+1} \equiv a x_n + b \pmod{M} \tag{1}

ただし、 x_n \{0, 1, 2, \ldots, M-1\} の中からとることにします。

このように数列  \{x_n\} を選ぶと、 x_0 を決める毎に異なる疑似乱数の列が得られるというわけです。


たとえば、 a = 13, b = 5, M = 24 とします。このとき、 x_0 = 8 とすると

 \begin{align} x_0 &= 8, \\
x_1 &= 13\times 8 + 5 = 109 \equiv 13 \pmod{24}, \\
x_2 &= 13\times 13 + 5 = 174 \equiv 6 \pmod{24}, \\
x_3 &= 13\times 6 + 5 = 83 \equiv 11 \pmod{24}, \\
& \vdots \end{align}

のように数列  8, 13, 6, 11, \ldots が得られます。

今回の数列は結構優秀で、数列をこのまま続けていくと、こうなるのですが・・・

 {\bf 8},13,6,11,4,9,2,7,0,5,22,3,20,1,18,23,16,21,14,19,12,17,10,15,{\bf 8}\ldots


実は、 8 からスタートして  8 に戻ってくるまで、 0 から  23 までの数がすべて1回ずつ出力されています。つまり、この数列の周期は  24 というわけですね。周期は法  M を超えることはないので、これが最大周期になります。


パラメータ  (a, b, M) によっては最大周期とならないケースも存在します。たとえば、 a = 15, b = 5, M = 24 とすると

 8,21,11,15,23,15,23,15,23, \ldots

となりますが、これは  15, 23 が繰り返されるので、周期  2 となります。


あとで述べるように、一般に線形合同法によって得られる数列は周期  \lambda を持ち、その周期は  \lambda \leq M となります。

今回のメインテーマは、パラメータ  (a, b, M) がどのような条件のとき周期最大( \lambda = M)となるのか、という問題です。周期は長ければ長いほど疑似乱数としては優秀だと考えられるので、気になる問題設定です。


線形合同法において最大周期になる必要十分条件は知られていて、以下の定理1が成り立ちます。

定理1
パラメータ  (a, b, M) に対する周期を  \lambda とする。このとき、次の必要十分条件が成り立つ:

 \newcommand{\HLNO}{\unicode[\sans-serif,STIXGeneral]{x306E}}  \lambda = M \;\; \Longleftrightarrow \;\; \begin{cases} \text{(i)}\;\;\; (b, M) = 1 \\
\text{(ii)} \;\;\; \text{任意}\HLNO{奇素数} \; p \; \text{に対して} \;\; p\mid M \; \Longrightarrow \; p \mid (a-1) \\
\text{(iii)} \;\;\; 4\mid M \; \Longrightarrow \; 4 \mid (a-1) \\
\end{cases}


実際、 a = 13, \; b = 5, \; M = 24 のケースでは、条件 (i), (ii), (iii) を満たすので最大周期  \lambda = 24 になったというわけですね。


しかし、一体どうしてこのような必要十分条件になるのか気になりますね。そこで、今回の記事は 定理1を証明 してみたいと思います。


自力で考えてみてもなかなか難しかったので、証明がどこかに載っていないか調べてみましたが、ネット上で一般的なケースについての証明は見かけませんでした。

その後、Knuth先生の "The Art of Computer Programming Volume2 Seminumerical Algorithms" に証明が載っていることを知り、今回参考にさせていただきました。


しかしながら、証明を読んでいて納得いかない部分がいくつかありました。

こちらの記事では、大枠の証明は上記に従いつつも、いくらか自分流に修正したものをまとめたいと思います。

続きを読む

テレビ番組 #ガリベンガーV に特別講師として出演しました(裏話など)

昨日5/15に放送された テレビ番組「ガリベンガーV」 という番組に出演させていただきました。

TVerでも期間限定(5月22日(土) 23:40まで)で見ることができるので、ぜひご覧になってください!
tver.jp

なかなかない機会ですので、今日は収録の思い出を語ったり、出演の裏話などをブログで紹介していきたいと思います!

続きを読む

1/512の有限小数と冪零元

今日は5月12日なので 512 の日ですね!

 512 = 2^9 なので、2のべき乗で表せる数というわけです!嬉しいですね!(え、嬉しくないですか?)


楽しくなってきたので他にも面白い性質ないかなと、Wikipediaの「512」という項目を調べてみると、次のような性質を見つけました。

 2^i \times 5^j i\geq 0, \; j \geq 0)で表せる24番目の数である。1つ前は500、次は625。(オンライン整数列大辞典の数列 A003592)

なるほど

 512 = 2^9 \times 5^0

と書けるので、 2^i \times 5^j で表せる数ということですね。

・・・ 5 関係ないですやん。


この性質に何の意味があるんだろう・・・。このWikipediaの記事を書いた人は、どういう気持ちでこの性質を追加したのだろう・・・。


このままでは512がかわいそうなので(?)、 2^i \times 5^j で表せる数に何か数学的な意味を見出してあげたいですね。

そこで私が思いついたのは

 \displaystyle \frac{1}{512}

という分数についてです。

続きを読む

テレビ出演&群論講座のお知らせ

いつもブログを読んでくださってありがとうございます!

今日5月9日は私の誕生日なのですが、今年で36歳を迎えまして「平方数歳」になりました。おかげさまで今年も楽しく数学をできています!

せっかくの36という年齢なので、36にまつわる何かをしたいですね。何かアイデアある方いましたら、ぜひコメント欄かTwitterで教えてください。


さて、今日は2つほどお知らせがあるのですが、その一つ目が テレビ出演 についてです。

テレビ朝日の ガリベンガーV という番組に出演することになりました。

f:id:tsujimotter:20210509221940p:plain:w300

ガリベンガーVという番組は、最近流行りのVTuberが出演して、わいわい楽しく科学的なトピックを勉強するという番組です。tsujimotterはもちろんVTuberとして・・・ではなく特別講師の方で出演させていただきます。

今回のテーマは 「数字0(ゼロ)」 です!

これまで85回ほど色んなテーマを紹介してきた番組ですが、数学の回は「今回が初めて」とのことです。そんな特別な回に講師として呼んでいただきました。

来週5/15(土)の深夜24時5分 に放送されます!
(土曜から日曜に変わる瞬間の時間です。)

テレビをお持ちでない方も(私も持っていないw)TVerというサイトで、放送直後から(無料で)見ることができます。便利な世の中になったものですね!

ぜひご覧になってください!
www.tv-asahi.co.jp


Twitterのハッシュタグ #ガリベンガーV で実況などしていただけると、大変喜びます!



裏話などは、また放送後に紹介できればと思っています。当日はVTuberのみなさんが(びっくりするぐらい)楽しそうに聞いてくださったので、私としてはとても楽しい気分で話せた収録でした。どんな形で放送されるかはわからないですが、これまでの放送の様子を見るにきっと楽しくまとめてくださると思います。お楽しみに!




もう一つのお知らせが、表現者のための数学 という数学の講座についてです。

peatix.com
【以前の申し込みページで申し込まれた方へ:手違いにより元のイベント申込ページが削除されてしまいました。お手数ですが、返金の完了を確認の上、再度こちらよりお申込いただけますでしょうか。】


キュレーターの高橋裕行さん、ピタゴラスイッチ等に携われた星功基さんのお二人と私の三人で、やさしく楽しく大学数学の初歩に親しむ講座を企画することになりました。

元々、高橋さんから「文系の人にわかるように群論について教えて欲しい」というリクエストがあり、群論の勉強会を開こうとなったのがきっかけです。人文科学でもレヴィ=ストロースの「親族の基本構造」など、群論を応用した研究があり、そういった事例が見聞きして群論に興味を持ったとのことです。

ちなみに高橋さんは、以前私がニコニコ学会βの本に載ったときにインタビューをしてくれた方です。そのときも色々と話を引き出してくださって、とても楽しいインタビューだったのを覚えています。

せっかく準備して話すなら、高橋さんだけでなくさまざまなバックグラウンドを持った方に対しても大学数学に親しむ機会を提供できるのではと思い、オープンなオンライン講座とすることになりました。

参加者としては次のような人たちを想定しています。

f:id:tsujimotter:20210509225024p:plain:w400

数学の専門的な話を勉強したい方向けの講座ではないので、その点はご注意ください。あくまで群論の初歩的なところに触れてみたい方向けの講座となっています。


今回のテーマ「群論」では、月1回ずつの3回に渡る講座となっていますが、5/13(木)の第1回 の内容は次のような話になりそうです。

1. なぜ「群」を学ぶのか?
2. キーワードは「対称性」?
3. 身近な対称性
4. 「対称性」から「群」へ(本日のメインパート)
5. 「巡回群」を探してみよう!

第2回では、巡回群以外の群や、もう少しだけ突っ込んだ群論の概念を紹介し、さらに群論の応用として上で触れたレヴィ=ストロースの事例や、音楽理論への事例などを紹介する予定です。

今回の講座の特色としては、単に群論の勉強をするというだけではなく、それを何かしらの表現活動(アート・デザイン・作曲・プログラミング・スポーツ・料理・文章執筆・動画制作 etc.)に活かしていただくというところにあります。

実際、第2回で紹介するように、群にはさまざまな分野への応用があります。また、群論そのものを使わずとも、そこで登場する「対称性」「可換・非可換」などのアイデアや、ものごとを抽象的に捉えて「異なるものを同じものとみなす思考」などは、さまざまな表現に応用できるものだと思います。

そこで第3回では、参加者のみなさんに群論のアイデアを使った「作品」を作っていただき、「課題発表会」でその内容を紹介していただこうと考えています。さまざまなバックグラウンドの参加者のアイデアを見ることで、より広い視野が得られるような会になることを期待しています。

tsujimotterは第1回に向けて絶賛準備中です。今の所かなり面白い講座になるのではないかという実感があります。まだ参加者は募集しています。みなさまのご参加をお待ちしております。

peatix.com
【以前の申し込みページで申し込まれた方へ:手違いにより元のイベント申込ページが削除されてしまいました。お手数ですが、返金の完了を確認の上、再度こちらよりお申込いただけますでしょうか。】


それでは今日はこの辺で!