以下の定理は基本定理と呼ばれるにふさわしい整数論の最も重要な定理の一つである。
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.
以上より定理は証明された。
問
整数の積がいくつでも定理が成り立つことを数学的帰納法で示せ。
さて、いよいよ本題である。
素因数分解は順序を考慮しなければただ一通りに表せる。
証明
仮にある数 N について、2通り以上に素因数分解されたとする。そのうちの2つを以下のように表す。
N = p_1p_2p_3 \cdots p_n = q_1q_2q_3 \cdots q_m
n \leqq m としても一般性を失わない。
このとき、p_1 \, | \, q_1q_2q_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_1p_2 \cdots p_n = q_1q_2 \cdots q_n で割ることで、1 = q_{n+1}q_{n+2} \cdots q_m となるが、これは不合理。よって n = m となり、これと (1) から、定理は証明される。
ユークリッドの補題・算術の基本定理から導ける定理をいくつか示す。
(a, x) = (a, y) = 1 \iff (a, xy) = 1
証明
まずは \Rightarrow を証明する。
算術の基本定理より、a = p_0p_1 \cdots p_l, x = q_0q_1 \cdots q_m, y = r_0r_1 \cdots r_n と素因数分解する。
このとき、a, x が同じ素因数を持つならば、1 より大きい公約数を持ち、定理 1.5 より最大公約数はその素因数の倍数なので、 (a, x) > 1 と、条件に反してしまう。したがって、a, x は同じ素因数を持たない。a, y も同様である。(1)
ここで、a, xy もしこれらが互いに素でないとしよう。(a, xy) = s_0s_1 \cdots s_k と素因数分解したとき、a = p_0p_1 \cdots p_l, xy =  q_0q_1 \cdots q_mr_0r_1 \cdots r_n は s_0 の倍数である。ユークリッドの補題より、この中のどれかに s_0 と同様なものがあるはずである。それが q, r どちらにあったとしても (1) と矛盾する。
よって、(a, xy) = 1
次に \Leftarrow を証明する。
算術の基本定理より、a = p_0p_1 \cdots p_l, x = q_0q_1 \cdots q_m, y = r_0r_1 \cdots r_n と素因数分解する。
a, xy が同じ素因数を持つならば、(a, xy) = 1 に反する。よって先ほどと同様に同じ素因数は持たない。(2)
さて、(a, x) = s_0s_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 の指数である。次の定理が成り立つ。
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 だから
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乗数。
\sqrt{2} = \frac{m}{n} を満たす整数 m, n は存在しない。
証明
両辺を2乗して、
2 = \frac{m^2}{n^2} \iff 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) \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 には (1) より 2 を因数に含む。したがって m^2 の素因数分解した形に置いて、2 の指数部分は偶数である。
また、n^2 の 2 の指数部分は偶数、よって 2n^2 の 2 の指数部分は奇数。しかし、これは素因数分解の一意性に反する。
よって、\sqrt{2} は無理数。
同様にして、\sqrt{d} は d が平方因子を持たないならば無理数であることが成り立つ。