https://tsujimotter.hatenablog.com/entry/approximation-of-root-41

突然ですが、みなさんは $\sqrt{41}$ の値がいくつかご存知ですか？

普段数学をやっていても、なかなかこの値の計算をすることはないですよね。

この問題を考えるきっかけとなったのは、三平方の定理です。

tsujimotterは、数学が苦手な学生向けの数学講義をしていて、三平方の定理の練習問題を作ろうと思っていたときのことです。下図左の斜辺の長さを求める問題を作ろうとして、間違えて右の方の問題を出してしまいました。

右側の問題について計算してみると、三平方の定理より斜辺 $x$ は

$x^2 = 4^2 + 5^2 = 16 + 25 = 41$

を満たすので、 $x = \sqrt{41}$ が得られます。

えっ、 $\sqrt{41}$ ってなんだよ、いったいいくつになるんだよ、と学生からは非難轟々（？）でしたが、
その場で $\sqrt{41}$ を概算する方法を思いついて場を収めることができました（？）。

概算の方法がちょっと面白かったので、その紹介をしたいと思います。

また、この問題を考えていくうちに、もっと一般化させたくなってきました。一般化していくと、意外なことに数論的にも少し面白いことが分かってきました。

なんと今回紹介する $\sqrt{41}$ の概算の方法を突き詰めていくと、先日記事としてまとめた「ニュートン法（前々回）」や「ヘンゼルの補題（前回）」が出てくるのです。

（実は、前回・前々回の記事は、今回のために準備した記事でした。）

ぜひ最後までご覧ください！

なお、今回の記事は、先日開催された日曜数学会ミニin北海道でtsujimotterが発表した内容をもとにしています。
tsujimotter.hatenablog.com

動画も撮影しているので、そのうち発表の様子もアップロードできたらと思っています。そちらもお楽しみに。

$\sqrt{41}$ の概算方法

さてその方法ですが、tsujimotterが気づいたのは次の式です：

$64^2 = 2^{12} = 4096 \hspace{100px} (1)$

$2$ のべき乗の表は、数学好きの人なら覚えている人も多いと思います：

$2^1 = 2$

$2^2 = 4$

$2^3 = 8$

$2^4 = 16$

$2^5 = 32$

$2^6 = 64$

$2^7 = 128$

$2^8 = 256$

$2^9 = 512$

$2^{10} = 1024$

$2^{11} = 2048$

$2^{12} = 4096$

ここで、 $2^6 = 64$ なので、それを2乗すると $2^{12} = 4096$ になります。

これにより式 $(1)$ を得るわけですが、面白いことに $4096$ は $4100$ に非常に近い値となります。そこで、式 $(1)$ の両辺を $100$ で割って

$6.4^2 = 40.96 \fallingdotseq 41$

が得られます。よって両辺の平方根をとることで

$\sqrt{41} \fallingdotseq 6.4 \hspace{100px} (2)$

という概算が得られるというわけです。あっという間でしたね！

こんなわけで、 $\sqrt{41}$ の概算値 $6.4$ が得られたわけですが、これは本当に近い値なんでしょうか。

実際、電卓で計算してみると

$\sqrt{41} = \mathbf{6.4}03124\ldots$

となり、小数点以下1桁まで計算できています。

実は、この近似式を用いてもう少しだけ計算を進めることができます。

先ほどの式

$64^2 = 4096 = 4100 - 4$

からスタートして、両辺を $100$ で割ります。

$6.4^2 = 41 - 0.04$

$\therefore 41 = 6.4^2 + 0.04$

両辺の平方根をとると、次のように計算を進めることができます：

$\begin{align*} \sqrt{41} &= \sqrt{6.4^2 + 0.04} \\ &= 6.4 \cdot \left(1 + \frac{0.04}{6.4^2}\right)^{\frac{1}{2}} \\ &\fallingdotseq 6.4 \cdot \left(1 + \frac{0.04}{2\cdot 6.4^2}\right) \\ &= 6.4 + \frac{0.04}{2\cdot 6.4} \\ &= 6.4 + 0.003125 \\ &= 6.403125 \end{align*}$

