文献あり

15と互いに素な中心二項係数の無限性

733

本稿では以下の定理の証明を紹介する：

（Erdős-Graham-Ruzsa-Straus 1975）

正整数 $n$ であって $(\binom{2 n}{n})$ が $15$ と互いに素であるものは無限に存在する．

定理中の $15$ という数に特別な意味はなく，相異なる奇素数 $p, q$ を用いて $p q$ と表せる数であれば同様に成立する（原論文ではその形で述べられている）のだが，記号が煩雑になるのでここでは $15$ の場合に限って説明する．

なお，正整数 $n$ であって $(\binom{2 n}{n})$ が $105$ と互いに素であるものが無限に存在するかどうかは，2024年現在未解決のようである（ https://www.erdosproblems.com/376 ）．

記号

$\sum_{n = 0}^{d} a_{n} p^{n}$ のことを $a_{d} a_{d - 1} \dots a_{1} a_{0}_{(p)}$ で表す．例えば $48 = 1210_{(3)}$ である．また正整数の $p$ 進表記においては，常に左側に「 $\dots 00$ 」が省略されているとみなす．例えば
$48 = \dots 001210_{(3)}$
であり，特に $48$ の $3$ 進表記には「 $012$ 」という並びが含まれると考える．

Kummerの定理を用いた言い換え

まず以下の有名な事実を思い出そう．

（Kummerの定理）

二項係数 $(\binom{m + n}{m})$ が素数 $p$ で割り切れる回数は， $m + n$ を $p$ 進法で計算した時の繰り上がりの個数に等しい．

特に $(\binom{2 n}{n})$ が素数 $p$ と互いに素であることは， $n$ の $p$ 進表記が $0, 1, \dots, \frac{p - 1}{2}$ のみからなることと同値である．このような $n$ を $p$ -goodな数と呼ぼう．すると定理1は次のように言い換えられる：

（定理1の言い換え）

正整数 $n$ であって $3$ -goodかつ $5$ -goodであるものは無限に存在する．すなわち， $3$ 進表記が $0, 1$ のみからなり， $5$ 進表記が $0, 1, 2$ のみからなるような正整数は無限に存在する．

例えば $37 = 1101_{(3)} = 122_{(5)}$ なので $37$ は $3$ -goodかつ $5$ -goodである．

証明

