素因数分解とは
素因数分解とは,ある自然数をいくつかの素数の積で表すことである。現在は中学3年生で学習するようである。高等学校でも,数学Aの「整数の性質」で再考するが,詳細は明記されていない。
素因数分解の一意性
学生はあまり意識しないが,素因数分解は積の順序を除けばただ1通りで表すことができる。実は明らかではなく,教科書を見ても「よく知られている」と書かれてあるだけである。ここでは,その事実を証明してみよう。
記号
を自然数全体の集合,を整数全体の集合とする。とある場合には,「は自然数である」という意味である。
素因数分解の一意性を証明するために,次の補題を準備する。
ユークリッドの補題
が素数 かつに対して,がの倍数ならば,またははの倍数
()
を素数とし,をの倍数とする。の最大公約数をとすると,は素数なので,またはである。のとき,はの倍数。のときは,あるが存在して,。両辺倍すると,となるが,はの倍数なので,もの倍数となる。
()
をの正の約数とすると,あるが存在して,
はの倍数であるから,仮定より,またははの倍数である。
- はの倍数であるから,あるが存在して,。(★)より, すなわち を得る。なので。
- はの倍数であるから,あるが存在して,。(★)より, すなわち を得る。(★)からがわかるので,。
以上より,の正の約数はまたはであるから,は素数である。
この補題を利用すると,次の定理が証明できる。
素因数分解の一意性
任意のに対して,ある素数が存在して
と(積の順序を除いて)一意的に表すことができる。
【素因数分解可能性】
のときは,0個の素数の積で表せると考えればよいので,以下としよう。
素数の積で表せない1より大きい自然数が存在すると仮定する。最小性原理により,そのような最小のがとれる。は素数ではないので,を満たすが存在して,。の最小性により,は素数の積に分解できるから,もそれらの積で表すことができる。
【一意的】
2通りの素数の積で表せる自然数が存在すると仮定する。このような自然数をとする。が素数を用いて
と表せているとしよう。はで割り切れるので,をの約数としても一般性を失わない。これを繰り返してとなる。は素数であるから,()であることがわかる。もとの式より,ならば
となり不適。よって,である。