途中の近似計算は、 $x \ll 1$ のときの

$\displaystyle (1 + x)^{\frac{1}{2}} \fallingdotseq 1 + \frac{1}{2}x$

という近似を用いています。

この近似式は、左辺のテイラー展開（あるいは一般化二項展開）を1次で打ち切ったものと考えることができます。あるいはニュートン法の1ステップによる近似と同値であることも以下の記事で示しました：
tsujimotter.hatenablog.com

結果として得られた

$\sqrt{41} \fallingdotseq \mathbf{6.40312}5$

ですが、これは小数点以下5桁まで一致する、非常によい近似となっています。
（ここまでは十分紙の上の手計算でも行えるのもポイントです。）

なお、話の流れ上、いきなり上の解法を説明しましたが、もう少しオーソドックスに概算する方法もあります。

$41$ を挟む平方数を考えると

$6^2 = 36 < 41 < 49 = 7^2$

があります。したがって

$6 < \sqrt{41} < 7$

が成り立ちますので、 $\sqrt{41}$ の整数部分が $6$ であることが分かります。

さらに、小数第一位を求めるために $6.1^2 = 37.21, \;\; 6.2^2 = 38.44, \;\; 6.3^2 = 39.69, \;\; 6.4^2 = 40.96, \;\; 6.5^2 = 42.25$ と順に計算していくと

$6.4^2 < 41 < 6.5^2$

であることがわかり、 $\sqrt{41} = \mathbf{6.4}\ldots$ までが確定します。

この記事では、この素朴な方法そのものよりも、「なぜ $6.4$ という値がこんなにうまく出てくるのか？」という構造の方にフォーカスして話を進めていきます。

整数論的な構造を考える（一般化）

さて、 $\sqrt{41}$ そのものの概算は以上でおしまいなのですが、同様の方法で $\sqrt{41}$ 以外のほかの例は作れないのかという疑問が浮かんできます。すなわち、もっと一般化できないのかという疑問です。

$\sqrt{41}$ の近似の背景には

$64^2 = 4100 - 4$

という式がありました。これを一般化して

$x^2 = 100N + a \hspace{100px} (3)$

という「構造」を考えてみましょう。 $x^2$ が $100N$ を近似して、その誤差が $a$ であるという感じですね。この式から平方根の近似式

$\displaystyle \sqrt{N} \fallingdotseq \frac{x}{10}$

が得られます。誤差の $a$ は小さければ小さいほどよいのですが、さまざまな $a$ を考えて、対応する $x, N$ を探してみたいと思います。

ここで、上の式は $\bmod{100}$ で考えると見通しが良くなります。実際

$x^2 \equiv a \pmod{100} \hspace{100px} (4)$

となります。合同式 $(4)$ は $a$ が $\bmod{100}$ の平方剰余であることを意味しています。 $a$ が平方剰余であるときに限り、対応する $x, N$ が存在します。

$\sqrt{41}$ のときは $a = -4$ の解というわけです。

一般に、上記の合同式を解くためには中国剰余定理が使えます。 $100 = 4\cdot 25$ （ $4$ と $25$ は互いに素）なので、 $x$ が合同式 $(4)$ の解であることと、 $x$ が以下の連立合同式

$\begin{cases} x^2 \equiv a \pmod{4} \\ x^2 \equiv a \pmod{25} \end{cases}$

の解であることは同値です。

以下の (i), (ii) のそれぞれについて、場合分けして考えます。

(i) $x^2 \equiv a \pmod{4}$ が解をもつ $a$ の条件：
$x \equiv 0, 1, 2, 3\pmod{4}$ をそれぞれ2乗すると

