【基本】素数と素因数分解

ここでは、素数と素因数分解について見ていきます。

【広告】

素数

2以上の自然数のうち、1とそれ自身以外に正の約数をもたないものを、素数(prime number) といいます。例えば、 $2$ は、正の約数が $1,2$ だけなので、素数です。一方、 $6$ は、 $1,6$ 以外に $2,3$ という正の約数を持つので、素数ではありません。このような、2以上の自然数で、素数ではないものを、合成数(composite number) といいます。

素数の「素」には、「もとになるもの」といった意味があります。また、「合成数」という言葉には、何かを組み合わせて作られた数、というような意味にとれますね。後で見るように、合成数は素数の積で表すことができます。積で分解していくと、合成数は素数の積で分解できる数、素数はこれ以上分解できない最小単位の数、と考えることができます。

なお、1は、素数にも合成数にも含みません。

素因数分解

2以上の自然数は、素数の積で書くことができます。

例えば、 $252$ という自然数について考えてみましょう。まず、 $2$ で割れることがわかります。 $2$ で何度か割っていくと、\[ 252=2^2\times 63 \]と書けることがわかります。後半部分は、さらに $3$ で割れるので、繰り返し割っていくと、\[ 252=2^2\times 3^2 \times 7 \]となります。これ以上、素数の積に分解することができないので、これが最終形です。

一般に、整数がいくつかの整数の積で表されるとき、その積に表れる1つ1つの整数を、因数(factor) といいます。また、素数である因数は、素因数(prime factor) といい、自然数を素数だけの積の形で表すことを、素因数分解(prime factorization) するといいます。

先ほど見た例の結果をまとめると、「 $252$ を素因数分解すると、 $2^2\times 3^2 \times 7$ となる」といえます。

また、素数は、すでに素因数分解できていると考えます。素数 $5$ を素因数分解しても、結果は $5$ です。積の記号が出てこないですが、これを「素数の積で表した結果」だと考えます。

素因数分解に関する重要な事実

素因数分解に関して、2つの重要な事実があります。

1つは、「2以上の自然数は、素因数分解できる」ということです。

これは、背理法を使えば示すことができます。もし、素因数分解できない合成数があったとしましょう。そのような合成数のうち、一番小さいものを $M$ としましょう。 $M$ は合成数なので、2以上の2つの自然数 $a,b$ の積で書けます。この2つの自然数 $a,b$ は、元の数 $M$ より小さいため、素因数分解をすることができます。よって、 $M=ab$ の右辺が素数の積で表せることになるので、「 $M$ が素因数分解できない」ことに矛盾します。

このことから、「2以上の自然数は、素因数分解できる」ことがわかります。

2つ目の重要な事実は、「2以上の自然数は、積の順序の違いを除けば、素因数分解の方法は1通りである」ということです。

「積の順序の違いを除けば1通り」というのは、例えば、上で見た $252$ の例であれば、 $2^2\times 3^2 \times 7$ と書いたり、 $3^2\times 2^2 \times 7$ と書いたり、 $2\times 3 \times 7\times 2\times 3$ と書くこともできますが、これらは掛ける順番が違うだけで、並び替えれば全部同じになる、ということです。違う素因数が出てきたり、各素因数の指数(掛ける回数)が異なることはない、ということです。

これは簡単に示すことができないので、結果だけ知っておけばいいです。このことを、「素因数分解の一意性」と呼んだりします。

2以上の自然数は素因数分解できること、その方法は(積の順番を除くと)1通りであること。この2つはとても重要な定理で、「算術の基本定理」「整数論の基本定理」などと呼ばれています。

おわりに

ここでは、素数と素因数分解について見てきました。また、素因数分解が常にできて、その方法が一通りである、ということの紹介もしました。これらがどのように役立つかはなかなかわかりにくいですが、いろんな問題を考える上で基本となるものなので知っておきましょう。