問題 16

問題016｜整数・数列

前半戦

正の整数 $n$ と正の整数 $a_{1}, a_{2}, \dots, a_{n}$ に対して，

k_{1} a_{1} + k_{2} a_{2} + \dots + k_{n} a_{n} = gcd (a_{1}, a_{2}, \dots, a_{n})

を満たす整数 $k_{1}, k_{2}, \dots, k_{n}$ が存在することを示せ．

フィボナッチ数列 ${F_{n}}$ を

F_{1} = F_{2} = 1, F_{n + 1} = F_{n} + F_{n - 1} (n \geq 2)

で定める．任意の正の整数 $n$ に対して，

F_{1} (\binom{n}{1}) + F_{2} (\binom{n}{2}) + \dots + F_{n} (\binom{n}{n}) = F_{2 n}

が成り立つことを示せ．

後半戦

次の分数の値が整数となる整数 $n$ をすべて求めよ．

\frac{n^{3} - 3 n^{2} + 4}{2 n - 1}

$p > 17$ を満たす任意の素数 $p$ に対して， $p^{32} - 1$ が $16320$ で割り切れることを示せ．

ヒント設問 1

ヒント 1

$n$ についての数学的帰納法を用いる．

ヒント 2

$gcd (a_{1}, \dots, a_{n})$ と $a_{n + 1}$ に対して，2整数の最大公約数を整数係数の一次結合で表す結果を使う．

ヒント設問 2

ヒント 1

$α = (1 + \sqrt{5}) / 2, β = (1 - \sqrt{5}) / 2$ とおく．

ヒント 2

ビネの公式 $F_{k} = (α^{k} - β^{k}) / \sqrt{5}$ と二項定理を用い， $1 + α = α^{2}, 1 + β = β^{2}$ に注目する．

ヒント設問 3

ヒント 1

分数を $8$ 倍して整式の部分と余りに分け， $2 n - 1$ が $27$ の約数となることを示す．

ヒント 2

得られた候補は元の分数に代入して確認する．

ヒント設問 4

ヒント 1

$16320 = 2^{6} \cdot 3 \cdot 5 \cdot 17$ と分解する．

ヒント 2

$3, 5, 17$ についてはフェルマーの小定理を使う． $2^{6}$ については $p^{32} - 1$ を繰り返し平方の差として因数分解し， $p^{2} - 1$ が $8$ の倍数であることを利用する．

解答設問 1

$n$ についての数学的帰納法で示す． $n = 1$ のときは $k_{1} = 1$ とすればよい．また，11日目に示した結果より，任意の正の整数 $u, v$ に対して， $s u + t v = gcd (u, v)$ を満たす整数 $s, t$ が存在する．

ある正の整数 $n$ について題意が成り立つと仮定する．正の整数 $a_{1}, \dots, a_{n}, a_{n + 1}$ に対して $d = gcd (a_{1}, \dots, a_{n})$ とおくと，帰納法の仮定より，

k_{1} a_{1} + \dots + k_{n} a_{n} = d

を満たす整数 $k_{1}, \dots, k_{n}$ が存在する．ここで，2整数についての結果を $d, a_{n + 1}$ に適用すると，

s d + t a_{n + 1} = gcd (d, a_{n + 1}) = gcd (a_{1}, \dots, a_{n}, a_{n + 1})

を満たす整数 $s, t$ が存在する． $d$ の表示を代入すれば，

(s k_{1}) a_{1} + \dots + (s k_{n}) a_{n} + t a_{n + 1} = gcd (a_{1}, \dots, a_{n}, a_{n + 1})

となる．係数 $s k_{1}, \dots, s k_{n}, t$ はすべて整数なので， $n + 1$ についても題意が成り立つ．以上より，すべての正の整数 $n$ について証明された．

別解（整数係数の和の最小正値）

整数係数の和 $k_{1} a_{1} + \dots + k_{n} a_{n}$ のうち，正となるものの最小値を $d$ とする．例えば $a_{1}$ がこの形の正の数なので， $d$ は存在する．各 $a_{i}$ を $d$ で割り， $a_{i} = q_{i} d + r_{i}$ ， $0 \leq r_{i} < d$ とおく．余り $r_{i} = a_{i} - q_{i} d$ も同じ形の整数係数の和だから，最小性より $r_{i} = 0$ である．したがって $d$ はすべての $a_{i}$ の公約数である．

逆に， $g = gcd (a_{1}, \dots, a_{n})$ は任意の整数係数の和を割り切るので $g ∣ d$ である． $d$ が公約数であることと合わせて $d = g$ を得る． $d$ の選び方から，求める整数係数が存在する．

解答設問 2