当然だが $5$ -goodな正整数は無限個存在する．そこでまず $5$ -goodな正整数を取り，その $3$ 進表記に現れる $2$ をどうにかして（ $5$ -goodであることを保ちながら）除去するという方針が考えられる．一般に $3$ -goodでない数に対し，それに近い $3$ -goodな数を見つける方法を考えよう．
例えば $n = 101011201_{(3)}$ の場合， $n$ 以上で最小の $3$ -goodな数は $101100000_{(3)}$ である．一般に $n$ の $3$ 進表記に現れる $011 \dots 112$ という箇所（ $1$ は $0$ 個でもよい）のうち最も左にあるものを取って
$n = * \dots * 0 \underset{i 桁}{\underset{⏟}{11 \dots 112 * \dots *}}_{(3)}$
と表すと， $n$ 以上で最小の $3$ -goodな数は
$n^{'} = * \dots * 1 \underset{i}{\underset{⏟}{0 \dots 0}}_{(3)}$
である．以上の観察を踏まえて次のように定義する．

$3$ -goodでない正整数 $n$ に対し， $n$ の $3$ 進表記に現れる $011 \dots 112$ という箇所（ $1$ は $0$ 個でもよい）のうち最も左にあるものを取って
$n = * \dots * 0 \underset{i (n) 桁}{\underset{⏟}{11 \dots 112 * \dots *}}_{(3)}$
と表す．また $n$ の $3$ 進表記の下 $i (n)$ 桁を $T (n)$ で表す．

例えば $n = 10021201_{(3)}$ の場合， $i (n) = 5, T (n) = 21201_{(3)}$ である．以下の性質は容易にわかる：

$n$ 以上で最小の $3$ -goodな数は $n + 3^{i (n)} - T (n)$ である．
$T (n) \geq \frac{3^{i (n)} + 1}{2} .$

$n$ を $5$ -goodだが $3$ -goodでない正整数とする．このとき $5$ -goodな正整数 $n^{'}$ であって以下の条件をみたすものが存在する：
(1) $n$ と $n^{'}$ の $3$ 進表記は下 $i (n) + 1$ 桁のみが異なる．
(2) 以下のいずれかが成り立つ：

$n^{'}$ は $3$ -goodである．
$n^{'}$ は $3$ -goodでなく， $i (n) > i (n^{'})$ が成り立つ．
$n^{'}$ は $3$ -goodでなく， $i (n) = i (n^{'}), T (n) > T (n^{'})$ が成り立つ．

$v_{5} (n) = m$ とおくと， $n$ 未満で最大の $5$ -goodな数は $n - \frac{5^{m} + 1}{2}$ である． $\frac{5^{m} + 1}{2} \leq T (n)$ ならば， $n^{'} = n - \frac{5^{m} + 1}{2}$ とすれば条件を満たす．そこで以下では
$\frac{5^{m} - 1}{2} \geq T (n)$
と仮定してよい． $x = 3^{i (n)} - T (n)$ と定めると， $n$ 以上で最小の $3$ -goodな数は $n + x$ である．より一般に $x \leq y \leq x + \frac{3^{i (n)} - 1}{2}$ を満たす $y$ に対して， $n^{'} = n + y$ は条件(1), (2)を満たす．そこでこの範囲に $n + y$ が $5$ -goodとなるような $y$ が存在することを示せばよい． $T (n) \geq \frac{3^{i (n)} + 1}{2}$ より $x \leq \frac{3^{i (n)} - 1}{2}$ なので，この範囲にある $y$ に対して
$y \leq x + \frac{3^{i (n)} - 1}{2} \leq 3^{i (n)} \leq 2 T (n) \leq 5^{m} - 1$
が成り立つ．よって $n + y$ が $5$ -goodであることは， $y$ が $5$ -goodであることと同値である．また
$2 x = x + x \leq x + \frac{3^{i (n)} - 1}{2}$
なので， $x \leq y \leq 2 x$ の範囲に $5$ -goodな $y$ が存在することを示せばよい．これは次の補題から従う．

任意の正整数 $x$ に対し， $x \leq y \leq 2 x$ を満たす $5$ -goodな正整数 $y$ が存在する．

$5$ -goodな正整数 $n$ に対し， $n$ の $5$ 進表記を
$n = * \dots * a \underset{i}{\underset{⏟}{2 \dots 2}}_{(5)} (a < 2)$
とすると， $n$ よりも大きい最小の $5$ -goodな数は
$n^{'} = * \dots * (a + 1) \underset{i}{\underset{⏟}{0 \dots 0}}_{(5)}$
である．この表示から $n^{'} / n \leq 2$ がわかるのでよい．

（定理3の証明）

$\log_{3} 5$ は無理数なので， $k \log_{3} 5$ の小数部分が $\log_{3} (3 / 2)$ 未満となるような正整数kは無限個存在する．そのようなkに対して
$k \log_{3} 5 = d + x (d \in Z, 0 \leq x < \log_{3} (3 / 2))$
と表すと
$3^{d} \leq 5^{k} < \frac{3^{d + 1}}{2}$
なので， $n = 5^{k}$ と定めると $1 \underset{d}{\underset{⏟}{0 \dots 0}}_{(3)} \leq n \leq \underset{d + 1}{\underset{⏟}{1 \dots 1}}_{(3)}$ である．特に， $n$ は $3$ -goodでなければ $i (n) < d$ を満たす．この $n$ に対して命題4を繰り返し適用すると， $n$ の下 $d$ 桁のみを変更することで $3$ -goodかつ $5$ -goodな数 $n^{'}$ を得ることができる．このとき $n^{'} \geq 3^{d}$ なので，この方法でいくらでも大きい $3$ -goodかつ $5$ -goodな数が構成できる．