文献あり

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

問題

整数$n$に対して偶数なら$2$で割り、奇数なら二乗して$1$を引くという操作を繰り返したとき有限回の操作で整数が$0$になるとき、元の整数を良い整数する。良い整数を全て求めよ。

予想

良い整数は
$n=±2^l \cdot m \quad l \in \mathbb{Z}_{ \geq 0 },m \in \lbrace 2^k-1 ~|~ k \in \mathbb{N} \rbrace \cup \lbrace 2^k+1 ~|~ k \in \mathbb{N} \rbrace \cup \lbrace 11,23,181 \rbrace $
であると予想している。
　以下の予想を仮定し、議論を行う。この予想より弱い主張を後で解く。

正の整数$x$において$2^l±2^m+1=x^2$を満たす正の整数$l,m$が存在するとき$x\in \lbrace 2^k-1 ~|~ k \in \mathbb{N} \rbrace \cup \lbrace 2^k+1 ~|~ k \in \mathbb{N} \rbrace \cup \lbrace 11,23,181 \rbrace $である。

予想が正しいと仮定しての証明

　まず$n$は正かつ奇数であるとして良い。
　正の奇数に対して定義された関数$f$を$$f(x)= \begin{eqnarray} \left\{ \begin{array}{l} ~~~~~~~1 \qquad~~ x=1 \\ \dfrac{x^2-1}{2^{ \upsilon_2(x^2-1) }} \quad x≠1 \end{array} \right. \end{eqnarray}$$
と定める。$n$が良い整数であることと正の整数$a$が存在して$f^a(n)=1$となることが同値である。
$$ f(2^m±1)= \begin{eqnarray} \left\{ \begin{array}{l} ~~~~~~~1 \qquad~~ m=1\\ 2^{m-1}±1\quad m \geq 2 \end{array} \right. \end{eqnarray} $$
であるから$ A= \lbrace 2^k-1 ~|~ k \in\mathbb{N} \rbrace ,$$ B= \lbrace 2^k+1 ~|~ k \in \mathbb{N} \rbrace $と定めたとき$n \in A\cup B$は良い整数である。以降$n \notin A\cup B$で良い整数を考える。
　$n\notin A\cup B$が良い整数とするとある正の整数$a$が存在して$f^a(n)=1$である。$f(A\cup B)=A\cup B$であるからある正の奇数$x\notin A\cup B$が存在して$ f(x)\in A\cup B$となる。このような$x$について考える。
　$f(x) \in A\cup B$$ \Longleftrightarrow \dfrac{x^2-1}{2^{ \upsilon_2(x^2-1) }}=2^k±1$$ \Longleftrightarrow 2^l±2^m+1=x^2 $を満たす正の整数$l,m$が存在する。
この同値が成り立ち、$x\notin A\cup B$かつ$2^l±2^m+1=x^2$となる$x$は予想から$x \in \lbrace 11,23,181 \rbrace $である。よって
$$x\notin A\cup B,f(x) \in A\cup B \Longrightarrow x\in \lbrace 11,23,181 \rbrace $$
　次に$f(x')\in \lbrace 11,23,181 \rbrace $となる$x'$を考える。$ 11,23,181$は全て素数であるので$p\in \lbrace 11,23,181 \rbrace $とする。$p\cdot 2^{\upsilon_2(x'^2-1)}+1=x'^2$
$ \Longrightarrow p\cdot 2^{\upsilon_2(x'^2-1)-2}= \dfrac{x'+1}{2} \dfrac{x'-1}{2} $
$ \Longrightarrow \lbrace p,2^{\upsilon_2(x'^2-1)-2} \rbrace =\bigg\lbrace \dfrac{x'+1}{2} ,\dfrac{x'-1}{2} \bigg\rbrace $
$ \Longrightarrow \left| p-2^{\upsilon_2(x'^2-1)-2} \right|=1 $
しかしこれは矛盾である。よって$f(x')\in \lbrace 11,23,181 \rbrace $となる$x'$は存在しない。
　まとめると、正の整数$a$が存在して$f^a(n)=1$となるような正の奇数$n$は$\lbrace 2^k-1 ~|~ k \in \mathbb{N} \rbrace \cup \lbrace 2^k+1 ~|~ k \in \mathbb{N} \rbrace \cup \lbrace 11,23,181 \rbrace $のみであり、よい整数はこれに$2$の累乗と$ ±$を掛けたものが答えとなる。

予想について

　私はこの予想を証明することが出来なかった。この予想より弱い主張を以下を示す。

$2^l-2^m+1=x^2$となる正の整数$l,m$が存在するような正の整数$x \notin A \cup B$は$ 11,181$のみである。
$(2^7-2^3+1=11^2,2^{15}-2^3+1=181^2)$

定理1の証明

$$2^l-2^m+1=x^2 ~~\cdots (1)$$
　方針としては$x^2+(2^m-1)y^2=2^l$となる正の奇数$x,y$が$l$が特定の条件のとき一意に存在し、その$x,y$の値を求めることが原理的に可能であるので$y=1$となるものを求める。
　明らかに$l \geq m$であり、$x^2-1$は$8$の倍数であるから$m \geq 3$である。

$ (1)$において$l$が偶数のとき$l=m,2m-2$が必要。

$(1)$から$x^2≡1 \pmod{2^m} $$ \Longrightarrow x≡±1 \pmod{2^{m-1}} $$ \Longrightarrow x=1 ~or ~x \geq 2^{m-1}-1$
$x=1$ならば$l=m$であるので$x \geq 2^{m-1}-1$とする。そのとき
$2^l-2^m+1=x^2 \geq 2^{2m-2}-2^m+1$$ \Longrightarrow l \geq 2m-2$
一方、$2^l-2^m+1=x^2<(2^{ \frac{l}{2} })^2$$ \Longrightarrow 2^l-2^m+1 \leq (2^{ \frac{l}{2} }-1)^2=2^l-2^{ \frac{l}{2}+1 }+1$
$ \Longrightarrow l \leq 2m-2$
よって$l=2m-2$である。

$$x^2+(2^m-1)y^2=2^l $$
となる正の奇数$x,y$が存在する必要十分条件は$l=(m-2)k+2 \quad (k \in \mathbb{N} )$でありそのような$x,y$は一意に存在する。また、そのような$y$の値は $$y_1=y_2=1,y_{i+2}=y_{i+1}-2^{m-2}y_i $$における$ \left| y_{k} \right| $である。

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

$l≠(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 \geq 1+2^m-1=2^m$$
より$l_0 \geq m$であり$l_0=m$であるとすると$l_0≠(m-2)k+2$に矛盾するので$l_0 \geq m+1$である。
$$x_0^2-y_0^2≡x_0^2+(2^m-1)y_0^2≡2^{l_0}≡0 \pmod{2^m}$$
$$x_0^2-y_0^2≡x_0^2+(2^m-1)y_0^2-2^my_0^2≡2^{l_0}-2^my_0^2≡-2^my_0^2\not\equiv 0 \pmod{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 $のとき
$$\bigg(2y_0+\frac{x_0-y_0}{2^{m-1}}\bigg)^2+(2^m-1)\bigg(\frac{x_0-y_0}{2^{m-1}}\bigg)^2$$$$= \frac{1}{2^{m-2}}(x_0^2+(2^m-1)y_0^2)=2^{l_0-m+2} $$となり、$2y_0+\dfrac{x_0-y_0}{2^{m-1}},\dfrac{x_0-y_0}{2^{m-1}}$は共に奇数であるから$l=l_0-m+2≠(m-2)k+2$は$\bigg(2y_0+\dfrac{x_0-y_0}{2^{m-1}},\dfrac{x_0-y_0}{2^{m-1}}\bigg) $という解を持つので$l_0$の最小性に矛盾する。
　同様に$\upsilon_2(x_0+y_0)=m-1$のとき$l=l_0-m+2$において$\bigg( -2y_0+\dfrac{x_0+y_0}{2^{m-1}},\dfrac{x_0+y_0}{2^{m-1}}\bigg) $という解を持つので最小性に矛盾する。

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

$$x_1=y_1=1,$$
$$ \begin{eqnarray} \left\{ \begin{array}{l} x_{i+1}= \dfrac{x_i-(2^m-1)y_i}{2} \\ y_{i+1}=\dfrac{x_i+y_i}{2} \end{array} \right. \end{eqnarray} \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}≡x_i-(2^{m-1}-1)y_i≡x_i+y_i \pmod{4}$$
より帰納的に$x_i+y_i≡x_1+y_1≡2 \pmod{4} $である。$k\geq 2$のとき
$$2x_k=x_{k-1}-(2^m-1)y_{k-1}≡x_{k-1}+y_{k-1}≡2 \pmod{4} $$
$$2y_k=x_{k-1}+y_{k-1}≡2 \pmod{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=\bigg( \dfrac{x_i-(2^m-1)y_i}{2} \bigg)^2+(2^m-1)\bigg( \dfrac{x_i+y_i}{2}\bigg )^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{eqnarray} \left\{ \begin{array}{l} x^2+(2^m-1)y^2=2^l \\ x'^2+(2^m-1)y'^2=2^l \end{array} \right. \end{eqnarray}\quad\cdots (3) $$
となる正の奇数$x≠x',y≠y'$が存在すると仮定して矛盾を示す。
$$(x^2+(2^m-1)y^2-2^l)y'^2-(x'^2+(2^m-1)y'^2-2^l)y^2=0$$
$$ \Longleftrightarrow (xy'+x'y)(xy'-x'y)=2^l(y'^2-y^2)$$
$y'^2-y^2$は$8$の倍数であるから$(xy'+x'y)(xy'-x'y)$は$2^{l+3}$の倍数であり、$xy',x'y$は奇数であるから$xy'+x'y$または$xy'-x'y$は$2^{l+2}$の倍数である。ここで$xy'=x'y$ならば$y^2=y'^2 \Longrightarrow y=y'$となり仮定に矛盾するので$xy'≠x'y$である。$xy'+x'y \geq 2^{l+2}$または$\left| xy'-xy' \right|\geq 2^{l+2}$を得る。どちらにしろ$\max(xy',x'y)\geq 2^{l+1}$であり任意の正の整数$a,b$において$\max(a^2,b^2)\geq ab$であるから
$$2^{l+1}\leq\max(xy',x'y)\leq\max(x^2,y^2,x'^2,y^2)$$
しかしこれは$(3)$から大小関係より矛盾である。

以降$ \left| y_{k} \right| =1$となる$k$のみ考えれば良い。

$k$が偶数のとき$ \left| y_k \right| =1$となるものは$k=2$のみ。
また、$k$が奇数のとき$y_k=1$となるものは$k=1$のみ。

　$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} \pmod{2^{m-1}} $$
であり、$i \geq 2$のとき
$$y_{i+2}≡y_{i+1}+2^{m-2}≡y_i+2^{m-1}≡y_i \pmod{2^{m-1}} $$
また$y_3≡2^{m-2}+1 \pmod{2^{m-1}} $であるから$k \geq 3$のとき$y_k≡2^{m-2}+1 \pmod{2^{m-1}} $となり特に$y_k=1$とならない。

　以降$y_k=-1$となる奇数$k\geq 3$について考える。
　$m$が$3 $のときとそれ以外のときに分けて考える。

$m \geq 4$のとき

$$y_{i+2}≡y_{i+1}-2^{m-2}y_i≡y_{i+1} \pmod{4} $$
と$y_1=y_2=1$と合わせて$y_k≡1 \pmod{4} $となり特に$y_k=-1$とならないので$ \left| y_k \right|=1 $となる$k$は$1,2$のみ。このとき$l=m,2m-2$であり$x=1,2^{m-1}-1$となり、このとき$x\in A\cup B$となるので定理$1$を満たす$x$は存在しない。

$m=3$のとき

$$y_1=y_2=1,y_{i+2}=y_{i+1}-2y_i $$

$\displaystyle y_i= \frac{1}{2^{i-1}} \sum_{j=0}^{ \lbrack \frac{i-1}{2} \rbrack } {}_i \mathrm{ C }_{2j+1}(-7)^j $

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

正の整数$j$において$j- \upsilon_7((2j+1)!) \geq 1$

$j=1$のとき明らか。
$j \geq 2$のときルジャンドルの定理から
$$\upsilon_7((2j+1)!) =\sum_{i=1}^{∞} \bigg \lbrack \dfrac{2j+1}{7^i}\bigg\rbrack \leq \sum_{i=1}^{∞} \dfrac{2j+1}{7^i}=\dfrac{2j+1}{6} \leq j-1 $$
より補題を得る。

$k$を正の奇数、$1 \leq j \leq \dfrac{k-1}{2} $のとき$${}_{a+k} \mathrm{ C }_{2j+1}(-7)^j≡ {}_k \mathrm{ C }_{2j+1}(-7)^j \pmod{7^{ \upsilon_7(a)+1 }} $$
また、$j \geq \dfrac{k+1}{2} $のとき
$${}_{a+k} \mathrm{ C }_{2j+1}(-7)^j≡0 \pmod{7^{ \upsilon_7(a)+1 }} $$

上の等式の証明

$${}_{a+k} \mathrm{ C }_{2j+1}(-7)^j≡ {}_k \mathrm{ C }_{2j+1}(-7)^j \pmod{7^{ \upsilon_7(a)+1 }} $$
$$ \Longleftrightarrow (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)!) }} ≡k(k-1) \cdots (k-2j) \cdot \frac{7^{\upsilon_7((2j+1)!) }}{(2j+1)!}\cdot \frac{(-7)^j}{7^{\upsilon_7((2j+1)!) }} \pmod{7^{\upsilon_7(a)+1}}$$
ここで補題6より$\dfrac{(-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)!} ≡k(k-1) \cdots (k-2j)\cdot \frac{7^{\upsilon_7((2j+1)!) }} {(2j+1)!} \pmod{7^{\upsilon_7(a)}}$$
を示せば十分。$\dfrac{(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)!} ≡k(k-1) \cdots (k-2j)\cdot \frac{7^{\upsilon_7((2j+1)!) }} {(2j+1)!} \pmod{7^{\upsilon_7(a)}}$$
$$ \Longleftrightarrow (a+k)(a+k-1) \cdots (a+k-2j)≡k(k-1) \cdots (k-2j) \pmod{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)$$
$$ \geq \upsilon_7(a)-\upsilon_7((2j+1)!)+j $$ $$\geq\upsilon_7(a)+1\quad \because 補題~6$$
よって補題を得る。

$y_k=y_{k'}=-1$かつ$k≡k' \pmod{42} $となる相異なる正の整数の組$(k,k')$は存在しない。

　存在すると仮定して矛盾を示す。
$k< k'$とし$k'-k=a$とする。
$a≡0 \pmod{42} $であるからオイラーの定理より$7$と互いに素な整数$t$において$t^a≡1 \pmod{7^{\upsilon_7(a)+1}} $が成り立つことに注意する。補題5から
$\displaystyle -2^{k-1}= \sum_{j=0}^{ \lbrack \frac{k-1}{2} \rbrack } {}_k \mathrm{ C }_{2j+1}(-7)^j $
$\displaystyle -2^{k-1}≡-2^{a+k-1}= \sum_{j=0}^{ \lbrack \frac{a+k-1}{2} \rbrack } {}_{a+k} \mathrm{ C }_{2j+1}(-7)^j \pmod{7^{\upsilon_7(a)+1}} $
$$ \Longrightarrow \sum_{j=0}^{ \lbrack \frac{k-1}{2} \rbrack } {}_k \mathrm{ C }_{2j+1}(-7)^j ≡ \sum_{j=0}^{ \lbrack \frac{a+k-1}{2} \rbrack } {}_{a+k} \mathrm{ C }_{2j+1}(-7)^j \pmod{7^{\upsilon_7(a)+1}}$$
一方補題7から
$ \displaystyle \sum_{j=0}^{ \lbrack \frac{a+k-1}{2} \rbrack } {}_{a+k} \mathrm{ C }_{2j+1}(-7)^j $ $ \displaystyle≡{}_{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} }^{ \lbrack \frac{a+k-1}{2} \rbrack}{}_{a+k} \mathrm{ C }_{2j+1}(-7)^j $
$\displaystyle≡a+k+ \sum_{j=1}^{ \lbrack \frac{k-1}{2} \rbrack } {}_k \mathrm{ C }_{2j+1}(-7)^j+0 \pmod{7^{\upsilon_7(a)+1}}$
$\displaystyle \Longrightarrow \sum_{j=0}^{ \lbrack \frac{k-1}{2} \rbrack } {}_k \mathrm{ C }_{2j+1}(-7)^j≡a+k+ \sum_{j=1}^{ \lbrack \frac{k-1}{2} \rbrack } {}_k \mathrm{ C }_{2j+1}(-7)^j \pmod{7^{\upsilon_7(a)+1}}$
$\displaystyle \Longrightarrow k≡a+k \pmod{7^{\upsilon_7(a)+1}} \Longrightarrow a≡0 \pmod{7^{\upsilon_7(a)+1}}$
これは矛盾である。

$ \left| y_k \right|=1 $となる$k$は$k=1,2,3,5,13$のみ。

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