問題 14

問題014｜整数・二項係数

難易度 D 目安 50

前半戦

次の式の値が素数となる整数 $n$ は存在するか．

n^{4} - 6 n^{2} + 25

$n$ を非負整数とする． $n$ 次多項式 $P (x)$ が， $k = 0, 1, \dots, n$ に対して $P (k) = 2^{k}$ を満たしている． $P (n + 1)$ の値を求めよ．

後半戦

各項が正の整数である数列 ${a_{n}}$ が，任意の正の整数 $i, j$ に対して，

gcd (a_{i}, a_{j}) = gcd (i, j)

を満たすとする．このとき，すべての正の整数 $n$ に対して $a_{n} = n$ であることを示せ．

$p$ を素数， $n$ を非負整数とし， $n$ の $p$ 進展開を

n = n_{0} + n_{1} p + \dots + n_{t} p^{t} (0 \leq n_{i} < p)

とする．二項係数 $(\binom{n}{r})$ （ $r = 0, 1, \dots, n$ ）のうち， $p$ で割り切れないものの個数を $n_{0}, n_{1}, \dots, n_{t}$ を用いて表せ．

ヒント設問 1

ヒント 1

$(n^{2} + 5)^{2} - (4 n)^{2}$ と変形して因数分解する．

ヒント 2

各因数を平方の形に直し，どちらかが $1$ となる場合を調べる．

ヒント設問 2

ヒント 1

二項定理の和を，多項式 $(\binom{x}{r}) = x (x - 1) \dots (x - r + 1) / r!$ を用いて表す．

ヒント 2

条件を満たす多項式を作り， $P (x)$ との差が持つ零点の個数を考える．

ヒント設問 3

ヒント 1

条件は $i = j$ の場合にも成り立つ．

ヒント 2

$gcd (m, m) = m$ を用いる．

ヒント設問 4

ヒント 1

$(1 + x)^{p} \equiv 1 + x^{p} (\mod p)$ を繰り返し用い， $(1 + x)^{n}$ を $n$ の $p$ 進展開に沿って分解する．

ヒント 2

各因子から項を選ぶ方法と，その項の次数の $p$ 進展開を対応させる．

解答設問 1

与えられた式を因数分解すると，

\begin{aligned} n^{4} - 6 n^{2} + 25 & = (n^{2} + 5)^{2} - (4 n)^{2} \\ = (n^{2} + 4 n + 5) (n^{2} - 4 n + 5) \\ = {(n + 2)^{2} + 1} {(n - 2)^{2} + 1} \end{aligned}

となる． $n$ は整数なので，右辺の二つの因数はともに正の整数である．したがって，積が素数となるためには，少なくとも一方の因数が $1$ でなければならない．

$(n + 2)^{2} + 1 = 1$ となるのは $n = - 2$ ， $(n - 2)^{2} + 1 = 1$ となるのは $n = 2$ のときである．いずれの場合も，与えられた式の値は $16 - 24 + 25 = 17$ となり，これは素数である．よって，そのような整数は存在し，該当するのは $n = \pm 2$ である．

解答設問 2

$(\binom{x}{0}) = 1$ と定め， $1 \leq r \leq n$ に対して，

(\binom{x}{r}) = \frac{x (x - 1) \dots (x - r + 1)}{r!}

とおく．これは $x$ の $r$ 次多項式である．次の多項式を考える．

Q (x) = \sum_{r = 0}^{n} (\binom{x}{r})

$Q (x)$ は $n$ 次多項式である．整数 $k$ が $0 \leq k \leq n$ を満たすとき， $r > k$ ならば $(\binom{k}{r}) = 0$ なので，二項定理より，

Q (k) = \sum_{r = 0}^{k} (\binom{k}{r}) = (1 + 1)^{k} = 2^{k} = P (k)

となる．したがって，次数が高々 $n$ の多項式 $P (x) - Q (x)$ は，相異なる $n + 1$ 個の零点 $0, 1, \dots, n$ を持つ．零多項式でない多項式の零点の個数はその次数以下であるから， $P (x) - Q (x)$ は零多項式であり， $P (x) = Q (x)$ が成り立つ．

よって，再び二項定理を用いると，