$0^2 \equiv 0\pmod{4}$

$1^2 \equiv 1\pmod{4}$

$2^2 \equiv 0\pmod{4}$

$3^2 \equiv 1\pmod{4}$

より、 $a \equiv 0, 1\pmod{4}$ のときのみ解が存在する。

(ii) $x^2 \equiv a \pmod{25}$ が解をもつ $a$ の条件：
$x \equiv 0, 1, 2, 3, \ldots , 12 \pmod{25}$ をそれぞれ2乗して考えればよいです（ $13$ 以降は対称性から考える必要はない）。

これより

$a \equiv 0, 1, 4, 6, 9, 11, 14, 16, 19, 21, 24$

の11個が解をもつ $a$ の条件となります。

(i), (ii) より

$a \equiv 0, 1, 4, 9, 16, 21, 24, 25, 29, 36, 41, 44, 49, 56, 61, 64, 69, 76, 81, 84, 89, 96$

が連立合同式が解を持つ条件となり、中国剰余定理より上の合同式 $(4)$ が解を持つ条件と一致します。

分かりやすいように、 $\pm$ の符号を使って絶対最小剰余で考えると

$a \equiv 0, 1, \pm 4, 9, -11, \pm 16, -19, 21, \pm 24, 25, 29, -31, \pm 36, -39, 41, \pm 44, 49$

となります。

そこで、それぞれの $a$ について解 $x$ を具体的に計算してみましょう。

自明なケース： $a\equiv k^2 \pmod{100}$ の解（平方数）

・・・といいたいところなのですが、たとえば最初の方にある $a = 1, 4, 9, 16$ といった数は平方数であり、この場合は議論が簡単になります。

平方数の場合は $a = k^2$ とおくと

$x^2 \equiv k^2 \pmod{100}$

の解を求めることになりますが、このケースでは移項して因数分解することができます：

$x^2 - k^2 = (x - k) (x + k) \equiv 0 \pmod{100}$

このようにすると、 $x - k$ と $x + k$ を掛けて $100$ で割り切れるパターンが解になることが簡単にわかります。たとえば、次のような解が簡単に見つかります：

$x - k$ が $0$ に一致する
$x - k$ が $2$ で割り切れて、 $x + k$ が $50$
$x - k$ が $50$ で、 $x + k$ が $2$ で割り切れる
$x + k$ が $100$ に一致する

自明なケースでは、次のような解が得られます。

★ $a\equiv 1\pmod{100}$ の解：
合同式

$x^2 \equiv 1 \pmod{100}$

の解 $x$ は以下の4つ：

$x - 1$ が $0$ に一致する → $x \equiv 1$
$x - 1$ が $2$ で割り切れて、 $x + 1$ が $50$ → $x \equiv 49$
$x - 1$ が $50$ で、 $x + 1$ が $2$ で割り切れる → $x \equiv 51$
$x + 1$ が $100$ に一致する → $x \equiv 99$

よって、対応する平方根の近似は次のとおり：

$1^2 = 1 = 0 + 1$ より $\sqrt{0} \fallingdotseq 0.1$
$49^2 = 2401 = 2400 + 1$ より $\sqrt{24} \fallingdotseq 4.9$
$51^2 = 2601 = 2600 + 1$ より $\sqrt{26} \fallingdotseq 5.1$
$99^2 = 9801 = 9800 + 1$ より $\sqrt{98} \fallingdotseq 9.9$

★ $a\equiv 9\pmod{100}$ の解：
合同式

$x^2 \equiv 9 \pmod{100}$

の解 $x$ は以下の4つ：

$x - 3$ が $0$ に一致する → $x \equiv 3$
$x - 3$ が $2$ で割り切れて、 $x + 3$ が $50$ → $x \equiv 47$
$x - 3$ が $50$ で、 $x + 3$ が $2$ で割り切れる → $x \equiv 53$
$x + 3$ が $100$ に一致する → $x \equiv 97$

