15と互いに素な中心二項係数の無限性
本稿では以下の定理の証明を紹介する：
正整数$n$であって$\dbinom{2n}{n}$が$15$と互いに素であるものは無限に存在する．
定理中の$15$という数に特別な意味はなく，相異なる奇素数$p,q$を用いて$pq$と表せる数であれば同様に成立する（原論文ではその形で述べられている）のだが，記号が煩雑になるのでここでは$15$の場合に限って説明する．
なお，正整数$n$であって$\dbinom{2n}{n}$が$105$と互いに素であるものが無限に存在するかどうかは，2024年現在未解決のようである（ https://www.erdosproblems.com/376 ）．
記号
$\sum_{n=0}^d a_np^n$のことを$a_da_{d-1}\cdots a_1a_0{}_{(p)}$で表す．例えば$48=1210_{(3)}$である．また正整数の$p$進表記においては，常に左側に「$\cdots00$」が省略されているとみなす．例えば
$$
48=\cdots 001210_{(3)}
$$
であり，特に$48$の$3$進表記には「$012$」という並びが含まれると考える．
Kummerの定理を用いた言い換え
まず以下の有名な事実を思い出そう．
二項係数$\dbinom{m+n}{m}$が素数$p$で割り切れる回数は，$m+n$を$p$進法で計算した時の繰り上がりの個数に等しい．
特に$\dbinom{2n}{n}$が素数$p$と互いに素であることは，$n$の$p$進表記が$0,1,\cdots,\dfrac{p-1}{2}$のみからなることと同値である．このような$n$を$p$-goodな数と呼ぼう．すると定理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\cdots 112$という箇所（$1$は$0$個でもよい）のうち最も左にあるものを取って
$$
n = \ast\cdots\ast0\underbrace{11\cdots 112\ast\cdots\ast}_{i\text{桁}}\;{}_{(3)}
$$
と表すと，$n$以上で最小の$3$-goodな数は
$$
n' = \ast\cdots\ast1\underbrace{0\cdots 0}_{i}\;{}_{(3)}
$$
である．以上の観察を踏まえて次のように定義する．
$3$-goodでない正整数$n$に対し，$n$の$3$進表記に現れる$011\cdots 112$という箇所（$1$は$0$個でもよい）のうち最も左にあるものを取って
$$
n = \ast\cdots\ast0\underbrace{11\cdots 112\ast\cdots\ast}_{i(n)\text{桁}}\;{}_{(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 \dfrac{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-\dfrac{5^m+1}{2}$である．$\dfrac{5^m+1}{2}\leq T(n)$ならば，$n'=n-\dfrac{5^m+1}{2}$とすれば条件を満たす．そこで以下では
$$
\dfrac{5^m-1}{2}\geq T(n)
$$
と仮定してよい．$x = 3^{i(n)}-T(n)$と定めると，$n$以上で最小の$3$-goodな数は$n+x$である．より一般に$x\leq y\leq x+\dfrac{3^{i(n)}-1}{2}$を満たす$y$に対して，$n'=n+y$は条件(1), (2)を満たす．そこでこの範囲に$n+y$が$5$-goodとなるような$y$が存在することを示せばよい．$T(n)\geq \dfrac{3^{i(n)}+1}{2}$より$x\leq \dfrac{3^{i(n)}-1}{2}$なので，この範囲にある$y$に対して
$$
y\leq x+\dfrac{3^{i(n)}-1}{2}\leq 3^{i(n)}\leq 2T(n)\leq 5^m-1
$$
が成り立つ．よって$n+y$が$5$-goodであることは，$y$が$5$-goodであることと同値である．また
$$
2x = x+x\leq x+\dfrac{3^{i(n)}-1}{2}
$$
なので，$x\leq y\leq 2x$の範囲に$5$-goodな$y$が存在することを示せばよい．これは次の補題から従う．
任意の正整数$x$に対し，$x\leq y\leq 2x$を満たす$5$-goodな正整数$y$が存在する．
$5$-goodな正整数$n$に対し，$n$の$5$進表記を
$$
n=\ast\cdots\ast a\underbrace{2\cdots 2}_{i}{}_{(5)}\quad (a<2)
$$
とすると，$n$よりも大きい最小の$5$-goodな数は
$$
n'=\ast\cdots\ast (a+1)\underbrace{0\cdots 0}_{i}{}_{(5)}
$$
である．この表示から$n'/n\leq 2$がわかるのでよい．
$\log_35$は無理数なので，$k\log_35$の小数部分が$\log_3(3/2)$未満となるような正整数kは無限個存在する．そのようなkに対して
$$
k\log_35 = d + x\quad(d\in \mathbb{Z},\;0\leq x<\log_3(3/2))
$$
と表すと
$$
3^d \leq 5^k < \dfrac{3^{d+1}}{2}
$$
なので，$n=5^k$と定めると$1\underbrace{0\cdots 0}_{d}{}_{(3)}\leq n\leq \underbrace{1\cdots 1}_{d+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な数が構成できる．
