合成数

同義語：composite number

概要

前提知識: 素数, 約数, 整除関係, Eulerのφ関数, Fermatの小定理

合成数（composite number）は、$2$ 以上の整数のうち素数でないもの、つまり $1$ より大きい 2 つの数の積に分けられる数である。$4=2\cdot2$、$6=2\cdot3$、$91=7\cdot13$ などがそうである。素数が掛け算の「原子」なら、合成数は原子を 2 個以上組み合わせた「分子」にあたる。合成数であることは因数を 1 組見せれば確かめられるが、素数であることは「どんな因数もない」ことを確かめなければならず、この非対称が素数判定と素因数分解の難しさの出発点になる。この記事では、合成数を約数の個数・約数の和・Euler の関数・剰余環・Fermat の小定理のそれぞれで言い換える主定理と、その量的な形、奇数の合成数を平方数の差として見る Fermat の考え方を証明し、合成数がどれくらいあるか、どんな式が合成数を作るかを例と反例で見る。

定義

合成数

整数 $n\ge2$ が素数でないとき、$n$ を 合成数 という。すなわち $n$ が $1$ と $n$ 以外の正の約数をもつことであり、これは
$$ n=ab,\qquad 1< a< n,\quad 1< b< n $$
となる整数 $a,b$ があることと同値である。

同値であることは次のとおりである。$1< d< n$ となる約数 $d$ があれば $n=d\cdot(n/d)$ で、$d< n$ から $n/d>1$、$d>1$ から $n/d< n$ である。逆に $n=ab$、$1< a< n$ なら $a$ が $1,n$ 以外の約数である。定義は Ste17 Definition 1.1.3（p. 2）、Cri24 Definition 6.1.2（p. 71）と同じである。

$1$ は素数でも合成数でもない。$1$ の正の約数は $1$ だけであり、$1$ を $1$ より大きい数の積に分けることもできない。したがって $2$ 以上の整数は、素数と合成数のちょうど一方である（素数の記事の定義「素数と合成数」）。
$0$ と負の整数は、この記事では合成数と呼ばない。環 $\mathbb Z$ の言葉では、$0$ でも単元 $\pm1$ でもない整数 $n$ が $2$ つの単元でない整数の積に書けるとき $n$ は可約であり、$n\ge2$ について「可約」と「合成数」は同じことである。素数は、単元でない積に書けない元（既約元）にあたる。
合成数であることは掛け算についての性質であり、足し算とは関係がない。$4$ と $9$ は合成数だが $4+9=13$ は素数である。一方、合成数に $1$ より大きい数を掛けた数はまた合成数である。

直感

$n$ 個の点を長方形に並べることを考えると、$1$ 行に並べる以外の長方形が作れるのが合成数、作れないのが素数である。$12$ 個なら $2\times6$ や $3\times4$ に並ぶが、$13$ 個は $1\times13$ にしか並ばない。合成数であることの「証拠」は長方形の縦と横、つまり因数 $a,b$ の組であり、これを見せれば誰でも掛け算 1 回で確かめられる。しかし大きな数について証拠を 見つける のは難しい。この記事の主定理は、因数そのものを見せなくても合成数であることがわかる言い換え（約数の和、Euler の関数、Fermat の小定理が破れること）を並べたものであり、その 1 つは実際の素数判定の考え方の元になっている。

例と反例

最初の合成数と個数

$100$ 以下の合成数を小さい順に並べると
$$ 4,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30,32,33,34,\dots $$
と続く（Ste17 p. 2）。$2$ より大きい偶数はすべて $n=2\cdot(n/2)$ と分けられるので合成数であり、偶数の素数は $2$ だけである。$100$ 以下の素数は $25$ 個なので、$2$ 以上 $100$ 以下の合成数は $99-25=74$ 個ある。一般に $x\ge2$ 以下の合成数の個数は $\lfloor x\rfloor-1-\pi(x)$ である（$\pi(x)$ は素数計数関数）。$1000$ 以下では $831$ 個である。

$n^4+4$ は $n\ge2$ で合成数

