文献あり

ZFxRさんの問題を平方剰余で殴る

前置き

こんにちはさくねこです街歩きが楽しい季節になりました（ごててんさんの~~パクリ~~オマージュ）
前回の記事からもう1年近く経ちそうです、なにやってるんでしょうか。
さて、今回はタイトル通り ZFxRさんの自作整数問題を解いていこうと思います！
その問題がこちら

問題（ZFxR）

$2\displaystyle\sum_{t=0}^{k}10^t-m^2=2026$ となる自然数$(k,m)$の組を全て求めよ.

解法に平方剰余記号と相互法則を使いますが、 Wiki に書かれていることくらいしか使わないのであんまり知らなくても読めます。

実はこの解法でなんで解けたのかまだよくわかってないです...
背景を知っている方や証明の不備に気づいた方はぜひコメントしてください！

解法を決める

まず元記事にあるとおり、簡単に見つかる解$(k,m)=(3,14)$が1つあります。
すこしコンピュータの力を借りて計算すると、どうもこれ以外に解はみつからなさそうなので問題はその証明ですね！

まずは式を整理します。
$m^2$の項以外は偶数なので$m^2$も偶数であり、従って$m$も偶数になります。
また
\begin{align} \sum_{t=0}^{k}10^t = \frac{10^{k+1}-1}{9} \end{align}
から、$a:=k+1,\ b:=m/2$ とおいて整理することで
\begin{align} 10^a = 18b^2 + 9118 \tag{1} \end{align}
となります。

この手の整数問題の常套手段といえば剰余、不等式、因数分解ですよね。今回一番使えそうに見えるのは剰余だと思います。ところが、ここで壁が立ちはだかります...。

剰余で絞りきれない！

十分大きい$a$に対して左辺を消せる2の冪と5の冪の法が効果的に見えるので試してみます。

$\text{mod }2^k, 5^k$

\begin{aligned} \text{mod }4 &: \ a \geq 2 \text{ のとき } 2b^2 + 2 \equiv 0 \pmod{4},\quad \text{解は } b \equiv 1,3 \pmod{4} \\[6pt]\text{mod }8 &: \ a \geq 3 \text{ のとき } 2b^2 + 6 \equiv 0 \pmod{8},\quad \text{解は } b \equiv 1,3,5,7 \pmod{8} \\[6pt]\text{mod }16 &: \ a \geq 4 \text{ のとき } 2b^2 + 14 \equiv 0 \pmod{16},\quad \text{解は } b \equiv 1,3,5,7,9,11,13,15 \pmod{16} \\[6pt]\text{mod }32 &: \ a \geq 5 \text{ のとき } 18b^2 + 30 \equiv 0 \pmod{32},\quad \text{解は } b \equiv 3,5,11,13,19,21,27,29 \pmod{32} \\[12pt]\text{mod }5 &: \ a \geq 1 \text{ のとき } 3b^2 + 3 \equiv 0 \pmod{5},\quad \text{解は } b \equiv 2,3 \pmod{5} \\[6pt]\text{mod }25 &: \ a \geq 2 \text{ のとき } 18b^2 + 18 \equiv 0 \pmod{25},\quad \text{解は } b \equiv 7,18 \pmod{25} \\[6pt]\text{mod }125 &: \ a \geq 3 \text{ のとき } 18b^2 + 118 \equiv 0 \pmod{125},\quad \text{解は } b \equiv 7,118 \pmod{125}\end{aligned}

絞れてはいますが、知らない解が存在しないことまでは言えなさそうですね...
実はヘンゼルの補題による解の持ち上げを使うことで、$(1)$は$\text{mod }2^k \ (k\geq4)$で解をちょうど8個、$\text{mod }5^k$で解をちょうど2個持つことが示せてしまいます。つまり、法をどれだけ大きくしても候補を有限に絞り込むことができません！
では他の法を試したくなりますが、これも候補が残ってしまうことがわかります。
他の法は10と互いに素なので、$(1)$の左辺、右辺ともに$a, b$について剰余が周期的になります。$(1)$に$(k,m)=(3,14)$に対応する解$(a,b)=(4,7)$があることを踏まえると、その解が周期的に出てきてしまいます！

$\text{mod }7$

$(1)$の左辺$10^k$について：
$10^6 \equiv 1 \ (\text{mod }7)$より$\text{mod }7$において$1→3→2→6→4→5→1→3→2→...$と周期6でループ
$(2)$の右辺$18b^2 + 9118 $について：
$\text{mod }7$において
$4→1→6→5→5→6→1→4→1→6→...$と周期7でループ

ここから$(a \ \text{mod }6,b \ \text{mod }7)=(0,1), (0,6), (3,2), (3,5), (4,0), (5,3), (5,4)$が$\text{mod }7$における解.
特に, $(a \ \text{mod }6,b \ \text{mod }7)=(4,0)$は剰余を取る前の解$(a,b)=(4,7)$から出てくる.

つまり、どのような法をとっても候補を有限に絞り込むことができません！

今回の秘密兵器

