ゆるふわブログ

東京大学理科 I 類 2 年の学生です.プログラミング,大学の勉強,日常生活で感じたことをゆるふわに書いていけたらなと思います.技術的に拙いところがあっても温かい目で見守っていただければ幸いです.

素因数分解の可視化

まずはこれをご覧いただきたい.

See the Pen Prime Factorization by Ysmr-Ry (@As2) on CodePen.

おわかりいただけただろうか? 素因数分解を可視化しているのである.
この記事ではこの可視化のルールと気づいたこと,またおまけとして素因数分解について考えたことを綴ろうと思う.

ちなみに元ネタはこれである.

matome.naver.jp

素因数分解ってなんだっけ (真顔)

素因数分解は,(たぶん) 中学校ぐらいで習うことに加え,下手したら小学生でも知っているので大丈夫だとは思うが一応おさらいしておく.
ある整数 n にはそれを割り切る数がある.例えば,6 であれば,2 や 3 は 6 を割り切る.
そのような数を約数という.
だが,例えば 7 のように 1 か自分自身の 7 でしか割り切ることのできない数もある.それを数の素となる数ということで素数と呼ぶ.
素数を小さい方から書き出すというのをやったことがあるのではないだろうか.
2, 3, 5, 7, 11, 13, 17, 23, 29, …
整数はなんでも,素数を掛け合わせた形で表すことができる.その形の中での素数 1 つ 1 つのことを素因数と呼び,そのような形に分解することを素因数分解と呼ぶ.
例えば,12 であれば 12 = 2×2×3 と表すことができ,これを素因数分解と呼ぶ.素因数は 2, 3 である.

素因数分解の可視化のルール

この可視化のルールは蓋を開けてみれば至極単純である.
まずは一番単純な場合,可視化する数が素数である時を見てみよう.
例えば 5 である.

f:id:Ysmr_Ry:20170621234858p:plain

素数の場合は,円の中心が正多角形になっている.この場合は正 5 角形に並んでいる.
次に素因数を一つ増やして,35 = 7×5 を図示してみよう.

f:id:Ysmr_Ry:20170621235143p:plain

5 の時の図形 (上の画像) が正 7 角形上に並んでいることがわかる.
次は 385 = 11×7×5 だ!

f:id:Ysmr_Ry:20170622000046p:plain

正 11 角形上に 35 の図形が並んでいるのがわかるだろう.
以下同様だ.5005 = 13×11×7×5 の場合も一応見てみよう.

f:id:Ysmr_Ry:20170622000400p:plain

385 の図形が正 13 角形上に並んでいるのがわかるだろう.
このようなマトリョーシカのように入れ子になっている構造を (難しいが) 再帰的構造という.

自分自身が入れ子なフラクタル

もしも,整数を構成する素因数が全て同じ場合 (例えば 16 = 2×2×2×2 など) の場合はどうなるだろうか.
先ほどのルールに従えば同じ形が入れ子になっていくはずである.
無限に自分自身が入れ子になっている図形をフラクタルという.
つまり.フラクタルっぽくなるはずである.
では,実際に見てみよう.
1024 = 2×2×2×2×2×2×2×2×2×2 である.

f:id:Ysmr_Ry:20170622002548p:plain

これはシェルピンスキーのカーペットという有名なフラクタルのようになっている.
また,729 = 3×3×3×3×3×3 の場合である.

f:id:Ysmr_Ry:20170622002828p:plain

これもまたシェルピンスキーのギャスケットという有名なフラクタルである.
名前は知らずとも,このような形を見たことがある人も多いのではないだろうか.

素因数分解ってなんの意味があるの (おまけだから飛ばしてもいいよ)

素因数分解することで嬉しいこととはなんだろうか.
僕の中のイメージはこうだ.
素数とは の元 なのである.素因数分解とはいわば,数の化学式 なのである.
化学では,有限な種類の元素 (現在名前がついているのは 118 種) がどのように集まって化合物を作っているのかが重要である.
同じように,数がどのような素数でできているかが重要なのである.
(素数は無限にあるという違いはあるが…)
素因数分解をするといろいろなことがわかる.例えば, 360 = 2^3\times3^2\times5^1素因数分解すると,それぞれの素因数の肩に乗っている指数 (3,2,1) にそれぞれ 1 を足してかけると (3+1)(2+1)(1+1) = 24 であり,これが 360 の約数の個数である.また, 12 = 2^2\times3^1 など,それぞれの指数が 360 のものより小さい場合はその約数になる.(360 は 12 の約数) 約数の総和は (1+2+4+8)(1+3+9)(1+5) = 1170 である.
また,2 つの数の比較にも使える. 360 = 2^3\times3^2\times5^1 300 = 2^2\times3^1\times5^2 を考えよう.指数の列を書き出そう.
360 … (3,2,1)
300 … (2,1,2)
この中で,同じ列にあるものの中で小さい方をとって行くと,(2,1,1) である.これを数に直すと, 60 = 2^2\times3^1\times5^1 となり,360 と 300 の最大公約数である.
また,同じ列で大きい方をとって行くと (3,2,2) で, 1800 = 2^3\times3^2\times5^2 となり,360 と 300 の最小公倍数である.
このあたりは現在の 数学 A の教科書に載っていると思われるので,本棚から引っ張り出してみるのも一興だろう.
ちなみに,例えば 360 の約数の積は約数の個数 24 を用いて  360^{\frac{24}{2}} である.

ベクトルを知っているとこのようなことも言える.
最大公約数が 1 である場合,互いに素というが,a と b が互いに素の時,a ⊥ b と表す.
これは,指数を並べたものをベクトルとみると,内積が 0 となるからである.
例えば, 12 = 2^2\times3^1\times5^0\times7^0 35 = 2^0\times3^0\times5^1\times7^1 を考えよう.
指数を並べると,2, 3, 5, 7 に対応する指数を順に並べて,12 … (2,1,0,0), 35 … (0,0,1,1) である.
これらの同じ列にある数をかけて足し合わせると,2×0 + 1×0 + 0×1 + 0×1 = 0 であり,内積が 0 なので "直交" していると言える.よって,12 ⊥ 35 と表記する.
このようなベクトル的な考え方は「数学ガール」を参照されたい.

「互いに素」という概念

www.hyuki.com

素因数分解は暗号にも利用されているようである.

おわび

深夜なのでテンションがおかしくてすみません.短くあっさりと仕上げるつもりだったのですが,主に最後の方が冗長になってしまいましたすみませんなんでもし(ry
素因数分解は中学生でも知ってますが,それをこのように美しく Visualize できること,また,ベクトル的な見方など面白い捉え方もあるのだということを知ってもらい,素因数分解に対して楽しいイメージを持っていただければ幸いです.
何か不明な点があれば,どんな些細なことでも結構ですので,コメントで聞いてください.
ブクマやスターなどつけていただくと泣いて喜びます.