$1$ より大きい整数 $a$ は, 合成数であれば, 絶対値のより小さい正の整数 $b,$ $c$ の積 $a = bc$ に分解される. $b,$ $c$ は, 合成数であれば, 絶対値のより小さい正の整数の積に分解される. この操作を繰り返せば, $a$ は高々 $a$ 個の正の整数 $a_1,$ $\cdots,$ $a_l$ の積に分解され, どれも絶対値のより小さい整数の積に分解できなくなる. このとき $a_1,$ $\cdots,$ $a_l$ は素数であるから, $a$ は素数の積 \[ a = a_1\cdots a_l\] に分解できる.

　$p_1,$ $\cdots,$ $p_r$ を素数として, \[ q = p_1\cdots p_r+1\,(> 1)\] とおく.

(i)

$q$ が素数であるとき. $q$ は $p_1,$ $\cdots,$ $p_r$ と異なる素数の例を与える.

(ii)

$q$ が合成数であるとき. $q$ は, $p_1,$ $\cdots,$ $p_r$ と互いに素であるから, $p_1,$ $\cdots,$ $p_r$ と異なる素因数をもつ.

任意の素数の有限集合から新たな素数が得られるので, 素数は無限に存在する.

　$p$ を素数として, \[ q = p!+1\,(> 1)\] とおく.

(i)

$q$ が素数であるとき. $q$ は $p$ より大きい素数の例を与える.

(ii)

$q$ が合成数であるとき. $q$ は, $1,$ $\cdots,$ $p$ と互いに素であるから, $p$ より大きい素因数をもつ.

与えられた素数より大きい素数が存在するので, 素数は無限に存在する.

　こちらを参照.

　こちらを参照.

　$a$ を $1$ より大きい整数として, \[ a_1 = a, \quad a_{n+1} = a_n(a_n+1)\] で数列 $\{ a_n\}$ を定める. このとき, $a_1$ は少なくとも $1$ つの素因数をもつ. また, $a_n+1$ は, $a_n$ と互いに素であるから $a_n$ と異なる素因数をもち, $a_{n+1}$ は $a_n$ より多くの素因数をもつ. $\{ a_n\}$ において各項の素因数の個数は単調に増加するので, 素数は無限に存在する.

　合成数 $a$ が $[\sqrt a]$ 以下の素因数をもつことを示せばよい. 合成数 $a$ は, $1 < b \leqq c < a$ なる整数 $b,$ $c$ を用いて, $a = bc$ と表される. ここで, $p$ を $b$ の素因数とすると, \[ p^2 \leqq b^2 \leqq b\cdot c = a\] と $p > 0$ から $p \leqq \sqrt a$ となり, $p$ が整数であることから $p \leqq [\sqrt a]$ が得られる.

(i)

$s_1 = 2$ は素数である.

(ii)

$s_{n+1} = s_1\cdots s_n+1$ は $s_1,$ $\cdots,$ $s_n$ のいずれとも互いに素である. $s_{n+1} \geqq s_1+1 > 1$ であるから, $s_{n+1}$ は $s_1,$ $\cdots,$ $s_n$ の素因数と異なる素因数をもつ.

数列 $\{ s_n\}$ の各項は互いに異なる素因数をもつので, 素数は無限に存在する.

(i)

$F_1 = 3$ は素数である.

(ii)

$F_{n+1} = F_1\cdots F_n+2$ と $F_1,$ $\cdots,$ $F_n$ との最大公約数はいずれも $2$ の約数である. 定義から $\{ F_n\}$ の各項は奇数であるので, $F_{n+1}$ は $F_1,$ $\cdots,$ $F_n$ のいずれとも互いに素である. $F_{n+1} \geqq F_1+2 > 1$ であるから, $F_{n+1}$ は $F_1,$ $\cdots,$ $F_n$ の素因数と異なる素因数をもつ.

数列 $\{ F_n\}$ の各項は互いに異なる素因数をもつので, 素数は無限に存在する.

　奇数の素数 $p$ がある整数 $a,$ $b$ を用いて \[ p = a^2+b^2\] と表されるとする. 偶数 $2q$ ($q$: 整数) の平方 \[ (2q)^2 = 4q^2\] を $4$ で割った余りは $0,$ 奇数 $2q+1$ ($q$: 整数) の平方 \[ (2q+1)^2 = 4(q^2+q)+1\] を $4$ で割った余りは $1$ であるから, $p$ を $4$ で割った余りは $0,$ $1,$ $2$ のいずれかである. $p$ を $4$ で割った余りが $0,$ $2$ の場合は $p$ が奇数であることに反するから, $p$ を $4$ で割った余りは $1$ である.

(1)