よって、対応する平方根の近似は次のとおり：

$3^2 = 9 = 0 + 9$ より $\sqrt{0} \fallingdotseq 0.3$
$47^2 = 2209 = 2200 + 9$ より $\sqrt{22} \fallingdotseq 4.7$
$53^2 = 2809 = 2800 + 9$ より $\sqrt{28} \fallingdotseq 5.3$
$97^2 = 9409 = 9400 + 9$ より $\sqrt{94} \fallingdotseq 9.7$

非自明なケース： $a\equiv -4\pmod{100}$ の解

非自明なケース（平方数を除いたパターン）としては

$a \equiv -4, -11, -16, -19, 21, \ldots$

が検討対象となります。ここでは、具体的に $a\equiv -4$ のときを考えましょう。

考えたい合同式は

$x^2 \equiv -4\pmod{100}$

です。よって連立合同式

$\begin{cases} x^2 \equiv -4 \pmod{4} \\ x^2 \equiv -4 \pmod{25} \end{cases}$

を考えると、それぞれの解は $x \equiv 0, 2\pmod{4}$ と $x\equiv 11, 14\pmod{25}$ となります。

よって中国剰余定理より

$x \equiv 14, 36, 64, 86 \pmod{100}$

が元の合同式の解となります。

それぞれについて、対応する平方根の近似を求めてみましょう：

$14^2 = 196 = 200 - 4$ より $\sqrt{2} \fallingdotseq 1.4$
$36^2 = 1296 = 1300 - 4$ より $\sqrt{13} \fallingdotseq 3.6$
$64^2 = 4096 = 4100 - 4$ より $\sqrt{41} \fallingdotseq 6.4$
$86^2 = 7396 = 7400 - 4$ より $\sqrt{74} \fallingdotseq 8.6$

ここで3番目の式は、冒頭で紹介した $\sqrt{41} \fallingdotseq 6.4$ ですね。

他にも $\sqrt{2}, \sqrt{13}, \sqrt{74}$ の近似値が得られました。面白いですね！

そんなわけで、合同式

$x^2 \equiv a \pmod{100} \hspace{100px} (4\text{再掲})$

を考えることで、 $\sqrt{N} \fallingdotseq x$ という近似式が次々と得られることが分かりました。

さらに発展・・・ヘンゼルの補題へ

先ほどまでは

$x^2 \equiv a \pmod{100}$

を考えて、 $\sqrt{N} \fallingdotseq x$ という、 $\sqrt{N}$ の小数点以下1桁の近似式を得ることができました。

これをもっと発展させて

$x^2 \equiv a \pmod{10^n}$

の解を考えたくなるのは自然な発想でしょう。

これをすることで、小数点以下2桁・3桁・4桁と、どんどん精度の高い近似式が得られることが期待できます。

やはり中国剰余定理より

$\begin{cases} x^2 \equiv a \pmod{2^n} \\ x^2 \equiv a \pmod{5^n} \end{cases}$

なる連立合同式を考えることと同値です。それぞれの式に対して、具体的な $a$ の元で解の存在を考えてみましょう。

★ $a\equiv -4\pmod{10^n}$ のとき

この条件の元で、それぞれの合同式について考えてみたいと思います。

$x^2 \equiv -4 \pmod{5^n}$ の解を $n = 1, 2, 3, 4, 5, \ldots$ について考えてみると次のようになります：

$x^2 \equiv -4\pmod{5}$ の解　→ $x\equiv 1, 4\pmod{5}$
$x^2 \equiv -4\pmod{5^2}$ の解　→ $x\equiv 11, 14\pmod{5^2}$
$x^2 \equiv -4\pmod{5^3}$ の解　→ $x\equiv 11, 114\pmod{5^3}$
$x^2 \equiv -4\pmod{5^4}$ の解　→ $x\equiv 261, 364\pmod{5^4}$
$x^2 \equiv -4\pmod{5^5}$ の解　→ $x\equiv 2136, 989\pmod{5^5}$

