0

2004年 東京大学 理系 第2問

6
0
$$$$
2004年 東京大学 理系 第2問

自然数の2乗になる数を平方数という。以下の問いに答えよ。
(1) 10進法で表して3桁以上の平方数に対し,10の位の数を $a$,1の位の数を $b$ とおいたとき,$a+b$ が偶数となるならば,$b$ は $0$ または $4$ であることを示せ。
(2) 10進法で表して5桁以上の平方数に対し,1000の位の数,100の位の数,10の位の数,および1の位の数の4つすべてが同じ数となるならば,その平方数は $10000$ で割り切れることを示せ。


1. 問題の構造

1.1 記法と定式化

  • 平方数を $N=n^2$($n$ は自然数)と書く。
  • 整数 $x$ を自然数 $m$ で割った余りを $x\bmod m$($0\leqq x\bmod m\leqq m-1$)と書く。
  • $Q_m=\lbrace x^2\bmod m \mid x\in\mathbb{Z}\rbrace$ とおく。$N=n^2$ ならば $N\bmod m\in Q_m$ である。本稿では $Q_m$ の元を法 $m$ の平方剰余と呼ぶ($0$ や $m$ と互いに素でない剰余も含める。初等整数論では $m$ と互いに素なものに限る用法も多い)。
  • 非負整数 $N$ の $10^i$ の位の数を $\lfloor N/10^i\rfloor\bmod10$ と定める。$N$ の下位 $k$ 桁と $N\bmod10^k$ は互いに他を定める。桁数より上の位の数は $0$ とみなす。
  • 素数 $p$ と $0$ でない整数 $x$ について,$x$ が $p$ で割り切れる回数を $v_p(x)$ と書く(5 章で用いる)。
  1. の平方数は $q=\lfloor N/100\rfloor\geqq1$ として
    $$ N=100q+10a+b\qquad(0\leqq a,b\leqq9) $$
    と表され,仮定は $a\equiv b\pmod2$ と同値である。(2) の平方数は,4つの位に共通する数字を $d$ として
    $$ N=10000q+1111d\qquad(q\geqq1,\ 0\leqq d\leqq9) $$
    と表され,$0\leqq1111d\leqq9999$ であるから結論 $10000\mid N$ は $d=0$ と同値である。いずれの設問も,$N\bmod10^k$($k=2,4$)に関する平方の剰余条件の問題である。

1.2 平方数の剰余

本稿の高校数学の範囲の議論が用いる平方数の性質は,次の補題に尽きる。

平方数の剰余

任意の整数 $x$ について次が成り立つ。
(i) $Q_4=\lbrace0,1\rbrace$。
(ii) $Q_5=\lbrace0,1,4\rbrace$。したがって平方数の1の位は $0,1,4,5,6,9$ のいずれかである。
(iii) $x$ が奇数ならば $x^2\equiv1\pmod8$,偶数ならば $x^2\equiv0$ または $4\pmod{16}$ である。特に $Q_8=\lbrace0,1,4\rbrace$,$Q_{16}=\lbrace0,1,4,9\rbrace$。
(iv) $Q_{20}=\lbrace0,1,4,5,9,16\rbrace$。

(i) $x=2y$ ならば $x^2=4y^2$,$x=2y+1$ ならば $x^2=4y(y+1)+1$ である。
(ii) $x\equiv0,\pm1,\pm2\pmod5$ に応じて $x^2\equiv0,1,4\pmod5$ である。平方数の1の位 $b$ は $b\equiv x^2\pmod5$ を満たすから $b\bmod5\in\lbrace0,1,4\rbrace$ であり,$0\leqq b\leqq9$ のうちこれを満たすのは $0,1,4,5,6,9$ である。
(iii) $x=2y+1$ のとき $y(y+1)$ は偶数だから $x^2=4y(y+1)+1\equiv1\pmod8$,よって $x^2\bmod16\in\lbrace1,9\rbrace$。$x=2y$ のとき $x^2=4y^2$ と (i) より $x^2\bmod16\in\lbrace0,4\rbrace$,$x^2\bmod8\in\lbrace0,4\rbrace$。$0^2,1^2,2^2,3^2$ により各元はすべて現れる。
(iv) $x^2\bmod20$ は $x\bmod20$ で定まり,$(-x)^2=x^2$ だから $x=0,1,\ldots,10$ を調べれば足りる。その平方を $20$ で割った余りは順に $0,1,4,9,16,5,16,9,4,1,0$ である。

1.3 (1) の構造:偶奇の情報を残す法

  1. の仮定は $a,b$ の値ではなく,偶奇の一致だけを指定している。法 $10$ では $10a\equiv0$ となり $a$ の情報は失われる。一方,法 $4$ では $100q\equiv0$,$10a\equiv2a$ であり,
    $$ N\equiv2a+b\pmod4 $$
    に $a$ の偶奇が残る。仮定 $a\equiv b\pmod2$ は $2a\equiv2b\pmod4$ を与えるから,$N\equiv3b\equiv-b\pmod4$ となって $a$ が消える。これを1の位の制限と照合するのが本解である。
    情報の過不足をより正確に述べる。$20\mid100$ より
    $$ N\equiv10a+b\equiv10\,(a\bmod2)+b\pmod{20} $$
    であり,右辺は $0$ 以上 $19$ 以下の整数で,対 $(a\bmod2,\,b)$ と一対一に対応する。すなわち $(a\bmod2,\,b)$ のもつ情報は $N\bmod20$ と過不足なく一致する。仮定のもとでは $10a\equiv10b\pmod{20}$ だから
    $$ N\equiv11b\pmod{20} $$
    となり,(1) は $Q_{20}$ についての主張に帰着する( 3.1 節 )。$20=4\cdot5$ であり,本解の法 $4$ の条件と1の位の条件(法 $5$ の条件)は,この法 $20$ の条件を中国剰余定理によって二つに分けたものである。さらに $Q_{20}$ の元のうち $10$ 以上のものは $16$ だけであるから,$a$ が奇数となるのは $b=6$ の場合に限られる。これは「10の位が奇数 $\iff$ 1の位が $6$」という完全な記述を与える( 命題3 )。
    平方根の側から見ると,$(n+10)^2-n^2=20n+100\equiv0\pmod{20}$ であるから,$N\bmod20$ は $n\bmod10$ だけで決まる。したがって (1) は平方根の1の位の $10$ 通りを調べれば決着する。これが別解1 の出発点である。

1.4 (2) の構造:前問の再利用と法 16

  1. の平方数の10の位と1の位はともに $d$ であり,和 $2d$ は偶数である。よって (1) がそのまま適用でき,$d\in\lbrace0,4\rbrace$ となる。$d=0$ は結論そのものであるから,(2) の実質は
    $$ n^2\equiv4444\pmod{10000}\ \text{は解をもたない} $$
    ことの証明である。この不可能性は次の三通りに捉えられる。
  • 剰余の直接判定:$16\mid10000$,$4444\equiv12\pmod{16}$,$12\notin Q_{16}$(本解)。法 $8$ では $4444\equiv4\in Q_8$ であり,矛盾は生じない。
  • 平方因子の除去:$4444=4\cdot1111$ より $n=2m$ とおくと $m^2\equiv1111\pmod{2500}$,特に $m^2\equiv11\pmod{100}$ となり,(1) あるいは $Q_4$ に反する(別解2)。$4m^2\equiv12\pmod{16}\iff m^2\equiv3\pmod4$ であるから,これは本解と同じ障害の別の表現である。
  • 平方根の構成:$38^2=1444$ のように末尾 $444$ は実現されるが,末尾が $444$ の平方数の1000の位は必ず奇数になる(参考解2, 補題2 )。
  1. を用いない場合は,$1111\equiv7\pmod{16}$,$1111\equiv1\pmod5$ を用いて $d$ を直接分類できる(参考解1)。

