文献あり

等比数列と倍数にまつわる整数の問題〈解答アリ〉

143

$n$ を正の整数， $p$ を奇数の素数とし， $k$ は $p$ で割った余りが $1$ である自然数とする。また自然数 $N$ を $N = 1 + k + k^{2} + \dots + k^{n - 1}$
と定める。このとき $N$ が持つ素因数 $p$ の個数と $n$ が持つ素因数 $p$ の個数は等しいことを示せ。

例えば $n = 54 = 2 \cdot 3^{3}$ ， $p = 3$ ， $k = 7$ としますと， $N = 2^{3} \cdot 3^{3} \cdot 19 \cdot 37 \cdot 43 \cdot 109 \cdot 811 \cdot 1063 \cdot 2377 \cdot 117307 \cdot 2583253 \cdot 1628413557556843$
と素因数分解されますので， $N$ と $n$ はいずれも $3$ で $3$ 回割り切れることが分かります。

問題 1 における

p = 2

のとき

$n$ を正の整数とし， $k$ は $4$ で割った余りが $1$ である自然数とする。また自然数 $N$ を $N = 1 + k + k^{2} + \dots + k^{n - 1}$
とする。このとき $N$ が持つ素因数 $2$ の個数と $n$ が持つ素因数 $2$ の個数は等しいことを示せ。

例えば $n = 48 = 2^{4} \cdot 3$ ， $k = 5$ としますと， $N = 2^{4} \cdot 3^{2} \cdot 7 \cdot 13 \cdot 17 \cdot 31 \cdot 313 \cdot 601 \cdot 11489 \cdot 390001 \cdot 152587500001$
となります。

解答案

問題1の解答例

$p$ を素数とし， $n$ は $p$ で“きっかり” $s$ 回割れるとする。このとき $n$ は $n = h p^{s}$ と表せる（ $h$ は $p$ と互いに素）。このとき， $N = \frac{1 - k^{h p^{s}}}{1 - k}$
である。右辺の分子はさらに次の形に因数分解できる。 $1 - k^{h p^{s}} = (1 - k^{p^{s}}) (1 + k^{p^{s}} + k^{2 p^{s}} + \dots + k^{(k - 1) p^{s}})$
$k \equiv 1 (\mod p)$ なので， $1 + k^{p^{s}} + k^{2 p^{s}} + \dots + k^{(k - 1) p^{s}} \equiv \underset{h}{\underset{⏟}{1 + \dots + 1}} \equiv h (\mod p)$
である。 $h$ と $p$ は互いに素だから， $1 + k^{p^{s}} + k^{2 p^{s}} + \dots + k^{(k - 1) p^{s}}$ は $p$ で割り切れない。よって $\frac{1 - k^{p^{s}}}{1 - k}$
が $p$ で何回割り切れるかを考えればよい。次の等式を利用する。 $(*) \frac{1 - k^{p^{s}}}{1 - k} = \prod_{j = 1}^{s} {1 + (k^{p^{s - j}}) + {(k^{p^{s - j}})}^{2} + \dots + {(k^{p^{s - j}})}^{p - 1}}$
ここで $p$ は奇数の素数で， $k \equiv 1 (\mod p)$ だったので， $k^{p^{s - j}}$ はある整数 $q_{j}$ を用いて $k^{p^{s - j}} = p q_{j} + 1$ と表される。 $(*)$ 式の因数を書き換えると， $1 + (1 + p q_{j}) + (1 + p q_{j})^{2} + \dots + (1 + p q_{j})^{p - 1}$
となっている。この式を展開して整理すると，次のようになる。 $(#) p + \underset{♠}{\underset{⏟}{_{p} C_{p - 2} (p q_{j}) +_{p} C_{p - 3} (p q_{j})^{2} + \dots + (p q_{j})^{p - 1}}}$
$♠$ 部分については $p^{2}$ で割り切れるので， $(#)$ はきっかり $p$ で割り切れる。従って $(*)$ はきっかり $p$ で $s$ 回割り切れることになり，これは $N$ が $p$ で $s$ 回割り切れることに等しい。

問題2の解答案【前半は問題1と同様の議論】

問題1の解答案において， $(*) \frac{1 - k^{p^{s}}}{1 - k} = \prod_{j = 1}^{s} {1 + (k^{p^{s - j}}) + {(k^{p^{s - j}})}^{2} + \dots + {(k^{p^{s - j}})}^{p - 1}}$
までの議論は $p = 2$ であっても同様である。この $(*)$ は $p = 2$ においては， $(*) \prod_{j = 1}^{s} (1 + k^{2^{s - j}})$
と書き表せる。また $k \equiv 1 (\mod 4)$ とすると， $k^{2^{s - j}} \equiv 1 (\mod 4)$ となる。従って $(*)$ 式は， $\prod_{j = 1}^{s} (1 + 4 M_{j} + 1) (M_{j} \in Z)$
と表され， $2 + 4 M_{j}$ は $2$ の倍数だが $4$ の倍数でないため， $(*)$ は $2$ できっかり $s$ 回で割り切れる。よって $N$ も $2$ できっかり $s$ 回割り切れる。