さて手詰まりになったわけですが、実は私は類似の問題を知っています！
それがこれ、 Fibonacci 平方数が 0, 1, 144 のみであることの初等的証明です。
$(1)$は指数的に増加する項と平方数からなる方程式ですが、この問題におけるフィボナッチ数=平方数も同様の形の方程式になっています！解法を応用できないでしょうか？

上の記事の証明の概略は下のような感じです（$m$番目のフィボナッチ数を$F_m$と表します）：

$m$が奇数の場合, 剰余をとったときに$F_m$が定数になるように$m$に依存して適切な法を選択する
特殊な場合を除き, 剰余をとった方程式に解がないことを示す
$m$が偶数の場合, $m=f\cdot 2^e$となる奇数$f$をとって$m=f$の場合に帰着する

重要なのは法を$m$に依存して取ることで上の障害を回避しうるところです。
早速適用したいところですが、そのまま使えるほど今回の方程式は綺麗な形ではないです（定数部分が大きく法の選択が難しそう）。もう少し式変形を行ったのち、上のアイデアを使って決めるというのが証明の大筋です。

本題

絞り込み再び

ちょっと天啓ポイントその1です。

\begin{align} 10^a = 18b^2 + 9118 \tag{1} \end{align}
において$a\equiv 4 \ \text{mod } 6$ かつ $7\mid b$である.

$10^6-1=3^3 \cdot 7 \cdot 11 \cdot 13 \cdot 37$より$\text{mod }27, 7, 13$において左辺は$a$について周期6.
$(1)$の剰余をとると次のような表になる.

	$10^a$	$18b^3+9118$
$\text{mod }27$	1,10,19,1,10,19,...	10,19のいずれか
$\text{mod }7$	1,3,2,6,4,5,...	1,4,5,6のいずれか
$\text{mod }13$	1,10,9,12,3,4,...	0,3,5,7,10,11,12のいずれか

ここから両辺で整合的となるのは$a\equiv 4 \ \text{mod } 6$のときのみであることがわかる.$\text{mod } 7$において$(1)$は
\begin{align} 4 \equiv 4b^2 + 4 \pmod 7 \end{align}
となるので、$7\mid b$も従う.

固定の剰余は意味がないといっておきながら突然$\text{mod }27, 7, 13$を取りましたが、$b$が$7$で割り切れると分かったので$b=7c$とおけます。$(1)$に代入すると
\begin{align} 10^a = 882c^2 + 9118 = 882(c^2 - 1) + 10^4 \end{align}
すなわち
\begin{align} 5000\bigl(10^{a-4}-1\bigr)=441(c^2-1) \tag{2} \end{align}
となります。$\gcd(5000,441)=1$であることに注目すると、
\begin{align} 441 \mid 10^{a-4}-1 \end{align}
です。気合いの計算またはコンピュータにより$\text{mod }441$における$10$の位数が$42$、すなわち
\begin{align} 10^{42} \equiv 1 \text{ かつ } 1 \leq k \leq 41 \text{ において } 10^{k} \not\equiv 1 \ (\text{mod }441) \end{align}
とわかるので、$42$が$a-4$を割り切ることもわかります。そこで$a-4=42d \ (d\ge 0)$とおくことにします。$(2)$は
\begin{align} 5000\bigl(10^{42d}-1\bigr)=441(c^2-1) \tag{3} \end{align}
となり、$(c,d)=(1,0)$が冒頭の解$(a,b)=(4,7), (k,m)=(3,14)$に対応します。
示すべきことは「$d \ge 1$において$(3)$が解を持たないこと」です。

秘密兵器を使う

$d \ge 1$なので$d=e \cdot 2^n$（$e$ は奇数，$n\ge 0$）と書けます。
条件部分がちょっと天啓ポイントその2です。

各非負整数$n$に対して次のような素数$p$が存在することを示せば, $d \ge 1$において$(3)$は解を持たない：

$10^{42 \cdot 2^n} \equiv -1 \ (\text{mod }p)$, すなわち$p$は$10^{42 \cdot 2^n}+1$の約数
$p \neq 11$
$p$において$-79$が平方非剰余, すなわち$x^2 \equiv -79 \ (\text{mod }p)$が解を持たない

$p$による$(3)$の剰余に1つめの条件を代入すると
\begin{eqnarray} 5000\bigl((-1)^e-1\bigr) &\equiv& 441(c^2-1) \ &(\text{mod }p) \\ 441c^2 &\equiv& -9559 \ &(\text{mod }p) \\ \left(\frac{21c}{11}\right)^2 &\equiv& -79 \ &(\text{mod }p) \\ \end{eqnarray}
となる(2行目から3行目で, 2つめの条件により$\text{mod }p$において$11$の乗法逆元があることを使った).
しかし3行目は3つめの条件と矛盾するので$(3)$は解を持たない.

3つめの条件は法が$p$なので少々扱いにくいです。そこで法と剰余をひっくり返す平方剰余の相互法則の出番です！

平方剰余記号、補充法則、相互法則

