問題 17

問題017｜整数・素数

前半戦

$5$ 以上の素数の2乗を $12$ で割った余りは $1$ であることを示せ．

次の二つの命題を証明せよ．

(a) $p$ と $8 p - 1$ がともに素数ならば， $8 p + 1$ は合成数である．

(b) $p$ と $8 p^{2} + 1$ がともに素数ならば， $8 p^{2} - 1$ も素数である．

後半戦

正の整数 $n$ と有理数 $r$ を固定する．このとき，

\sum_{k = 1}^{n} \frac{1}{x_{k}} = r

を満たす正の整数の組 $(x_{1}, x_{2}, \dots, x_{n})$ は有限個であることを示せ．

任意の正の整数 $n$ に対して，次の数は素数ではないことを示せ．

10^{10^{10^{n}}} + 10^{10^{n}} + 10^{n} - 1

ヒント設問 1

ヒント 1

$5$ 以上の素数は $2, 3$ で割り切れない．

ヒント 2

$6$ で割った余りを調べる．

ヒント設問 2

ヒント 1

$3$ で割った余りに注目する．

ヒント 2

(a) は $p = 2, 3$ の場合も確認し，(b) は $p \neq 3$ のとき $p^{2} \equiv 1 (\mod 3)$ を用いる．

ヒント設問 3

ヒント 1

$r \leq 0$ の場合を確認した後， $n$ について帰納法を用いる．

ヒント 2

分母を小さい順に並べ，最小の分母に $x_{1} \leq n / r$ という上限があることを示す．

ヒント設問 4

ヒント 1

$n = 2^{m} k$ （ $k$ は奇数）と表し， $d = 10^{2^{m}} + 1$ を法として考える．

ヒント 2

$10^{n}$ は $- 1$ に合同となり，他の二つのべきは $1$ に合同となることを示す．

解答設問 1

$p$ を $5$ 以上の素数とする． $p$ は $2$ でも $3$ でも割り切れないので， $6$ で割った余りは $1$ または $5$ である．したがって，整数 $q$ を用いて $p = 6 q + 1$ または $p = 6 q - 1$ と表せる．いずれの場合も，

p^{2} = 36 q^{2} \pm 12 q + 1 = 12 (3 q^{2} \pm q) + 1

となる．よって， $p^{2}$ を $12$ で割った余りは $1$ である．

解答設問 2

(a) $p = 2$ のとき $8 p - 1 = 15$ は素数ではないので，仮定を満たさない． $p = 3$ のときは $8 p - 1 = 23$ が素数であり， $8 p + 1 = 25$ は合成数である．

以下， $p > 3$ とする． $p$ は素数なので， $3$ で割った余りは $1$ または $2$ である．もし $p \equiv 2 (\mod 3)$ ならば， $8 p - 1 \equiv 0 (\mod 3)$ となる．しかし $8 p - 1 > 3$ なので，これは $8 p - 1$ が素数であることに反する．よって $p \equiv 1 (\mod 3)$ であり，

8 p + 1 \equiv 2 \cdot 1 + 1 = 0 (\mod 3)

を得る． $8 p + 1 > 3$ だから， $8 p + 1$ は合成数である．

(b) $p \neq 3$ と仮定する． $p$ は素数なので $3$ で割り切れず， $p^{2} \equiv 1 (\mod 3)$ である．したがって，

8 p^{2} + 1 \equiv 2 \cdot 1 + 1 = 0 (\mod 3)

となる． $p \geq 2$ より $8 p^{2} + 1 \geq 33 > 3$ なので，これは $8 p^{2} + 1$ が素数であることに反する．よって $p = 3$ でなければならない．このとき $8 p^{2} - 1 = 71$ である． $\sqrt{71} < 9$ であり， $71$ は $9$ 未満の素数 $2, 3, 5, 7$ のいずれでも割り切れないので，素数である．

解答設問 3

左辺は正なので， $r \leq 0$ のとき解は存在しない．以下， $r > 0$ の場合を考える．まず，分母を小さい順に並べた解

x_{1} \leq x_{2} \leq \dots \leq x_{n}

が有限個であることを， $n$ についての数学的帰納法で示す．帰納法の命題は「任意の正の有理数 $r$ に対して，そのような解は有限個である」とする．

$n = 1$ のときは $x_{1} = 1 / r$ に限られるので，解は高々一つである．次に， $n - 1$ の場合に命題が成り立つと仮定する． $x_{1}$ が最小の分母なので，各 $k$ について $1 / x_{k} \leq 1 / x_{1}$ であり，

r = \sum_{k = 1}^{n} \frac{1}{x_{k}} \leq \frac{n}{x_{1}}

となる．したがって $1 \leq x_{1} \leq n / r$ であり， $x_{1}$ の候補は有限個である．

各候補 $x_{1}$ を固定すると，残りの項は，

\sum_{k = 2}^{n} \frac{1}{x_{k}} = r - \frac{1}{x_{1}}

を満たす．右辺が正でなければ解はなく，正ならば帰納法の仮定より残りの組は有限個である．よって，有限個の $x_{1}$ の候補を合わせても，並べ替え済みの解は有限個である．

最後に，各組の並べ方は高々 $n!$ 通りなので，順序を区別した元の組 $(x_{1}, \dots, x_{n})$ も有限個である．

解答設問 4

N = 10^{10^{10^{n}}} + 10^{10^{n}} + 10^{n} - 1

とおく． $n$ から $2$ の因子をすべて取り出し， $n = 2^{m} k$ と表す．ここで $m$ は非負整数， $k$ は正の奇数である．

d = 10^{2^{m}} + 1

とおくと， $10^{2^{m}} \equiv - 1 (\mod d)$ なので，任意の非負整数 $j$ に対して，

10^{2^{m} j} \equiv (- 1)^{j} (\mod d)

が成り立つ．特に， $k$ は奇数だから，

10^{n} = 10^{2^{m} k} \equiv - 1 (\mod d)

である．

次に， $10^{n}$ と $10^{10^{n}}$ がともに $2^{m + 1}$ の倍数であることを確認する．非負整数 $m$ に対して $2^{m} \geq m + 1$ なので， $n = 2^{m} k \geq m + 1$ である．したがって $10^{n} = 2^{n} 5^{n}$ は $2^{m + 1}$ で割り切れる．同様に， $10^{n} \geq n \geq m + 1$ なので， $10^{10^{n}} = 2^{10^{n}} 5^{10^{n}}$ も $2^{m + 1}$ で割り切れる．

よって，整数 $10^{n} / 2^{m}$ と $10^{10^{n}} / 2^{m}$ はともに偶数である．上の合同式にこれらを $j$ として代入すると，

\begin{aligned} 10^{10^{n}} & \equiv 1 (\mod d), \\ 10^{10^{10^{n}}} & \equiv 1 (\mod d) \end{aligned}

を得る．したがって，

N \equiv 1 + 1 - 1 - 1 = 0 (\mod d)

であり， $d$ は $N$ の約数である．さらに， $1 < d = 10^{2^{m}} + 1 \leq 10^{n} + 1 < N$ なので， $d$ は $1$ と $N$ のいずれでもない約数である．よって $N$ は合成数であり，素数ではない．

DISCUSSION

この問題の掲示板

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

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

まだ投稿はありません。