1.5 障害の所在:$2$ の冪と $5$ の冪

$10000=2^4\cdot5^4$,$\gcd(16,625)=1$ であるから,中国剰余定理により
$$ x^2\equiv A\pmod{10000}\ \text{が解をもつ}\iff x^2\equiv A\pmod{16}\ \text{と}\ x^2\equiv A\pmod{625}\ \text{がともに解をもつ} $$
が成り立つ。$A=4444$ について調べると次のようになる。

法$4444$ の剰余解の有無根拠
$5$$4$あり$2^2=4$
$625$$69$あり$87^2=7569=4444+5^5$
$8$$4$あり$2^2=4$
$16$$12$なし$Q_{16}=\lbrace0,1,4,9\rbrace$

障害は $2$ の冪の側にだけあり,しかも法 $8$ では現れず法 $16$ で初めて現れる。十進の下位 $k$ 桁は $N\bmod10^k$,したがって $N\bmod2^k$ を定めるが,$N\bmod2^{k+1}$ は定めない。よって法 $16=2^4$ の情報は下位4桁で初めて得られる。これが「末尾 $444$ は可能($38^2=1444$)であるが末尾 $4444$ は不可能」という境界の理由であり,(2) の「4つ」が結論の成り立つ最小の個数であることの理由である( 命題5 , 5.6 節 )。

1.6 桁数条件と実現例

  • 「3桁以上」「5桁以上」は,各位の数が先頭の $0$ でない本来の数字であることを保証する設定であり,合同式による議論には用いられない。実際,桁数より上の位を $0$ とみなせば (1) の結論はすべての平方数で成り立つ($4$,$64$ など。 命題3 )。また4桁の平方数で4つの数字がすべて等しいものは存在しない(本解 (2) の議論は $q=0$ でも成り立って $d=0$ を導くが,$d=0$ の4桁の数はない)。桁数条件が実際に効くのは,(1) を問題文の形のまま別の平方数に適用する場合(別解2)に限られる。
    1. の結論の $0,4$ はともに実現される:$10^2=100$($a+b=0$),$12^2=144$($a+b=8$)。
    1. の仮定を満たす平方数は存在する:$100^2=10000$。よって (2) は空虚な主張ではない。
    1. の「4つ」を下位3つに弱めた主張は偽である:$38^2=1444$。

1.7 作問の設計と解法の導出

以上の構造から,作問の設計は次のように読める(数値設定からの分析であり,出題者の意図についての推定を含む)。

  • 二段構成:(1) の仮定「$a+b$ が偶数」は,等式 $a=b$ を法 $2$ に落とした条件そのものである。(2) の下位2桁 $dd$ は常にこの仮定を満たし,(1) は (2) の候補を $10$ 個から $2$ 個に減らすふるいとして働く。
  • 法の隠蔽:(1) は実質的に $Q_{20}$ についての主張($N\equiv11b\pmod{20}$)であるが,問題文は数字の言葉で述べられており,$10a$ の偶奇を保つ法($4$ または $20$)を自ら選ぶことが求められる。
  • 閾値の配置:(1) を通過する $d=4$ は下位3桁まで実現される($12^2=144$,$38^2=1444$)。下位4桁で初めて,$16\mid10^4$,$16\nmid10^3$ によって排除される。「4つ」は結論が成り立つ最小の個数であり,問題はこの境界の上に置かれている( 1.5 節 )。
  • 結論の形:$10000\mid N$ は $d=0$ と同値であり,さらに平方根についての $100\mid n$ と同値である( 5.10 節 )。
    各構造がどの解法を導くかを整理する。
    着目する構造導かれる解法
    仮定を法 $4$ で用いて $a$ を消去し,1の位と照合本解 (1)
    $(a\bmod2,\,b)$ と $N\bmod20$ の一対一対応3.1 節
    $N\bmod20$ が $n\bmod10$ で決まる周期性別解1
    下位2桁 $dd$ への (1) の適用と $16\mid10^4$本解 (2)
    偶数の平方の法 $16$ の剰余を十進の桁へ翻訳3.2 節
    $4444=4\cdot1111$ による平方因子の除去別解2
    $1111d$ の法 $16$ と法 $5$ での直接評価参考解1
    平方根の桁の逐次決定(持ち上げ)参考解2

2. 本解:数字の偶奇と平方剰余

2.1 方針

  1. では仮定 $a\equiv b\pmod2$ を法 $4$ で用いて $a$ を消去し,得られる $b$ の候補を平方数の1の位の候補と照合する( 1.3 節 )。(2) では (1) によって共通の数字を $0,4$ に限定し,$4$ の場合を法 $16$ で排除する( 1.4 節 )。

2.2 解答

(1)

平方数を $N$ とし,$q=\lfloor N/100\rfloor$ とおくと
$$ N=100q+10a+b\qquad(0\leqq a,b\leqq9). $$
$a+b$ は偶数だから $a\equiv b\pmod2$,よって $2a\equiv2b\pmod4$ である。$100\equiv0$,$10\equiv2\pmod4$ より
$$ N\equiv2a+b\equiv2b+b=3b\equiv-b\pmod4. $$
補題1 (i) より $(-b)\bmod4\in\lbrace0,1\rbrace$,すなわち $b\equiv0$ または $3\pmod4$ であり,$0\leqq b\leqq9$ より
$$ b\in\lbrace0,3,4,7,8\rbrace. $$
一方, 補題1 (ii) より $b\in\lbrace0,1,4,5,6,9\rbrace$ である。両者の共通部分をとって,$b=0$ または $b=4$ である。

(2)

4つの位に共通する数字を $d$ とすると
$$ N=10000q+1111d\qquad(q\geqq1,\ 0\leqq d\leqq9). $$
$N$ は3桁以上の平方数で,その10の位と1の位はともに $d$ であり,和 $2d$ は偶数である。よって (1) より $d=0$ または $d=4$ である。
$d=4$ と仮定する。$10000=16\cdot625$,$4444=16\cdot277+12$ であるから
$$ N\equiv4444\equiv12\pmod{16}. $$
これは 補題1 (iii) の $Q_{16}=\lbrace0,1,4,9\rbrace$ に反する。ゆえに $d=0$ であり,$N=10000q$,すなわち $N$ は $10000$ で割り切れる。