すべての整数 $n$ について
$$ n^4+4=(n^2+2n+2)(n^2-2n+2) $$
である（右辺を展開すると $(n^2+2)^2-(2n)^2=n^4+4n^2+4-4n^2$）。$n\ge2$ なら $n^2-2n+2=(n-1)^2+1\ge2$ で、$n^2+2n+2>n^2-2n+2$ なので、両方の因数が $1$ より大きく、$n^4+4$ は合成数である。$n=3$ では $85=17\cdot5$、$n=5$ では $629=37\cdot17$ である。$n=1$ では小さい方の因数が $1$ になり、$1^4+4=5$ は素数である。

連続する合成数

$89$ と $97$ の間の $90,91,\dots,96$ は $7$ 個続けて合成数である（$91=7\cdot13$、$95=5\cdot19$ で、ほかは偶数か $3$ の倍数）。いくらでも長く続く合成数の並びは、$n!+2,\dots,n!+n$ の $n-1$ 個として作れる（素数の記事の「素数の分布」の節）。$7$ 個の並びを得るにはこの作り方では $n=8$ として $40322$ から始めることになり、実際の最初の並びよりずっと先になる。素数の積を使う作り方もあり、$N=2\cdot3\cdot5\cdot7=210$ とすると $N-7,\dots,N-2$、すなわち $203,\dots,208$ の $6$ 個が合成数になる。$2\le x\le7$ の各 $x$ の素因数 $p$ は $N$ と $x$ をともに割り切るので $N-x$ を割り切り、$1< p\le7<203\le N-x$ だからである（Cri24 Fact 21.3.5、p. 376）。

合成数を作りそうにない式が作る合成数

$n^2+n+41$ は $n=0,1,\dots,39$ で素数だが、$n=40$ では $40^2+40+41=41^2=1681$ で合成数である。定数でない整数係数の多項式が正の整数でとる値がすべて素数になることはない（初等整数論の記事の定理「素数だけを値にとる多項式は定数」）。
$2^n-1$ は $n$ が合成数なら合成数である（Mersenne素数の記事の系「素数になるための指数の条件」）が、$n$ が素数でも合成数になりうる。$2^{11}-1=2047=23\cdot89$ である（同じ記事の例「反例：指数が素数でも合成数になるMersenne数」）。
Fermat 数 $2^{32}+1=4294967297=641\cdot6700417$ は合成数である（Fermat数の記事の例「反例：$F_5$ は 641 で割り切れる」）。

反例の表

合成数について成り立つ主張の条件を外すと、次のように崩れる。

外す条件	反例	成り立たなくなること
$n\ge2$	$n=1$	素数か合成数のどちらか一方であること
$n\neq4$	$n=4$	合成数 $n$ で $(n-1)!\equiv0\pmod n$（$3!=6\equiv2\pmod4$）
すべての $a$（$n$ と互いに素でないものも含めて）調べる	$n=561=3\cdot11\cdot17$	「調べた $a$ のすべてで $a^{n-1}\equiv1\pmod n$ なら $n$ は素数」という判定（$n$ と互いに素な $a$ だけを調べると、合成数 $561$ を見分けられない）
$n$ が奇数	$n=6$	合成数が $x^2-y^2$（$x-y\ge2$）の形に書けること
$n\ge2$	$n=1$	$n^4+4$ が合成数であること（$5$ は素数）
$0\le n\le39$	$n=40$	$n^2+n+41$ が素数であること（$41^2$）

2 行目は Wilsonの定理の記事の命題「合成数での余り」、3 行目は既約剰余類群の記事の例「最小の Carmichael 数 $561$」、4 行目は thm-cmp-fermat-difference の条件、5 行目は ex-cmp-germain である。3 行目の区別は thm-cmp-characterization の (7) で詳しく述べる。

性質

主定理：合成数の言い換え

$n$ の正の約数の個数を $\tau(n)$、正の約数の和を $\sigma(n)$、$1\le a\le n$ で $\gcd(a,n)=1$ となる $a$ の個数を $\varphi(n)$（Eulerのφ関数）、素因数を重複をこめて数えた個数を $\Omega(n)$ と書く。

