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

🕒 2018/07/16 🔄 2023/05/01

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

📘 目次

素数

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つはとても重要な定理で、「算術の基本定理」や「整数論の基本定理」などと呼ばれています。