2^n-23がとりうる最大の平方数は2025

2025,整数

191

問題

正の整数 $n$ において $2^{n} - 23$ が平方数となるときその平方数として取りうる最大値を求めよ。

~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~
~

答え

答は $2025$ です。はい。では証明。

証明

$2^{n} - 23 = x^{2}$ とする。

与式を満たす $n$ において $n \equiv 2 (\mod 3)$ が成り立つ。

$1, 2, 4 \equiv 2^{n} \equiv x^{2} + 23 \equiv 2, 3, 4, 6 (\mod 7)$ $⟹ 2^{n} \equiv 2, 4 ⟹ n \equiv 1, 2 (\mod 3)$
$n \equiv 1 (\mod 3)$ と仮定すると
$2, 7 \equiv 2^{n} \equiv x^{2} + 23 \equiv 0, 3, 5, 6 (\mod 9)$
となり矛盾。

$n = 3 m + 2$ とする。 $m = 0$ のとき大小関係から明らかに矛盾であるから $m \geq 1$ とする。

$x^{2} + 23 y^{2} = 2^{3 m + 2}$ を満たす正の奇数の組 $(x, y)$ はちょうど $1$ つ存在し、その $y$ の値は数列 ${y_{i}}_{i \geq 1}, y_{1} = 1, y_{2} = 3,$ $y_{i + 2} = 3 y_{i + 1} - 8 y_{i}$ における $| y_{m} |$ である。

存在することの証明

