自然数の2乗になる数を平方数という。以下の問いに答えよ。
(1) 10進法で表して3桁以上の平方数に対し,10の位の数を $a$,1の位の数を $b$ とおいたとき,$a+b$ が偶数となるならば,$b$ は $0$ または $4$ であることを示せ。
(2) 10進法で表して5桁以上の平方数に対し,1000の位の数,100の位の数,10の位の数,および1の位の数の4つすべてが同じ数となるならば,その平方数は $10000$ で割り切れることを示せ。
本稿の高校数学の範囲の議論が用いる平方数の性質は,次の補題に尽きる。
任意の整数 $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$ である。
$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 節 )。
以上の構造から,作問の設計は次のように読める(数値設定からの分析であり,出題者の意図についての推定を含む)。
| 着目する構造 | 導かれる解法 |
|---|---|
| 仮定を法 $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 |
平方数を $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$ である。
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$ で割り切れる。
3.1・3.2 節は本解の一部分に対する別証,3.3・3.4 節は本解と異なる着眼に立つ別解である。3.5・3.6 節の参考解はいずれも高校数学の範囲で完結するが,本解と同じ系列に属するか,試験場の答案としては計算量が過大であるため参考解とする。
$(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 )。
「偶数の平方は法 $16$ で $0$ または $4$」を十進の桁の言葉に翻訳する。$10000$ と $1000$ はともに $8$ の倍数であるから,$\lfloor N/8\rfloor$ の偶奇は1000の位の偶奇と下位3桁だけで表される。
$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$ である。
$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}
$$
を与える。
$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$ である。
$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) によって既に除かれている。
末尾が $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$ だけずれる。
| $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}$ | 解なし |
| $r$ | $38$ | $462$ | $538$ | $962$ |
|---|---|---|---|---|
| $r^2$ | $1444$ | $213444$ | $289444$ | $925444$ |
| $c_0$ | $1$ | $3$ | $9$ | $5$ |
| 解法 | 対象 | 主に利用する構造 | (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$ の直接評価で除かれる。
本問から,「平方数の十進表示の下位の桁に条件が課された問題」に対する探索手順を抽出する。
手順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$,法 $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 節 |
本問の構造は,閾値型の問題の設計原理として読める。整数 $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) のように,ある法の平方剰余についての主張を数字の言葉で言い換えた補題を前問に置けば,後問の候補を絞るふるいとして働かせることができる。
| 事項 | 高校数学での扱い | 一般理論 |
|---|---|---|
| 合同式・余り | 合同式の計算,余りによる分類 | 剰余環 $\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 節はすべて左欄の範囲で完結する。右欄は,それらの計算が成り立つ理由を説明する理論である。
平方数 $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$ であることから従う。
$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$ による。
数字 $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$ である。
$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$ である。
$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$ の部分が再現され,次のことが読み取れる。
素数 $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$ 進整数環の理論は必要ない。
参考解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$ 個の数字はすべて実現される」という形は,二つの素数の側のこの振る舞いをそのまま反映している。
$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$ は奇数)。
$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$ という基数の性質に依存している。
$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$ 個であったことと一致する。
合同式の記号 $\equiv$ と,それを用いた平方剰余の体系的な理論は,Gauss の『整数論(Disquisitiones Arithmeticae)』(1801)による。平方剰余そのものは Euler,Legendre らによって研究され,Legendre は記号 $\left(\frac{a}{p}\right)$ を導入した。法を互いに素な因子に分けて扱う考えは中国の『孫子算経』の問題に遡り,中国剰余定理の名はこれに由来する。素数冪を法とする合同式の根を順に持ち上げる考えは,Hensel による $p$ 進数の導入(1897)によって解析的な枠組みを得た。素数冪ごとの条件を局所的に調べる視点は,Hasse による二次形式の局所大域原理(1920年代)へと発展した。ただし本問は有限の法 $10^4$ での可解性の問題であり,大域的な問いは含まない。