このように、 $n = 5$ までは解が2つずつ存在することがわかりました。

実は、「ヘンゼルの補題」により、この先もずっと解が存在することが保証されています。

tsujimotter.hatenablog.com

実際、 $F(x) = x^2 + 4$ とすると、 $F'(x) = 2x$ となります。ここで

$F'(1) = 2 \not\equiv 0\pmod{5}, \; F'(4) = 8 \not\equiv 0\pmod{5}$

を満たすため、ヘンゼルの補題の条件を満たします。

したがって、

$x_n \equiv 1\pmod{5}, \;\; F(x_n) \equiv 0 \pmod{5^n}$

$y_n \equiv 4\pmod{5}, \;\; F(y_n) \equiv 0 \pmod{5^n}$

を満たす $x_n, y_n$ が任意の $n$ でそれぞれ一意的に存在します。

すなわち、この $x_n$ の系列、 $y_n$ の系列を $5$ 進数と思うと、 $x^2 = -4$ は $5$ 進数に2つの解を持つということになります。

$\bmod{5^n}$ の場合はちゃんとヘンゼルの補題が成立する、すなわちヘンゼるパターンというわけですね！

同様に、 $x^2 \equiv -4 \pmod{2^n}$ の解を $n = 1, 2, 3, 4, 5, \ldots$ について考えてみたいのですが、ここで問題が生じます：

$x^2 \equiv -4\pmod{2}$ の解　→ $x\equiv 0\pmod{2}$
$x^2 \equiv -4\pmod{2^2}$ の解　→ $x\equiv 0, 2\pmod{2^2}$
$x^2 \equiv -4\pmod{2^3}$ の解　→ $x\equiv 2, 6\pmod{2^3}$
$x^2 \equiv -4\pmod{2^4}$ の解　→ 解なし
$x^2 \equiv -4\pmod{2^5}$ の解　→ 解なし

$\bmod{2^4}$ で解がなくなってしまいました。以降は、以下の理屈により解が存在しないことが分かります。

仮に $n \geq 4$ において

$x_n^2 \equiv -4 \pmod{2^n}$

の解があったとすると、 $\bmod{2^4}$ をとっても合同式が成り立つはずです。

$x_n^2 \equiv -4 \pmod{2^4}$

しかし、前述の計算により、 $\bmod{2^4}$ には解が存在しないから不合理です。

すなわち、 $x^2 = -4$ は $2$ 進整数の範囲には解を持たないということが分かりました。

つまり、ヘンゼルの補題が成り立たないパターン、ヘンゼらないパターンというわけですね。

★ $a\equiv 41 \pmod{10^n}$ のとき

解がちゃんとあるパターンも考えたいので、 $a = 41$ としてみましょう。

$a = 41$ を選んだ理由は、色々試行錯誤をした結果、解を見つけた最初の例だったからです。他の $a$ ではなかなか解が見つからないのですが、その理由は後ほど分かります。

され、 $x^2 \equiv 41 \pmod{5^n}$ の解を $n = 1, 2, 3, 4, 5, 6, \ldots$ について考えてみると次のようになります：

$x^2 \equiv 41\pmod{5}$ の解　→ $x\equiv 1, 4\pmod{5}$
$x^2 \equiv 41\pmod{5^2}$ の解　→ $x\equiv 21, 4\pmod{5^2}$
$x^2 \equiv 41\pmod{5^3}$ の解　→ $x\equiv 71, 54 \pmod{5^3}$
$x^2 \equiv 41\pmod{5^4}$ の解　→ $x\equiv 71, 554\pmod{5^4}$
$x^2 \equiv 41\pmod{5^5}$ の解　→ $x\equiv 696, 2429\pmod{5^5}$
$x^2 \equiv 41\pmod{5^6}$ の解　→ $x\equiv 696, 14929\pmod{5^6}$