2.3 検証・検算

  • 二つの条件の役割:法 $4$ の条件だけでは $b=3,7,8$ が,1の位の条件だけでは $b=1,5,6,9$ が残る。いずれか一方では結論に届かず,両者を合わせたものが法 $20$ の条件である( 3.1 節 )。
  • 剰余の計算:$4444=16\cdot277+12$。また $4444=8\cdot555+4$ で $4\in Q_8$ であるから,法 $8$ では矛盾が生じない。$2$ の冪として法 $16$ は必要最小である。
  • 結論の鋭さ:$10^2=100$,$12^2=144$ により (1) の $b=0,4$ はともに実現される。$100^2=10000$ は (2) の仮定と結論を満たし,$38^2=1444$ は (2) を下位3桁に弱めた主張の反例である。
  • 有限検査:(1) の条件は $N\bmod20$,したがって $n\bmod10$ で決まる。(2) の条件は $n^2\bmod10000$ で決まり,$(n+5000)^2\equiv n^2\pmod{10000}$ であるから $n\bmod5000$ で決まる。よって有限個の剰余類の検査はそれ自体が完全な証明になる。実際,計算機で $n=0,1,\ldots,9999$ について $n^2\bmod10000$ を調べると,$1111d$($1\leqq d\leqq9$)に一致するものは存在せず,$0$ に一致するのは $n\equiv0\pmod{100}$ の $100$ 個である。

3. 別解と参考解

3.1・3.2 節は本解の一部分に対する別証,3.3・3.4 節は本解と異なる着眼に立つ別解である。3.5・3.6 節の参考解はいずれも高校数学の範囲で完結するが,本解と同じ系列に属するか,試験場の答案としては計算量が過大であるため参考解とする。

3.1 (1) の別証:法 20 による一括判定

着想・方針

$(a\bmod2,\,b)$ の情報は $N\bmod20$ と一致する( 1.3 節 )。仮定を法 $20$ の合同式に直接翻訳する。

解答

$N=100q+10a+b$ において $20\mid100$,また $a\equiv b\pmod2$ より $10a\equiv10b\pmod{20}$ であるから
$$ N\equiv11b\pmod{20}. $$
$b=0,1,\ldots,9$ に対する $11b\bmod20$ は次のとおりである。

$b$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$
$11b\bmod20$$0$$11$$2$$13$$4$$15$$6$$17$$8$$19$

補題1 (iv) の $Q_{20}=\lbrace0,1,4,5,9,16\rbrace$ に属するのは $b=0$ と $b=4$ の場合だけである。

検証・検算

$11\equiv-1\pmod4$,$11\equiv1\pmod5$ であるから,$N\equiv11b\pmod{20}$ は $N\equiv-b\pmod4$ と $N\equiv b\pmod5$ の組と同値である。前者は本解の法 $4$ の式,後者は1の位の条件そのものであり,この別証は本解の二条件を中国剰余定理で一つにまとめたものである。$Q_{20}$ の元 $16$ は $(a\bmod2,\,b)=(1,6)$ に対応し,$a$ が奇数となる唯一の場合である(例:$14^2=196$,$16^2=256$。 命題3 )。

3.2 $d=4$ の排除の他の導出:1000の位の偶奇検査

着想・方針

「偶数の平方は法 $16$ で $0$ または $4$」を十進の桁の言葉に翻訳する。$10000$ と $1000$ はともに $8$ の倍数であるから,$\lfloor N/8\rfloor$ の偶奇は1000の位の偶奇と下位3桁だけで表される。

偶数の平方数の1000の位

$n$ を偶数とし,$n^2$ の1000の位の数を $c$,$t=n^2\bmod1000$ とする。このとき
$$ c\equiv\left\lfloor\frac{t}{8}\right\rfloor\pmod2. $$

$q'=\lfloor n^2/10000\rfloor$ とおくと $n^2=10000q'+1000c+t$($0\leqq t\leqq999$)である。 補題1 (iii) より $n^2=16k$ または $n^2=16k+4$($k$ は整数)と書けるから,$\lfloor n^2/8\rfloor=2k$ は偶数である。一方,$10000q'+1000c=8(1250q'+125c)$ より
$$ \left\lfloor\frac{n^2}{8}\right\rfloor=1250q'+125c+\left\lfloor\frac{t}{8}\right\rfloor. $$
これが偶数であり $125$ は奇数であるから,$c\equiv\lfloor t/8\rfloor\pmod2$ である。

解答

  1. より $d\in\lbrace0,4\rbrace$ である。$d=4$ と仮定する。$N$ の1の位は $4$ で $N$ は偶数であるから,$n$ は偶数である($n$ が奇数なら $n^2$ は奇数)。$t=444$ であり $\lfloor444/8\rfloor=55$ は奇数であるから, 補題2 より1000の位は奇数である。これは1000の位が $d=4$ であることに反する。ゆえに $d=0$ であり,$10000\mid N$ である。

検証・検算

  • $38^2=1444$($t=444$,$c=1$),$112^2=12544$($\lfloor544/8\rfloor=68$,$c=2$)はいずれも補題と整合する。
  • 偶数の仮定は外せない:$37^2=1369$ では $\lfloor369/8\rfloor=46$ は偶数であるが $c=1$ である。
  • 補題の証明は $Q_{16}$ の偶数の平方に対応する部分 $\lbrace0,4\rbrace$ だけを用いており,本解の法 $16$ の議論を十進の桁へ翻訳したものである。独立の障害を与えるものではないが,任意の下位3桁から1000の位の偶奇を決める一般的な検査式として 5.3 節 で用いる。

3.3 別解1:(1) 平方根の1の位による分類

着想・方針

$N\bmod20$ は $n\bmod10$ だけで決まる( 1.3 節 )。平方根を $n=10u+r$ と分け,交差項 $20ur$ が10の位に偶数しか寄与しないことを用いて,$10$ 通りの $r$ に帰着する。

解答

$n=10u+r$($u\geqq0$,$0\leqq r\leqq9$),$r^2=10v+w$($0\leqq v\leqq8$,$0\leqq w\leqq9$)とおくと
$$ n^2=100u^2+20ur+r^2=100u^2+10(2ur+v)+w. $$
$0\leqq w\leqq9$ であるから $b=w$,また $a=(2ur+v)\bmod10$ であり,$a\equiv2ur+v\equiv v\pmod2$ である。したがって
$$ a+b\equiv v+w\pmod2. $$
$r=0,1,\ldots,9$ について $v+w$ の偶奇は次のとおりである。

$r$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$
$r^2$$0$$1$$4$$9$$16$$25$$36$$49$$64$$81$
$(v,w)$$(0,0)$$(0,1)$$(0,4)$$(0,9)$$(1,6)$$(2,5)$$(3,6)$$(4,9)$$(6,4)$$(8,1)$
$v+w$ の偶奇偶奇偶奇奇奇奇奇偶奇

よって $a+b$ が偶数となるのは $r\in\lbrace0,2,8\rbrace$ のときに限り,このとき $b=w\in\lbrace0,4\rbrace$ である。
この議論は同時に,同値
$$ a+b\ \text{が偶数}\iff n\equiv0,2,8\pmod{10} $$
を与える。

検証・検算

  • 繰り上がり:$2ur+v$ は $10$ 以上になりうるので,$a=2ur+v$ ではなく $a\equiv2ur+v\pmod{10}$ である。偶奇の議論にはこれで足りる。
  • 対称性:$(10-r)^2=100-20r+r^2$ より,$r$ と $10-r$ では $w$ が一致し $v$ の偶奇が等しい。表の $1\leftrightarrow9$,$2\leftrightarrow8$,$3\leftrightarrow7$,$4\leftrightarrow6$ の各組で最下行が一致することと整合する。
  • 具体例:$12^2=144$,$18^2=324$(ともに $a+b$ は偶数,$b=4$),$14^2=196$($a$ は奇数,$b=6$)。
  • $v$ が奇数となるのは $r=4,6$ のときだけで,そのとき $w=6$ である。これは「10の位が奇数 $\iff$ 1の位が $6$」を与える( 命題3 )。

