じゅんにーさんの過去最高難度問題について初等的に考察

$(1)$から$x^2\equiv 1(\mathrm{mod}{2}^m)$$⟹x\equiv \pm 1(\mathrm{mod}{2}^{m-1})$$⟹x=1orx\ge 2^{m-1}-1$
$x=1$ならば$l=m$であるので$x\ge 2^{m-1}-1$とする。そのとき
$2^l-2^m+1=x^2\ge 2^{2m-2}-2^m+1$$⟹l\ge 2m-2$
一方、$2^l-2^m+1=x^2<(2^{\frac{l}{2}}{)}^2$$⟹2^l-2^m+1\le (2^{\frac{l}{2}}-1{)}^2=2^l-2^{\frac{l}{2}+1}+1$
$⟹l\le 2m-2$
よって$l=2m-2$である。

$l=(m-2)k+2$が必要条件であることの証明

$l\ne (m-2)k+2$で存在すると仮定し、$l_0$をそのうち最小のものとする。また、$(x_0,y_0)$を$l=l_0$における解とする。
$$2^{l_0}=x_0^2+(2^m-1)y_0^2\ge 1+2^m-1=2^m$$
より$l_0\ge m$であり$l_0=m$であるとすると$l_0\ne (m-2)k+2$に矛盾するので$l_0\ge m+1$である。
$$x_0^2-y_0^2\equiv x_0^2+(2^m-1)y_0^2\equiv 2^{l_0}\equiv 0(\mathrm{mod}{2}^m)$$
$$x_0^2-y_0^2\equiv x_0^2+(2^m-1)y_0^2-2^m{y}_0^2\equiv 2^{l_0}-2^m{y}_0^2\equiv -2^m{y}_0^2\not\equiv 0(\mathrm{mod}{2}^{m+1})$$
より${\upsilon }_2(x_0^2-y_0^2)=m$でり、$x_0,y_0$は奇数であるから${\upsilon }_2(x_0-y_0)=m-1$または${\upsilon }_2(x_0+y_0)=m-1$である。
　${\upsilon }_2(x_0-y_0)=m-1$のとき
$$(2y_0+\frac{x_0-y_0}{2^{m-1}}{)}^2+(2^m-1)(\frac{x_0-y_0}{2^{m-1}}{)}^2$$$$=\frac{1}{2^{m-2}}(x_0^2+(2^m-1)y_0^2)=2^{l_0-m+2}$$となり、$2y_0+{\displaystyle \frac{x_0-y_0}{2^{m-1}}},{\displaystyle \frac{x_0-y_0}{2^{m-1}}}$は共に奇数であるから$l=l_0-m+2\ne (m-2)k+2$は$(2y_0+{\displaystyle \frac{x_0-y_0}{2^{m-1}}},{\displaystyle \frac{x_0-y_0}{2^{m-1}}})$という解を持つので$l_0$の最小性に矛盾する。
　同様に${\upsilon }_2(x_0+y_0)=m-1$のとき$l=l_0-m+2$において$(-2y_0+{\displaystyle \frac{x_0+y_0}{2^{m-1}}},{\displaystyle \frac{x_0+y_0}{2^{m-1}}})$という解を持つので最小性に矛盾する。

$l=(m-2)k+2$のとき存在することの証明

