問題 18

問題018｜整数・素数

前半戦

正の実数 $a, b$ が $\frac{1}{a} + \frac{1}{b} = 1$ を満たし，正の整数 $m, n, N$ に対して，

⌊ m a ⌋ = ⌊ n b ⌋ = N

が成り立つとする． $a, b$ を $m, n$ を用いて表せ．ただし， $⌊ x ⌋$ は $x$ を超えない最大の整数を表す．

素数が無限に存在することを証明せよ．

後半戦

任意の正の整数 $n$ に対して， $3^{3^{n}} + 1$ は少なくとも $2 n + 1$ 個の正の約数を持つことを示せ．

$p$ を奇素数とする．等差数列

2 p + 1, 4 p + 1, 6 p + 1, \dots

には素数が無限に存在することを証明せよ．すなわち，正の整数 $k$ を用いて $2 p k + 1$ と表される素数が無限に存在することを示せ．

ヒント設問 1

ヒント 1

床関数の条件を不等式で表し，それぞれ $a, b$ で割って足す．

ヒント 2

$N \leq m + n < N + 1$ から，左側の等号が成立することを使う．

ヒント設問 2

ヒント 1

素数が有限個であると仮定し，それらをすべて掛けた数に $1$ を加える．

ヒント 2

その数自身が素数とは限らないので，素因数に注目する．

ヒント設問 3

ヒント 1

$A_{n} = 3^{3^{n}} + 1$ とおく．

ヒント 2

平方の差も使って $A_{n + 1}$ を $A_{n}$ と二つの $1$ より大きい整数の積に分解し， $A_{n}$ より大きい約数を二つ作る．

ヒント設問 4

ヒント 1

該当する素数が有限個 $q_{1}, \dots, q_{r}$ だと仮定し， $A = 2 p q_{1} \dots q_{r}$ ， $M = 1 + A + \dots + A^{p - 1}$ とおく．

ヒント 2

$M$ の素因数 $q$ に対して， $A^{p} \equiv 1 (\mod q)$ だが $A ≢ 1 (\mod q)$ であることを示す．最小の正の指数とフェルマーの小定理を使うと， $p ∣ q - 1$ が得られる．

解答設問 1

床関数の定義より，

N \leq m a < N + 1, N \leq n b < N + 1

である． $a, b > 0$ なので，それぞれを $a, b$ で割って足すと，

N (\frac{1}{a} + \frac{1}{b}) \leq m + n < (N + 1) (\frac{1}{a} + \frac{1}{b})

となる．仮定を用いれば $N \leq m + n < N + 1$ である． $m + n$ は整数なので $m + n = N$ を得る．

ここで， $m - N / a$ と $n - N / b$ はともに非負であり，その和は $m + n - N (1 / a + 1 / b) = 0$ である．したがって両方とも $0$ であり， $m = N / a, n = N / b$ となる．よって，

a = \frac{m + n}{m}, b = \frac{m + n}{n}

である．逆に，これらの値を取れば $1 / a + 1 / b = 1$ ， $m a = n b = m + n$ となり， $N = m + n$ として条件を満たす．

解答設問 2

素数が有限個であると仮定し，そのすべてを $p_{1}, p_{2}, \dots, p_{r}$ とする．

M = p_{1} p_{2} \dots p_{r} + 1

とおく． $M > 1$ なので， $M$ は少なくとも一つの素因数 $q$ を持つ．しかし，どの $p_{i}$ で割っても $M$ の余りは $1$ だから， $q$ は $p_{1}, \dots, p_{r}$ のいずれとも異なる．これはすべての素数を列挙したという仮定に矛盾する．よって，素数は無限に存在する．

解答設問 3

$A_{n} = 3^{3^{n}} + 1$ とおき， $n$ についての数学的帰納法で示す． $n = 1$ のとき $A_{1} = 28$ は相異なる正の約数 $1, 2, 28$ を持つので，少なくとも $3 = 2 \cdot 1 + 1$ 個の正の約数を持つ．

ある $n \geq 1$ について， $A_{n}$ が少なくとも $2 n + 1$ 個の正の約数を持つと仮定する．

u = 3^{3^{n}}, v = 3^{(3^{n} + 1) / 2}

とおく． $3^{n}$ は奇数なので $v$ は整数であり， $v^{2} = 3 u$ である．したがって，

\begin{aligned} A_{n + 1} & = u^{3} + 1 \\ = (u + 1) (u^{2} - u + 1) \\ = (u + 1) {(u + 1)^{2} - v^{2}} \\ = A_{n} (u + 1 - v) (u + 1 + v) \end{aligned}

となる． $n \geq 1$ より $(3^{n} + 1) / 2 < 3^{n}$ なので $v < u$ であり， $B = u + 1 - v > 1$ ， $C = u + 1 + v > 1$ である．

$A_{n + 1} = A_{n} B C$ より， $A_{n}$ のすべての正の約数は $A_{n + 1}$ の約数でもある．さらに，

