算術の基本定理

算術の基本定理によると、1より大きいどんな自然数も、ただ1通りに素数の積に分解できます。たとえば、15は2つの素数の積 3 · 5 に、30は3つの素数の積 2 · 3 · 5 に、16は4つの素数の積 2 · 2 · 2 · 2 に分解できます。このように数を素数の積で表したものを、素因数分解といいます。たとえば、10の素因数分解は 2 · 5 です。

いちばん簡単な素因数分解をもつのは素数そのものです。それ以上分解する必要がないからです。7の素因数分解は、そのまま7です。

素因数分解を計算する

算術の基本定理の内容

算術の基本定理は、次の2つのことを述べています。

• 1より大きいどんな自然数にも、素因数分解が見つかる。
• どの数も、素因数分解はただ1通りである。

これが本当に成り立つことを証明してみましょう。

存在の証明

まず、1より大きいどんな自然数にも、少なくとも1つの素因数分解が存在することを証明します。それには数学的帰納法を使います。数学的帰納法の最初の段階として、1より大きい最小の自然数、つまり2は素数であることを確認します。

次に、素因数分解が見つかる数の列 2, …, n があるとき、この列に n + 1 を加えると、その新しい数にも素因数分解が存在することを示します。まず、例で見てみましょう。

はじめは、列 2, …, n は少し変わった形で、2という1つの数しか含みません。この列に n + 1、つまり3を加えたとき、3にも素因数分解が存在することを示したいわけです。3は素数なので、もちろん素因数分解が存在します。3そのものです。

これで、列 2, …, n は 2, 3 の2つの項になりました。この列に4を加えます。4は素数ではないので、1より大きく4より小さい2つの自然数の積に分解できるはずです。そのような数は、すべてこの列に入っています。そして、この列には素因数分解をもつ数しかありません。したがって、4にも素因数分解 2 · 2 があるはずです。

一般の証明にもどると、次のように書けます。2は素数なので、素因数分解をもちます。ここで、列 2, …, n のどの数も素因数分解できると仮定します。これが帰納法の仮定です。すると、n + 1 は素数であって、そのまま素数の積に分解できるか、合成数であるかのどちらかです。合成数なら、次の式を満たす自然数 a, b が存在するはずです。

$$n+1=a\cdot b$$

このとき、これらの自然数は、もちろん n + 1 より小さく、1より大きくなければなりません。

$$\begin{array}{rcl}a>1,& & a<n+1\\ b>1,& & b<n+1\end{array}$$

したがって、a, b は列 2, …, n に入っているはずです。そして、この列のどの数にも素因数分解が存在するので（これが帰納法の仮定です）、次のように書けます。

$$\begin{array}{rcl}a& =& p_1\cdot p_2\cdot \dots \cdot p_i\\ b& =& q_1\cdot q_2\cdot \dots \cdot q_j\end{array}$$

ここで、すべての p_i と q_j は素数で、p₁ · p₂ · … · p_i と q₁ · q₂ · … · q_j はそれぞれの素因数分解です。また、n + 1 は積 n + 1 = a · b に分解できるのでした。したがって、次の式も成り立ちます。

$$\begin{array}{rcl}n+1& =& a\cdot b\\ & =& p_1\cdot p_2\cdot \dots \cdot p_i\cdot q_1\cdot q_2\cdot \dots \cdot q_j\end{array}$$

つまり、n + 1 は素数の積 p₁ · p₂ · … · p_i · q₁ · q₂ · … · q_j に分解でき、新しく加えた数 n + 1 も素因数分解をもちます。このことから、1より大きいどんな自然数にも、少なくとも1つの素因数分解があることがわかります。

一意性の証明

次に、1より大きいどんな自然数にも、素因数分解が2通り以上はないことを示しましょう。この定理は背理法で証明します。定理が正しくないと仮定します。つまり、異なる2つの素因数分解をもつ、1より大きい自然数 n が存在すると仮定します。

$$\begin{array}{rcl}n& =& p_1\cdot p_2\cdot \dots \cdot p_i\\ n& =& q_1\cdot q_2\cdot \dots \cdot q_j\end{array}$$

さらに、素因数分解が2通り以上ある数のうちで、n が最小であると仮定します。つまり、それより小さい自然数で、素因数分解が2通り以上あるものは存在しません。q₁ は n を割り切る素数の1つなので、当然 q₁ は p₁ · p₂ · … · p_i も割り切ります。

ここで、ユークリッドの補題を使います。これは、素数 p が2つの整数の積 a · b を割り切るなら、p は a と b の少なくとも一方を割り切る、というものです。例を挙げます。素数3は84を割り切ります。84は積 12 · 7 に分解できます。ユークリッドの補題によると、素数3は12と7の少なくとも一方を割り切ります。この場合は12を割り切ります。

この補題を使うと、q₁ が p₁ · p₂ · … · p_i を割り切るなら、p₁, p₂, …, p_i の少なくとも1つも割り切ることになります。一般性を失わずに、q₁ が p₁ を割り切るとしてかまいません。ところが、p₁ も素数です。素数がほかの素数を割り切るのは、どんなときでしょうか。たとえば、素数7で割り切れる素数は何でしょうか。やはり7だけです。7がほかの素数を割り切ることはできません。もし割り切るなら、その数は素数ではなくなってしまいます。したがって、p₁ = q₁ でなければなりません。

つまり、2つの素因数分解には、共通の素数 p₁（q₁）が1つあります。2つの式の両辺を、それぞれ p₁、q₁ で割りましょう。

$$\begin{array}{rcl}\frac{n}{p_1}& =& \frac{p_1\cdot p_2\cdot \dots \cdot p_i}{p_1}\\ \frac{n}{q_1}& =& \frac{q_1\cdot q_2\cdot \dots \cdot q_j}{q_1}\end{array}$$

p₁ = q₁ なので、左辺は同じ数になります。これを m とします。すると、次の式が成り立ちます。

$$m=\frac{n}{p_1}=\frac{n}{q_1}$$

右辺は約分するだけです。

$$\begin{array}{rcl}m& =& p_2\cdot p_3\cdot \dots \cdot p_i\\ m& =& q_2\cdot q_3\cdot \dots \cdot q_j\end{array}$$

n をその素因数の1つで割ると m になるので、m は n より小さい自然数であることは確かです。ところが、2つの式の右辺は、どちらも m の素因数分解です。つまり、n より小さく、しかも異なる2つの素因数分解をもつ数 m をつくれたことになります。これは、n が素因数分解を2通り以上もつ最小の数である、という仮定に矛盾します。

したがって、「素因数分解を2通り以上もつ最小の数」は存在しない、と考えるしかありません。「素因数分解を2通り以上もつ最小の数」が存在しないということは、素因数分解を2通り以上もつ数は1つも存在しないということです。つまり、1より大きいどんな整数も、素因数分解はただ1通りです。