約数と倍数 , 素数と素因数分解

第 8 回のテーマは「 約数と倍数 , 素数と素因数分解 」です。

約数と倍数の関係や仕組み、数の素と言われる「 素数 」の定義、そして数を素数に分解する「 素因数分解 」の概念などを書いていきます。

これらは繋がっている話なので、一緒にまとめて理解していきたいと思います。

さらに余談ですが、「 素数とセミの不思議な関係 」や「 素因数分解と暗号 」という話も面白いと感じたので書いておきます。

約数と倍数

約数 」とは、割り算して割り切れた時の割る数 」のことです。つまり割り切れる数です。

例えば、21 ÷ 7 = 3  とは  21 ÷ 3 = 7  でもあるので「 3 7 」は「 21 の約数 」であると言えます。

倍数 」とは、約数から見た時の割られる数( 元の数 ) 」のことです。

上の例なら、213 の倍数( 九九の 3 の段 )であり、7 の倍数( 九九の 7 の段 )でもある。となります。

つまり、約数倍数は「 表と裏の関係 」です。約数を掛ければ倍数になり、倍数を割れば約数が導き出されます。

割り算約数が、掛け算倍数が求められるのも、割り算と掛け算が逆の関係( 計算 )「 1 つの組 」だから「 表裏一体 」なのです。詳細は第 4 回「 割り算の概念 」四則計算の関係性に書いています。

例えば、12 の約数は全部で「 1 , 2 , 3 , 4 , 6 , 12 」ですが、

これは、12 を「 1 , 2 , 3 , 4 , 6 , 12 」のどれで割っても割り切れますし、12 は「 1 , 2 , 3 , 4 , 6 , 12 」それぞれの倍数になっているということです。

素数とは?

数はどんな数でも 1 」と「 その数自身では割り切れます

そして「 素数 」とは 1 と自分自身しか約数を持たない自然数 つまり「 1その数自身でしか割り切れない自然数 」の事を言います。

よって「 約数が 2 つだけ 」なので「 1 は素数ではなく 2 は素数 」となります。

そして「 素数は自然数 」なので負の素数は存在しません

前回( 奇数と偶数 , 三角数と四角数 )、偶数とは 2 で割り切れるもの、つまり「 2 の倍数 」が偶数である事を知りました。

ということは「 偶数 」は必ず「 2 の約数を持っている 」ということです。

よって「 偶数は素数ではない 」と言えます。「 2 」自体は例外ということです。

以上より、「 2 以外の素数は全て奇数の中にある 」ということになります。

素数の見つけ方( 2 ケタまで )

100 ぐらいまでの数であれば、それぞれの倍数を消していけば素数は見つかります

2 , 3 , 5 , 7 の倍数、この辺りまで消すと、残った数が素数です。( 4 , 6 , 8 の倍数は 2 の倍数でもあるので省略できます )

素数と蝉(セミ)

余談ですが「 十三年蝉 」や「 十七年蝉 」と呼ばれる蝉(セミ)がいます。別名「 素数蝉

この蝉は、その名の通りの年数だけ、地中に潜って成虫になるまでを過ごします。

なぜ彼らは、潜伏年数として「 素数の 13 , 17 」を選んだのでしょうか。

  • 天敵( 外敵 )との成長周期が一致しないようにするため( 地上に出た時に天敵に遭わないように )
  • 他種との交わりを断つため

以上のような、生存戦略の為だと言われています。

例えば、天敵が 3 年周期なら、3 と 13 が一致するのは最短( 最小公倍数 )で 3 × 13 = 39 年後となり、3 と 17 なら 3× 17 = 51 年後となります。

これがもし、12 年蝉だったなら、3 と 12 だと 12 の倍数は常に 3 の倍数でもあるので、12 年蝉が地上に出る時には常に天敵がいることになってしまいます。

自然界の生物はやはり賢いのですね。

素因数分解とは?

自然数 」というのは、1 以外、「 素数 or 素数の掛け算 」で出来ています。

そこで、自然数を素数の積( 掛け算 )に分解することを素因数分解 」と言います。そして素因数分解で出てきた素数を、元の自然数の「 素因数 」と言います。

素因数とは「 元の数( 自然数 )の原因となっている素数 」という意味です。素因数を掛け算したら元の数( 自然数 )に戻ります。

なので自然数を素因数の積に分解するのが素因数分解という事です。

そして、この「 元の自然数 」を「 合成数 」と言います。つまり「 合成数 」を「 素因数分解 」すると「 素数の掛け算 」に直せるという事です。

ちなみに、素因数分解因数分解の違いは、素因数分解が「 素数の掛け算 」に分解するのに対し、因数分解は「 式の掛け算 」に分解する事です。

自然数の構成

例えば、1 を除いた 10 までの自然数を見てみると、

2 , 3 は素数。4 は素数の積( 2×2 )。5 は素数。6 は素数の積( 2×3 )。7 は素数。8 は素数の積( 2×2×2 )。9 は素数の積( 3×3 )。10 は素数の積( 2×5 )。

以上のように、1 以外の自然数は素数 or 素数の積 で出来ています。

合成数を素数の積に直せるという事は、その素数で合成数が割り切れるという事なので、その素数は合成数の約数と言えます。

つまり、合成数の約数となる素数を「 素因数 」と呼んでいます。

よって、自然数とは「 1 , 素数 , 合成数(素数の積)の 3 つに分類される」という事です。

素数は「 数の素 」という意味を持ち、別名「 自然数の原子 」とも言われます。

