合成数Nは1より大きく√N以下の約数をもつ

今回からいよいよ素数や合成数に関する定理が登場します。

素数と合成数

まずは素数と合成数を定義しておきます。

合成数については「1 と自分自身以外に最低でも 1 つの約数をもつ」と言いかえることもできます（後述する定理 B1 の証明でこの事実を用います）。

素数を小さい順に並べてみます。
$$2,3,5,7,11,13,17,19\cdots$$
合成数は 1 と素数以外の数なので、素数同士の間隔を埋めるように
$$4,6,8,9,10,12,14,15\cdots$$
となります。1 は素数でも合成数でもないので、どちらにも含まれていません。つまり自然数は 1 と素数と合成数で構成されます。

合成数Nは1より大きく√N以下の約数をもつ

合成数 12 の約数を全て並べてみます。
$$1,2,3,4,6,12$$
12 の平方根は 3.464 ですが、この値より小さく、1 以外の約数 (2 と 3) が存在しています。実はどんな合成数 $N$ についても、1 より大きく $\sqrt{N}$ 以下の約数をもつことが知られています。

【証明】$N$ は合成数なので、1 ではない 2 つの数 $a$ と $b$ の積に分解できるはずです。すなわち小さくないほうを $b$ として
$$N=a\times b(1<a\le b,a,b\in \mathbb{Z})$$
と表すことができます。$1<a\le b$ なので
$$N=a\times b\ge a\times a=a^2$$
すなわち $a\le \sqrt{N}$ が示されました。（証明終）

1より大きな整数は1個以上の素因数をもつ

たとえば 100 という数を適当に分解して
$$100=4\times 25$$
と表したとします。さらに 4 も分解してみると
$$4=2\times 2$$
というように素数 2 が現れました。このように、合成数の中に積の形で含まれる素数のことを素因数とよびます。一般に 1 より大きな整数は、上のように積の形に分解していけば必ずどこかで素因数が現れます。あまりに自明なことではありますが、これも定理として載せておきます。

【証明】$N$ が素数であれば、$N$ 自身が素因数です。$N$ が合成数であれば、
$$N=a_1\times b_1(1<a_1<N)$$
のように積の形に分解することができます。$a_1$ が素数であれば、それが素因数です。$a_1$ が合成数であれば、
$$a_1=a_2\times b_2(1<a_2<a_1)$$
のように積の形に分解することができます。$a_2$ が素数であれば、それが素因数です。これを繰り返していくと $a_k$ は単調減少かつ $a_k\ne 1$ なので、有限回操作で必ず素数となります。（証明終）

整数abが素数pで割り切れるならば、a,bのいずれかはpで割り切れる

「36 = 4 × 9 は 2 で割り切れるので、4 は素数 2 で割り切れます」というような当たり前のことを述べているのが次の定理です。

$\vee$ は論理和の記号、すなわち「または」を表す記号です。$A\vee B$ は $A$ と $B$ がともに成り立つ場合も含みます。したがって、たとえば「 108 = 9 × 12 は素数 3 で割り切れて、9 も 12 も 3 で割り切れる」というようなことも含まれています。

【証明】証明には定理A11
$$(a,b)=1,a|bc⟹a|c$$
を用います。素数 $p$ の約数は 1 か $p$ です。$p|a$ ならば定理は成り立っています。$a$ が $p$ で割り切れないときは
$$(p,a)=1,p|ab$$
なので $p|b$ となります。（証明終）

整数nが素数p,qで割り切れるならばnはpqで割り切れる

次の定理もほぼ自明としてよいぐらいの事実です。たとえば「 20 は相異なる素数 2 と 5 で割り切れるならば、20 は 2 × 5 = 10 で割り切れる」というようなことを述べています。

【証明】この定理の証明にも定理A11
$$(a,b)=1,a|bc⟹a|c$$
を用います。$p|n,q|n$ なので整数 $a,b$ を用いて
$$n=pa=qb$$
と表すことができます。$(p,q)=1,p|qb$ なので $p|b$ であり、整数 $k$ を用いて
$$b=pk,n=pqk$$
と表せます。よって $pq|n$ となります。（証明終）
　