3.4 別解2:(2) 補助平方数への帰着

着想・方針

$4444=4\cdot1111$ に着目する。$4$ で割り切れる平方数の根は偶数であるから,$4$ で割った商も平方数である。この新しい平方数の下位2桁に (1) を再び適用する。

解答

本解と同様に,(1) より $d\in\lbrace0,4\rbrace$ である。$d=4$ と仮定すると
$$ N=10000q+4444=4\,(2500q+1111). $$
$n$ が奇数なら $N$ は奇数であるから,$n$ は偶数である。$n=2m$($m$ は自然数)とおくと
$$ m^2=2500q+1111. $$
$100\mid2500$ より $m^2\equiv11\pmod{100}$,すなわち $m^2$ の10の位と1の位はともに $1$ である。また $m^2\geqq1111$ より $m^2$ は3桁以上の平方数である。その10の位と1の位の和 $1+1=2$ は偶数であるのに1の位は $1$ であり,(1) に反する。ゆえに $d=0$ であり,$10000\mid N$ である。

検証・検算

  • 平方数を $4$ で割った商が平方数であることは,$n$ が偶数であることを確かめて初めて言える。$m^2\geqq100$ の確認は (1) を問題文の形のまま適用するために必要である。
  • 終結の短縮:(1) を再適用せず,$m^2\equiv1111\equiv3\pmod4$ として 補題1 (i) に反するとしてもよい。$n^2=4m^2$ より $n^2\equiv12\pmod{16}\iff m^2\equiv3\pmod4$ であるから,これは本解と同じ障害である。
  • 4桁が必要な理由:末尾 $444$ の平方数 $n^2=1000q+444$ に同じ操作を行うと $m^2=250q+111$ となり,$100\nmid250$ のため $m^2$ の下位2桁は $q$ に依存して定まらない。実際 $38^2=1444$ からは $19^2=361$ が得られ,矛盾は生じない。$10000/4=2500$ が $100$ の倍数であることがこの解法の要である。

3.5 参考解1:(2) を (1) に依存せず直接分類

着想・方針

$1111\equiv7\pmod{16}$,$1111\equiv1\pmod5$ を用いて,$n^2\equiv1111d$ を二つの小さな法で直接評価し,候補の共通部分をとる。

解答

$N=10000q+1111d$ とする。$16\mid10000$,$1111=16\cdot69+7$ より $N\equiv7d\pmod{16}$ であり, 補題1 (iii) より $7d\bmod16\in\lbrace0,1,4,9\rbrace$ である。$7\cdot7=49\equiv1\pmod{16}$ であるから,$7$ を掛けて
$$ d\equiv0,\ 7,\ 28,\ 63\equiv0,\ 7,\ 12,\ 15\pmod{16}. $$
$0\leqq d\leqq9$ より $d\in\lbrace0,7\rbrace$ である。次に $5\mid10000$,$1111\equiv1\pmod5$ より $N\equiv d\pmod5$ である。$d=7$ とすると $N\equiv2\pmod5$ となり, 補題1 (ii) に反する。ゆえに $d=0$ であり,$10000\mid N$ である。

検証・検算

各 $d$ についての判定は次のとおりである。

$d$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$
$7d\bmod16$$0$$7$$14$$5$$12$$3$$10$$1$$8$$15$
$Q_{16}$ に属するか○××××××○××
$d\bmod5$$0$$1$$2$$3$$4$$0$$1$$2$$3$$4$
$Q_5$ に属するか○○××○○○××○

法 $16$ だけでは $d=7$ が,法 $5$ だけでは $d=1,4,5,6,9$ が残る。両方を満たすのは $d=0$ だけである。$7777\equiv1\pmod{16}$ であり,$d=7$ は $2$ の冪の側では排除できない。本解では $d=7$ は (1) によって既に除かれている。

3.6 参考解2:(2) 平方根の桁の持ち上げ

着想・方針

末尾が $44$,$444$ となる平方数の根を下位の桁から順に決め,次の桁へ進めるかを調べる。$k\geqq1$ のとき $2k\geqq k+1$ であるから
$$ (r+10^ku)^2=r^2+2r\cdot10^ku+10^{2k}u^2\equiv r^2+2r\cdot10^ku\pmod{10^{k+1}} $$
であり,根の $10^k$ の位を $u$ だけずらすと,平方の $10^k$ の位は $2ru\bmod10$ だけずれる。

解答

  1. より $d\in\lbrace0,4\rbrace$ である。$d=4$ と仮定すると $n^2\equiv4444\pmod{10^4}$,特に $n^2\equiv44\pmod{100}$,$n^2\equiv444\pmod{1000}$ である。
    第1段(法 $100$)。$0^2,1^2,\ldots,9^2$ のうち1の位が $4$ のものは $2^2$ と $8^2$ だけであるから,$n\equiv2$ または $8\pmod{10}$ である。$n=10u+2$ のとき $n^2\equiv40u+4\pmod{100}$ で,$40u+4\equiv44\iff40(u-1)\equiv0\pmod{100}\iff u\equiv1\pmod5$。$n=10u+8$ のとき $n^2\equiv60u+64\pmod{100}$ で,$60u+64\equiv44\iff60u\equiv80\pmod{100}\iff3u\equiv4\pmod5\iff u\equiv3\pmod5$。よって
    $$ n\equiv12,\ 38,\ 62,\ 88\pmod{100}. $$
    第2段(法 $1000$)。上の各 $r$ について $n=r+100s$ とおき,$r^2$ の100の位を $h_0$ とすると,$r^2\bmod1000=100h_0+44$ より $n^2$ の100の位は $(h_0+2rs)\bmod10$ である。これが $4$ となる条件は次のとおりである。
    $r$$r^2$$h_0$$2r\bmod10$条件$s\bmod10$
    $12$$144$$1$$4$$4s\equiv3\pmod{10}$解なし
    $38$$1444$$4$$6$$6s\equiv0\pmod{10}$$0,5$
    $62$$3844$$8$$4$$4s\equiv6\pmod{10}$$4,9$
    $88$$7744$$7$$6$$6s\equiv7\pmod{10}$解なし
    よって
    $$ n\equiv38,\ 462,\ 538,\ 962\pmod{1000}. $$
    第3段(法 $10^4$)。上の各 $r$ について $n=r+1000s$ とおき,$r^2$ の1000の位を $c_0$ とすると,$n^2$ の1000の位は $(c_0+2rs)\bmod10$ であり,その偶奇は $c_0$ の偶奇に等しい。
    $r$$38$$462$$538$$962$
    $r^2$$1444$$213444$$289444$$925444$
    $c_0$$1$$3$$9$$5$
    $c_0$ はすべて奇数であるから,$n^2\equiv444\pmod{1000}$ を満たす平方数の1000の位は奇数であり,$4$ にはなりえない。ゆえに $d=0$ であり,$10000\mid N$ である。

