1が素数でないのはなぜ？素因数分解定理の証明

本記事の内容

本記事は「なぜ\(1\)が素数に含まれないのか？」ということと「素因数分解定理」および「素因数分解の一意性」について解説する記事です。

本記事を読むに当たり、素数について知っている必要があるため、以下の記事も合わせてご覧ください。

素数は「1とその数でしか割り切れない数」ではない？

...

for-spring.com

2023.03.07

素因数分解定理

素因数分解は中学数学で学習する内容です(今もそうかは分かりませんが、筆者のときはそうでした)。
故に、「素因数分解？知ってるよ。」という方が大半だと思います。

しかし、「なぜ素因数分解ができるの？」ということまで踏み込んだ話はされていなかったはずです。
経験上、というより中学生で習う以上、概念自体は難しいものではありませんが、「そもそもなぜ可能なのか？」ということを考えてみようと思います。

言葉のお話

素因数分解の例

問題です。

答えは\(284=2^2\times 71\)です。

確かに、計算すればこのように素数の積に分解することができますし、これがどんな合成数に対しても同様なことができるということは直感的に分かると思います。

その直感が数学的に正しいと証明するのがこの記事です。

素因数分解定理の明示

素因数分解定理を一言で言えば、

です。

ここで、合成数とは以下でした。

後述しますが、素数には\(1\)が含まれていないことが素因数分解には一意性が担保されている理由の一つです。

素因数分解定理の証明

では、証明に入ります。

定理0.(素因数分解定理)の証明

合成数に対する数学的帰納法で証明します。

①\(a=4\)のとき

このとき、\(4=2\times2\)と分解されるため、成り立ちます。

「いきなり\(a=4\)かよ？」と思うかもしれませんが、合成数を小さい順に\(x_1,x_2,\cdots,x_k,\cdots\)と並べたとき、\(4\)は最小の合成数であるため、\(x_1=4\)です。
つまり、数学的帰納法の最初は「最小の合成数」に対して議論することになります。
したがって、\(a=4\)の場合を考えるのです。

よく見る数学的帰納法の書き方に準じれば、合成数を小さい順に\(x_1,x_2,\cdots,x_k,\cdots\)と並べたとき、\(k=1\)の場合を証明したことになります。

②ある合成数\(a\)よりも小さい合成数については主張が正しいと仮定

ある合成数\(a\)までは主張が成り立ったとします。
すなわち、\(a\)よりも小さい合成数に関しては定理が正しいと仮定します。

②-1. 分解の可能性の証明

まず、そもそも分解ができるのか？ということを証明します。
\(a\)は合成数ですから、\(1\)と\(a\)以外にも正の約数を持ちます。
したがって、
$$
(1<\exists b<a )\ (1<\exists c<a)\ {\rm s.t.}\ a=bc
$$
です。
このとき、

1. \(b\)も\(c\)も素数
2. \(b\)は素数で\(c\)は合成数
3. \(b\)は合成数で\(c\)は素数
4. \(b\)も\(c\)も素数

のいずれか1つが成り立ちます。

1. \(b\)も\(c\)も素数であるとき
   今、\(a=bc\)であるので、合成数\(a\)についても素数の積で分解することができます。
2. \(b\)は素数で\(c\)は合成数であるとき
   \(1<c<a\)であり、今「\(a\)より小さい合成数については主張が正しいと仮定」しているため、\(c\)も素数の積で分解することができます。
   したがって、\(a\)は素数の積で分解することができます。
3. \(b\)は合成数で\(c\)は素数であるとき
   2.と同様で、2.における\(b\)と\(c\)の役割を交換すれば良いため、この場合も\(a\)は素数の積で分解することができます。
4. \(b\)も\(c\)も合成数であるとき
   2.および3.の場合を合わせればOKです。
   今\(1<b,c<a\)で、帰納法の仮定から\(b\)も\(c\)も素数の積で分解することができるため、\(a\)は素数の積で分解することができます。

したがって、任意の合成数\(a\)は素数の積で分解することができます。

②-2. 分解が重複を含めて一意的であることの証明

合成数\(a\)を以下の2パターンで素数の積に分解できたとします。
$$
a=p_1p_2\cdots p_n=q_1q_2\cdots q_n
$$
ここで、素数\(p_i\)の個数と\(q_i\)の個数が一致していますが、もし仮に一致しなければ、\(p_1p_2\cdots p_n=q_1q_2\cdots q_n\)とはなりえません。

次の事実を使います。

定理1.の証明は【代数学の基礎シリーズ】初等整数論編 その7を御覧ください。

定理1.を使うと、\(p_1p_2\cdots p_n\)は素数\(q_1\)で割り切れる為\(p_1,p_2,\cdots,p_n\)の中で少なくとも1つは\(q_1\)で割り切れます。
すなわち、
$$
(1\leq \exists i<n)\ {\rm s.t.}\ q_1|p_i
$$
です。
今、\(p_1\)が\(q_1\)で割り切れたとしましょう。
すると、\(q_1\)は素数ですから、\(p_1=q_1\)です(素数だからそれ以上割れない)。
したがって、
$$
p_2\cdots p_n=q_2\cdots q_n
$$
です。
ここで、
$$
b=p_2\cdots p_n=q_2\cdots q_n
$$
とすれば、\(b<a\)ですから、帰納法の仮定からこれら2つの分解は一致しています。
したがって、証明完了です。