$a$を整数, $p$を正の奇素数とする.
\begin{align} \left( \frac{a}{p} \right) := \begin{cases} \;\;1 & (a \text{ は } p \text{ を法として平方剰余})\\ -1 & (a \text{ は } p \text{ を法として平方非剰余})\\ \;\;0 & (p \mid a) \end{cases} \end{align}
と定めたものを平方剰余記号（ルジャンドル記号）と呼ぶ.
以下の公式が成り立つ：
\begin{align} \left( \frac{a}{p} \right) &= \left( \frac{b}{p} \right) \ \left(a\equiv b \ (\text{mod }p)\right)\\ \left( \frac{ab}{p} \right) &= \left( \frac{a}{p} \right)\left( \frac{b}{p} \right)\\ \left( \frac{-1}{p} \right) &= (-1)^{\frac{p-1}{2}} \text{ （第一補充法則）}\\ \left( \frac{2}{p} \right) &= (-1)^{\frac{p^2-1}{8}} \text{ （第二補充法則）}\\ \left( \frac{p}{q} \right)\left( \frac{q}{p} \right) &= (-1)^{\frac{(p-1)(q-1)}{4}} \text{ （相互法則）}\\ \end{align}

公式の証明は他の記事に任せることにして、結果だけありがたく使わせてもらうことにしましょう！
補題2の3つめの条件は$\displaystyle \left( \frac{-79}{p} \right)=-1$と書けます。これを変形すると、
\begin{align} -1 = \left( \frac{-79}{p} \right) = \left( \frac{-1}{p} \right)\left( \frac{79}{p} \right) = (-1)^{\frac{p-1}{2}}(-1)^{\frac{(p-1)(79-1)}{4}}\bigg( \frac{p}{79} \bigg) =\bigg( \frac{p}{79} \bigg) \end{align}
となりました。
ここで$\displaystyle \left( \frac{ab}{p} \right) = \left( \frac{a}{p} \right)\left( \frac{b}{p} \right)$に注意すると、ある整数$f$が特定の法で平方非剰余であるとき、その素因数$p$であって同じ法で平方非剰余であるものが少なくとも1つとれます（素因数がすべて平方剰余なら、対応する平方剰余記号の値はすべて1なのでその積となるもとの$f$に対応する平方剰余記号の値も1となってしまいます）。
これを使って補題2を書きなおすと次のようになります：

各非負整数$n$に対して次のような正の整数$f$が存在することを示せば, $d \ge 1$において$(3)$は解を持たない：

$f$は$10^{42 \cdot 2^n}+1$の約数
$f$は$11$と互いに素
$\displaystyle \bigg( \frac{f}{79} \bigg) = -1$

最後のステップ

こうして問題は$f$を見つけることに集約されました。
といっても$f$は$10^{42 \cdot 2^n}+1$の約数なので、分かりやすいものはそう多くありません。明らかなのは$10^{42 \cdot 2^n}+1$自身で、$k$が奇数のときに$x^k+1$が$x+1$で割り切れることを思い出すと$10^{2 \cdot 2^n}+1$も約数になることがわかります。この2つは$11$で割った余りが$(-1)^{\text{偶数}}+1=2$となるので、$11$と互いに素です。
いよいよ大詰めです！

\begin{align} \left(\frac{10^j+1}{79}\right)= \begin{cases} -1 & (j\equiv 3,4,5,8,9,10 \pmod{13}), \\ 1 & (j\equiv 0,1,2,6,7,11,12 \pmod{13}) \end{cases} \end{align}
が成り立つ.

再びパワーに頼ると$10$ の $79$ における位数は $13$ であるとわかる. したがって, $j$の$13$における剰余だけによって$\displaystyle \left(\frac{10^j+1}{79}\right)$の値が決まる.
$j=0,1,\dots,12$ を直接計算すると結果が得られる.

\begin{align} f:= \begin{cases} 10^{42\cdot 2^n}+1 & \text{if } 2^n \equiv 1,3,6,7,10,12 \pmod{13} \\ 10^{2\cdot 2^n}+1 & \text{if } 2^n \equiv 2,4,5,8,9,11 \pmod{13} \end{cases} \end{align}
とおくと補題3の条件を満たす.

$2^n \pmod{13}$ は直接計算により
\begin{align} \{1,2,4,8,3,6,12,11,9,5,10,7\} \end{align}
を巡回するとわかる. そして$2^n \pmod{13}$ が$\{1,3,6,7,10,12\}$に入るときは $j=42\cdot 2^n \equiv 3\cdot 2^n$ が，それ以外のときは $j=2\cdot 2^n$が，補題4で値が$-1$になる$j$の剰余類$\{3,4,5,8,9,10\}$に入る←！？（一番の天啓ポイントその3）.
そこで本補題のように$f$を定めると, 補題4から$\displaystyle \left(\frac{f}{79}\right)=-1$であり, すでに述べた通り$10^{42 \cdot 2^n}+1$の約数かつ$11$と互いに素なので補題3の条件を満たす.