検証・検算

  • 各段の解の個数(法 $100$ で $4$ 個,法 $1000$ で $4$ 個)は,$0\leqq n\leqq999$ の全数検査と一致する。
  • 「ずれが偶数」だけでは不可能性は示せず,基準となる $c_0$ がすべて奇数であることが必要である。この一様性は 補題2 ($\lfloor444/8\rfloor=55$ は奇数)によって説明される。
  • 副産物:$(38+1000s)^2$ の1000の位は $s=0,1,2,3,4$ に対し $1,7,3,9,5$ となり,奇数はすべて実現される( 定理4 )。

3.7 同じ系列に属する変形

独立の解法と数えないもの
  • 本解 (1) を $b$ の偶奇で場合分けする形:$b$ が奇数なら $a$ も奇数で,奇数の1の位の候補 $1,5,9$ はすべて $4$ で割って $1$ 余るから $N\equiv2+1=3\pmod4$ となり不適。$b$ が偶数なら $a$ も偶数で $N\equiv b\pmod4$,よって $b\in\lbrace0,4,8\rbrace\cap\lbrace0,4,6\rbrace=\lbrace0,4\rbrace$。本解と同じ計算の並べ替えである。
  • 本解 (1) の最終段で,1の位の列挙の代わりに $N\equiv b\pmod5$ と $Q_5$ を用いる: 補題1 (ii) の言い換えである。
  • 別解2 の終結を法 $4$ または法 $8$ に変える:$v_2(N)=2$ より $v_2(n)=1$,すなわち $m$ は奇数で $m^2\equiv1\pmod8$ のはずが,$m^2=2500q+1111\equiv4q+7\pmod8$ は $3$ または $7$ である。いずれも平方因子除去の系列に属する。
  • 参考解1 を法 $20$ と法 $16$ の交差として述べる:$N\equiv11d\pmod{20}$ から $d\in\lbrace0,4\rbrace$,$N\equiv7d\pmod{16}$ から $d\in\lbrace0,7\rbrace$。まとめると法 $80$ による判定になる( 命題6 )。
  • $9$ 倍による変形:$9\cdot1111=9999\equiv-1\pmod{10000}$ より $(3n)^2\equiv-d\pmod{10000}$。$d=4$ のとき $-4\equiv9996\equiv12\pmod{16}$ となり,本解と同じ判定に戻る。
  • 差分 $(n+1)^2-n^2=2n+1$,奇数の和 $n^2=\sum_{j=1}^{n}(2j-1)$,正方形の面積分割 $(10u+r)^2=100u^2+20ur+r^2$:いずれも平方の剰余を列挙する手段であり,別解1 または 2.3 節の有限検査に含まれる。
採用しない経路と誤りやすい点
  • $n^2\equiv4444\pmod{10000}$ から $n^2\equiv4444\pmod{32}$ を導くことはできない($32\nmid10000$)。法 $32$ を用いるなら $10000q$ の寄与を残す必要がある。
  • 法 $16$ だけから $d=0$ と結論するのは誤りである($d=7$ が残る)。
  • 法 $625$ で $4444$ が平方剰余でないとする推論は誤りである($87^2\equiv4444\pmod{625}$)。不可能性の原因は $2$ の冪の側にある。
  • 微分・積分,座標・ベクトル・複素数・三角関数などの連続的な道具:本問は有限個の剰余類に関する問題であり,独立した経路を与えない。

3.8 解法の比較

解法対象主に利用する構造(1) の利用長所注意点
本解(1)(2)法 $4$ と1の位,法 $16$(2) で利用最短,検算点が明確法 $4$ の段階で残る $3,7,8$ の処理
3.1 節(1)法 $20$—一つの表で完結$Q_{20}$ の確認
3.2 節(2)法 $16$ の十進桁への翻訳利用一般の下位3桁に使える根が偶数であることの確認
別解1(1)根の1の位と繰り上がり—同値条件が得られる$a$ は合同式で扱う
別解2(2)平方因子の除去2回利用設問間の連関が明快根の偶奇と $m^2\geqq100$
参考解1(2)法 $16$ と法 $5$不要(1) なしで完結$d=7$ の処理
参考解2(2)根の桁の持ち上げ利用境界の構造が見える計算量が多い

試験場での第一選択は本解である。(1) の仮定を一つの合同式に直接反映でき,(2) は (1) による候補の限定と法 $16$ の一行で完結する。別解2 は設問間の連関を最もよく示し,参考解2 は「なぜ4桁目で不可能になるか」を構成的に示す。$d=4$ を排除する障害はすべての解法で同一($Q_{16}$,あるいは $n=2m$ のもとでの $Q_4$)であり,各解法の違いはその障害への到達経路にある。$d=7$ などそれ以外の数字は,(1) を経由する解法では1の位の条件(法 $5$)で,参考解1 では法 $5$ の直接評価で除かれる。


4. 汎用的な探索手順

本問から,「平方数の十進表示の下位の桁に条件が課された問題」に対する探索手順を抽出する。

4.1 意思決定の流れ

手順1:桁条件を合同式に翻訳する。下位 $k$ 桁の条件は $N\bmod10^k$ の条件である。同じ数字の繰り返しは $d\cdot(10^k-1)/9$ とまとめ,変数を減らす。
手順2:条件が実際に用いる情報だけを保つ最小の法を選ぶ。数字の偶奇が条件なら,その位の偶奇を保つ法(10の位なら法 $4$ または法 $20$)を,1の位なら法 $5$ を考える。$10^k=2^k5^k$ と分解し,$2$ の側と $5$ の側を別々に調べる。
手順3:平方数の取りえない剰余を探す。ある法で矛盾が出なければ,その素数の冪を上げる(本問では $8\to16$)。奇素数 $p$ と $p\nmid A$ については,$x^2\equiv A$ がすべての $p^e$ を法として解けるかは法 $p$ だけで決まる。$p=2$ では,奇数 $u$ について法 $8$ まで($u\equiv1\pmod8$),$A=4u$ については法 $32$ まで調べる必要がある( 5.7 節 , 5.8 節 )。
手順4:前の小問の仮定が後の小問で自動的に満たされていないかを確かめる(本問では $a=b=d$ から $a+b=2d$)。
手順5:平方因子を取り除いて新しい平方数を作り,既知の命題に帰着できないかを調べる。根が割り切れることを先に示し,新しい対象が既知の命題の仮定(桁数など)を満たすことを確認する。
手順6:構造が見えなければ,平方根を下位の桁から持ち上げる。$(r+10^ku)^2\equiv r^2+2r\cdot10^ku\pmod{10^{k+1}}$ において,$2r$ と $10$ の最大公約数が次の桁の自由度を決める。
手順7:有限性を用いて検算する。条件は $n\bmod10^k$(周期性・対称性によりさらに縮小できる)だけで決まるので,全剰余類の検査は完全な確認になる。
手順8:境界例で主張の鋭さを確かめる(本問では $1444$ と $4444$)。

4.2 症状と有効な道具

症状検討する表現・道具本問での例
数字の偶奇だけが条件にあるその位の偶奇を保つ法(法 $4$,法 $20$)本解 (1),3.1 節
1の位が条件にある法 $5$(法 $10$)本解 (1)
下位 $k$ 桁が固定されている法 $2^k$ と法 $5^k$ への分解1.5 節
小さい法で矛盾が出ない$2$ の冪を上げる本解 (2)($8\to16$)
前問の仮定と同じ形が現れる前問の再利用本解 (2)
剰余が平方因子 $4$ を含む根の偶奇を確定して縮約別解2
根の末位で周期的に決まる根の末位による場合分け別解1
実現できる桁とできない桁の境界を知りたい根の持ち上げ,桁の偶奇検査参考解2,3.2 節,5.3 節

