§A4.2素数と素因数分解

証明.$p\nmid a$とする。$p$の正の約数は$1,p$だけであるので、$\gcd(p,a)=1$である。§A4.3 補題 1.1により、$px+ay=1$を満たす整数$x,y$が存在する。両辺に$b$を掛けると$pbx+aby=b$となる。$p\mid ab$であるので左辺の各項は$p$で割り切れ、$p\mid b$が成り立つ。▨

証明.$n\ge 2$とし、$n$より小さい$2$以上の整数はすべて素数の積として表されると仮定する。$n$が素数ならば、$n$自身が求める表示である。$n$が合成数ならば、$n=ab$を満たす整数$a,b$を$2\le a,b<n$となるように取ることができる。帰納法の仮定により$a,b$はともに素数の積として表されるので、$n$も同じ形で表される。$n=2$の場合は素数の場合に含まれるので、帰納法によって存在が従う。

$n=p_1\cdots p_r=q_1\cdots q_s$を二つの素数の積による表示とし、$r,s\ge1$とする。補題 2.1を繰り返し用いると、$p_1$はいずれかの$q_j$を割り切る。$q_j$は素数であり$p_1>1$であるので、$p_1=q_j$である。因子の順序を入れ替え、両辺からこの共通因子を一つずつ除く。残った積にも同じ議論を繰り返すことができる。一方の因子だけが先に尽きると、$1$が素数の空でない積に等しくなるが、そのような積は$2$以上である。したがって両辺の因子は同時に尽き、二つの表示は順序を除いて一致する。▨

証明.$d$が$N$の正の約数なら、正の整数$m$を用いて$N=dm$と書くことができる。定理 2.2により、$d$に現れる素数は$p_i$のいずれかであり、その指数は$e_i$を超えない。逆に$0\le f_i\le e_i$なら、$p_1^{e_1-f_1}\cdots p_k^{e_k-f_k}$を掛けると$N$になるので、$p_1^{f_1}\cdots p_k^{f_k}$は$N$の約数である。指数の異なる組から同じ約数が得られることは、素因数分解の一意性によって起こらない。各$f_i$には$e_i+1$通りの選び方があるので、約数の個数は選び方の個数の積である。総和の式の積を分配法則で展開すると、各因子から$p_i^{f_i}$を一つずつ選んだ積が一度ずつ現れる。各項は正の約数と一対一に対応するので、この展開の値が約数の総和である。▨

証明.$A,B$の一方が$1$なら、最大公約数は$1$、最小公倍数は他方の数であり、表示された式が成り立つ。$A,B\ge2$とする。命題 4.1により、公約数に現れる$p_i$の指数は$a_i,b_i$の両方以下である。したがって、すべての正の公約数は表示された$d$を割り切り、$d$自身も公約数である。よって$d$は最大公約数である。定理 2.2により、正の公倍数には各$p_i$が少なくとも$\max(a_i,b_i)$個現れる。したがって、すべての正の公倍数は表示された$L$の倍数であり、$L$自身も公倍数なので最小である。$\min(a_i,b_i)+\max(a_i,b_i)=a_i+b_i$であるので、$dL=AB$が成り立つ。▨

証明. 素数が有限個しかないと仮定し、すべての素数を$p_1,p_2,\ldots,p_n$とする。$2$は素数であるので$n\ge1$である。$N=p_1p_2\cdots p_n+1$とおく。$N$は各$p_i$で割ると$1$余るので、どの$p_i$によっても割り切れない。一方、$N\ge2$であるので、定理 2.2により$N$の素因子$q$が存在する。$q$は素数であるのに、列挙したどの$p_i$とも異なる。これは$p_1,\ldots,p_n$がすべての素数であるという仮定に矛盾する。したがって素数は無限に存在する。▨