整数 \[ b = 4p_1{}^2\cdots p_r{}^2+1\] は $2,$ $p_1,$ $\cdots,$ $p_r$ のいずれとも互いに素であるから, $b$ の素因数 $p$ は $2,$ $p_1,$ $\cdots,$ $p_r$ と異なる. 仮定から $4$ で割った余りが $1$ である素数は $p_1,$ $\cdots,$ $p_r$ のみであるので, $p$ は非負整数 $n$ を用いて $p = 4n+3$ の形に表される.

(2)

$a^2+1 \equiv 0 \pmod p$ であるから, \[ a^2 \equiv -1 \pmod p\] が成り立つ. 両辺を $2n+1$ 乗すると, \[ a^{p-1} = a^{4n+2} = (a^2)^{2n+1} \equiv (-1)^{2n+1} = -1 \pmod p\] が得られる. これは「フェルマーの小定理」の主張 \[ a^{p-1} \equiv 1 \pmod p\] に反する.
　ゆえに, $4$ で割った余りが $1$ である素数は無限に存在する.

　$1$ より大きい整数 $a$ に対して示せば十分である. $a$ が素数 $a_1,$ $\cdots,$ $a_l$ の積 \[ a = a_1\cdots a_l \quad \cdots [1]\] に分解できることは, 上で示した通りである. 一意性について示すため, $a$ が素数 $b_1,$ $\cdots,$ $b_m$ の積 \[ a = b_1\cdots b_m\] にも分解できたとする. $l,$ $m > 1$ のとき, \[ a_1\cdots a_l = b_1\cdots b_m\] が成り立ち, 右辺は素数 $a_1$ で割り切れるから, 下記の補題によりある $b_k$ $(1 \leqq k \leqq m)$ は $a_1$ で割り切れる. よって, 必要に応じて番号をつけ替えると, $a_1 = b_1$ となる. このとき, \[ a_2\cdots a_l = b_2\cdots b_m\] となるから, 必要に応じて番号をつけ替えながら同様の操作を続けると, \[ a_1 = b_1, \quad \cdots, \quad a_l = b_l, \quad l = m\] となる. ゆえに, 表示 $[1]$ は, 順序の違いを除いてただ $1$ 通りである.

　$ab$ が $p$ の倍数であり, $a$ が $p$ の倍数でないとすると, $a,$ $p$ は互いに素であるから, $ax+py = 1$ は整数解 $x,$ $y$ をもつ. よって, $b = abx+bpy$ は $p$ の倍数である.

(1)

素因数分解の一意性により,

$a = p^{\mathrm{ord}_p(a)}a',$　$b = p^{\mathrm{ord}_p(b)}b'$　($a',$ $b'$: $p$ と互いに素な整数)

と表せる. このとき,

$ab = p^{\mathrm{ord}_p(a)+\mathrm{ord}_p(b)}a'b'$　($a'b'$: $p$ と互いに素な整数)

となるから, \[\mathrm{ord}_p(ab) = \mathrm{ord}_p(a)+\mathrm{ord}_p(b) \quad \cdots [1]\] が成り立つ.

(2)

$a,$ $b$ の最大公約数を $g$ として, $a = a_0g,$ $b = b_0g$ ($a_0,$ $b_0$: $0$ でない整数) とおく. このとき, \[\begin{aligned} \mathrm{ord}_p(x) &= \mathrm{ord}_p(a)-\mathrm{ord}_p(b) \\ &= \mathrm{ord}_p(a_0g)-\mathrm{ord}_p(b_0g) \\ &= \mathrm{ord}_p(a_0)+\mathrm{ord}_p(g)-\mathrm{ord}_p(b_0)-\mathrm{ord}_p(g) \quad (\because [1]) \\ &= \mathrm{ord}_p(a_0)-\mathrm{ord}_p(b_0) \end{aligned}\] が成り立つから, この値は $a,$ $b$ のとり方によらず一定である.

(3)