4.3 類題設計への応用

本問の構造は,閾値型の問題の設計原理として読める。整数 $A$ を,法 $2^{e-1}$ では平方剰余,法 $2^e$ では非平方となるように選び,$5$ の側では可解性を保つ(例えば $5\nmid A$ かつ $A\bmod5\in\lbrace1,4\rbrace$)。このとき中国剰余定理により,下位 $e-1$ 桁が $A$ の下位 $e-1$ 桁と一致する平方数は存在し,下位 $e$ 桁が一致する平方数は存在しない。本問は $A=4444$,$e=4$ の場合である。また (1) のように,ある法の平方剰余についての主張を数字の言葉で言い換えた補題を前問に置けば,後問の候補を絞るふるいとして働かせることができる。


5. 発展事項

5.1 高校数学と一般理論の境界

事項高校数学での扱い一般理論
合同式・余り合同式の計算,余りによる分類剰余環 $\mathbb{Z}/m\mathbb{Z}$
平方数の余り有限個の剰余の列挙( 補題1 )平方剰余,Legendre 記号
法の分解法 $4,5,16$ を個別に調べる中国剰余定理
平方因子の除去$4\mid n^2\Rightarrow2\mid n$$p$ 進付値 $v_p(n^2)=2v_p(n)$
根の桁の決定平方の展開Hensel の補題,$p$ 進整数
法 $16$ の障害$Q_{16}=\lbrace0,1,4,9\rbrace$$2$ 進単数が平方 $\iff\equiv1\pmod8$

本解・別解・参考解と 3.1・3.2 節はすべて左欄の範囲で完結する。右欄は,それらの計算が成り立つ理由を説明する理論である。

5.2 下位2桁の完全な偶奇構造

平方数の下位2桁

平方数 $n^2$ の10の位を $a$,1の位を $b$ とする($n^2 < 10$ のときは $a=0$)。このとき次が成り立つ。
(i) $a$ が奇数 $\iff b=6$。
(ii) $a+b$ が偶数 $\iff b\in\lbrace0,4\rbrace\iff n\equiv0,2,8\pmod{10}$。

$n^2\equiv10\,(a\bmod2)+b\pmod{20}$ の右辺は $0$ 以上 $19$ 以下であり, 補題1 (iv) より $\lbrace0,1,4,5,9,16\rbrace$ に属する。したがって $(a\bmod2,\,b)$ は $(0,0),(0,1),(0,4),(0,5),(0,9),(1,6)$ のいずれかであり,(i) が従う。(ii) の第一の同値:$b=6$ なら (i) より $a+b$ は奇数,$b\neq6$ なら $a$ は偶数で,$a+b$ が偶数 $\iff$ $b$ が偶数 $\iff b\in\lbrace0,4\rbrace$ である($b\in\lbrace0,1,4,5,9\rbrace$)。第二の同値は,$b=(n\bmod10)^2\bmod10$ であり,$r=0,1,\ldots,9$ に対する $r^2\bmod10$ が $0,1,4,9,6,5,6,9,4,1$ であることから従う。

  1. は (ii) の一方向にあたり,(ii) はその逆も成り立つことを示している。(i) は,平方数の10の位の偶奇が1の位だけで決まるという規則である。

5.3 末尾 $c444$ の平方数と解の個数

末尾が444の平方数の1000の位

$0\leqq c\leqq9$ とする。$n^2\equiv1000c+444\pmod{10000}$ を満たす整数 $n$ が存在するための必要十分条件は,$c$ が奇数であることである。$c$ が奇数のとき,その解は法 $10000$ でちょうど $8$ 個ある。

必要性:$n^2$ の1の位が $4$ であるから $n$ は偶数であり, 補題2 と $\lfloor444/8\rfloor=55$ より $c$ は奇数である。
十分性と個数:$n^2\equiv1000c+444\pmod{10^4}$ ならば $n^2\equiv444\pmod{1000}$ であり, 3.6 節 より $n\bmod1000$ は $r\in\lbrace38,462,538,962\rbrace$ のいずれかである。法 $10^4$ の剰余類は $n\equiv r+1000s$($0\leqq s\leqq9$)と一意に書け,$n^2$ の1000の位は $(c_0+2rs)\bmod10$ である($c_0$ は $r^2$ の1000の位で,いずれも奇数)。$2r\bmod10$ は $6,4,6,4$ のいずれかであり,$2r\bmod10=2g$($g\in\lbrace2,3\rbrace$)と書くと $2rs\bmod10=2\,(gs\bmod5)$ である。$5\nmid g$ より $s\mapsto gs\bmod5$ は $s=0,\ldots,9$ 上で各値をちょうど $2$ 回ずつとるから,$2rs\bmod10$ は各偶数剰余をちょうど $2$ 回ずつとる。$c$ が奇数なら $c-c_0$ は偶数であるから,各 $r$ について条件を満たす $s$ はちょうど $2$ 個あり,解は合計 $4\cdot2=8$ 個である。

下位3桁との対比が本問の境界を明らかにする。100の位については
$$ (12+100s)^2\equiv144+400s,\qquad(38+100s)^2\equiv444+600s\pmod{1000} $$
より,$s=0,\ldots,4$ に対して100の位は前者で $1,5,9,3,7$,後者で $4,0,6,2,8$ をとる。よって末尾が $h44$ の平方数は $h=0,1,\ldots,9$ のすべてについて存在する。法 $100$ の根 $12,38,62,88$ の平方 $144,1444,3844,7744$ の100の位は $1,4,8,7$ であり,根の類によって基準の偶奇が異なるためである。一方1000の位では,法 $1000$ の四つの根の基準の偶奇がすべて奇数にそろい( 補題2 ),偶数の $c$ は実現されない。

末尾実現される直前の数字理由
$h44$$h=0,1,\ldots,9$根の類ごとに基準の偶奇が異なる
$c444$$c=1,3,5,7,9$基準の偶奇が奇数にそろう

同じ議論により,次の一般形が得られる。$0\leqq t\leqq999$ について,$r^2\equiv t\pmod{1000}$ を満たす偶数 $r$ で $5\nmid r$ のものが存在するならば,
$$ n^2\equiv1000c+t\pmod{10^4}\ \text{が解をもつ}\iff c\equiv\left\lfloor\frac{t}{8}\right\rfloor\pmod2 $$
である。必要性は 補題2 により($t$ が偶数なのですべての根は偶数),十分性は上の証明と同じく $\gcd(2r,10)=2$ による。

5.4 同じ数字が並ぶ末尾

数字 $d$ を $k$ 個並べた数を $R_k(d)=d\cdot\dfrac{10^k-1}{9}$ とおく。

同じ数字で終わる平方数

$n^2\equiv R_k(d)\pmod{10^k}$ を満たす整数 $n$ が存在するような数字 $d\in\lbrace0,1,\ldots,9\rbrace$ は次のとおりである。
(i) $k=1$ のとき $d\in\lbrace0,1,4,5,6,9\rbrace$。
(ii) $k=2,3$ のとき $d\in\lbrace0,4\rbrace$。
(iii) $k\geqq4$ のとき $d=0$ のみ。

