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

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

p | a b ⇒ p | a ∨ p | b {\displaystyle p\,|\,ab\Rightarrow p\,|\,a\vee p\,|\,b} (ただし p は素数)
算術の基本定理

また、整数の積の数が多くても、数学的帰納法で証明できる。
算術の基本定理

証明 1 素数の定義より、 ( a , p ) = 1 , p {\displaystyle (a,p)=1,p} である。
算術の基本定理

( a , p ) = p {\displaystyle (a,p)=p} ならば p | a {\displaystyle p\,|\,a} より定理は正しい。 ( a , p ) = 1 {\displaystyle (a,p)=1} ならば、定理 1.6 より、 p | b {\displaystyle p\,|\,b} より、定理は正しい。
算術の基本定理

以上より、定理は証明された。
算術の基本定理

証明 2 ( a , p ) = p {\displaystyle (a,p)=p} ならば p | a {\displaystyle p\,|\,a} より定理は正しい。 ( a , p ) = 1 {\displaystyle (a,p)=1} ならば、定理 1.9 より、 a x + p y = 1 ⋯ ( 1 ) {\displaystyle ax+py=1\cdots (1)} なる x , y {\displaystyle x,y} が存在する。
算術の基本定理

( 1 ) ⟺ a b x + b p y = b {\displaystyle (1)\iff abx+bpy=b} ここで仮定より p | a b ⟺ a b = p k {\displaystyle p\,|\,ab\iff ab=pk} なのでこれを代入して p ( k x + b y ) = b . {\displaystyle p(kx+by)=b.}
算術の基本定理

以上より定理は証明された。
算術の基本定理

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

さて、いよいよ本題である。
算術の基本定理

素因数分解は順序を考慮しなければただ一通りに表せる。
算術の基本定理

証明 仮にある数 N {\displaystyle N} について、2通り以上に素因数分解されたとする。そのうちの2つを以下のように表す。
算術の基本定理

N = p 1 p 2 p 3 ⋯ p n = q 1 q 2 q 3 ⋯ q m {\displaystyle N=p_{1}p_{2}p_{3}\cdots p_{n}=q_{1}q_{2}q_{3}\cdots q_{m}}
算術の基本定理

n ≦ m {\displaystyle n\leqq m} としても一般性を失わない。
算術の基本定理

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

p 2 , p 3 , p 4 , ⋯ p n {\displaystyle p_{2},p_{3},p_{4},\cdots p_{n}} についても同様にすることで、 p 1 = q 1 , p 2 = q 2 , p 3 = p 3 , ⋯ p n = q n ⋯ ( 1 ) . {\displaystyle p_{1}=q_{1},p_{2}=q_{2},p_{3}=p_{3},\cdots p_{n}=q_{n}\cdots (1).} 両辺を p 1 p 2 ⋯ p n = q 1 q 2 ⋯ q n {\displaystyle p_{1}p_{2}\cdots p_{n}=q_{1}q_{2}\cdots q_{n}} で割ることで、 1 = q n + 1 q n + 2 ⋯ q m {\displaystyle 1=q_{n+1}q_{n+2}\cdots q_{m}} となるが、これは不合理。よって n = m {\displaystyle n=m} となり、これと (1) から、定理は証明される。
ユークリッドの補題・算術の基本定理の重要性

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

( a , x ) = ( a , y ) = 1 ⟺ ( a , x y ) = 1 {\displaystyle (a,x)=(a,y)=1\iff (a,xy)=1}
ユークリッドの補題・算術の基本定理の重要性

証明 まずは ⇒ {\displaystyle \Rightarrow } を証明する。
ユークリッドの補題・算術の基本定理の重要性

