とある整数論の問題と、その鮮やかな解法

次の問題は1984年にハンガリーのとある数学コンテストで出題されたものです。

問題. $a,b$ を正整数とする。どんな素数 $p$ についても $a$ を $p$ で割った余りが $b$ を $p$ で割った余り以下であるとき、 $a=b$ を示せ。

これはもともとPálfyという数学者が予想し、ErdősがSylvester-Shurの定理から従うことを指摘したという経緯があります。しかしこれを数学コンテストに出題したところ、Szegedyという学生が簡潔でself-containdな解法を発見しました。その後、彼ら3人はその解法を共著論文にまとめています。今回はそのエレガントな解法を紹介したいと思います。

以下 $a,b$ を $p$ で割った余りを $a_p,b_p$ と書きます。

問題の解答. $a\neq b$ と仮定する。まず $p$ を十分大きくとることで $a\lt b$ がわかる。さらに $a$ を $b-a$ に変えても仮定は保たれるから、最初から $1\leq a\leq b/2$ としてよい。

$A=1\cdot2\cdots (a-1)a\\B=(b-a+1)\cdots (b-1)b$

と置く。また $\alpha(p^k),\beta(p^k)$ を $A,B$ それぞれの因子（掛けられている $a$ 個の数）のうち $p^k$ で割れるものの個数とする。すると

$\displaystyle{A=\prod_p p^{\sum_{k=1}^\infty\alpha(p^k)},~B=\prod_p p^{\sum_{k=1}^\infty\beta(p^k)}.}$

ここで $A,B$ の因子はどちらも $a$ 個の連続した自然数だから $|\alpha(p^k)-\beta(p^k)|\leq1$ がわかる。さらに $A,B$ の因子を大きい方から順に見ていくと、問題の仮定 $a_p\leq b_p$ より $A$ の因子の方が先に $p$ で割れるから $\alpha(p)\geq \beta(p)$ である。とくに $p\gt a$ ならば $\alpha(p)=\beta(p)=0$ である。ゆえに上の式は

$\displaystyle{\frac{B}{A}=\prod_{p\leq a} p^{\sum_{k=1}^\infty(\beta(p^k)-\alpha(p^k))}}$

となる。 $\beta(p^k)\gt 0$ となる最大の $k$ を $\kappa(p)$ と置くと上の指数部分は

$\displaystyle{\sum_{k=1}^\infty(\beta(p^k)-\alpha(p^k))=(\beta(p)-\alpha(p))+\sum_{k=2}^{\kappa(p)}(\beta(p^k)-\alpha(p^k))-\sum_{k=\kappa(p)+1}^\infty \alpha(p^k)\\ \leq 0+\sum_{k=2}^{\kappa(p)}1=\kappa(p)-1}$