数オリの問題に留数を使うその2

992

数オリの問題を解いていて面白い解法を見つけたので書いておきます．

問題 (Mediterranean 2021-1)
次の条件をみたす最小の正整数 $M$ を求めよ．
条件: どのような整数 $a, b, c$ に対してもある整数係数多項式 $P (x)$ が存在して $P (1) = a M, P (2) = b M, P (4) = c M$ となる．

$a_{n} = 4^{n} - 3 \cdot 2^{n} + 2$ とすると
$a_{0} = a_{1} = 0, a_{2} = 6 a_{n + 3} = 7 a_{n + 2} - 14 a_{n + 1} + 8 a_{n}$
から任意の自然数 $n$ に対して $a_{n}$ が $6$ の倍数であることがわかり，特に $P (4) - 3 P (2) + 2 P (1) = (c - 3 b + 2 a) M$ は $6$ の倍数である．
$c - 3 b + 2 a$ が $6$ と互いに素なときを考えると， $M$ が $6$ の倍数であることがわかる．
また， $P (x) = 2 a (x - 2) (x - 4) - 3 b (x - 1) (x - 4) + c (x - 1) (x - 2)$ という多項式を考えることで最小値が $M = 6$ であることがわかる．

(ラグランジュ補間と因数定理を組み合わせると簡単に解けるのですが気付かなかったことにします)
この問題を一般化してみます．

$n$ を正の整数とし， $a_{1}, \dots, a_{n}$ を相異なる整数とする．次の条件をみたす最小の正整数 $M$ を求めよ．
条件: どのような整数 $b_{1}, \dots, b_{n}$ に対してもある整数係数多項式 $P (x)$ が存在して $P (a_{1}) = b_{1} M, \dots, P (a_{n}) = b_{n} M$ となる．

補題を用意します．

$f (x), g (x) \in Z [x]$ で $g$ がモニック多項式であるとき， $\frac{f (z)}{g (z)}$ の無限遠点における留数は整数である．

無限遠点での留数については参考文献をご覧ください．(記事下にあります)

$z^{\deg f} f (\frac{1}{z}) = \bar{f} (z), z^{\deg g} g (\frac{1}{z}) = \bar{g} (z)$ とする．
$g$ はモニックなので $h (z) \in Z [z]$ が存在して $\bar{g} (z) = 1 - z h (z)$ となる．
原点を中心とする半径 $R$ の円周を反時計周りに $1$ 周する積分路を $C_{R}$ とすると， $- \oint_{C_{R}} \frac{f (z)}{g (z)} d z = \oint_{C_{1 / R}} \frac{\bar{f} (z)}{\bar{g} (z)} z^{\deg g - \deg f - 2} d z$ となるので $\frac{f (z)}{g (z)}$ の無限遠点での留数は $\frac{\bar{f} (z)}{\bar{g} (z)}$ の $z = 0$ でのLaurent展開の係数として与えられることがわかる．
ここで， $\frac{\bar{f} (z)}{\bar{g} (z)} = \bar{f} (z) (1 + z h (z) + z^{2} h^{2} (z) + \dots)$ となり，これは整数係数なので， $\frac{f (z)}{g (z)}$ の無限遠点での留数が整数になることがわかる．

$f$ を， $C$ において有限個の点 $a_{1}, \dots, a_{n}$ を除いて正則な関数とするとき， $Res (f, \infty) = - \sum_{i = 1}^{n} Res (f, a_{i})$

$Res (f, \infty) = - \frac{1}{2 π i} \oint_{C_{R}} f (z) d z$ と留数定理よりしたがう．

$\frac{P (z)}{(z - a_{1}) \dots (z - a_{n})}$ に補題1を適用すると，これの無限遠点での留数は整数であり，補題2より， $\sum_{i = 1}^{n} \frac{P (a_{i})}{\prod_{j \neq i} (a_{i} - a_{j})} = \sum_{i = 1}^{n} \frac{b_{i} M}{\prod_{j \neq i} (a_{i} - a_{j})}$ は整数です．
これより， $M$ は $\prod_{j \neq i} (a_{i} - a_{j}) (i = 1, \dots, n)$ の公倍数とわかります．(これは自明ではないけどここでは説明を省略します)
また，ラグランジュ補間による構成を考えると， $M$ が最小公倍数のときに最小値を実現することがわかります．