合成数の言い換え

$n\ge2$ を整数とする。次の条件は互いに同値である。
(1) $n$ は合成数である。
(2) $1< d\le\sqrt n$ を満たす $n$ の約数 $d$ がある。
(3) $\tau(n)\ge3$ である。
(4) $\sigma(n)>n+1$ である。
(5) $\varphi(n)< n-1$ である。
(6) 剰余環 $\mathbb Z/n\mathbb Z$ は整域でない（$0$ でない 2 つの類の積が $0$ になる）。
(7) $1\le a\le n-1$ の範囲に、$a^{n-1}\not\equiv1\pmod n$ となる整数 $a$ がある。
(8) $\Omega(n)\ge2$ である。

余分な約数がどこに現れるかを見る

各条件を (1) と比べる。
(1)⇔(2)：(1) なら、$n$ の $1$ より大きい最小の約数 $p$ は $p\le\sqrt n$ を満たす（素数の記事の命題「素因数の存在」の 2）。逆に (2) の $d$ は $d\le\sqrt n< n$ なので、$1,n$ 以外の約数であり、$n$ は合成数である。
(1)⇔(3)⇔(4)：$n\ge2$ なので $1$ と $n$ は異なる約数であり、$\tau(n)\ge2$、$\sigma(n)\ge n+1$ である。$n$ が素数であることは約数が $1,n$ だけであることなので、$\tau(n)=2$ とも $\sigma(n)=n+1$ とも同値である。どちらの等号も、$1,n$ 以外の約数が 1 つでもあれば破れる（その約数の分だけ個数と和が増える）。
(1)⇔(5)：$\gcd(n,n)=n>1$ なので $a=n$ は数えられず、$\varphi(n)\le n-1$ である。等号は、$1\le a\le n-1$ のすべての $a$ が $n$ と互いに素であることと同じである。$n$ に $1< d< n$ の約数 $d$ があれば $\gcd(d,n)=d>1$ なので等号は成り立たない。逆に $1\le a\le n-1$ で $g=\gcd(a,n)>1$ となる $a$ があれば、$g$ は $1< g\le a< n$ を満たす $n$ の約数なので $n$ は合成数である。
(1)⇔(6)：整域の記事の命題「$\mathbb{Z}/n\mathbb{Z}$ が整域になる条件」による（合成数 $n=ab$ では $\bar a\bar b=\bar0$）。
(1)⇔(7)：$n$ が素数なら、$1\le a\le n-1$ は $n$ で割り切れないので Fermatの小定理により $a^{n-1}\equiv1\pmod n$ であり、(7) は成り立たない。$n$ が合成数なら、$1< d< n$ となる約数 $d$ をとる。もし $d^{n-1}\equiv1\pmod n$ なら $n\mid d^{n-1}-1$ で、$d\mid n$ から $d\mid d^{n-1}-1$ となる。$n-1\ge1$ なので $d\mid d^{n-1}$ でもあり、$d\mid 1$ となって $d>1$ に反する。よって $a=d$ が (7) の $a$ である。
(1)⇔(8)：素因数分解 $n=p_1\cdots p_k$（重複を許す）は一意であり（素数の記事の定理「算術の基本定理」）、$\Omega(n)=k$ である。$k=1$ は $n$ が素数であること、$k\ge2$ なら $n=p_1\cdot(p_2\cdots p_k)$ は $1$ より大きい 2 数の積である。$\square$

は 試し割り の根拠である。$n$ が合成数かどうかは $\sqrt n$ 以下の素数で割ってみれば決まり、どれでも割り切れなければ $n$ は素数である（Cri24 Algorithm 6.2.3、p. 76。同じ事実を使って $n$ 以下の素数をすべて並べる素数のふるいは Ste17 Algorithm 1.2.3、p. 12）。たとえば $221$ については $\sqrt{221}<15$ なので $2,3,5,7,11,13$ を試せばよく、$221=13\cdot17$ が見つかる。
の証明では、$n$ と互いに素 でない $a$（$n$ の約数そのもの）を使った。$n$ と互いに素な $a$ だけを調べるのでは、(7) の代わりにならない。$341=11\cdot31$ は $2^{340}\equiv1\pmod{341}$ を満たし（初等整数論の記事の例「反例：Fermat の小定理の逆は成り立たない」）、$561$ は $561$ と互いに素なすべての $a$ で $a^{560}\equiv1\pmod{561}$ を満たす合成数（Carmichael 数）である。したがって、Fermat の小定理が破れる $a$ を見つければ因数を知らずに合成数だと断定できる一方、破れる $a$ が見つからないことは素数である証拠にならない（Carmichael 数と最小の $561$ については Ste17 §2.4、p. 37）。