\begin{aligned} P (n + 1) & = \sum_{r = 0}^{n} (\binom{n + 1}{r}) \\ = \sum_{r = 0}^{n + 1} (\binom{n + 1}{r}) - (\binom{n + 1}{n + 1}) \\ = 2^{n + 1} - 1 \end{aligned}

となる．

別解（有限差分）

関数 $f$ に対して $Δ f (x) = f (x + 1) - f (x)$ と定める．多項式では差を取るたびに次数が下がるので， $Δ^{n + 1} P = 0$ である．一方， $E (x) = 2^{x}$ とおけば $Δ E = E$ より $Δ^{n + 1} E (0) = 1$ である．

$R (x) = E (x) - P (x)$ とすると，仮定から $R (0) = \dots = R (n) = 0$ である．差を繰り返し取った $Δ^{n + 1} R (0)$ は $R (0), \dots, R (n + 1)$ の一次結合であり，最後の $R (n + 1)$ の係数は $1$ なので，

2^{n + 1} - P (n + 1) = R (n + 1) = Δ^{n + 1} R (0) = 1.

よって $P (n + 1) = 2^{n + 1} - 1$ である．これは $n = 0$ の場合も含む．

解答設問 3

任意の正の整数 $n$ に対して，条件に $i = j = n$ を代入すると，

gcd (a_{n}, a_{n}) = gcd (n, n)

を得る． $a_{n}, n$ は正の整数なので，左辺は $a_{n}$ ，右辺は $n$ に等しい．したがって，すべての正の整数 $n$ に対して $a_{n} = n$ である．

解答設問 4

以下，多項式の合同式は，同じ次数の項の係数がそれぞれ合同であることを表す．

$p$ は素数なので， $1 \leq j \leq p - 1$ に対して $(\binom{p}{j})$ は $p$ の倍数である．したがって，二項定理より

(1 + x)^{p} \equiv 1 + x^{p} (\mod p)

が成り立つ．これを繰り返すと，任意の非負整数 $i$ に対して

(1 + x)^{p^{i}} \equiv 1 + x^{p^{i}} (\mod p)

を得る．よって， $n$ の $p$ 進展開を用いると，

\begin{aligned} (1 + x)^{n} & = \prod_{i = 0}^{t} {((1 + x)^{p^{i}})}^{n_{i}} \\ \equiv \prod_{i = 0}^{t} (1 + x^{p^{i}})^{n_{i}} \\ = \prod_{i = 0}^{t} (\sum_{r_{i} = 0}^{n_{i}} (\binom{n_{i}}{r_{i}}) x^{r_{i} p^{i}}) (\mod p) \end{aligned}

となる．

右辺の積から項を一つ選ぶことは，各 $i$ について $0 \leq r_{i} \leq n_{i}$ を満たす整数 $r_{i}$ を選ぶことに対応する．その項の次数は

r = r_{0} + r_{1} p + \dots + r_{t} p^{t}

である．各 $r_{i}$ は $p$ 未満なので， $p$ 進展開の一意性により，異なる選び方から同じ次数の項が生じることはない．また， $r_{i} \leq n_{i}$ より $0 \leq r \leq n$ である．

$0 \leq r_{i} \leq n_{i} < p$ より， $n_{i}!$ ， $r_{i}!$ ， $(n_{i} - r_{i})!$ はいずれも $p$ で割り切れない．したがって， $(\binom{n_{i}}{r_{i}})$ も $p$ で割り切れず，選ばれた項の係数

\prod_{i = 0}^{t} (\binom{n_{i}}{r_{i}})

も $p$ で割り切れない．一方，このような選び方で現れない次数の係数は，右辺では $0$ である．

以上より，左辺の二項係数が $p$ で割り切れない次数は，このような選び方にちょうど対応する．各 $r_{i}$ の選び方は $n_{i} + 1$ 通りなので，求める個数は

\prod_{i = 0}^{t} (n_{i} + 1)

である． $n = 0$ の場合も，二項係数は $(\binom{0}{0}) = 1$ の一つだけであり，この公式が成り立つ．

DISCUSSION

この問題の掲示板

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

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

まだ投稿はありません。