$F_{0} = 0$ と定めると， $F_{k + 2} = F_{k + 1} + F_{k}$ は $k = 0$ から成り立つ．ここで，

α = \frac{1 + \sqrt{5}}{2}, β = \frac{1 - \sqrt{5}}{2}

とおく． $α, β$ は方程式 $t^{2} = t + 1$ の解なので，

α^{2} = α + 1, β^{2} = β + 1

を満たす．したがって，数列 $B_{k} = (α^{k} - β^{k}) / \sqrt{5}$ は，

\begin{aligned} B_{k + 2} & = \frac{α^{k} (α + 1) - β^{k} (β + 1)}{\sqrt{5}} \\ = B_{k + 1} + B_{k} \end{aligned}

を満たす．また， $B_{0} = 0, B_{1} = (α - β) / \sqrt{5} = 1$ である．初期値と漸化式がフィボナッチ数列と一致するので，帰納的に，

F_{k} = \frac{α^{k} - β^{k}}{\sqrt{5}} (k \geq 0)

が成り立つ．これがビネの公式である．

$F_{0} = 0$ より，求める和には $k = 0$ の項を加えてよい．ビネの公式を代入し，二項定理を用いると，

\begin{aligned} \sum_{k = 1}^{n} F_{k} (\binom{n}{k}) & = \sum_{k = 0}^{n} F_{k} (\binom{n}{k}) \\ = \frac{1}{\sqrt{5}} {\sum_{k = 0}^{n} (\binom{n}{k}) α^{k} - \sum_{k = 0}^{n} (\binom{n}{k}) β^{k}} \\ = \frac{(1 + α)^{n} - (1 + β)^{n}}{\sqrt{5}} \\ = \frac{α^{2 n} - β^{2 n}}{\sqrt{5}} \\ = F_{2 n} \end{aligned}

となる．よって，題意の等式が成り立つ．

解答設問 3

F (n) = \frac{n^{3} - 3 n^{2} + 4}{2 n - 1}

とおく．整数 $n$ に対して $2 n - 1 \neq 0$ である．分子を $8$ 倍すると，

8 (n^{3} - 3 n^{2} + 4) = (2 n - 1) (4 n^{2} - 10 n - 5) + 27

となるので，

8 F (n) = 4 n^{2} - 10 n - 5 + \frac{27}{2 n - 1}

を得る．したがって， $F (n)$ が整数ならば $27 / (2 n - 1)$ も整数であり， $2 n - 1$ は $27$ の正または負の約数でなければならない．よって，

2 n - 1 \in {- 27, - 9, - 3, - 1, 1, 3, 9, 27}

から，候補は

n = - 13, - 4, - 1, 0, 1, 2, 5, 14

である．これらを元の分数に代入すると，順に

F (n) = 100, 12, 0, - 4, 2, 0, 6, 80

となり，すべて整数である．よって，求める整数は

n = - 13, - 4, - 1, 0, 1, 2, 5, 14

である．

解答設問 4

16320 = 2^{6} \cdot 3 \cdot 5 \cdot 17

であり，右辺の四つの因数はどの二つも互いに素である．したがって， $p^{32} - 1$ がそれぞれで割り切れることを示せばよい．

まず， $p > 17$ は素数なので， $p$ は $3, 5, 17$ のいずれとも互いに素である．フェルマーの小定理より，

\begin{aligned} p^{2} & \equiv 1 (\mod 3), \\ p^{4} & \equiv 1 (\mod 5), \\ p^{16} & \equiv 1 (\mod 17) \end{aligned}

となる．それぞれを $16$ 乗， $8$ 乗， $2$ 乗すれば， $p^{32}$ は $3, 5, 17$ のいずれを法としても $1$ に合同である．よって， $p^{32} - 1$ は $3, 5, 17$ で割り切れる．

次に， $2^{6}$ について考える． $p$ は奇数なので， $p - 1, p + 1$ はともに偶数であり，その一方は $4$ の倍数である．したがって，

p^{2} - 1 = (p - 1) (p + 1)

は $8$ の倍数である．また，平方の差の因数分解を繰り返すと，

p^{32} - 1 = (p^{2} - 1) (p^{2} + 1) (p^{4} + 1) (p^{8} + 1) (p^{16} + 1)

となる．右辺の最初の因数は $2^{3}$ の倍数であり，残りの四つの因数はすべて偶数なので，積は $2^{3 + 4} = 2^{7}$ の倍数である．特に， $2^{6}$ で割り切れる．

以上より， $p^{32} - 1$ は互いに素な $2^{6}, 3, 5, 17$ のすべてで割り切れるため，その積 $16320$ で割り切れる．

DISCUSSION

この問題の掲示板

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

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

まだ投稿はありません。