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

算術の基本定理

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

定理 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)⟺abx+bpy=b$ ここで仮定より $p|ab⟺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⟺(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⟺p^e\mid n,\gcd (p,n/p^e)=1$ が成り立つ。また $e$ は同じ素因数を全てべき乗の形にまとめて素因数分解したときにあらわれる $p$ の指数である。次の定理が成り立つ。

定理 1.15

$N$ が $n$乗数 $⟺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⟺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$乗数。

√2の無理性の証明

$\sqrt{2}=\frac{m}{n}$ を満たす整数 $m,n$ は存在しない。

証明
両辺を2乗して、

$2=\frac{m^2}{n^2}⟺2n^2=m^2\cdots (1)$

$m=p_0^{a_0}{p}_1^{a_1}\cdots p_k^{a_k},n=q_0^{b_0}{q}_1^{b_1}\cdots q_l^{b_l}$ と素因数分解すれば、

$(1)⟺2q_0^{2b_0}{q}_1^{2b_1}\cdots q_l^{2b_l}=p_0^{2a_0}{p}_1^{2a_1}\cdots p_k^{2a_k}$

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

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

よって、$\sqrt{2}$ は無理数。

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