$d=0$ はすべての $k$ で $n=10^k$ により実現される。(i) は 補題1 (ii) と $1^2,2^2,5^2,4^2,3^2$ による。(ii):$n^2$ の下位2桁が $dd$ なら 命題3 (ii) より $d\in\lbrace0,4\rbrace$ であり,$k=3$ でも下位2桁の条件から同じ制限が従う。$d=4$ は $12^2=144$,$38^2=1444$ で実現される。(iii):$n^2\equiv R_k(d)\pmod{10^k}$ から $n^2\equiv1111d\pmod{10^4}$ が従い, 3.5 節 の議論(法 $16$ と法 $5$ の合同式だけを用いる)より $d=0$ である。

  1. の「4つ」は,$d=0$ だけが残る最小の $k$ に一致する。

5.5 判定に必要な最小の法

法80の最小性

$M$ を $10000$ の正の約数とし,
$$ S_M=\lbrace d\in\lbrace0,1,\ldots,9\rbrace \mid 1111d\bmod M\in Q_M\rbrace $$
とおく。$S_M=\lbrace0\rbrace$ となるための必要十分条件は $80\mid M$ である。

$80\mid M$ とする。$d\in S_M$ ならば $x^2\equiv1111d\pmod M$ となる $x$ があり,$16\mid M$,$5\mid M$ より法 $16$ と法 $5$ でも成り立つから, 3.5 節 の議論により $d=0$ である。また $x=0$ により $0\in S_M$ である。
逆に $M=2^\alpha5^\beta$($0\leqq\alpha,\beta\leqq4$)とする。$\alpha\leqq3$ ならば,$4444-2^2=8\cdot555$ より $x=2$ は法 $2^\alpha$ で $x^2\equiv4444$ を満たし,$87^2-4444=5^5$ より $x=87$ は法 $5^\beta$ で $x^2\equiv4444$ を満たす。中国剰余定理により法 $M$ の解が存在し,$4\in S_M$ である。$\beta=0$ ならば $M\mid16$ であり,$7777-1=16\cdot486$ より $x=1$ が解となって $7\in S_M$ である。ゆえに $S_M=\lbrace0\rbrace$ ならば $\alpha=4$ かつ $\beta\geqq1$,すなわち $80\mid M$ である。

  1. の判定に必要な情報は $N\bmod80$ に過不足なく集約される。$2$ の側の $16$ が $d=4$ を,$5$ の側の $5$ が $d=7$ を排除し,(1) はそのうち法 $20$ の部分を担っている。

5.6 中国剰余定理と局所的な障害

$10^k=2^k5^k$ であるから,中国剰余定理により,$x^2\equiv A\pmod{10^k}$ の可解性は $x^2\equiv A\pmod{2^k}$ と $x^2\equiv A\pmod{5^k}$ の可解性の両立と同値であり,解の個数は両者の積になる。各数字 $d$ について,$1111d$ が法 $2^e$ で初めて平方剰余でなくなる指数 $e(d)$ と,法 $5^f$ で初めて平方剰余でなくなる指数 $f(d)$ を $4$ 以下の範囲で求めると,次のようになる(「—」は $4$ 以下に存在しないことを表す)。

$d$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$
$e(d)$—$2$$2$$3$$4$$2$$2$—$4$$2$
$f(d)$——$1$$1$—$2$—$1$$1$—

法 $p^e$ で非平方なら法 $p^{e'}$($e'\geqq e$)でも非平方であり,$k\leqq4$ では $R_k(d)\equiv1111d\pmod{10^k}$ であるから,$n^2\equiv R_k(d)\pmod{10^k}$ が解をもつための必要十分条件は $e(d) > k$ かつ $f(d) > k$ である。これにより 命題5 の $k\leqq4$ の部分が再現され,次のことが読み取れる。

  • $d=4$ は,$5$ の側で排除されず,かつ $2$ の側で法 $8$ まで生き残る唯一の非零の数字である。本問 (2) の「4つ」は $e(4)=4$ に対応する。
  • $d=7$ は $2$ の側では排除されず($7777\equiv1\pmod{16}$),$5$ の側だけで排除される。

5.7 $2$ 進付値と奇数の平方

素数 $p$ について $v_p(n^2)=2v_p(n)$ である。$d=4$ とすると $N=4(2500q+1111)$ で括弧内は奇数だから $v_2(N)=2$,よって $v_2(n)=1$,$n=2m$($m$ は奇数)である。 補題1 (iii) より $m^2\equiv1\pmod8$ であるが,$m^2=2500q+1111\equiv4q+7\pmod8$ は $3$ または $7$ であり,矛盾する(法 $4$ の段階で既に $m^2\equiv3$ である)。
この現象の一般形は,$2$ 進整数環 $\mathbb{Z}_2$ における平方の判定法である。$0$ でない $x\in\mathbb{Z}_2$ を $x=2^vu$($u$ は単数)と書くとき,$x$ が $\mathbb{Z}_2$ で平方であるための必要十分条件は,$v$ が偶数かつ $u\equiv1\pmod8$ であることである。有限の法では,奇数 $u$ について
$$ x^2\equiv4u\pmod{16}\ \text{が解をもつ}\iff u\equiv1\pmod4,\qquad x^2\equiv4u\pmod{2^e}\ (e\geqq5)\ \text{が解をもつ}\iff u\equiv1\pmod8 $$
が成り立つ。実際,$x$ は偶数でなければならず,$x=2y$ とおくと $y^2\equiv u\pmod{2^{e-2}}$ に帰着する。$e-2=2$ の場合は 補題1 (i),$e-2\geqq3$ の場合は「奇数 $u$ が法 $2^j$($j\geqq3$)で平方剰余 $\iff u\equiv1\pmod8$」という標準的な事実による。$4444=4\cdot1111$,$1111\equiv3\pmod4$ であるから障害は法 $16$ で現れ,十進の下位 $k$ 桁は法 $2^k$ の情報しか含まないので,下位4桁で初めて検出される。
注意:末尾が $4444$ であるという条件から,$2$ 進の等式 $n^2=4444$ が得られるわけではない。用いるのは有限の合同条件 $n^2\equiv4444\pmod{16}$ だけであり,本問の証明に $2$ 進整数環の理論は必要ない。

5.8 Hensel の補題と $p=2$ の特殊性

