初等整数論/算術の基本定理

算術の基本定理編集

以下の定理は基本定理と呼ばれるにふさわしい整数論の最も重要な定理の一つである。


定理 1.12 (w:ユークリッドの補題)編集

  (ただし p は素数)

また、整数の積の数が多くても、数学的帰納法で証明できる。

証明 1
素数の定義より、  である。

  ならば   より定理は正しい。
  ならば、定理 1.6 より、  より、定理は正しい。

以上より、定理は証明された。

証明 2
  ならば   より定理は正しい。
  ならば、定理 1.9 より、  なる   が存在する。

  ここで仮定より   なのでこれを代入して  

以上より定理は証明された。


整数の積がいくつでも定理が成り立つことを数学的帰納法で示せ。


さて、いよいよ本題である。

定理 1.13 (算術の基本定理, 素因数分解の一意性)編集

素因数分解は順序を考慮しなければただ一通りに表せる。

証明
仮にある数   について、2通り以上に素因数分解されたとする。そのうちの2つを以下のように表す。

 

  としても一般性を失わない。

このとき、  より、定理 1.11 から、  は左辺のどれかを割り切る。それを適当に文字を割り当てて、  とすると、どちらも素数であるから  

  についても同様にすることで、  両辺を   で割ることで、  となるが、これは不合理。よって   となり、これと (1) から、定理は証明される。

ユークリッドの補題・算術の基本定理の重要性編集

ユークリッドの補題・算術の基本定理から導ける定理をいくつか示す。

定理 1.14編集

 

証明
まずは   を証明する。

算術の基本定理より、  と素因数分解する。

このとき、  が同じ素因数を持つならば、1 より大きい公約数を持ち、定理 1.5 より最大公約数はその素因数の倍数なので、   と、条件に反してしまう。したがって、  は同じ素因数を持たない。  も同様である。(1)

ここで、  もしこれらが互いに素でないとしよう。  と素因数分解したとき、   の倍数である。ユークリッドの補題より、この中のどれかに   と同様なものがあるはずである。それが   どちらにあったとしても (1) と矛盾する。

よって、 

次に   を証明する。

算術の基本定理より、  と素因数分解する。

  が同じ素因数を持つならば、  に反する。よって先ほどと同様に同じ素因数は持たない。(2)

さて、  と素因数分解したとき、   の倍数である。ユークリッドの補題より、  は素因数に   を持つ。そうすると、  は少なくとも   の倍数なので   となり、矛盾する。

したがって、  となり、どうように、  である。

以上によって定理は証明された。


   の約数だが    の約数でないことを   とかくことにする。このとき   が成り立つ。また   は同じ素因数を全てべき乗の形にまとめて素因数分解したときにあらわれる   の指数である。次の定理が成り立つ。

定理 1.15編集

  乗数   のとき常に  

証明
  のとき   とおくと   である。よって   のとき   である。

逆に   のとき常に   とし、  と同じ素因数を全てべき乗の形にまとめて素因数分解する。すると、  だから

 
定理 1.15'編集

  となる   が存在する。

証明1
  は自明なので、  を証明する。

  と同じ素因数を全てべき乗の形にまとめて素因数分解する。すると、  となる。したがって、

 

となる。仮に、  同じ素因数を持つなら   となるため、  は同じ素因数を持たない。(2)

また、素因数分解の一意性によって、  を素因数分解したものの積が (1) に等しく、(2) より、  と表せる。  も同様である。したがって、定理が証明される。

証明2
やはり   は自明なので、  を証明する。  とすると、  より   である。よって先の定理の   より   である。したがって先の定理の  より   乗数。同様に   乗数。

√2の無理性の証明編集

  を満たす整数   は存在しない。

証明
両辺を2乗して、

 

  と素因数分解すれば、

 

ここで、  には (1) より   を因数に含む。したがって   の素因数分解した形に置いて、2 の指数部分は偶数である。

また、  の 2 の指数部分は偶数、よって   の 2 の指数部分は奇数。しかし、これは素因数分解の一意性に反する。

よって、  は無理数。

同様にして、   が平方因子を持たないならば無理数であることが成り立つ。