量的な形

主定理の (4) と (5) は、合成数では $\sigma(n)$ と $\varphi(n)$ が素数の場合の値 $n+1$、$n-1$ から $\sqrt n$ 程度離れる、という形に強められる。

約数の和と Euler の関数の評価

$n$ を合成数とする。

$\sigma(n)\ge n+1+\sqrt n$ である。
$\varphi(n)\le n-\sqrt n$ である。
どちらも、等号が成り立つのは $n=p^2$（$p$ は素数）のとき、かつそのときに限る。

最小の素因数 $p$ とその相手 $n/p$ を使う

$p$ を $n$ の最小の素因数とする。$n$ は合成数なので $p\le\sqrt n$ であり（thm-cmp-characterization の (2) の証明）、$n/p\ge\sqrt n\ge p>1$、$n/p< n$ である。

$1$、$n/p$、$n$ は相異なる約数なので $\sigma(n)\ge1+n/p+n\ge n+1+\sqrt n$ である。等号が成り立つなら、$n/p=\sqrt n$、すなわち $n=p^2$ である。逆に $n=p^2$ の約数は $1,p,p^2$ なので $\sigma(p^2)=1+p+p^2=n+1+\sqrt n$ である。
$1\le a\le n$ のうち $p$ の倍数は $p,2p,\dots,(n/p)p$ の $n/p$ 個で、どれも $n$ と互いに素でない。よって $\varphi(n)\le n-n/p\le n-\sqrt n$ である。等号が成り立つなら、まず $n/p=\sqrt n$ から $n=p^2$ である。逆に $n=p^2$ なら、$n$ と互いに素でないのは $p$ の倍数だけなので $\varphi(p^2)=p^2-p=n-\sqrt n$ である。$\square$

$n=91=7\cdot13$ では $\sigma(91)=1+7+13+91=112\ge91+1+\sqrt{91}\approx101.5$、$\varphi(91)=6\cdot12=72\le91-\sqrt{91}\approx81.5$ である。$n=49$ では $\sigma(49)=57=49+1+7$、$\varphi(49)=42=49-7$ で等号になる。対偶を読めば、$\varphi(n)>n-\sqrt n$ となる $n\ge2$ は素数である。

奇数の合成数と平方数の差

奇数の合成数は平方数の差

$n\ge3$ を奇数とする。$n$ が合成数であることと、
$$ n=x^2-y^2,\qquad x,y\text{ は }0\text{ 以上の整数},\qquad x-y\ge2 $$
と書けることは同値である。さらに、分解 $n=ab$（$1\le a\le b$）と、表し方 $n=x^2-y^2$（$x>y\ge0$）は
$$ (a,b)\longmapsto\Bigl(x,y\Bigr)=\Bigl(\frac{a+b}2,\ \frac{b-a}2\Bigr),\qquad (x,y)\longmapsto(a,b)=(x-y,\ x+y) $$
によって 1 対 1 に対応する。

積と和・差を行き来する

$n=ab$、$1\le a\le b$ とする。$n$ は奇数なので $a,b$ はともに奇数で、$a+b$ と $b-a$ は偶数である。よって $x=(a+b)/2$、$y=(b-a)/2$ は $0$ 以上の整数で、$x>y$（$a\ge1$ より）、
$$ x^2-y^2=(x-y)(x+y)=a\cdot b=n $$
である。逆に $n=x^2-y^2$、$x>y\ge0$ なら、$a=x-y\ge1$、$b=x+y\ge a$ で $ab=n$ である。2 つの対応は互いに逆写像である（$x-y=a$、$x+y=b$ を解くと $x,y$ が、逆も同様に決まる）。
この対応で $x-y=a$ なので、「$x-y\ge2$ の表し方がある」ことは「$a\ge2$ の分解 $n=ab$、$a\le b$ がある」ことと同じである。$a\ge2$ なら $b=n/a< n$ であり、$a\le b$ から $a< n$ でもあるので、これは $n$ が合成数であることと同値である。$\square$

