インテジャーズ

INTEGERS

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

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