$x_{1} = 3, y_{1} = 1$
$\begin{array}{r} {\begin{cases} x_{k + 1} = \frac{3 x_{k} - 23 y_{k}}{2} \\ y_{k + 1} = \frac{x_{k} + 3 y_{k}}{2} \end{cases} \end{array}$
を満たす数列における $(| x_{m} |, | y_{m} |)$ が題意を満たすことを示す。特に $x_{m}^{2} + 23 y_{m}^{2} = 2^{3 m + 2}$ を満たし、 $x_{m}, y_{m}$ が奇数になることを示せば良い。
$8 (x_{k}^{2} + 23 y_{k}^{2}) = (\frac{3 x_{k} - 23 y_{k}}{2})^{2} + 23 (\frac{x_{k} + 3 y_{k}}{2})^{2} = x_{k + 1}^{2} + 23 y_{k + 1}^{2}$
と $x_{1}^{2} + 23 y_{1}^{2} = 32$ と合わせて帰納的に $x_{m}^{2} + 23 y_{m}^{2} = 2^{3 m + 2}$ を満たし、
$x_{k + 1} - y_{k + 1} = x_{k} - 13 y_{k} \equiv x_{k} - y_{k} (\mod 4) ⟹ x_{m} - y_{m} \equiv x_{1} - y_{1} \equiv 2 (\mod 4)$ であり、 $m \geq 2$ のとき
$2 x_{m} = 3 x_{m - 1} - 23 y_{m - 1} \equiv - (x_{m - 1} - y_{m - 1}) \equiv 2 (\mod 4) ⟹ x_{m} \equiv 1 (\mod 2)$
$2 y_{m} = x_{m - 1} + 3 y_{m - 1} \equiv x_{m - 1} - y_{m - 1} \equiv 2 (\mod 4) ⟹ y_{m} \equiv 1 (\mod 2)$
より $m \geq 2$ のとき $x_{m}, y_{m}$ が奇数であることが示せ、 $m = 1$ のときは明らかに奇数であるから示せた。

$2$ つ以上存在しないことの証明

$\begin{array}{r} {\begin{cases} x^{2} + 23 y^{2} = 2^{3 m + 2} \\ x^{' 2} + 23 y^{' 2} = 2^{3 m + 2} \end{cases} \end{array} \dots (i)$
となる正の奇数の組 $(x, y, x^{'}, y^{'}), x \neq x^{'}, y \neq y^{'}$ が存在したとして矛盾を示す。 $2$ つの式を上手く足し合わせると
$(x y^{'} + x^{'} y) (x y^{'} - x^{'} y) = 2^{3 m + 2} (y^{' 2} - y^{2}) \dots (i i)$
ここで $x y^{'} = x^{'} y$ と仮定すると $(i i)$ から $y = y^{'}$ となるので矛盾。 $y^{' 2} - y^{2}$ は $8$ の倍数であるから $(i i)$ の右辺は $2^{3 m + 5}$ の倍数。よって $(x y^{'} + x^{'} y) (x y^{'} - x^{'} y)$ は $2^{3 m + 5}$ の倍数であるが $gcd (x y^{'} + x^{'} y, x y^{'} - x^{'} y) = 2$ より $x y^{'} + x^{'} y, x y^{'} - x^{'} y$ のうち一方は $2^{3 m + 4}$ の倍数である。よって $max (x y^{'} + x^{'} y, | x y^{'} - x^{'} y |) \geq 2^{3 m + 4}$ が成り立つ。( $x y^{'} - x^{'} y \neq 0$ に注意する。)よって
$max (x y^{'}, x^{'} y) \geq 2^{3 m + 3}$ が言える。任意の正の整数 $a, b$ において $max (a^{2}, b^{2}) \geq a b$ が成り立つから $max (x^{2}, y^{2}, x^{' 2}, y^{' 2}) \geq max (x y^{'}, x^{'} y) \geq 2^{3 m + 3}$
であるが、 $(i)$ から大小関係より明らかに矛盾である。

　よって先ほどの結果から $x^{2} + 23 y^{2} = 2^{3 m + 2}$ を満たす $x, y$ は
$x_{1} = 3, y_{1} = 1$
$\begin{array}{r} {\begin{cases} x_{k + 1} = \frac{3 x_{k} - 23 y_{k}}{2} \\ y_{k + 1} = \frac{x_{k} + 3 y_{k}}{2} \end{cases} \end{array}$
を満たす数列における $(| x_{m} |, | y_{m} |)$ のみが解である。 $2$ つ目の式から $2 y_{k + 1} - 3 y_{k} = x_{k}$ でありそれを $1$ つ目の式に代入すると
$2 y_{k + 2} - 3 y_{k + 1} = \frac{6 y_{k + 1} - 9 y_{k} - 23 y_{k}}{2} ⟹ y_{k + 2} = 3 y_{k + 1} - 8 y_{k}$ となり、 $y_{1} = 1, y_{2} = 3$ であるから補題を得る。

補題1,2より $| y_{m} | = 1$ となるような $m$ のみが解である。

$y_{m} = - 1$ を満たす $m$ は存在しない。

$y_{i + 2} \equiv 3 y_{i + 1} - 8 y_{i} \equiv y_{i} (\mod 3)$ かつ $y_{1} = 1, y_{2} = 3$ であるから $y_{m} \equiv - 1 (\mod 3)$ となる $m$ は存在せず、特に $y_{m} = - 1$ となる $m$ も存在しない。

以降、 $y_{m} = 1$ となる $m$ のみ考える。

$y_{i} = \frac{1}{2^{i - 1}} \sum_{k = 0}^{[\frac{i - 1}{2}]}_{i} C_{2 k + 1} 3^{i - 2 k - 1} (- 23)^{k}$

数列 ${y_{i}}$ は三項間漸化式であるから解くと $y_{i} = \frac{(\frac{3 + \sqrt{- 23}}{2})^{i} - (\frac{3 - \sqrt{- 23}}{2})^{i}}{\sqrt{- 23}}$
二項定理で展開して整理すると
$\frac{(\frac{3 + \sqrt{- 23}}{2})^{i} - (\frac{3 - \sqrt{- 23}}{2})^{i}}{\sqrt{- 23}}$ $= \frac{\sum_{k = 0}^{i}_{i} C_{j} (\sqrt{- 23})^{k} 3^{i - k} - \sum_{k = 0}^{i}_{i} C_{k} (- 1)^{k} (\sqrt{- 23})^{k} 3^{i - k}}{2^{i} \sqrt{- 23}}$
$= \frac{\sum_{k = 0}^{[\frac{i}{2}]} (_{i} C_{2 k} (\sqrt{- 23})^{2 k} 3^{i - 2 k} -_{i} C_{2 k} (- 1)^{2 k} (\sqrt{- 23})^{2 k} 3^{i - 2 k}) + \sum_{k = 0}^{[\frac{i - 1}{2}]} (_{i} C_{2 k + 1} (\sqrt{- 23})^{2 k + 1} 3^{i - 2 k - 1} -_{i} C_{2 k + 1} (- 1)^{2 k + 1} (\sqrt{- 23})^{2 k + 1} 3^{i - 2 k - 1})}{2^{i} \sqrt{- 23}}$
$= \frac{2 \sqrt{- 23} \sum_{k = 0}^{[\frac{i - 1}{2}]}_{i} C_{2 k + 1} 3^{i - 2 k - 1} (- 23)^{k}}{2^{i} \sqrt{- 23}}$
$= \frac{1}{2^{i - 1}} \sum_{k = 0}^{[\frac{i - 1}{2}]}_{i} C_{2 k + 1} 3^{i - 2 k - 1} (- 23)^{k}$

$y_{m} = 1 ⟹ m \equiv 1, 3 (\mod 2 \cdot 11 \cdot 23)$

$\mod 47$ を考える。 $y_{m} = 1$ のとき特に $y_{m} \equiv 1 (\mod 47)$ である。数列 ${y_{i}}$ の法 $47$ を頑張って計算すると

$i$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$	$13$	$14$	$15$	$16$	$17$	$18$	$19$	$20$	$21$	$22$	$23$	$24$	$25$	$26$	$27$	$28$	$29$	$30$	$31$	$32$	$33$	$34$	$35$	$36$	$37$	$38$	$39$	$40$	$41$	$42$	$43$	$44$	$45$	$46$	$47$	$48$
$y_{i} (\mod 47)$	$1$	$3$	$1$	$26$	$23$	$2$	$10$	$14$	$9$	$9$	$2$	$28$	$21$	$27$	$7$	$40$	$17$	$13$	$47$	$28$	$14$	$6$	$0$	$46$	$44$	$46$	$21$	$24$	$45$	$37$	$33$	$38$	$38$	$45$	$19$	$26$	$20$	$40$	$7$	$30$	$34$	$3$	$19$	$33$	$41$	$0$	$1$	$3$

のようになり、周期 $46$ であり、余りが $1$ になるのは $m \equiv 1, 3 (\mod 2 \cdot 23)$ である。
次に法 $23$ を考える。補題4より
$2^{m - 1} = 2^{m - 1} y_{m} = \sum_{k = 0}^{[\frac{m - 1}{2}]}_{m} C_{2 k + 1} 3^{m - 2 k - 1} (- 23)^{k} \equiv m 3^{m - 1} (\mod 23)$ $⟹ 2^{m - 1} \equiv m 3^{m - 1} (\mod 23)$
$2^{i}, 3^{i}$ の法 $23$ は以下のようになる。

$i$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$
$2^{i} (\mod 23)$	$2$	$4$	$8$	$16$	$9$	$18$	$13$	$3$	$6$	$12$	$1$
$3^{i} (\mod 23)$	$3$	$9$	$4$	$12$	$13$	$16$	$2$	$6$	$18$	$8$	$1$

周期は $11$ である。先ほどの議論から特に $m \equiv 1, 3 (\mod 23)$ が成り立つ。
・ $m \equiv 1 (\mod 23)$ のとき
$2^{m - 1} \equiv 3^{m - 1} (\mod 23)$ が成り立つので先ほどの表から $m - 1 \equiv 0 (\mod 11) ⟹ m \equiv 1 (\mod 11) ⟹ m \equiv 1 (\mod 2 \cdot 11 \cdot 23)$
・ $m \equiv 3 (\mod 23)$ のとき
$2^{m - 1} \equiv 3^{m} (\mod 23)$ が成り立つので先ほどの表から $m - 1 \equiv 2 (\mod 11) ⟹ m \equiv 3 (\mod 11) ⟹ m \equiv 3 (\mod 2 \cdot 11 \cdot 23)$
以上より補題を得る。

$k \geq 1$ において $k - υ_{23} ((2 k + 1)!) \geq 1$

$k = 1$ のときは明らかに成り立つ。
$k \geq 2$ のときルジャンドルの定理から
$υ_{23} ((2 k + 1)!) = \sum_{i = 1}^{\infty} [\frac{2 k + 1}{23^{i}}]$ $\leq \sum_{i = 1}^{\infty} \frac{2 k + 1}{23^{i}} = \frac{2 k + 1}{22} \leq k - 1$
より補題を得る。

$y_{m} = 1$ となる $m$ は $1, 3$ のみである。

まず $y_{1} = y_{3} = 1$ は簡単に確認できる。それ以外に存在すると仮定する。 $y_{m} = 1, m \neq 1, 3$ とすると補題5より $23$ の倍数でない正の整数 $t$ と正の整数 $l$ を用いて $m = 22 t \cdot 23^{l} + s s \in {1, 3}$
と表せる。 $a = 22 t \cdot 23^{l}$ としたとき、オイラーの定理より $23$ と互いに素な整数 $k$ において $k^{a} \equiv 1 (\mod 23^{l + 1})$ が成り立つことに注意して補題4にその $m$ を代入することを考える。
・ $s = 1$ のとき
$2^{a} = 2^{a} y_{a + 1} =$ $\sum_{k = 0}^{\frac{a}{2}}_{a + 1} C_{2 k + 1} 3^{a - 2 k} (- 23)^{k}$
$⟹ 1 \equiv \sum_{k = 0}^{\frac{a}{2}}_{a + 1} C_{2 k + 1} 3^{a - 2 k} (- 23)^{k} (\mod 23^{l + 1})$
補題6を用いると $k \geq 1$ のとき
$υ_{23} (_{a + 1} C_{2 k + 1} 3^{a - 2 k} (- 23)^{k})$ $= υ_{23} ((a + 1) a \dots (a - 2 k + 1)) - υ_{23} ((2 k + 1)!) + υ_{23} (23^{k})$
$\geq υ_{23} (a) + 1$ $= l + 1$ であるから
$\sum_{k = 0}^{\frac{a}{2}}_{a + 1} C_{2 k + 1} 3^{a - 2 k} (- 23)^{k}$ $\equiv_{a + 1} C_{1} 3^{a} \equiv a + 1 (\mod 23^{l + 1})$ $⟹ 22 t \cdot 23^{l} \equiv a \equiv 0 (\mod 23^{l + 1})$
$t$ は $23$ の倍数でないのでこれは矛盾である。
・ $s = 3$ のとき
$2^{a + 2} = 2^{a + 2} y_{a + 3} =$ $\sum_{k = 0}^{\frac{a}{2} + 1}_{a + 3} C_{2 k + 1} 3^{a + 2 - 2 k} (- 23)^{k}$
$⟹ 4 \equiv \sum_{k = 0}^{\frac{a}{2} + 1}_{a + 3} C_{2 k + 1} 3^{a + 2 - 2 k} (- 23)^{k} (\mod 23^{l + 1})$
先ほどと同じ議論から $k \geq 2$ において $υ_{23} (_{a + 3} C_{2 k + 1} 3^{a + 2 - 2 k} (- 23)^{k}) \geq l + 1$ より
$\sum_{k = 0}^{\frac{a}{2} + 1}_{a + 3} C_{2 k + 1} 3^{a + 2 - 2 k} (- 23)^{k}$ $\equiv_{a + 3} C_{1} 3^{a + 2} +_{a + 3} C_{3} 3^{a} (- 23)$ $\equiv (a + 3) 9 - 23 \equiv a + 4 (\mod 23^{l + 1})$
$⟹ 22 t \cdot 23^{l} \equiv a \equiv 0 (\mod 23^{l + 1})$
これも矛盾である。

$m = 1, 3$ のとき $n = 5, 11$ である。そのとき $x^{2} = 9, 2025$ より答えは $2025$

あとがき

$2025$ 年ということで答えが $2025$ になる問題を解いてみました。 Ramanujan-Skolem equation という $x^{2} + 7 = 2^{n}$ というディオファントス方程式の $7$ のところが $23$ になった問題でした。だま氏の記事を参考に作成しました。
こちらの記事によると一般的に $x^{2} + D = 2^{n}$ の $D$ に依存する $n$ の上限値があるみたいです。