この場合も、「ヘンゼルの補題」により、この先もずっと解が存在することが保証されます。

したがって、それぞれの解を $\mathbf{x} = (x_n)_{n=1}^{\infty}, \;\; \mathbf{y} = (y_n)_{n=1}^{\infty}$ とおくと、 $\mathbf{x}, \mathbf{y}$ は $\mathbb{Z}_5$ の元となり $F(X) = X^2 - 41 = 0$ の2解となります。

同様に、 $x^2 \equiv 41 \pmod{2^n}$ の解を $n = 1, 2, 3, 4, 5, 6, \ldots$ について考えてみます。

$x^2 \equiv 41\pmod{2}$ の解　→ $x\equiv 1\pmod{2}$
$x^2 \equiv 41\pmod{2^2}$ の解　→ $x\equiv 1, 3\pmod{2^2}$
$x^2 \equiv 41\pmod{2^3}$ の解　→ $x\equiv 1, 3, 5, 7\pmod{2^3}$
$x^2 \equiv 41\pmod{2^4}$ の解　→ $x\equiv 3, 5, 11, 13\pmod{2^4}$
$x^2 \equiv 41\pmod{2^5}$ の解　→ $x\equiv 3, 13, 19, 29\pmod{2^5}$
$x^2 \equiv 41\pmod{2^6}$ の解　→ $x\equiv 13, 19, 45, 51\pmod{2^6}$

解は確かにあるようですが、解の個数が一定ではなく増えているところがあります。どうも様子が変ですね。

系列が分かりやすいように、 $x_{n+1}\equiv x_{n} \pmod{2^n}$ が成り立つときに線で結ぶと、次の図のようになります。

解の枝が増えるところもあれば、枝が伸びない解もあります。ヘンゼるときとヘンゼらないときがあるというわけです。一意的に伸びていた $\bmod{5^n}$ の場合と大きく異なりますね。

これはいったいどういうことでしょう。ちょっと複雑な状況になっているので、記事の最後に議論したいと思います。

最後に、 $a = 41$ のケースについて、具体的な平方根の近似式を求めてみましょう。

$n = 4$ として $\bmod{10000}$ において、解があるようなので、そのケースで計算してみます。

合同式

$x^2 \equiv 41\pmod{10000}$

の解は、連立合同式

$\begin{cases} x^2 \equiv 41 \pmod{16} \\ x^2 \equiv 41 \pmod{625} \end{cases}$

の解を考えれば良いことになります。それぞれ

$\begin{cases} x \equiv 3, 5, 11, 13 \pmod{16} \\ x \equiv 71, 554 \pmod{625} \end{cases}$

となりますので、中国剰余定理より

$x\equiv 1179, 2429, 2571, 3821, 6179, 7429, 7571, 8821\pmod{10000}$

が元の合同式の解となります。

それぞれについて、対応する平方根の近似を求めてみましょう：

$1179^2 = 1390000 + 41$ 　→　 $\sqrt{139} \fallingdotseq 11.79$

$2429^2 = 5900000 + 41$ 　→　 $\sqrt{590} \fallingdotseq 24.29$

$2571^2 = 6610000 + 41$ 　→　 $\sqrt{661} \fallingdotseq 25.71$

$3821^2 = 14600000 + 41$ 　→　 $\sqrt{1460} \fallingdotseq 38.21$

$6179^2 = 38180000 + 41$ 　→　 $\sqrt{3818} \fallingdotseq 61.79$

$7429^2 = 55190000 + 41$ 　→　 $\sqrt{5519} \fallingdotseq 74.29$

$7571^2 = 57320000 + 41$ 　→　 $\sqrt{5732} \fallingdotseq 75.71$

$8821^2 = 77810000 + 41$ 　→　 $\sqrt{7781} \fallingdotseq 88.21$