参考解2 の持ち上げ公式
$$ (r+10^ku)^2\equiv r^2+2r\cdot10^ku\pmod{10^{k+1}}\qquad(k\geqq1) $$
の一次の係数 $2r$ は,$f(x)=x^2$ の導関数 $f'(r)$ にあたる。素数冪を法とする場合,$p$ が奇素数で $p\nmid r$ ならば $f'(r)=2r$ は法 $p$ で可逆であり,$r^2\equiv A\pmod{p^k}$ の根 $r$ は法 $p^{k+1}$ の根へ一意に持ち上がる(Hensel の補題)。したがって奇素数の側では,$p\nmid A$ である限り $x^2\equiv A$ の可解性は法 $p$ で決まる。本問で $5$ の側に障害がない($4444\equiv4\equiv2^2\pmod5$)のはこのためである。
$p=2$ では $f'(r)=2r$ は決して単数にならず,単純な形の Hensel の補題は使えない。一般形($\lvert f(a)\rvert_2 < \lvert f'(a)\rvert_2^{\,2}$ ならば $a$ の近くに根が存在する)を $f(x)=x^2-u$,$a$ 奇数に適用すると,条件は $a^2\equiv u\pmod8$ となる。これが 5.7 節 の「$u\equiv1\pmod8$」の由来である。
十進の持ち上げでは,$2r\bmod10$ が $10$ と互いに素にならないため,$5\nmid r$ のとき次の桁の法 $5$ の成分は自由に選べるが,法 $2$ の成分すなわち偶奇は $r$ によって固定される。 定理4 の「偶奇が固定され,その偶奇の $5$ 個の数字はすべて実現される」という形は,二つの素数の側のこの振る舞いをそのまま反映している。

5.9 他の進法への一般化

他の基数における末尾4444

$B\geqq5$ を整数とする。$B$ 進法で表して下位4桁がすべて $4$ である平方数が存在するための必要十分条件は,$B$ が奇数であるか $8\mid B$ であることである。

$R=1+B+B^2+B^3$ とおくと,条件は $n^2\equiv4R\pmod{B^4}$ の可解性である。$B$ の各素因数 $p$ について $R\equiv1\pmod p$ であり,中国剰余定理により各 $p^{4v_p(B)}$ を法とする可解性を調べればよい。
奇素数 $p$ については $4R\equiv4=2^2\pmod p$ は $0$ でない平方剰余であるから,Hensel の補題により任意の $p$ の冪を法として解をもつ。
$B$ が偶数のとき,$v=v_2(B)$ とおく。法 $2^{4v}$($4v\geqq4$)で $x^2\equiv4R$ ならば $x$ は偶数で,$x=2y$ とおくと $y^2\equiv R\pmod{2^{4v-2}}$ に帰着する($R$ は奇数)。

  • $v=1$:$B\equiv2\pmod4$ より $R\equiv1+B\equiv3\pmod4$ であり,法 $4$ で解がない。
  • $v=2$:$B\equiv4\pmod8$,$B^2\equiv0\pmod{16}$ より $R\equiv1+B\equiv5\pmod8$ であり,法 $2^6$ で解がない( 5.7 節 )。
  • $v\geqq3$:$R\equiv1\pmod8$ であり,任意の $2$ の冪を法として解をもつ。
    以上より,不可能であるのは $v_2(B)\in\lbrace1,2\rbrace$ のときに限る。

$B=10$ は $v_2(B)=1$ の場合であり,本問 (2) の $d=4$ の排除にあたる。一方 $(4444)_7=1600=40^2$,$198^2=39204=(114444)_8$,$2350^2=5522500=(544444)_{16}$ のように,$B=7,8,16$ では実現される。本問の結論は $10\equiv2\pmod4$ という基数の性質に依存している。

5.10 結論の言い換え:$100\mid n$

$10000\mid n^2\iff100\mid n$ である。実際,$v_2(n^2)=2v_2(n)$ より $v_2(n^2)\geqq4\iff v_2(n)\geqq2$ であり,$v_5$ についても同様である。したがって (2) は「下位4桁がすべて同じ数字である平方数は,その平方根の下位2桁が $00$ である」と言い換えられる。これは 2.3 節 の有限検査で,$n^2\equiv0\pmod{10^4}$ の解が $n\equiv0\pmod{100}$ の $100$ 個であったことと一致する。

5.11 歴史的背景

合同式の記号 $\equiv$ と,それを用いた平方剰余の体系的な理論は,Gauss の『整数論(Disquisitiones Arithmeticae)』(1801)による。平方剰余そのものは Euler,Legendre らによって研究され,Legendre は記号 $\left(\frac{a}{p}\right)$ を導入した。法を互いに素な因子に分けて扱う考えは中国の『孫子算経』の問題に遡り,中国剰余定理の名はこれに由来する。素数冪を法とする合同式の根を順に持ち上げる考えは,Hensel による $p$ 進数の導入(1897)によって解析的な枠組みを得た。素数冪ごとの条件を局所的に調べる視点は,Hasse による二次形式の局所大域原理(1920年代)へと発展した。ただし本問は有限の法 $10^4$ での可解性の問題であり,大域的な問いは含まない。


6. 最終整理

6.1 全体の構造マップ

  • 十進の桁条件 → 法 $10^k$ における平方の剰余条件
    • (1):$(a\bmod2,\,b)$ の情報は $N\bmod20$ に一致
      • 平方数の側:法 $4$ で $a$ を消去し1の位と照合 → 本解;法 $20$ で一括 → 3.1 節
      • 平方根の側:$n\bmod10$ の $10$ 通り → 別解1
      • 強化:$a$ 奇 $\iff b=6$;$a+b$ 偶 $\iff b\in\lbrace0,4\rbrace\iff n\equiv0,2,8\pmod{10}$( 命題3 )
    • (2):下位2桁 $dd$,$a+b=2d$ → (1) → $d\in\lbrace0,4\rbrace$
      • $d=4$ の排除(障害は法 $16$,すなわち $2$ の側のみ)
        • 剰余の直接判定 $4444\equiv12\pmod{16}$ → 本解;桁の偶奇検査 → 3.2 節
        • 平方因子の除去 $m^2\equiv11\pmod{100}$ → (1) の再適用 → 別解2
        • 根の持ち上げ:末尾 $444$ の平方数の1000の位は奇数 → 参考解2
        1. を用いない分類:法 $16$ で $\lbrace0,7\rbrace$,法 $5$ で $7$ を除去 → 参考解1(法 $80$ が必要十分)
    • 境界:$16\mid10^4$,$16\nmid10^3$ → 末尾 $444$ は可能,$4444$ は不可能 → 「4つ」は最小
    • 帰結:$10000\mid n^2\iff100\mid n$;基数 $B$ では $v_2(B)\in\lbrace1,2\rbrace$ のとき同じ現象

6.2 数学的教訓

  • 十進の下位 $k$ 桁の条件は法 $10^k$ の合同条件であり,$10^k=2^k5^k$ によって $2$ の側と $5$ の側に分けて調べられる。
  • 条件が実際に担う情報を見極め,それを過不足なく保つ法を選ぶ。(1) の仮定の情報は $N\bmod20$ に一致し,法 $10$ では失われる。
  • 矛盾が出なければ法を強める。$4444$ は法 $8$ では平方剰余であり,法 $16$ で初めて非平方となる。
  • 前問の仮定が後問で自動的に満たされる設計を見抜けば,候補は一挙に減る。
  • 平方因子の除去は,根が割り切れることと,新しい対象が既知の命題の仮定を満たすことを確かめてから行う。
  • 構成的な方法(根の持ち上げ)は不存在の証明としては重いが,「どの桁で,なぜ不可能になるか」を明らかにする。
  • 同一の障害を法の言い換えで水増しせず,発想の入口が異なるものだけを独立の解法として数える。
  • 条件が有限個の剰余類で決まる問題では,全数検査はそれ自体が証明になり,最も確実な検算になる。
投稿日:5日前
数学の力で現場を変える アルゴリズムエンジニア募集 - Mathlog served by OptHub

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

医学部・難関大受験生の指導を行っています。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中