ここで、\(a\)を素因数の積に分解したとき、その中で等しいものを一つのベキにまとめて
$$
a=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}
$$
と書くことができます。
ただし、\(p_1,\cdots,p_k\)は相異なる素数です。
また、\(a\)の素因数は\(p_1,\cdots,p_k\)ですべてであることもわかります。

定理0.(素因数分解定理)の証明終わり

素因数分解は強力です。

なぜ強力なのか？という話ですが、素因数分解定理が成り立つことで、個人的に嬉しいと思うことを紹介します。

本質的に約数をすべて列挙したことになる。

正の整数\(a\)を素因数分解して
$$
a=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}
$$
と書いたとしましょう。
このとき、ベキを分解して
$$
a=p_1p_2\cdots p_n
$$
と書けます。
ただし、\(p_1,\cdots,p_n\)は重複を許します。
このとき、\(p_1,\cdots,p_n\)から\(p_i\)を好きなだけ選んできます。
例えば\(n=5\)として
$$
a=p_1p_2p_3p_4p_5
$$
と書いたとして、\(p_2,p_4,p_5\)を選びそれらの積\(p_2p_4p_5\)を考えると、\(p_2p_4p_5\)は\(a\)の約数の1つです。
この操作を繰り返し行えば約数のすべてを知ることができます。

最初に挙げた問題を例に取れば、
$$
284=2^2\times 71
$$
ですから、
$$
284=2\times2\times 71
$$
と書き直して、\(p_1=2\)、\(p_2=2\)、\(p_3=71\)とします。
故に約数の個数は\(6\)個とわかります。
そして約数も
$$
p_1=p_2,\ p_3,\ p_1\times p_2,\ p_1(=p_2)\times p_3,\ p_1\times p_2\times p_3,\ 1
$$
により
$$
1,\ 2,\ 4,\ 71,\ 142,\ 284
$$
と分かるわけです。

整数の積に関する分解の最小単位だから。

正の整数\(a\)を素因数分解して
$$
a=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}
$$
と書いたとしましょう。
\(p_1,p_2,\cdots p_k\)は相異なる素数であり、素数は\(1\)と自身以外で割り切れない為、この表現以上に\(p_i\)を積の形で分解することができません。
つまり、\(p_i=q_s\times q_t\)というようにさらなる分解をすることができません。
そういう意味で、「整数の積において最小単位である」といえます。

ある正の整数が与えられたときはその素因数を考えるというある種の「1つのものさし」が得られたと表現しても良いでしょう。

結局の所何が言いたいか、というと整数を考えるときは(一概には言えませんが)素因数を考えるだけで基本的には良いということになるのです。

なぜ\(1\)は素数に含まれないのか？

一言で言えば、

です。
最初に挙げた問題を例にとります。
\(1\)が素数出ない世界(通常の世界)では
$$
284=2^2\times 71
$$
と素因数分解できます。

もし仮に、\(1\)も素数であるような世界を考えたとすると、\(1\)はどんな整数に掛けても値は変わりません。
つまり、
$$
(\forall n\in\mathbb{Z})\ n\cdot 1=1\cdot n=n
$$
ということです。
故に、
\begin{eqnarray}
284&=&2^2\times 71\\
&=&1\times2^2\times 71\\
&=&1\times1\times2^2\times 71\\
&=&1\times1\times1\times2^2\times 71\\
&=&1\times1\times1\times1\times2^2\times 71\\
&\vdots&
\end{eqnarray}
のすべてが素因数分解となってしまいます。
となると、ある整数が与えられたときの素因数分解は一意性が担保されなくなってしまいます。
平たく言えば、この世界で素因数分解を考えたとき
$$
a=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}
$$
と書いたとしましょう。
このとき、\(p_i\)のうちのどれかが\(1\)である可能性を追加で考える必要が出てきます。
先に述べた通り\(1\)は積について特別ですので、\(p_i\)に\(1\)が含まれていようが含まれていなかろうが値は変わらないのにも関わらず余分に考えるパターンが増えてしまうということになるのです。

素因数分解の応用先例：RSA暗号

RSA暗号は本ブログで以前紹介しました。
詳しくは【代数学の基礎シリーズ】初等整数論編 その1を御覧ください。
サラッと復習すると

1. 受信者が公開鍵を作る。
1. 十分大きな2つの素数\(p,q\ (p\neq q)\)を選び、\(n=pq\)として、\(n\)から\(p\)と\(q\)を計算することが実用上必要な時間にできない(例えば数百年とか)ようにする。
2. \(e\)と\(\varphi(n)\)が互いに素であるような\(2\)以上の整数\(e\)を求める。 ただし、
   \(\varphi(n)=|\{i\in\mathbb{Z}|1\leq i\leq n, i\)と\(n\)は互いに素\(\}|\)
   とします。