素数 $p\ge3$ の表し方は $a=1$ に対応する $p=\bigl(\frac{p+1}2\bigr)^2-\bigl(\frac{p-1}2\bigr)^2$ ただ 1 つであり、合成数には $x-y\ge2$ の表し方が少なくとももう 1 つある。この事実を因数の探索に使うのが Fermat の因数分解法 で、$\sqrt n$ 以上の最小の整数 $x$ から始めて、$x^2-n$ が平方数になるまで $x$ を $1$ ずつ増やす（Cri24 Fact 12.5.7・Algorithm 12.5.9、p. 202）。2 つの因数が近いときに速く終わる方法である。

Fermat の方法で $5959$ を分解する

$\sqrt{5959}\approx77.2$ なので $x=78$ から始める。
$$ 78^2-5959=125,\qquad 79^2-5959=282,\qquad 80^2-5959=441=21^2 $$
で、$125$、$282$ は平方数でなく、$441$ で平方数になる。よって $5959=80^2-21^2=(80-21)(80+21)=59\cdot101$ である。同じく $899=30^2-1^2=29\cdot31$ は最初の $x=30$ で終わる。

偶数の合成数では、この定理は成り立たない。$x^2-y^2=(x-y)(x+y)$ の 2 因数は偶奇が等しいので、平方数の差は奇数か $4$ の倍数であり、$n\equiv2\pmod 4$ の合成数（$6,10,14,\dots$）は平方数の差に書けない。これが反例の表の 4 行目である。

合成数はどれくらいあるか

素数計数関数の記事の命題「素数の割合の極限」により $\pi(x)/x\to0$ なので、$x$ 以下の合成数の個数 $\lfloor x\rfloor-1-\pi(x)$ を $x$ で割ったものは $1$ に近づく。つまり、正の整数から無作為に選んだ数は、選ぶ範囲を大きくするほど合成数である割合が $1$ に近づく。$100$ 以下では $74$ 個、$1000$ 以下では $831$ 個が合成数である。ex-cmp-runs のとおり合成数だけの並びはいくらでも長くなるが、それでも素数は無限にあり（素数の記事の定理「素数の無限性」）、合成数の並びは必ずどこかで途切れる。

補足

合成数を法とする計算で起こること

法 $n$ が合成数になると、素数を法とするときに成り立つ事実がいくつも崩れる。$\mathbb Z/n\mathbb Z$ に $0$ でない零因子が現れ（主定理の (6)）、$x^2\equiv1\pmod n$ が $\pm1$ 以外の解をもちうる（法 $15$ での $4^2\equiv1$）。どの事実がどう崩れるかは合成数を法とする合同式と既約剰余類群の記事で扱う。暗号の RSA 方式は、$2$ つの大きな素数の積である合成数 $n$ について、$n$ そのものは公開しても因数が見つけにくいことを使っている（Eulerのφ関数の記事の例「RSA暗号と $\varphi(pq)$」）。

文献

合成数の定義は Ste17 Definition 1.1.3（p. 2）、Cri24 Definition 6.1.2（p. 71）にある。試し割りは Cri24 Algorithm 6.2.3（p. 76）、同じ事実を使う素数のふるいは Ste17 Algorithm 1.2.3（p. 12）、合成数の長い並びは Cri24 Fact 21.3.5（p. 376）と Sho08 Exercise 1.28（p. 13）、$\mathbb Z/n\mathbb Z$ が体になるのは $n$ が素数のときに限ることは Sho08 Example 7.11（p. 170）、Fermat の因数分解法は Cri24 §12.5（p. 202）にある。