フィボナッチ・フリーク

数学の小ネタ集。

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

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

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

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

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

 

問題の解答. a\neq bと仮定する。まずpを十分大きくとることでa\lt bがわかる。さらにab-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}

と評価できるから

\displaystyle{\frac{B}{A}\biggm\vert \prod_{p\leq a}p^{\kappa(p)-1}}.

変形すると

\displaystyle{\frac{(b-a+1)\cdots (b-1)b}{\prod_{p\leq a}p^{\kappa(p)}}\biggm\vert\frac{1\cdot2\cdots(a-1)a}{\prod_{p\leq a}p}}

となる(両辺は整数になっている)。左辺分子の因子のうち約分されるものは高々\pi(a)個(\pi(n)n以下の素数の個数)なので

(左辺)\geq(b-a+1)^{a-\pi(a)}.

一方右辺分子の因子はちょうど\pi(a)個約分されるので

(右辺)\leq a^{a-\pi(a)}.

よってb-a+1\leq a.これは最初に課した仮定b\geq2aに矛盾している。よってa=bが示された。~~~\square

 

まさに見事な証明と言うほかありません。この証明を部屋に飾って眺めていたいくらいです。 いつかこんな証明がしてみたいですね。