この決めた\(e,n\)を公開鍵と呼びます。
2. 送信者は受信者の公開鍵を取得する。
3. 暗号化したいメッセージを送信者が公開鍵を使って暗号化し、送信する。
\(n\)よりも小さい正の整数\(A\)を送るとします。
\(A^\prime\equiv A^e\ ({\rm mod}\ n)\)となる\(A^\prime\)を計算します(\(A^e\)を\(n\)で割った余りが\(A^\prime\))。
この\(A^\prime\)を暗号として受信者に送信します。
4. 受信者が暗号化されたメッセージを受け取る。
5. 受信者は暗号文を秘密鍵で暗号化する前のメッセージに復号化する。
\(ed\equiv1\ ({\rm mod}\ \varphi(n))\)を満たす正の整数\(d\)を求めます。
この\(d\)が暗号を復号化するための鍵、すなわち秘密鍵です。
すると、\(A\equiv\left( A^\prime\right)^d\ ({\rm mod}\ n)\)が成り立つため、\(A\)が分かる、ということです。

というようなものでした。
素因数分解は1.に出てきます。
つまり

の「\(n=pq\)として」の部分です。
\(n=pq\)はまさに素因数分解を表わしています。
仮に\(n\)が与えられたとしても、これを2つの相異なる素数\(p\)および\(q\)の積に分けるというのが誠に難しいというような\(n\)を選ぶことがセキュリティの高さを担保しているのです。

小話：素因数分解の一意性が成り立たない世界があります。

初等整数論のお話をしているため、本シリーズで考えている数は勿論整数ですが、素因数分解の一意性が成り立つというのは整数の重要な性質です。

整数以外でも素因数分解の一意性が成り立つ世界もある。

整数の世界をちょっと飛び出して、次のような世界を考えます。
$$
\mathbb{Z}[-1]=\left\{a+b\sqrt{-1}\middle|a,b\in\mathbb{Z}\right\}
$$
このとき、
$$
2=2+\sqrt{-1}\times0,\quad 5=5+\sqrt{-1}\times0
$$
により、\(2,5\in\mathbb{Z}[-1]\)です。
\(2,5\)は整数の世界、すなわち\(\mathbb{Z}\)では素数ですが、\(\mathbb{Z}[-1]\)では素数では有りません。
なぜなら
\begin{eqnarray}
2&=&(1+\sqrt{-1})(1-\sqrt{-1})\\
5&=&(1+2\sqrt{-1})(1-2\sqrt{-1})
\end{eqnarray}
となるからです。
その代わり、
$$
1\pm i,\quad 1\pm 2i
$$
などが素数となります。
この世界では、実は素因数分解の一意性が成り立ちます。

整数の世界から飛び出して、素因数分解の一意性が成り立たない世界がある。

整数の世界からちょっと飛び出して、次のような世界を考えます。
$$
\mathbb{Z}[-5]=\left\{a+\sqrt{5}ib=a+b\sqrt{-5}\middle|a,b\in\mathbb{Z}\right\}
$$
このとき、\(6=6+0\times\sqrt{-5}\)により\(6\in\mathbb{Z}[-5]\)です。
また、同様にして\(2,3\in\mathbb{Z}[\sqrt{-5}]\)です。
しかしこのとき
$$
6=2\times 3=\left( 1+\sqrt{-5}\right)\left( 1-\sqrt{-5}\right)
$$
となって、素因数分解の一意性が成り立ちません。

皆様のコメントを下さい！

このブログを読んでいただいている方の多くは「数学に興味がある」という方だと思います。
そして、数学科卒だったり数学科に在籍していたり、某か数学と関わりが深い学問を専攻している方だと思います。

数学科卒、数学科在籍の方はなぜ数学科に進学しましたか？
数学科以外の方は、なぜ数学科に進学しなかったのですか？
是非コメントで教えて下さい！

※実は筆者が通っていたのはは数学科ではないです。

結

今回は「なぜ\(1\)が素数に含まれないのか？」ということと「素因数分解定理」および「素因数分解の一意性」について解説しました。
また、素因数分解の応用先としてRSA暗号があることも述べました。
さらに小話として素因数分解の一意性が成り立たない世界があるということも紹介しました。

結局言いたいことは素因数分解は、整数を積で分けたときの最小単位である、ということです。
故に、何か素数を積の単位で考えたいときは、結局は素因数を考えればOKということが素因数分解定理から言えます。

次回は素因数分解定理から得られる事実を数個紹介します。
(2023/3/14追記：合同式に変更します)

乞うご期待！
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、「定理〇〇の△△が分からない！」などいただければ全てお答えします！
お問い合わせの内容にもよりますが、ご質問はおおよそ１週間以内にお答えします。
(難しかったらもう少しかかる∂かもしれませんが…)

初等整数論について、以下の書籍をオススメします！