1より大きな整数は有限個の素数の積で表せる

たとえば 60 という数は
$$60=2^2\times 3\times 5$$
というように素数の積で表すことができます。そして素数の順序を考えなければ、この分解方法はただの一通りしかありません。これも当たり前のことではありますが、数論の根幹をなすような重要な定理です。

【証明】$1$ より大きい整数が有限個の素数の積で表せることを証明します。

$n$ が素数であれば、$n=n$ というように、素数 1 個の積で表せるので定理は成り立ちます。したがって $n$ が素数でない場合を考えます。証明には数学的帰納法を用います。まず最小の合成数である 4 について、4 よりも小さく 1 よりも大きな 2, 3 はどちらも素数なので素因数分解できます。次に 1 より大きく $n$ より小さい整数は全て素因数分解できるような $n$ を選びます。そのとき、$n$ の 1 以外の約数のうち最小数は素数となります。それを $p$ とすると、正整数 $a$ を用いて
$$n=pa$$
と表すことができます。このとき $a<n$ なので仮定により
$$a=p_1{p}_2\cdots p_k$$
と表せます。よって
$$n=pa=p{p}_1{p}_2\cdots p_k$$
となって $n$ も素因数分解することができます。$n=4$ は素因数分解できるので、次の合成数 $n=6$ も素因数分解できて、またその次の合成数 $n=8$ も素因数分解できて … これを繰り返して全ての合成数 $n$ について素因数分解できます。（証明終）

次に素因数分解の仕方が一通りであることを証明します。
$n$ が 2 通りに素因数分解されたと仮定します。
$$n=p_1{p}_2\cdots p_j=q_1{q}_2\cdots q_k$$
$p_1,p_2,\cdots ,p_j$, $q_1,q_2,\cdots ,q_k$ は全て素数です。重複があっても構いません。ここで定理B3

により、$p_1$ は $q_1,q_2,\cdots ,q_k$ のうちどれかを割り切ることができます。
$$p_1|q_1{q}_2\cdots q_k$$
$q$ の添え字の番号はどのように入れ替えてもかまわないので、右辺の素因数のうち、$p_1$ で割り切るものを $q_1$ に選びます。しかし $p_1,q_1$ はともに素数なので $p_1=q_1$ です。そこで、この数で両辺を割ると
$$p_2{p}_3\cdots p_j=q_2{q}_3\cdots q_k$$
となります。同じように $p_2=q_2,p_3=q_3$ として次々に割っていくと、仮に $j>k$ とした場合、
$$p_{k+1}\cdots p_j=1$$
となってしまいますが、これは明らかに矛盾しています。よって $j=k$, すなわち素因数分解の方法は唯の一通りであることが示されました。（証明終）

標準素因数分解

ある数 $n$ を素因数分解したとき、同じ種類の素因数をまとめて

と書くような記述の仕方を標準素因数分解とよびます。たとえば $480200$ を標準素因数分解すると
$$480200=2^3{5}^2{7}^4$$
のように表すことができます。

素因数分解を用いてGCDとLCMを計算する

素因数分解を用いると最大公約数 (GCD) と最小公倍数 (LCM) を簡単に計算することができます。たとえば 126 と 600 をそれぞれ素因数分解すると
$$\begin{array}{r}126=2^1\times 3^2\times 5^0\times 7^1\\ 600=2^3\times 3^1\times 5^2\times 7^0\end{array}$$
となります。比較しやすくするために、指数部分が 0 や 1 である場合も書いてあります。最大公約数は各因数からベキ指数の小さいほう（正確に言うと大きくないほう）を選んで掛け合わせます：
$$(126,600)=2^1\times 3^1\times 5^0\times 7^0=6$$
最小公倍数はベキ指数の大きいほう（正確に言うと小さくないほう）を選んで
$$\{126,600\}=2^3\times 3^2\times 5^2\times 7^1=12600$$
と計算できます。一般には次のように計算します。

ここで $\min (a,b)$ は $a,b$ の最小値、$\max (a,b)$ は$a,b$ の最大値を表します。詳しくは 小さくない数と大きくない数 の記事を参照してください。