$$x_1=y_1=1,$$
$$\begin{array}{r}\{\begin{array}{l}{x}_{i+1}={\displaystyle \frac{x_i-(2^m-1)y_i}{2}}\\ y_{i+1}={\displaystyle \frac{x_i+y_i}{2}}\end{array}\end{array}\cdots (2)$$
としたとき$(x,y)=(\left|x_k\right|,\left|y_k\right|)$が題意を満たすことを示す。特に$x_k,y_k$が奇数かつ$x_k^2+(2^m-1)y_k^2=2^{(m-2)k+2}$を示せば十分である。

$\cdot x_k,y_k$が奇数であることの証明

$$x_{i+1}+y_{i+1}\equiv x_i-(2^{m-1}-1)y_i\equiv x_i+y_i(\mathrm{mod}4)$$
より帰納的に$x_i+y_i\equiv x_1+y_1\equiv 2(\mathrm{mod}4)$である。$k\ge 2$のとき
$$2x_k=x_{k-1}-(2^m-1)y_{k-1}\equiv x_{k-1}+y_{k-1}\equiv 2(\mathrm{mod}4)$$
$$2y_k=x_{k-1}+y_{k-1}\equiv 2(\mathrm{mod}4)$$より$x_k,y_k$は奇数であり、$x_1,y_1$は明らかに奇数であるから示された。

$\cdot x_k^2+(2^m-1)y_k^2=2^{(m-2)k+2}$の証明

$x_1^2+(2^m-1)y_1^2=2^m$かつ
$$x_{i+1}^2+(2^m-1)y_{i+1}^2=({\displaystyle \frac{x_i-(2^m-1)y_i}{2}}{)}^2+(2^m-1)({\displaystyle \frac{x_i+y_i}{2}}{)}^2=2^{m-2}(x_i^2+(2^m-1)y_i^2)$$
であるから帰納的に得る。
　$(2)$から$x_i$を消去するように変形すると$y_1=y_2=1,y_{i+2}=y_{i+1}-2^{m-2}{y}_i$を得る。

高々$1$つしか存在しないことの証明

$$\begin{array}{r}\{\begin{array}{l}{x}^2+(2^m-1)y^2=2^l\\ x^{\prime 2}+(2^m-1)y^{\prime 2}=2^l\end{array}\end{array}\cdots (3)$$
となる正の奇数$x\ne x^{\prime },y\ne y^{\prime }$が存在すると仮定して矛盾を示す。
$$(x^2+(2^m-1)y^2-2^l)y^{\prime 2}-(x^{\prime 2}+(2^m-1)y^{\prime 2}-2^l)y^2=0$$
$$⟺(x{y}^{\prime }+x^{\prime }y)(x{y}^{\prime }-x^{\prime }y)=2^l(y^{\prime 2}-y^2)$$
$y^{\prime 2}-y^2$は$8$の倍数であるから$(x{y}^{\prime }+x^{\prime }y)(x{y}^{\prime }-x^{\prime }y)$は$2^{l+3}$の倍数であり、$x{y}^{\prime },x^{\prime }y$は奇数であるから$x{y}^{\prime }+x^{\prime }y$または$x{y}^{\prime }-x^{\prime }y$は$2^{l+2}$の倍数である。ここで$x{y}^{\prime }=x^{\prime }y$ならば$y^2=y^{\prime 2}⟹y=y^{\prime }$となり仮定に矛盾するので$x{y}^{\prime }\ne x^{\prime }y$である。$x{y}^{\prime }+x^{\prime }y\ge 2^{l+2}$または$|x{y}^{\prime }-x{y}^{\prime }|\ge 2^{l+2}$を得る。どちらにしろ$max(x{y}^{\prime },x^{\prime }y)\ge 2^{l+1}$であり任意の正の整数$a,b$において$max(a^2,b^2)\ge ab$であるから
$$2^{l+1}\le max(x{y}^{\prime },x^{\prime }y)\le max(x^2,y^2,x^{\prime 2},y^2)$$
しかしこれは$(3)$から大小関係より矛盾である。

　$k$が偶数のとき$l$は偶数であり、補題2より$\left|y_k\right|=1$となるのは$k=2$のみである。
　$k$が奇数のとき$$y_{i+2}=y_{i+1}-2^{m-2}{y}_i\equiv y_{i+1}+2^{m-2}(\mathrm{mod}{2}^{m-1})$$
であり、$i\ge 2$のとき
$$y_{i+2}\equiv y_{i+1}+2^{m-2}\equiv y_i+2^{m-1}\equiv y_i(\mathrm{mod}{2}^{m-1})$$
また$y_3\equiv 2^{m-2}+1(\mathrm{mod}{2}^{m-1})$であるから$k\ge 3$のとき$y_k\equiv 2^{m-2}+1(\mathrm{mod}{2}^{m-1})$となり特に$y_k=1$とならない。

数列$\{y_i\}$は三項間漸化式であるから解くと$y_i={\displaystyle \frac{({\displaystyle \frac{1+\sqrt{-7}}{2}}{)}^i-({\displaystyle \frac{1-\sqrt{-7}}{2}}{)}^i}{\sqrt{-7}}}$
二項定理で展開して整理すると
${\displaystyle \frac{({\displaystyle \frac{1+\sqrt{-7}}{2}}{)}^i-({\displaystyle \frac{1-\sqrt{-7}}{2}}{)}^i}{\sqrt{-7}}}$ $={\displaystyle \frac{1}{2^i\sqrt{-7}}(\sum _{j=0}^i{}_i{\mathrm{C}}_j(\sqrt{-7}{)}^j-\sum _{j=0}^i{}_i{\mathrm{C}}_j(-1{)}^j(\sqrt{-7}{)}^j)}$
$={\displaystyle \frac{1}{2^i\sqrt{-7}}(\sum _{j=0}^{[\frac{i}{2}]}({}_i{\mathrm{C}}_{2j}(\sqrt{-7}{)}^{2j}-{}_i{\mathrm{C}}_{2j}(-1{)}^{2j}(\sqrt{-7}{)}^{2j})+\sum _{j=0}^{[\frac{i-1}{2}]}({}_i{\mathrm{C}}_{2j+1}(\sqrt{-7}{)}^{2j+1}-{}_i{\mathrm{C}}_{2j+1}(-1{)}^{2j+1}(\sqrt{-7}{)}^{2j+1}))}$
$={\displaystyle \frac{1}{2^i\sqrt{-7}}(2\sqrt{-7}\sum _{j=0}^{[\frac{i-1}{2}]}{}_i{\mathrm{C}}_{2j+1}(-7{)}^j)}$
$={\displaystyle \frac{1}{2^{i-1}}\sum _{j=0}^{[\frac{i-1}{2}]}{}_i{\mathrm{C}}_{2j+1}(-7{)}^j}$

$j=1$のとき明らか。
$j\ge 2$のときルジャンドルの定理から
$${\upsilon }_7((2j+1)!)=\sum _{i=1}^{\infty }[{\displaystyle \frac{2j+1}{7^i}}]\le \sum _{i=1}^{\infty }{\displaystyle \frac{2j+1}{7^i}}={\displaystyle \frac{2j+1}{6}}\le j-1$$
より補題を得る。

上の等式の証明

$${}_{a+k}{\mathrm{C}}_{2j+1}(-7{)}^j\equiv {}_k{\mathrm{C}}_{2j+1}(-7{)}^j(\mathrm{mod}{7}^{{\upsilon }_7(a)+1})$$
$$⟺(a+k)(a+k-1)\cdots (a+k-2j)\cdot \frac{7^{{\upsilon }_7((2j+1)!)}}{(2j+1)!}\cdot \frac{(-7{)}^j}{7^{{\upsilon }_7((2j+1)!)}}\equiv k(k-1)\cdots (k-2j)\cdot \frac{7^{{\upsilon }_7((2j+1)!)}}{(2j+1)!}\cdot \frac{(-7{)}^j}{7^{{\upsilon }_7((2j+1)!)}}(\mathrm{mod}{7}^{{\upsilon }_7(a)+1})$$
ここで補題6より${\displaystyle \frac{(-7{)}^j}{7^{{\upsilon }_7((2j+1)!)}}}$は$7$の倍数であるから
$$(a+k)(a+k-1)\cdots (a+k-2j)\cdot \frac{7^{{\upsilon }_7((2j+1)!)}}{(2j+1)!}\equiv k(k-1)\cdots (k-2j)\cdot \frac{7^{{\upsilon }_7((2j+1)!)}}{(2j+1)!}(\mathrm{mod}{7}^{{\upsilon }_7(a)})$$
を示せば十分。${\displaystyle \frac{(2j+1)!}{7^{{\upsilon }_7((2j+1)!)}}}$は整数であり$7$と互いに素であるから
$$(a+k)(a+k-1)\cdots (a+k-2j)\cdot \frac{7^{{\upsilon }_7((2j+1)!)}}{(2j+1)!}\equiv k(k-1)\cdots (k-2j)\cdot \frac{7^{{\upsilon }_7((2j+1)!)}}{(2j+1)!}(\mathrm{mod}{7}^{{\upsilon }_7(a)})$$
$$⟺(a+k)(a+k-1)\cdots (a+k-2j)\equiv k(k-1)\cdots (k-2j)(\mathrm{mod}{7}^{{\upsilon }_7(a)})$$
この合同式は明らかに成り立つので補題を得る。

下の等式の証明

$${\upsilon }_7({}_{a+k}{\mathrm{C}}_{2j+1}(-7{)}^j)$$ $$={\upsilon }_7((a+k)(a+k-1)\cdots (a+1)a(a-1)\cdots (a+k-2j))-{\upsilon }_7((2j+1)!)+{\upsilon }_7((-7{)}^j)$$
$$\ge {\upsilon }_7(a)-{\upsilon }_7((2j+1)!)+j$$ $$\ge {\upsilon }_7(a)+1\because 補題6$$
よって補題を得る。

　存在すると仮定して矛盾を示す。
$k<k^{\prime }$とし$k^{\prime }-k=a$とする。
$a\equiv 0(\mathrm{mod}42)$であるからオイラーの定理より$7$と互いに素な整数$t$において$t^a\equiv 1(\mathrm{mod}{7}^{{\upsilon }_7(a)+1})$が成り立つことに注意する。補題5から
${\displaystyle -2^{k-1}=\sum _{j=0}^{[\frac{k-1}{2}]}{}_k{\mathrm{C}}_{2j+1}(-7{)}^j}$
${\displaystyle -2^{k-1}\equiv -2^{a+k-1}=\sum _{j=0}^{[\frac{a+k-1}{2}]}{}_{a+k}{\mathrm{C}}_{2j+1}(-7{)}^j(\mathrm{mod}{7}^{{\upsilon }_7(a)+1})}$
$$⟹\sum _{j=0}^{[\frac{k-1}{2}]}{}_k{\mathrm{C}}_{2j+1}(-7{)}^j\equiv \sum _{j=0}^{[\frac{a+k-1}{2}]}{}_{a+k}{\mathrm{C}}_{2j+1}(-7{)}^j(\mathrm{mod}{7}^{{\upsilon }_7(a)+1})$$
一方補題7から
${\displaystyle \sum _{j=0}^{[\frac{a+k-1}{2}]}{}_{a+k}{\mathrm{C}}_{2j+1}(-7{)}^j}$ ${\displaystyle \equiv {}_{a+k}{\mathrm{C}}_1+\sum _{j=1}^{\frac{k-1}{2}}{}_{a+k}{\mathrm{C}}_{2j+1}(-7{)}^j+\sum _{j=\frac{k+1}{2}}^{[\frac{a+k-1}{2}]}{}_{a+k}{\mathrm{C}}_{2j+1}(-7{)}^j}$
${\displaystyle \equiv a+k+\sum _{j=1}^{[\frac{k-1}{2}]}{}_k{\mathrm{C}}_{2j+1}(-7{)}^j+0(\mathrm{mod}{7}^{{\upsilon }_7(a)+1})}$
${\displaystyle ⟹\sum _{j=0}^{[\frac{k-1}{2}]}{}_k{\mathrm{C}}_{2j+1}(-7{)}^j\equiv a+k+\sum _{j=1}^{[\frac{k-1}{2}]}{}_k{\mathrm{C}}_{2j+1}(-7{)}^j(\mathrm{mod}{7}^{{\upsilon }_7(a)+1})}$
${\displaystyle ⟹k\equiv a+k(\mathrm{mod}{7}^{{\upsilon }_7(a)+1})⟹a\equiv 0(\mathrm{mod}{7}^{{\upsilon }_7(a)+1})}$
これは矛盾である。

$\left|y_1\right|=\left|y_2\right|=1$は簡単に得る。
$k\ge 3$のとき
補題5から$y_k=-1$のとき
$$-2^{k-1}=\sum _{j=0}^{[\frac{k-1}{2}]}{}_k{\mathrm{C}}_{2j+1}(-7{)}^j⟹-2^{k-1}\equiv k(\mathrm{mod}7)$$
上の合同式の周期は$21$であるから満たすような$k$を計算すると$k\equiv 3,5,13(\mathrm{mod}21)$また補題4から$k$は奇数であり$k\equiv 3,5,13(\mathrm{mod}42)$となる。
$k=3,5,13$のとき$y_k=-1$となるので補題8よりこれ以外に存在しない。よって補題を得る。