いろいろな近似が得られて面白いですね！

おわりに

そんなわけで、 $\sqrt{41}$ の概算という素朴な問題からスタートして、一般化を進めていった結果かなり深いところまで到達しました。

最初は、実数でのニュートン法による近似の話からスタートしましたが、最終的にはヘンゼルの補題にまで辿り着きました。
よくよく考えてみると、ヘンゼルの補題は $p$ 進数におけるニュートン法だと思えるわけで、不思議な偶然ですね。

ある意味、前半の議論と後半の議論は同じ問題を別の視点から見ていたということでしょうか。

というわけで、思わぬ面白い問題に出会うことができて、とても楽しい日曜数学でした。

それでは今日はこの辺で！

補足： $x^2 \equiv 41 \pmod{2^n}$ の解について

合同式

$x^2 \equiv 41 \pmod{2^n}$

の解について考えると、次の図のような系列が得られるのでした。

解の枝が増えるところもあれば、枝が伸びない解もあり、一意的に伸びていた $\bmod{5^n}$ の場合と大きく異なります。いったいどういうことなのでしょうか。

これはヘンゼルの補題の証明の流れをあらためて思い出す必要があります。

まず、

$F(X) = X^2 - 41$

とおくと、今の問題は $F(x_n) \equiv 0 \pmod{2^n}$ の解を求める問題です。

$F(X)$ を微分すると

$F'(X) = 2X$

となります。

ここで、

$F(x_n) \equiv 0 \pmod{2^n}$

を満たす $x_n$ があるときに、 $n$ を一つ増やした

$F(x_{n+1}) \equiv 0 \pmod{2^{n+1}}, \;\; x_{n+1} \equiv x_n\pmod{2^n}$

を満たす $x_{n+1}$ があるかどうか考えましょう。

ヘンゼルの補題によれば、 $F'(x_n) \not\equiv 0 \pmod{2}$ を満たすのであれば、上記のような解は存在し、 $x_n \pmod{2}$ に対して一意的に存在するのでした。

残念ながら、今回は $F'(x_n) \equiv 0 \pmod{2}$ となってしまうので、ヘンゼルの補題は適用できず、解が存在するかどうか分からないというわけです。
（だから、解の系列が枝分かれしたり、枝が途切れたりしたわけです。）

そこで、証明の流れをよくよく考えながら、この場合で言えることを考えましょう。

まず、 $x_{n+1} \equiv x_n \pmod{2^n}$ より、

$x_{n+1} = x_{n} + A\cdot 2^n$

と置きましょう（ $A = 0$ または $A = 1$ ）。諸々の条件を満たす $A$ が存在するか考えましょう。

ここで、 $F(X)$ を多項式で展開して、 $X = x_{n+1}$ を代入すると

$F(x_{n+1}) \equiv F(x_n) + A\cdot 2^n F'(x_n) \pmod{2^{n+1}}$

が成り立ちます。

ここで、 $F(x_n) \equiv 0 \pmod{2^n}$ の条件より

$F(x_{n}) = B\cdot 2^n$

と置くと、上の合同式は

$F(x_{n+1}) \equiv (B + A F'(x_n)) \cdot 2^n \pmod{2^{n+1}}$

となります。

この右辺が $0\bmod{2^{n+1}}$ になるためには

$B + A F'(x_n) \equiv 0 \pmod{2}$

である必要があります。

今、 $F'(x_n) \equiv 0 \pmod{2}$ であることを踏まえると、以下のいずれかとなります：

① $B \equiv 0 \pmod{2}$ であれば $A = 0$ でも $A = 1$ でも $F(x_{n+1}) \equiv 0 \pmod{2^{n+1}}$ が成り立つ
② $B \not\equiv 0 \pmod{2}$ であれば $F(x_{n+1}) \equiv 0 \pmod{2^{n+1}}$ を満たす $x_{n+1}$ はない