素因数分解の目的

自然数の構成要素( どんな数で出来ているのか )が分かる事で、別の自然数との共通部分( 構成要素に同じ数が存在 )を見つける事ができます。

例えば、51 と 24 なら「 51 = 3 × 17 」「 24 = 2 × 2 × 2 × 3 」と素因数分解できます。

これにより、両方とも「 3 」という素数( 素因数 )が含まれている事が分かります。

素因数分解のやり方

合成数を素数( 2 , 3 , 5 , 7 , 11 , 13 … )の小さい方から順に割っていきます。この時、割り切れないものは除外します。合成数が 1 になったら( その数自身でしか割れない )終了です。

結果、割り切れた素数が「 素因数 」という事になります。

例えば、51 なら 2 では割り切れないので3 で割ります。51 ÷ 3 = 17 と合成数が 17 になりました。この 17 は 17 だけで割り切れる( 素数 )ので、17 ÷ 17 = 1 と合成数が 1 になったので終了です。

結果、割り切れた素数は「 3 , 17 」つまり「 51 の素因数は 3 と 17 」となります。これは「 3 × 17 = 51 」という事です。

24 なら 2 で割ると 24 ÷ 2 = 12 となり、12 はまだ 2 で割れるので 12 ÷ 2 = 6  まだ 2 で割れるので 6 ÷ 2 = 3  今度は 3 で割れるので 3 ÷ 3 = 1 と合成数が 1 になったので終了です。

結果、割り切れた素数は「 2 , 2 , 2 , 3 」よって「 24 の素因数は 2 と 2 と 2 と 3 」となります。これは「 2×2×2×3 = 24 」という事です。

素因数の規則性

素因数は一部に規則性があり、見分ける方法があります。

・合成数の「 一の位 」が「 偶数 」なら「 素因数 2 」( 2 の倍数 )を持ちます。

・合成数の「 各位の数を足した数 」が「 3 で割り切れる 」なら「 素因数 3 」( 3 の倍数 )を持ちます。例えば 45 → 4+5=9=3×3 なので 45 は素因数 3 を持つ。

・合成数の「 一の位 」が「 0 か 5 」なら「 素因数 5 」( 5 の倍数 )を持ちます。

・合成数の「 各位の数を足した数 」が「 9 で割り切れる 」なら「 素因数 9 」( 9 の倍数 )を持ちます。( 9 の倍数は 3 の倍数でもあるので、3 の倍数を繰り返しても OK です )

素因数分解の例題

26190 」を素因数分解してみます。

まず「 10 の倍数( 10 で割れる) 」なので 26190 ÷ 10 = 2619 つまり「 26190 = 10 × 2619 」となり、10 の倍数は「 2 5 の倍数 」なので「 2 × 5 × 2619 」となります。

次に「 2619 」に注目し「 2 + 6 + 1 + 9 = 18 」と各位を足すと「 9 の倍数 」になるので「 素因数 9 」を持ちます。よって 2619 ÷ 9 = 291 つまり「 2619 = 9 × 291 」となります。

さらに「 291 」に注目し「 2 + 9 + 1 = 12 」と各位を足すと「 3 の倍数 」になるので「 素因数 3 」を持ちます。よって 291 ÷ 3 = 97 つまり「 291 = 3 × 97 」となります。

97 」は素数なのでここで終了です。

以上をまとめると「 26190 = 2 × 5 × 9 × 3 × 97 」となります。\(9\) は \(3^2\) なので \(3\) でまとめ、素因数の小さい順に並べ直すと

\(26190=2\times3^3\times5\times97\) となります。

素因数分解と暗号

数ケタぐらいまでの数( 合成数 )なら、何とか素因数分解できますが、10 ケタ以上の大きな数の素因数分解は 非常に困難 」です。

素因数分解されたものから、合成数に戻すのはカンタン( 素因数を全て掛ければ OK )ですが逆は困難という事です。

まさに「 一方通行の計算 」と言えるのが素因数分解です。

この素因数分解の手順は、合成数に一致するまで、ひたすら素数を順に掛けていく( 素数同士の掛け算をしていく )のですが、

1 秒間に何千億回もの計算ができるコンピューターを使っても、まるで歯が立たないと言われています。

世界中の数学者たちが、極めて高度な理論( アルゴリズム )を用いたプログラムを研究していますが、具体的で有効な素因数分解の方法は分かっていません

そこで、この「 計算の一方通行性 」を利用して「 暗号 」を作ることが考案されました。

巨大な合成数( 公開鍵 )に暗号文を隠し、それを解読する鍵を、その合成数の素因数( 秘密鍵 )の中に組み込みます。

これにより、合成数が分かっても素因数分解できなければ、中身は分からない。なので公開鍵( 暗号文 )は隠さなくても OK となります。

実際の例が、クレジットカードなどの電子マネーです。現代の「 電子暗号 」は、素因数分解により支えられています

あとがき

今回から急に数学的な話になってしまったのですが、小学校で習う「 約数 , 倍数 」というのは「 表裏一体の関係 」で「 素数や素因数分解 」と密接な関係がありました。

数の入門 」として「 素数 , 素因数分解 」は、決して外すことのできない大切な知識です。

数の素、素数という名は伊達じゃないなと感じました。そして数を素数に分解する素因数分解も、偉大な仕組みだと思います。

素因数分解の話はまだ続きます。さらに詳しく掘り下げていきたいと思います。

最後までお読み頂きまして、誠にありがとうございました。