IMO 1990 Problem 3

$\displaystyle \frac{2^n+1}{n^2}$ が整数となるような $1$ より大きい整数 $n$ を全て決定せよ。

解答 $n > 1$ とし、 $\displaystyle \frac{2^n+1}{n^2}$ が整数であると仮定する。 $n$ は奇数でなければならない。 $k:=\mathrm{ord}_3n$ とする。このとき、 $2^n\equiv -1 \pmod{3^{2k}}$ であるので、指数持ち上げ補題より( $x=4, y=1$ として適用)、 $k \geq 2k-1$ 、すなわち $k=0, 1$ が従う。よって、 $3$ で割れない奇数 $m$ を用いて $n=3^{\epsilon}m$ と書ける( $\epsilon \in \{0, 1\}$ )。 $n=3$ のときは $\frac{2^n+1}{n^2}=1$ である。 $m > 1$ と仮定して、 $m$ の最小の素因数を $p(> 3)$ とする。

$2^n\equiv -1 \pmod{p} \tag{1}$

である。 $i:=\mathrm{Ind}_2(p)$ とする(指数)。(1)より $i \mid 2n$ 。 $i$ が奇数であれば $i \mid n$ 、 $2^n \equiv 1 \pmod{p}$ となって(1)に矛盾。よって、 $i=2j$ と書ける( $j \geq 1$ )。 $j \mid n$ である。Fermatの小定理より $j \mid \frac{p-1}{2}$ なので、 $j < p$ 。 $p$ の最小性より $j=1$ or $3$ である。 $j=1$ とすると、 $i=2$ で $2^2 \equiv 1 \pmod{p}$ と矛盾である。 $j=3$ であっても $i=6$ で $2^6 \equiv 1 \pmod{p}$ となるので $p=7$ しかあり得ない。ところが、 $\mathrm{Ind}_2(7)=3 \neq 6$ なので矛盾。つまり、 $n=3$ のみである。

INTEGERS

数、特に整数に関する記事。

IMO 1990 Problem 3