$x = \dfrac{a}{b},$ $y = \dfrac{c}{d}$ ($a,$ $b,$ $c,$ $d$: $0$ でない整数) とする. このとき, $xy = \dfrac{ac}{bd}$ であるから, \[\begin{aligned} \mathrm{ord}_p(xy) &= \mathrm{ord}_p(ac)-\mathrm{ord}_p(bd) \\ &= \mathrm{ord}_p(a)+\mathrm{ord}_p(c)-\mathrm{ord}_p(b)-\mathrm{ord}_p(d) \quad (\because [1]) \\ &= \mathrm{ord}_p(a)-\mathrm{ord}_p(b)+\mathrm{ord}_p(c)-\mathrm{ord}_p(d) \\ &= \mathrm{ord}_p(x)+\mathrm{ord}_p(y) \quad \cdots [2] \end{aligned}\] が成り立つ. さらに, \[\mathrm{ord}_p(x) = \mathrm{ord}_p\left(\frac{x}{y}\cdot y\right) = \mathrm{ord}_p\left(\frac{x}{y}\right)+\mathrm{ord}_p(y)\] であるから, \[\mathrm{ord}_p\left(\frac{x}{y}\right) = \mathrm{ord}_p(x)-\mathrm{ord}_p(y) \quad \cdots [2]'\] が成り立つ.

(4A)

二項係数の定義と $[2],$ $[2]',$ $[*]$ により, \[\begin{aligned} &m = \mathrm{ord}_p\left(\frac{(2n)!}{n!n!}\right) = \mathrm{ord}_p((2n)!)-2\,\mathrm{ord}_p(n!) \\ &= \sum_{k = 1}^\infty\left[\frac{2n}{p^k}\right] -2\sum_{k = 1}^\infty\left[\frac{n}{p^k}\right] = \sum_{k = 1}^\infty\left(\left[\frac{2n}{p^k}\right] -2\left[\frac{n}{p^k}\right]\right) \quad \cdots [3] \end{aligned}\] が成り立つ. $x = \dfrac{n}{p^k}$ について, $2x-1 < [2x] \leqq 2x,$ $-2x \leqq -2[x] < -2(x-1)$ であるから, 辺々を加えると,

$-1 < [2x]-2[x] < 2$　よって　$[2x]-2[x] = 0,\ 1$

が得られる. ここで, $[2x]-2[x] = 1$ のとき, $0 \leqq 2[x] = [2x]-1 \leqq 2x-1$ となり, $1 \leqq 2x$ つまり $p^k \leqq 2n$ が成り立つ. よって, $p^k \leqq 2n$ なる正の整数 $k$ の最大値を $M$ とおくと, $[3]$ から

$m \leqq (p^k \leqq 2n$ なる正の整数 $k$ の個数$)\times 1 = M$

となり, $p^m \leqq p^M \leqq 2n$ したがって $p^m \leqq 2n$ が成り立つ.

(4B)

$dx^2$ が整数であるとする. このとき, すべての素数 $p$ に対して, $d$ が $1$ 以外の平方数で割り切れないことから $\mathrm{ord}_p(d) \leqq 1$ であることに注意すると \[\begin{aligned} \mathrm{ord}_p(dx^2) &\geqq 0 \\ \mathrm{ord}_p(d)+2\,\mathrm{ord}_p(x) &\geqq 0 \quad (\because [2]) \\ 2\,\mathrm{ord}_p(x) &\geqq -\mathrm{ord}_p(d) \geqq -1 \end{aligned}\] が得られ, $2\,\mathrm{ord}_p(x)$ は偶数であるから

$2\,\mathrm{ord}_p(x) \geqq 0$　よって　$\mathrm{ord}_p(x) \geqq 0$

が成り立つ. よって, $x$ は整数である.

　$e = \mathrm{ord}_p(a),$ $f = \mathrm{ord}_p(b)$ とおく. 素因数分解の一意性により, と表せる.

(i)

$e < f$ のとき. \[ a+b = p^e(a'+p^{f-e}b')\] であり, $a'+p^{f-e}b'$ は $p$ で割り切れないから, $\mathrm{ord}_p(a+b) = e$ が成り立つ.

(ii)

$e > f$ のとき. \[ a+b = p^f(p^{e-f}a'+b')\] であり, $p^{e-f}a'+b'$ は $p$ で割り切れないから, $\mathrm{ord}_p(a+b) = f$ が成り立つ.

(iii)

$e = f$ のとき. \[ a+b = p^e(a'+b')\] であるから, $\mathrm{ord}_p(a+b) \geqq e$ が成り立つ.

(i)～(iii) から, \[\mathrm{ord}_p(a+b) \geqq \min\{ e,f\} = \min\{\mathrm{ord}_p(a),\mathrm{ord}_p(b)\}\] が成り立つ.

　正の整数 $m,$ $n$ が互いに素であるとする.

(i)

$m$ または $n$ が $1$ であるとき. $\mu (1) = 1$ により, $\mu (m) = 1$ かつ $mn = n,$ または $\mu (n) = 1$ かつ $mn = m$ であるから, $\mu (mn) = \mu (m)\mu (n)$ が成り立つ.

(ii)

$m$ または $n$ が $1$ 以外の平方数で割り切れるとき. $mn$ は平方数で割り切れ, $\mu (m) = 0$ または $\mu (n) = 0$ であるから, \[\mu (mn) = 0 = \mu(m)\mu (n)\] が成り立つ.

(iii)

$m,$ $n$ が $1$ より大きく, ともに $1$ 以外の平方数で割り切れないとき. $m$ が相異なる $r$ 個の素数の積に分解され, $n$ が相異なる $s$ 個の素数の積に分解されるとする. このとき, 仮定により $mn$ は相異なる $r+s$ 個の素数の積に分解されるから, \[\mu (mn) = (-1)^{r+s} = (-1)^r(-1)^s = \mu (m)\mu (n)\] が成り立つ.

(i)～(iii) から, 互いに素な正の整数 $m,$ $n$ に対して $\mu (mn) = \mu (m)\mu (n)$ が成り立つ.

(1)

$a$ が

$a = p_1{}^{e_1}\cdots p_r{}^{e_r}$ 　($p_1,$ $\cdots,$ $p_r$: 相異なる素数, $e_1,$ $\cdots,$ $e_r$: 正の整数)

と素因数分解されるとする. このとき, \[\mathrm{rad}\,(\mathrm{rad}\,(a)) = \mathrm{rad}\,(p_1\cdots p_r) = p_1\cdots p_r = \mathrm{rad}\,(a)\] が成り立つ. また, \[ a^n = p_1{}^{e_1n}\cdots p_r{}^{e_rn}\] であるから, \[\mathrm{rad}\,(a^n) = p_1\cdots p_r = \mathrm{rad}\,(a) \quad \cdots [1]\] が成り立つ.

(2)

$a$ が (1) のように, $b$ が

$b = q_1{}^{f_1}\cdots q_s{}^{f_s}$ 　($q_1,$ $\cdots,$ $q_s$: 相異なる素数, $f_1,$ $\cdots,$ $f_s$: 正の整数)

と素因数分解されるとする. $a,$ $b$ が互いに素なとき,

$\mathrm{rad}\,(a) = p_1\cdots p_r,$ $\mathrm{rad}\,(b) = q_1\cdots q_s$ は互いに素　$\cdots [2]$

であり,

$ab = p_1{}^{e_1}\cdots p_r{}^{e_r}q_1{}^{f_1}\cdots q_s{}^{f_s}$ 　($p_1,$ $\cdots,$ $p_r,$ $q_1,$ $\cdots,$ $q_s$: 相異なる素数)

であるから \[\mathrm{rad}\,(ab) = p_1\cdots p_rq_1\cdots q_s = \mathrm{rad}\,(a)\,\mathrm{rad}\,(b) \quad \cdots [3]\] が成り立つ.

(3)

$a,$ $b$ を

$a = a'g,$ $b = b'g$　($a',$ $b',$ $g$: 互いに素な正の整数)

と表す ($g$ は $a,$ $b$ の最大公約数). このとき, \[ ab = a'b'g^2, \quad [a,b] = a'b'g\] と (1), (2) により \[\begin{aligned} \mathrm{rad}\,(ab) &= \mathrm{rad}\,(a'b'g^2) \\ &= \mathrm{rad}\,(a')\,\mathrm{rad}\,(b')\,\mathrm{rad}\,(g^2) \quad (\because [3]) \\ &= \mathrm{rad}\,(a')\,\mathrm{rad}\,(b')\,\mathrm{rad}\,(g) \quad (\because [1]), \\ \mathrm{rad}\,([a,b]) &= \mathrm{rad}\,(a'b'g) \\ &= \mathrm{rad}\,(a')\,\mathrm{rad}\,(b')\,\mathrm{rad}\,(g) \quad (\because [3]), \\ [\mathrm{rad}\,(a),\mathrm{rad}\,(b)] &= [\mathrm{rad}\,(a'g),\mathrm{rad}\,(b'g)] \\ &= [\mathrm{rad}\,(a')\,\mathrm{rad}\,(g),\mathrm{rad}\,(b')\,\mathrm{rad}\,(g)] \quad (\because [3]) \\ &= \mathrm{rad}\,(a')\,\mathrm{rad}\,(b')\,\mathrm{rad}\,(g) \quad (\because [2]) \end{aligned}\] であるから, \[\mathrm{rad}\,(ab) = \mathrm{rad}\,([a,b]) = [\mathrm{rad}\,(a),\mathrm{rad}\,(b)]\] が成り立つ.

(1)

すべての整数 $a$ に対して $a^n-a$ が $n$ の倍数であるとする. このとき, $(n-1)^n-(n-1)$ は $n$ の倍数であるから, $(-1)^n+1$ は $n$ の倍数である (二項定理を使った). $n$ が偶数であるとき, $n$ は $(-1)^n+1 = 2$ の約数となるから, $n = 2$ となる. $2$ は素数であるから,「カーマイケル数」は奇数である.

(2)

「カーマイケル数」$n$ の素因数分解における素数 $p$ の指数を $m$ とおく. $p^{(m-1)n}-p^{m-1}$ は $n$ で割り切れ, $n$ は $p^m$ で割り切れるから, \[\frac{p^{(m-1)n}-p^{m-1}}{p^m} = \frac{p^{(m-1)(n-1)}-1}{p}\] は整数である. これが成り立つのは $m = 1$ の場合に限るから,「カーマイケル数」は相異なる素数の積である.