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

算術の基本定理

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

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

$p\,|\,ab\Rightarrow p\,|\,a\vee p\,|\,b$ (ただし p は素数)

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

証明 1
素数の定義より、 $(a,p)=1,p$ である。

$(a,p)=p$ ならば $p\,|\,a$ より定理は正しい。
$(a,p)=1$ ならば、定理 1.6 より、 $p\,|\,b$ より、定理は正しい。

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

証明 2
$(a,p)=p$ ならば $p\,|\,a$ より定理は正しい。
$(a,p)=1$ ならば、定理 1.9 より、 $ax+py=1\cdots (1)$ なる $x,y$ が存在する。

$(1)\iff abx+bpy=b$ ここで仮定より $p\,|\,ab\iff ab=pk$ なのでこれを代入して $p(kx+by)=b.$

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

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

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

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

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

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

$N=p_{1}p_{2}p_{3}\cdots p_{n}=q_{1}q_{2}q_{3}\cdots q_{m}$

$n\leqq m$ としても一般性を失わない。

このとき、 $p_{1}\,|\,q_{1}q_{2}q_{3}\cdots q_{m}$ より、定理 1.11 から、 $p_{1}$ は左辺のどれかを割り切る。それを適当に文字を割り当てて、 $q_{1}$ とすると、どちらも素数であるから $p_{1}=q_{1}$

$p_{2},p_{3},p_{4},\cdots p_{n}$ についても同様にすることで、 $p_{1}=q_{1},p_{2}=q_{2},p_{3}=p_{3},\cdots p_{n}=q_{n}\cdots (1).$ 両辺を $p_{1}p_{2}\cdots p_{n}=q_{1}q_{2}\cdots q_{n}$ で割ることで、 $1=q_{n+1}q_{n+2}\cdots q_{m}$ となるが、これは不合理。よって $n=m$ となり、これと (1) から、定理は証明される。

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

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

定理 1.14

$(a,x)=(a,y)=1\iff (a,xy)=1$

証明
まずは $\Rightarrow$ を証明する。

算術の基本定理より、 $a=p_{0}p_{1}\cdots p_{l},x=q_{0}q_{1}\cdots q_{m},y=r_{0}r_{1}\cdots r_{n}$ と素因数分解する。

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

ここで、 $a,xy$ もしこれらが互いに素でないとしよう。 $(a,xy)=s_{0}s_{1}\cdots s_{k}$ と素因数分解したとき、 $a=p_{0}p_{1}\cdots p_{l},xy=q_{0}q_{1}\cdots q_{m}r_{0}r_{1}\cdots r_{n}$ は $s_{0}$ の倍数である。ユークリッドの補題より、この中のどれかに $s_{0}$ と同様なものがあるはずである。それが $q,r$ どちらにあったとしても (1) と矛盾する。

よって、 $(a,xy)=1$

次に $\Leftarrow$ を証明する。

算術の基本定理より、 $a=p_{0}p_{1}\cdots p_{l},x=q_{0}q_{1}\cdots q_{m},y=r_{0}r_{1}\cdots r_{n}$ と素因数分解する。

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

さて、 $(a,x)=s_{0}s_{1}\cdots s_{k}$ と素因数分解したとき、 $a,x$ も $s_{0}$ の倍数である。ユークリッドの補題より、 $a,x$ は素因数に $s_{0}$ を持つ。そうすると、 $(a,xy)$ は少なくとも $s_{0}$ の倍数なので $(a,xy)>1$ となり、矛盾する。

したがって、 $(a,x)=1$ となり、どうように、 $(a,y)=1$ である。

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

$p^{e}$ は $n$ の約数だが $p^{e+1}$ が $n$ の約数でないことを $p^{e}\mid \mid n$ とかくことにする。このとき $p^{e}\mid \mid n\iff p^{e}\mid n,\gcd(p,n/p^{e})=1$ が成り立つ。また $e$ は同じ素因数を全てべき乗の形にまとめて素因数分解したときにあらわれる $p$ の指数である。次の定理が成り立つ。

定理 1.15

$N$ が $n$ 乗数 $\iff p^{e}\mid \mid N$ のとき常に $n\mid e$

証明
$N=M^{n}$ のとき $M=p_{1}^{\beta _{1}}\cdots p_{m}^{\beta _{m}}$ とおくと $N=p_{1}^{n\beta _{1}}\cdots p_{m}^{n\beta _{m}}$ である。よって $p_{i}^{e}\mid \mid N$ のとき $e=n\beta _{i}$ である。

逆に $p^{e}\mid \mid N$ のとき常に $n\mid e$ とし、 $N=p_{1}^{\alpha _{1}}\cdots p_{m}^{\alpha _{m}}$ と同じ素因数を全てべき乗の形にまとめて素因数分解する。すると、 $\alpha _{i}=n\beta _{i}$ だから

N=p_{1}^{n\beta _{1}}\cdots p_{m}^{n\beta _{m}}=(p_{1}^{\beta _{1}}\cdots p_{m}^{\beta _{m}})^{n}

定理 1.15'

$z^{n}=xy\wedge (x,y)=1\iff x=a^{n},y=b^{n}$ となる $a,b$ が存在する。

証明1
$\Leftarrow$ は自明なので、 $\Rightarrow$ を証明する。

$z=p_{0}^{\alpha _{0}}p_{1}^{\alpha _{1}}\cdots p_{m}^{\alpha _{m}}$ と同じ素因数を全てべき乗の形にまとめて素因数分解する。すると、 $z^{n}=p_{0}^{n\alpha _{0}}p_{1}^{n\alpha _{1}}\cdots p_{m}^{n\alpha _{m}}$ となる。したがって、

$xy=p_{0}^{n\alpha _{0}}p_{1}^{n\alpha _{1}}\cdots p_{m}^{n\alpha _{m}}\cdots (1)$

となる。仮に、 $x,y$ 同じ素因数を持つなら $(x,y)>1$ となるため、 $x,y$ は同じ素因数を持たない。(2)

また、素因数分解の一意性によって、 $x,y$ を素因数分解したものの積が (1) に等しく、(2) より、 $x=r_{0}^{n\beta _{0}}r_{1}^{n\beta }\cdots r_{k}^{n\beta _{k}}=(r_{0}^{\beta _{0}}r_{1}^{\beta }\cdots r_{k}^{\beta _{k}})^{n}$ と表せる。 $y$ も同様である。したがって、定理が証明される。

証明2
やはり $\Leftarrow$ は自明なので、 $\Rightarrow$ を証明する。 $p^{e}\mid \mid x$ とすると、 $\gcd(x,y)=1$ より $p^{e}\mid \mid z^{n}$ である。よって先の定理の $\Leftarrow$ より $n\mid e$ である。したがって先の定理の $\Rightarrow$ より $x$ も $n$ 乗数。同様に $y$ も $n$ 乗数。