インテジャーズ

INTEGERS

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

IMO 1990 Problem 3

高校数学 整数 整数-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のみである。

mod 1989

整数 整数-1989

私は1989年生まれですが、1989の現れる問題を発見したので紹介します。

問題*1 3以上の整数nに対して合同式
\displaystyle n^{n^{n^n}}\equiv n^{n^n} \pmod{1989}
が成り立つことを示せ。

integers.hatenablog.com

で紹介されているCarmichaelの定理を用います。

証明. nが奇数であれば

n^n\equiv n \pmod{4} \tag{1}

が成り立つ。理由: n^n-n=n(n^{n-1}-1)であり、\lambda(4)=2 \mid n-1である。

n^{n^n}\equiv n^n \pmod{3} \tag{2}

理由: n^{n^n}-n^n=n^n(n^{n^n-n}-1)であり、\lambda(3)=2 \mid n^n-nである。

n\geq 3であれば

n^{n^n}\equiv n^n \pmod{16} \tag{3}

理由: nが偶数のときはn \geq 4より成立。nが奇数のときはn^{n^n}-n^n=n^n(n^{n^n-n}-1)であり、(1)より\lambda(16)=4 \mid n^n-nより成立。

(2)、(3)よりn\geq 3であればa=6, 12, 16に対して

n^{n^n}\equiv n^n \pmod{a}

が成り立つことが示された。

\displaystyle n^{n^{n^n}}-n^{n^n}=n^{n^n}(n^{n^{n^n}-n^n}-1)

なので、\lambda(9)=6, \ \lambda(13)=12, \ \lambda(17)=16に注意すると

\displaystyle n^{n^{n^n}} \equiv n^{n^n} \pmod{b}

がb=9, 13, 17に対して成立する。1989=9\times 13 \times 17なので、中国式剰余定理より

\displaystyle n^{n^{n^n}}\equiv n^{n^n} \pmod{1989}

が示された。 Q.E.D.

*1:バルカン数学オリンピックの問題？

0.011010100010100010100010000010100000100... は無理数

数 数-0.011010100010100010100010000010100000100...

bを2以上の整数とし、以下、正の実数をb進法表示で表します。ただし、\cdots r\dot{0}ではなく\cdots (r-1)\dot{(b-1)}を採用します(r \geq 1)。

定理 小数第素数位が1であり、それ以外が0であるような小数
0.011010100010100010100010000010100000100\dots
は無理数である*1。

ここでは、Nasehpourの方法を紹介します*2。

証明. 正の実数rの小数部分0.r_1r_2\cdotsに対して

\displaystyle \lim_{n\to\infty}\frac{r_1+\cdots +r_n}{n}

が存在するとき、その極限値を\mathrm{Av}(r)と表す。

0\leq d \leq b-1に対してA(d, n):=\{1\leq j\leq n \mid r_j=d\}とする。各dに対して極限値\lim_{n \to \infty}\frac{\#A(d, n)}{n}=\omega_dが存在すれば、

\displaystyle \mathrm{Av}(r)=\sum_{d=1}^{b-1}d\omega_d \tag{1}

が成り立つ。理由: 任意に\varepsilon > 0をとる。十分大きいnに対して

\displaystyle \left|\frac{\#A(d, n)}{n}-\omega_d\right| < \varepsilon

が成り立ち、

\displaystyle \frac{r_1+\cdots +r_n}{n}=\frac{1}{n}\sum_{d=0}^{b-1}\sum_{i \in A(d, n)}r_i=\sum_{d=1}^{b-1}d\frac{\#A(d, n)}{n}

なので、

\displaystyle \left|\frac{r_1+\cdots +r_n}{n}-\sum_{d=1}^{b-1}d\omega_d\right| < \frac{b(b-1)\varepsilon}{2}

が得られる。

rが有理数であればrの小数部分は循環小数0.r_1\cdots r_n \dot{q_1}\cdots \dot{q_m}の形になり、このとき

\displaystyle \omega_{q_1}=\cdots = \omega_{q_m}=\frac{1}{m}

であり、d \in \{0, 1, \dots, b-1\} \setminus \{q_1, \dots, q_m\}に対しては\omega_d=0なので、(1)より

\displaystyle \mathrm{Av}(r) = \frac{q_1+\cdots + q_m}{m}

となって、これは正の有理数である(q_1=\cdots =q_m=0は許されていない)。よって、以上の考察から\mathrm{Av}(r) = 0であればrは無理数であるという無理数判定法が得られた*3。

rを0.011010100010100010100010000010100000100\dotsとする。すると、素数密度零補題より

\displaystyle \mathrm{Av}(r) = \lim_{n \to \infty}\frac{\pi(n)}{n}=0

なのでrは無理数である。 Q.E.D.

*1:最初に述べた小数表示のルールに則っていることを確認するために素数の無限性が必要。

*2:P. Nasehpour, A simple criterion for irrationality of some real numbers, arXiv. もちろん、もっと自明に直接的に示すことができますが、一応もう少しgeneralな無理数判定法を一つ提示しています。例えば、ラッキー数バージョンであっても同じ仕組みで説明できます。

*3:逆は成り立たない。