整数の話#2素数と素因数分解

佐久知氷仙です。

今回も前回と引き続いて整数の話をしたいと思います。
今回は素数についてです。

素数との出会い

素数という言葉を知ったのは小学5年生のときです。というのもファイナルファンタジータクティクスというゲームがあるのですが、その中に算術士というジョブがあります。その算術士は例えばレベルが3の倍数のキャラクター全員(敵味方の区別なく)に強力な魔法を使えるというチート級のアビリティが使えたのです。その3の倍数のところが素数にも変更できたのですが、素数ってどういうこと？って思ってました。それが素数という言葉を初めて知ったきっかけです。そこで当時担任の先生だったこうもと先生という女の先生に聴くことにしました。そうすると次のように教えてくれました。

素数とは

素数とはその約数の数がちょうど2つの整数だよと教えてくれました。では、1は素数でしょうか？いいえ、1は素数ではありません。なぜなら、1=1×1としか表せないので約数は1しかないのです。よって約数の数はちょうど1つです。なので1は素数ではないのです。このとき、あ！確かにそうだ！なるほど！という感じがしたのを覚えています。
では、2は素数でしょうか？はい、2は素数です。なぜなら、2=1×2と表すことができ、1と2以外に約数をもたないので約数の数はちょうど2つです。なので、2は素数です。最小の素数といえるでしょう。
では、3は素数でしょうか？はい、3も素数です。なぜなら、3=1×3と表すことができ、1と3以外に約数をもたないので約数の数はちょうど2つです。なので3は素数です。
では、4は素数でしょうか？いいえ、4は素数ではありません。なぜなら、4=1×4=2×2と表せるので4の約数は1、2、4の3つです。なので4は素数ではないのです。
では、5は・・・という具合にいくらでも素数か素数でないかいえそうですね。それから1と素数以外の整数は合成数と呼ばれます。なので４は合成数といえますね。

素数は何個あるのか？

素数はいったい何個あるんだろう？そう考えるのは自然です。では、仮に素数が2と3の2個だけだったとしましょう。そこで、2×3+1を考えるのです。これは2でも割り切れませんし、3でも割り切れません。2×3+1＝7は7=1×7と表せるので7の約数はちょうど2つです。よって、2と3から新たな素数7を作ることができました。
では次に2×3×7+1を考えましょう。これも2でも3でも7でも割り切れません。2×3×7+1=43は注意深く調べるとこれも43=1×43としか表せないため素数であることがわかります。なので2と3と7から新たな素数43を作ることができました。
で再び2×3×7×43+1を考えるのです。これも2でも3でも7でも43でも割り切れません。2×3×7×43+1=1807を調べてみると1807＝13×139と表せることに気づきます。なので1807は合成数です。しかしその約数13も139もどちらも素数です。あらたに13と139という素数を作ることができました。
このように新たに得られた素数を𝑝とすると、素数は2×3×∙∙∙×𝑝+1という操作を続ければ、これが素数だとしても新たな素数が、合成数だとしてもその約数として新たな素数が得ることができます。このような議論から素数は無限に、つまり何個でも多く存在することがいえるのです。

素因数分解

例えば12を考えてみましょう。12=2×6と表せます。左の2は素数なのでこれ以上分解できません。なので6ほうをもう少し分解していきましょう。12=2×2×3となります。この右辺にでているのはすべて素数です。このように整数は素数の積に分解することができるのです。これを素因数分解といいます。しかも順序の違いを無視するとただ1通りに表せるのです。さらに指数をつかうともったきれいに表すことができます。つまり、12=2²×3¹という風にあらわすことができます。この素因数分解を使って前回の最大公約数と最小公倍数の関係がどんな整数でも正しいか調べてみましょう。

素因数分解による証明

前回と同様にまず𝑎=12,𝑏=15をそれぞれ素因数分解してみましょう。
𝑎=2²×3¹×5⁰
𝑏=2⁰×3¹×5¹
わかりやすく1も0乗で表してみました。
𝑑=gcd(𝑎,𝑏)=3でした。
𝑑も素因数分解してみましょう。
𝑑=2⁰×3¹×5⁰
こうすると法則がみえてきませんか？
つまり最大公約数は𝑎,𝑏のそれぞれの素因数の指数が小さい方を選んでいるのです。𝑚=lcm(𝑎,𝑏)=60も素因数分解してみましょう。
𝑚=2²×3¹×5¹
逆に最小公倍数の方は𝑎,𝑏のそれぞれの素因数の指数が大きい方を選んでいるのです。
なので、𝑑×𝑚=2⁽⁰⁺²⁾×3⁽¹⁺¹⁾×5⁽⁰⁺¹⁾=𝑎×𝑏がいえるわけです。
これを一般化することで、任意の整数に対して𝑎×𝑏=𝑑×𝑚がいえるのです。つまり、𝑎の2の指数を𝑎₂、𝑏の2の指数を𝑏₂とすると、𝑑の2の指数はmin(𝑎₂,𝑏₂)となり、𝑚の2の指数はmax(𝑎₂,𝑏₂)となります。ちなみにmin(𝑥,𝑦)は𝑥,𝑦の小さい方をとる関数で、逆にmax(𝑥,𝑦)は𝑥,𝑦の大きい方をとる関数です。
よって、𝑎×𝑏の2の指数は𝑎₂+𝑏₂、𝑑×𝑚の2の指数はmin(𝑎₂,𝑏₂)+max(𝑎₂,𝑏₂)=𝑎₂+𝑏₂となり、𝑎×𝑏=𝑑×𝑚の2の指数はどちらも、𝑎₂+𝑏₂です。これが3以上の他の素数の指数に対しても同じことがいえるので、𝑎×𝑏=𝑑×𝑚がいえるわけです。証明終わり。

以上が前回残ってあった部分の解説でした。
これからも数学のさまざまなことをお話していきたいと思っています。
今回は以上です。最後まで読んでいただきありがとございました。