合成数

合成数とは、正の整数である約数において、1とそれ自身以外の約数を持つ整数のことを言う。

例

ここで、6が合成数かどうかを考える。まず、約数として

• $6 = 6n, n \in \mathbb{Z}$
• $6 = 1n, n \in \mathbb{Z}$

が考えられる。もし、これだけしか約数が存在しない場合は、素数とすることができる。しかし、実際には

• $6 = 3n, n \in \mathbb{Z}$

になるn = 2を発見する。6において、1とそれ自体以外の約数があることが判明した。従って、これは合成数である。

応用

このように、1かそれ自体以外の約数が発見できれば、それが素数ではないことが証明できる。この方法を利用したのがエラトステネスのふるいである。