A_{n} < A_{n} B < A_{n} B C = A_{n + 1}

なので， $A_{n} B$ と $A_{n + 1}$ は， $A_{n}$ の約数には含まれない相異なる二つの正の約数である．よって， $A_{n + 1}$ の正の約数は少なくとも $(2 n + 1) + 2 = 2 (n + 1) + 1$ 個ある．以上より，すべての正の整数 $n$ について題意が成り立つ．

別解（奇数の約数を連鎖させる）

$A_{j} = 3^{3^{j}} + 1$ （ $j = 0, 1, \dots, n$ ）とおく． $A_{0} = 4$ であり， $u = 3^{3^{j - 1}}$ とすると

A_{j} = A_{j - 1} (u^{2} - u + 1) (j \geq 1)

である． $u^{2} - u + 1$ は $1$ より大きい奇数なので， $D_{j} = A_{j} / 4$ とおけば

1 = D_{0} < D_{1} < \dots < D_{n}, D_{0} ∣ D_{1} ∣ \dots ∣ D_{n}

となり，すべての $D_{j}$ は奇数である．

したがって， $D_{j}, 2 D_{j}, 4 D_{j}$ （ $0 \leq j \leq n$ ）はすべて $A_{n} = 4 D_{n}$ の約数である．同じ組の中では値が異なり，異なる組 $D_{j}$ ， $2 D_{j}$ ， $4 D_{j}$ の間でも含まれる $2$ の因子の個数が異なるため重複しない．よって正の約数は少なくとも $3 (n + 1) \geq 2 n + 1$ 個ある．

解答設問 4

$p$ を固定した奇素数とする． $2 p k + 1$ と表される素数が有限個であると仮定し，そのすべてを $q_{1}, \dots, q_{r}$ とする．

A = 2 p q_{1} q_{2} \dots q_{r}, M = 1 + A + A^{2} + \dots + A^{p - 1}

とおく．該当する素数が一つもない場合は，空の積を $1$ として $A = 2 p$ と定める．いずれの場合も $M > 1$ なので， $M$ は素因数 $q$ を持つ．この $q$ が，新しい $2 p k + 1$ 型の素数となることを示す．

素因数 $q$ の基本的な性質

$A$ は $2, p, q_{1}, \dots, q_{r}$ のすべての倍数である．したがって，これらのいずれで割っても $M$ の余りは $1$ となる．よって，

q \neq 2, q \neq p, q \neq q_{i} (1 \leq i \leq r)

である．また， $q ∣ A$ ならば $M \equiv 1 (\mod q)$ となって矛盾するので， $q$ と $A$ は互いに素である．

等比数列の和の恒等式より，

(A - 1) M = A^{p} - 1

であるから， $q ∣ M$ より $A^{p} \equiv 1 (\mod q)$ を得る．一方，もし $A \equiv 1 (\mod q)$ ならば， $M$ は $p$ 個の項の和なので $M \equiv p (\mod q)$ となる．これは $q ∣ M$ より $q ∣ p$ ，すなわち $q = p$ を意味し，矛盾する．したがって，

A^{p} \equiv 1 (\mod q), A ≢ 1 (\mod q)

である．

最小の指数を調べる

$A^{h} \equiv 1 (\mod q)$ を満たす最小の正の整数を $h$ とする． $A^{p} \equiv 1$ よりそのような $h$ は存在し， $A ≢ 1$ より $h > 1$ である．

一般に， $A^{t} \equiv 1 (\mod q)$ ならば $h ∣ t$ となる．実際， $t = u h + v$ ， $0 \leq v < h$ と割り算を行うと，

1 \equiv A^{t} = (A^{h})^{u} A^{v} \equiv A^{v} (\mod q)

を得る． $v > 0$ ならば $h$ の最小性に反するので， $v = 0$ である．

これを $t = p$ に適用すると $h ∣ p$ となる． $p$ は素数で $h > 1$ だから， $h = p$ である．さらに， $q$ は素数で $gcd (A, q) = 1$ なので，フェルマーの小定理より，

A^{q - 1} \equiv 1 (\mod q)

である．同じ議論を $t = q - 1$ に適用すれば， $p = h ∣ q - 1$ を得る．

矛盾を導く

$q \neq 2$ なので $q - 1$ は偶数である． $p$ は奇素数なので $gcd (2, p) = 1$ であり， $2 p ∣ q - 1$ が成り立つ．したがって，正の整数 $k$ を用いて，

q = 2 p k + 1

と表せる．ところが， $q$ は $q_{1}, \dots, q_{r}$ のいずれとも異なる．これは，該当する素数をすべて列挙したという仮定に矛盾する．よって， $2 p k + 1$ と表される素数は無限に存在する．

DISCUSSION

この問題の掲示板

この掲示板は公開されています。ニックネームと本文は、ログインしていない人にも表示されます。Googleアカウントの名前は表示されません。

閲覧はどなたでもできます。ログインすると投稿できます。

まだ投稿はありません。