算術の基本定理より、 a = p 0 p 1 ⋯ p l , x = q 0 q 1 ⋯ q m , y = r 0 r 1 ⋯ r n {\displaystyle 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 {\displaystyle a,x} が同じ素因数を持つならば、1 より大きい公約数を持ち、定理 1.5 より最大公約数はその素因数の倍数なので、 ( a , x ) > 1 {\displaystyle (a,x)>1} と、条件に反してしまう。したがって、 a , x {\displaystyle a,x} は同じ素因数を持たない。 a , y {\displaystyle a,y} も同様である。(1)
ユークリッドの補題・算術の基本定理の重要性

ここで、 a , x y {\displaystyle a,xy} もしこれらが互いに素でないとしよう。 ( a , x y ) = s 0 s 1 ⋯ s k {\displaystyle (a,xy)=s_{0}s_{1}\cdots s_{k}} と素因数分解したとき、 a = p 0 p 1 ⋯ p l , x y = q 0 q 1 ⋯ q m r 0 r 1 ⋯ r n {\displaystyle 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 {\displaystyle s_{0}} の倍数である。ユークリッドの補題より、この中のどれかに s 0 {\displaystyle s_{0}} と同様なものがあるはずである。それが q , r {\displaystyle q,r} どちらにあったとしても (1) と矛盾する。
ユークリッドの補題・算術の基本定理の重要性

よって、 ( a , x y ) = 1 {\displaystyle (a,xy)=1}
ユークリッドの補題・算術の基本定理の重要性

次に ⇐ {\displaystyle \Leftarrow } を証明する。
ユークリッドの補題・算術の基本定理の重要性

算術の基本定理より、 a = p 0 p 1 ⋯ p l , x = q 0 q 1 ⋯ q m , y = r 0 r 1 ⋯ r n {\displaystyle 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 y {\displaystyle a,xy} が同じ素因数を持つならば、 ( a , x y ) = 1 {\displaystyle (a,xy)=1} に反する。よって先ほどと同様に同じ素因数は持たない。(2)
ユークリッドの補題・算術の基本定理の重要性

さて、 ( a , x ) = s 0 s 1 ⋯ s k {\displaystyle (a,x)=s_{0}s_{1}\cdots s_{k}} と素因数分解したとき、 a , x {\displaystyle a,x} も s 0 {\displaystyle s_{0}} の倍数である。ユークリッドの補題より、 a , x {\displaystyle a,x} は素因数に s 0 {\displaystyle s_{0}} を持つ。そうすると、 ( a , x y ) {\displaystyle (a,xy)} は少なくとも s 0 {\displaystyle s_{0}} の倍数なので ( a , x y ) > 1 {\displaystyle (a,xy)>1} となり、矛盾する。
ユークリッドの補題・算術の基本定理の重要性

したがって、 ( a , x ) = 1 {\displaystyle (a,x)=1} となり、どうように、 ( a , y ) = 1 {\displaystyle (a,y)=1} である。
ユークリッドの補題・算術の基本定理の重要性

以上によって定理は証明された。
ユークリッドの補題・算術の基本定理の重要性

p e {\displaystyle p^{e}} は n {\displaystyle n} の約数だが p e + 1 {\displaystyle p^{e+1}} が n {\displaystyle n} の約数でないことを p e ∣∣ n {\displaystyle p^{e}\mid \mid n} とかくことにする。このとき p e ∣∣ n ⟺ p e ∣ n , gcd ( p , n / p e ) = 1 {\displaystyle p^{e}\mid \mid n\iff p^{e}\mid n,\gcd(p,n/p^{e})=1} が成り立つ。また e {\displaystyle e} は同じ素因数を全てべき乗の形にまとめて素因数分解したときにあらわれる p {\displaystyle p} の指数である。次の定理が成り立つ。
ユークリッドの補題・算術の基本定理の重要性

N {\displaystyle N} が n {\displaystyle n} 乗数 ⟺ p e ∣∣ N {\displaystyle \iff p^{e}\mid \mid N} のとき常に n ∣ e {\displaystyle n\mid e}
ユークリッドの補題・算術の基本定理の重要性

証明 N = M n {\displaystyle N=M^{n}} のとき M = p 1 β 1 ⋯ p m β m {\displaystyle M=p_{1}^{\beta _{1}}\cdots p_{m}^{\beta _{m}}} とおくと N = p 1 n β 1 ⋯ p m n β m {\displaystyle N=p_{1}^{n\beta _{1}}\cdots p_{m}^{n\beta _{m}}} である。よって p i e ∣∣ N {\displaystyle p_{i}^{e}\mid \mid N} のとき e = n β i {\displaystyle e=n\beta _{i}} である。
ユークリッドの補題・算術の基本定理の重要性

逆に p e ∣∣ N {\displaystyle p^{e}\mid \mid N} のとき常に n ∣ e {\displaystyle n\mid e} とし、 N = p 1 α 1 ⋯ p m α m {\displaystyle N=p_{1}^{\alpha _{1}}\cdots p_{m}^{\alpha _{m}}} と同じ素因数を全てべき乗の形にまとめて素因数分解する。すると、 α i = n β i {\displaystyle \alpha _{i}=n\beta _{i}} だから
ユークリッドの補題・算術の基本定理の重要性

z n = x y ∧ ( x , y ) = 1 ⟺ x = a n , y = b n {\displaystyle z^{n}=xy\wedge (x,y)=1\iff x=a^{n},y=b^{n}} となる a , b {\displaystyle a,b} が存在する。
ユークリッドの補題・算術の基本定理の重要性

証明1 ⇐ {\displaystyle \Leftarrow } は自明なので、 ⇒ {\displaystyle \Rightarrow } を証明する。
ユークリッドの補題・算術の基本定理の重要性

z = p 0 α 0 p 1 α 1 ⋯ p m α m {\displaystyle z=p_{0}^{\alpha _{0}}p_{1}^{\alpha _{1}}\cdots p_{m}^{\alpha _{m}}} と同じ素因数を全てべき乗の形にまとめて素因数分解する。すると、 z n = p 0 n α 0 p 1 n α 1 ⋯ p m n α m {\displaystyle z^{n}=p_{0}^{n\alpha _{0}}p_{1}^{n\alpha _{1}}\cdots p_{m}^{n\alpha _{m}}} となる。したがって、
ユークリッドの補題・算術の基本定理の重要性

x y = p 0 n α 0 p 1 n α 1 ⋯ p m n α m ⋯ ( 1 ) {\displaystyle xy=p_{0}^{n\alpha _{0}}p_{1}^{n\alpha _{1}}\cdots p_{m}^{n\alpha _{m}}\cdots (1)}
ユークリッドの補題・算術の基本定理の重要性

となる。仮に、 x , y {\displaystyle x,y} 同じ素因数を持つなら ( x , y ) > 1 {\displaystyle (x,y)>1} となるため、 x , y {\displaystyle x,y} は同じ素因数を持たない。(2)
ユークリッドの補題・算術の基本定理の重要性

また、素因数分解の一意性によって、 x , y {\displaystyle x,y} を素因数分解したものの積が (1) に等しく、(2) より、 x = r 0 n β 0 r 1 n β ⋯ r k n β k = ( r 0 β 0 r 1 β ⋯ r k β k ) n {\displaystyle 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 {\displaystyle y} も同様である。したがって、定理が証明される。
ユークリッドの補題・算術の基本定理の重要性

証明2 やはり ⇐ {\displaystyle \Leftarrow } は自明なので、 ⇒ {\displaystyle \Rightarrow } を証明する。 p e ∣∣ x {\displaystyle p^{e}\mid \mid x} とすると、 gcd ( x , y ) = 1 {\displaystyle \gcd(x,y)=1} より p e ∣∣ z n {\displaystyle p^{e}\mid \mid z^{n}} である。よって先の定理の ⇐ {\displaystyle \Leftarrow } より n ∣ e {\displaystyle n\mid e} である。したがって先の定理の ⇒ {\displaystyle \Rightarrow } より x {\displaystyle x} も n {\displaystyle n} 乗数。同様に y {\displaystyle y} も n {\displaystyle n} 乗数。
ユークリッドの補題・算術の基本定理の重要性

2 = m n {\displaystyle {\sqrt {2}}={\frac {m}{n}}} を満たす整数 m , n {\displaystyle m,n} は存在しない。
ユークリッドの補題・算術の基本定理の重要性

証明 両辺を2乗して、
ユークリッドの補題・算術の基本定理の重要性

2 = m 2 n 2 ⟺ 2 n 2 = m 2 ⋯ ( 1 ) {\displaystyle 2={\frac {m^{2}}{n^{2}}}\iff 2n^{2}=m^{2}\cdots (1)}
ユークリッドの補題・算術の基本定理の重要性

m = p 0 a 0 p 1 a 1 ⋯ p k a k , n = q 0 b 0 q 1 b 1 ⋯ q l b l {\displaystyle 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 ) ⟺ 2 q 0 2 b 0 q 1 2 b 1 ⋯ q l 2 b l = p 0 2 a 0 p 1 2 a 1 ⋯ p k 2 a k {\displaystyle (1)\iff 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 {\displaystyle m} には (1) より 2 {\displaystyle 2} を因数に含む。したがって m 2 {\displaystyle m^{2}} の素因数分解した形に置いて、2 の指数部分は偶数である。
ユークリッドの補題・算術の基本定理の重要性

また、 n 2 {\displaystyle n^{2}} の 2 の指数部分は偶数、よって 2 n 2 {\displaystyle 2n^{2}} の 2 の指数部分は奇数。しかし、これは素因数分解の一意性に反する。
ユークリッドの補題・算術の基本定理の重要性

よって、 2 {\displaystyle {\sqrt {2}}} は無理数。
ユークリッドの補題・算術の基本定理の重要性

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